Moving average online algorithm

Eu quero implementar um algoritmo iterativo, que calcula a média ponderada. A lei de peso específico não importa, mas deve estar perto de 1 para os valores mais recentes e perto de 0 para o mais antigo. O algoritmo deve ser iterativo. Isto é, não deve recordar todos os valores anteriores. Deve saber apenas um valor mais recente e qualquer informação agregativa sobre passado, como valores anteriores da média, somas, contagens etc. Por exemplo, o seguinte algoritmo pode ser: Dará peso exponencial decrescente, que pode não ser bom. É possível ter a etapa que diminui o peso ou algo o que as exigências para pesar a lei são seguintes: 1) O peso diminui em 2 passado) I tem alguma duração média ou característica de modo que os valores mais velhos esta duração importam muito menos do que uns mais novos 3) Deve ser capaz de definir esta duração Eu preciso o seguinte. Suponha que vi são valores, onde v1 é o primeiro. Também suponha wi são pesos. Mas w0 é o ÚLTIMO. Então, depois que o primeiro valor veio eu tenho a primeira média Depois que o segundo valor v2 veio, eu deveria ter média Com o próximo valor eu deveria ter Nota, esse perfil de peso está se movendo comigo, enquanto eu estou movendo ao longo da seqüência de valor. I. e. Cada valor não tem seu próprio peso o tempo todo. Meu objetivo é ter esse peso mais baixo enquanto vai para o passado. Gt Mas minha tarefa é ter a média recalculada cada vez que o novo valor chega com valores antigos reponderados. OP Sua tarefa é quase sempre impossível, mesmo com esquemas de ponderação excepcionalmente simples. Você está pedindo para, com O (1) memória, rendimento médio com um esquema de ponderação em mudança. Por exemplo, à medida que novos valores estão sendo passados, para algumas seqüências de pesos que mudam quase arbitrariamente. Isto é impossível devido à injetividade. Uma vez que você mescla os números juntos, você perde uma enorme quantidade de informações. Por exemplo, mesmo se você tivesse o vetor de peso. Não foi possível recuperar o vetor de valor original ou vice-versa. Há apenas dois casos que eu posso pensar de onde você poderia fugir com isso: pesos constantes, tais como 2,2,2. 2: isso é equivalente a um algoritmo de média on-line, que você não quer porque os valores antigos não estão sendo reponderados. Os pesos relativos das respostas anteriores não mudam. Por exemplo, você poderia fazer pesos de 8,4,2,1. E adicionar em um novo elemento com peso arbitrário como. 1. mas você deve aumentar todos os anteriores pelo mesmo fator multiplicativo, como 16,8,4,21. Assim, a cada passo, você está adicionando um novo peso arbitrário e um novo reescalonamento arbitrário do passado, então você tem 2 graus de liberdade (apenas 1 se você precisa manter seu produto ponto normalizado). Os vetores de peso que você obtém pareceriam: Assim, qualquer esquema de ponderação que você possa fazer parecer que vai funcionar (a menos que você precise manter a coisa normalizada pela soma de pesos, caso em que você deve então dividir a nova média pelo novo Soma, que você pode calcular mantendo apenas O (1) memória). Simplesmente multiplique a média anterior pelo novo s (que implicitamente distribuirá sobre o ponto-produto nos pesos) e adere ao novo valor de wnew. Aqui eu estou supondo que você quer os pesos para somar a 1. Desde que você pode gerar um peso relativo sem ele mudar no futuro, você pode acabar com uma solução que imita esse comportamento. Isto é, suponha que você definiu seus pesos como uma seqüência e definiu a entrada como seqüência. Considere a forma: soma (s0i0 s1i1 s2i2. Snin) soma (s0 s1 s2. Sn). Observe que é trivialmente possível calcular isso de forma incremental com um par de contadores de agregação: Claro, calculateWeightFromCounter () neste caso não deve gerar pesos que somam a um - o truque aqui é que nós médio dividindo pela soma dos pesos De modo que no final, os pesos praticamente parecem somar a um. O verdadeiro truque é como você calculaWeightFromCounter (). Você poderia simplesmente retornar o próprio contador, por exemplo, no entanto, note que o último número ponderado não seria perto da soma dos contadores necessariamente, então você pode não acabar com as propriedades exatas que você deseja. (É difícil dizer desde, como mencionado, youve deixou um problema bastante aberto.) Respondeu Mar 28 12 às 21:45 O problema é que os pesos estão mudando com cada novo valor. No seu caso, eles não são. Ndash Suzan Cioc Mar 29 12 at 14:43 Os pesos reais usados ​​estão mudando com cada novo valor - os quotweightsquot estão sendo divididos por um número sucessivamente maior, impondo assim que os pesos reais usados ​​sempre somam a 1. ndash Kaganar Mar 29 12 At 14:45 Isso é muito longo para postar em um comentário, mas pode ser útil saber. Suponha que você tem: w0vn. Wnv0 (bem chamar isso w0..nvn..0 para breve) Então o próximo passo é: w0vn1. Wn1v0 (e isto é w0..n1vn1..0 para o short) Isto significa que nós precisamos uma maneira de calcular w1..n1vn..0 de w0..nvn..0. É certamente possível que vn..0 seja 0. 0, z, 0. 0 onde z está em algum local x. Se não temos qualquer armazenamento extra, então f (zw (x)) zw (x 1) onde w (x) é o peso para o local x. Reorganizando a equação, w (x 1) f (zw (x)) z. Bem, w (x 1) melhor ser constante para uma constante x, então f (zw (x)) z melhor ser constante. Portanto, f deve deixar z propagar - isto é, f (zw (x)) zf (w (x)). Mas aqui novamente temos um problema. Note que se z (que poderia ser qualquer número) pode propagar através de f. Então w (x) certamente pode. Então f (zw (x)) w (x) f (z). Assim, f (w (x)) w (x) f (z). Mas para um x constante. W (x) é constante e, portanto, f (w (x)) também será constante. W (x) é constante, então f (z) melhor ser constante de modo que w (x) f (z) é constante. Assim, f (w (x)) w (x) c em que c é uma constante. Assim, f (x) cx em que c é uma constante quando x é um valor de peso. Isto é, cada peso é um múltiplo do anterior. Assim, os pesos assumem a forma w (x) mbx. Observe que isso pressupõe que a única informação f seja o último valor agregado. Note que em algum momento você será reduzido a este caso a menos que você esteja disposto a armazenar uma quantidade não constante de dados que representam sua entrada. Você não pode representar um vetor de comprimento infinito de números reais com um número real, mas pode aproximá-los de alguma forma em uma quantidade constante e finita de armazenamento. Mas isso seria meramente uma aproximação. Embora eu não tenha provado isso rigorosamente, é minha conclusão que o que você quer é impossível de fazer com um alto grau de precisão, mas você pode ser capaz de usar log (n) espaço (que também pode ser O (1) para muitos Aplicações práticas) para gerar uma aproximação de qualidade. Você pode ser capaz de usar ainda menos. Respondeu Mar 29 12 at 23:01 Eu tentei praticamente codificar algo (em Java). Como foi dito, seu objetivo não é realizável. Você só pode contar a média de um número de últimos valores lembrados. Se você não precisa ser exato, você pode aproximar os valores mais antigos. Eu tentei fazê-lo lembrando os últimos 5 valores exatamente e os valores mais antigos apenas somados por 5 valores, lembrando os últimos 5 SUMs. Então, a complexidade é O (2n) para lembrar os últimos valores nnn. Esta é uma aproximação muito grosseira. Você pode modificar os tamanhos de matriz lastValues ​​e lasAggregatedSums como você deseja. Veja esta imagem ascii-art tentando exibir um gráfico dos últimos valores, mostrando que as primeiras colunas (dados mais antigos) são lembradas como valor agregado (não individualmente), e somente os primeiros 5 valores são lembrados individualmente. Desafio 1. Meu exemplo não conta pesos, mas eu acho que não deveria ser problema para você adicionar pesos para o LastAggregatedSums apropriadamente - o único problema é que se você quiser pesos mais baixos para valores mais antigos, seria mais difícil, porque a matriz está girando, então Não é fácil saber qual o peso para qual membro da matriz. Talvez você pode modificar o algoritmo para sempre mudar valores na matriz em vez de girar Em seguida, adicionando pesos shouldnt ser um problema. Desafio 2. Os arrays são inicializados com 0 valores, e esses valores estão contando com a média desde o início, mesmo quando não temos receber valores suficientes. Se você estiver executando o algoritmo por muito tempo, você provavelmente não se preocupe que está aprendendo por algum tempo no início. Se você fizer isso, você pode postar uma modificação -) respondeu Jan 21 14 at 15:59 Sua resposta 2017 Stack Exchange, IncA Mais de perto o algoritmo avançado CODAS média móvel A média móvel versátil no algoritmo CODAS avançado filtra o ruído de forma de onda, os extratos significam e Elimina a deriva da linha de base. A média móvel é uma técnica matemática simples usada principalmente para eliminar aberrações e revelar a tendência real em uma coleção de pontos de dados. Você pode estar familiarizado com ele a partir da média de dados ruidosos em uma experiência de física de caloiro, ou de rastrear o valor de um investimento. Você pode não saber que a média móvel é também um protótipo do filtro de resposta de impulso finito, o tipo mais comum de filtro usado em instrumentação computadorizada. Nos casos em que uma dada forma de onda está cheia de ruído, onde uma média precisa de ser extraída de um sinal periódico, ou quando uma linha de base lentamente a deriva necessita de ser eliminada a partir de um sinal de frequência mais elevada, um filtro de média móvel pode ser aplicado para atingir o desejado resultado. O algoritmo de média móvel do Advanced CODAS oferece esse tipo de desempenho de filtragem de forma de onda. Advanced CODAS é um pacote de software de análise que opera em arquivos de dados de forma de onda existentes criados pela primeira geração de pacotes de aquisição de dados WinDaq ou de segunda geração do WinDaq. Além do algoritmo de média móvel, o CODAS avançado também inclui um utilitário de geração de relatórios e rotinas de software para integração de formas de onda, diferenciação, captação de picos e vales, rectificações e operações aritméticas. Teoria do Filtro de Movimentação Média O algoritmo de média móvel DATAQ Instruments permite uma grande flexibilidade nas aplicações de filtragem de formas de onda. Ele pode ser usado como um filtro passa-baixa para atenuar o ruído inerente em muitos tipos de formas de onda, ou como um filtro passa-alta para eliminar uma linha de base derivada de um sinal de freqüência mais alta. O procedimento usado pelo algoritmo para determinar a quantidade de filtragem envolve o uso de um fator de suavização. Esse fator de suavização, controlado por você através do software, pode ser aumentado ou diminuído para especificar o número de pontos de dados de forma de onda reais ou amostras que a média móvel se espalhará. Qualquer forma de onda periódica pode ser pensada como uma seqüência longa ou coleção de pontos de dados. O algoritmo realiza uma média móvel tomando dois ou mais destes pontos de dados da forma de onda adquirida, somando-os, dividindo sua soma pelo número total de pontos de dados adicionados, substituindo o primeiro ponto de dados da forma de onda pela média apenas calculada e Repetindo os passos com o segundo, terceiro e assim por diante pontos de dados até o final dos dados é atingido. O resultado é uma segunda forma de onda gerada que consiste nos dados médios e que tem o mesmo número de pontos que a forma de onda original. Figura 1 8212 Qualquer forma de onda periódica pode ser considerada como uma seqüência longa ou coleção de pontos de dados. Na ilustração acima, pontos de dados de forma de onda consecutivos são representados por quotyquot para ilustrar como a média móvel é calculada. Neste caso, um fator de suavização de três foi aplicado, o que significa que três pontos de dados consecutivos da forma de onda original são adicionados, sua soma dividida por três, e então este quociente é plotado como o primeiro ponto de dados de uma forma de onda gerada. O processo se repete com o segundo, terceiro e assim por diante pontos de dados da forma de onda original até o final dos dados é atingido. Uma técnica de quotfeatheringquot especial calcula a média dos pontos de dados iniciais e finais da forma de onda original para garantir que a forma de onda gerada contenha o mesmo número de pontos de dados que o original. A Figura 1 ilustra como o algoritmo de média móvel é aplicado a pontos de dados de forma de onda (que são representados por y). A ilustração apresenta um fator de suavização de 3, o que significa que o valor médio (representado por a) será calculado sobre 3 valores de dados de forma de onda consecutivos. Observe a sobreposição que existe nos cálculos da média móvel. É essa técnica de sobreposição, junto com um tratamento especial de início e fim que gera o mesmo número de pontos de dados na forma de onda média, como existia no original. A forma como o algoritmo calcula uma média móvel merece um olhar mais atento e pode ser ilustrado com um exemplo. Digamos que temos sido em uma dieta de duas semanas e queremos calcular o nosso peso médio nos últimos 7 dias. Dividimos nosso peso no dia 7 com o nosso peso nos dias 8, 9, 10, 11, 12 e 13 e, em seguida, multiplicamos por 17. Para formalizar o processo, isso pode ser expresso como: a (7) 17 (y 7) y (8) y (9) y (13)) Esta equação pode ser mais generalizada. A média móvel de uma forma de onda pode ser calculada por: Onde: um valor médio n ponto de dados posição s fator de suavização y valor de ponto de dados real Figura 2 8212 A forma de onda da célula de carga mostrada original e não filtrada no canal superior e como um ponto 11 Movendo a forma de onda média no canal inferior. O ruído que aparece na forma de onda original foi devido às intensas vibrações criadas pela prensa durante a operação de embalagem. A chave para esta flexibilidade de algoritmos é a sua ampla gama de fatores de suavização selecionáveis ​​(de 2 - 1.000). O fator de suavização determina quantos pontos de dados ou amostras reais serão calculados. Especificar qualquer fator de suavização positivo simula um filtro passa-baixa enquanto especifica um fator de suavização negativo simula um filtro passa-alta. Dado o valor absoluto do fator de suavização, valores maiores aplicam maiores restrições de suavização na forma de onda resultante e, inversamente, valores menores aplicam menos suavização. Com a aplicação do fator de suavização apropriado, o algoritmo também pode ser usado para extrair o valor médio de uma dada forma de onda periódica. Um fator de alisamento positivo mais alto é tipicamente aplicado para gerar valores de forma de onda média. Aplicando o Algoritmo de Média Móvel Uma característica saliente do algoritmo de média móvel é que ele pode ser aplicado muitas vezes à mesma forma de onda se necessário para obter o resultado de filtragem desejado. A filtragem de formas de onda é um exercício muito subjetivo. O que pode ser uma forma de onda devidamente filtrada para um usuário pode ser inaceitavelmente ruidoso para outro. Só você pode avaliar se o número de pontos médios selecionados foi muito alto, muito baixo ou apenas correto. A flexibilidade do algoritmo permite ajustar o fator de suavização e fazer outra passagem através do algoritmo quando resultados satisfatórios não são alcançados com a tentativa inicial. A aplicação e as capacidades do algoritmo de média móvel podem ser melhor ilustradas pelos exemplos seguintes. Figura 3 8212 A forma de onda de ECG mostrada original e não filtrada no canal superior e como uma forma de onda média movimentada de 97 pontos no canal inferior. Observe a ausência de deriva de linha de base no canal inferior. Ambas as formas de onda são mostradas em uma condição comprimida para fins de apresentação. Uma Aplicação de Redução de Ruído Nos casos em que uma dada forma de onda está cheia de ruído, o filtro de média móvel pode ser aplicado para suprimir o ruído e produzir uma imagem mais clara da forma de onda. Por exemplo, um cliente CODAS avançado estava usando uma prensa e uma célula de carga em uma operação de embalagem. O seu produto era para ser comprimido até um nível predeterminado (monitorizado pela célula de carga) para reduzir o tamanho da embalagem necessária para conter o produto. Por razões de controle de qualidade, eles decidiram monitorar a operação da prensa com instrumentação. Um problema inesperado apareceu quando eles começaram a ver a saída de células de carga em tempo real. Uma vez que a máquina de prensa vibrou consideravelmente durante a operação, a forma de onda de saída das células de carga era difícil de discernir porque continha uma grande quantidade de ruído devido à vibração como mostrado no canal superior da Figura 2. Este ruído foi eliminado gerando um canal com média móvel de 11 pontos como mostrado no canal inferior da Figura 2. O resultado foi uma imagem muito mais clara da saída das células de carga. Uma aplicação na eliminação da deriva da linha de base Nos casos em que uma linha de base lentamente derivada precisa ser removida de um sinal de freqüência mais alta, o filtro da média móvel pode ser aplicado para eliminar a linha de base da derivação. Por exemplo, uma forma de onda ECG tipicamente exibe algum grau de desvio de linha de base como pode ser visto no canal superior da Figura 3. Esta deriva de linha de base pode ser eliminada sem alterar ou perturbar as características da forma de onda como mostrado no canal inferior da Figura 3. Isto é conseguido aplicando um factor de suavização de valor negativo apropriado durante o cálculo da média móvel. O fator de suavização apropriado é determinado dividindo um período de forma de onda (em segundos) pelo intervalo de amostra de canais. O intervalo de amostra dos canais é simplesmente o recíproco da taxa de amostragem dos canais e é exibido convenientemente no menu de utilitário de média móvel. O período de forma de onda é facilmente determinado a partir da tela de exibição, posicionando o cursor em um ponto conveniente na forma de onda, definindo um marcador de tempo e, em seguida, movendo o cursor um ciclo completo longe do marcador de tempo exibido. A diferença de tempo entre cursor e marcador de tempo é um período de forma de onda e é exibido na parte inferior da tela em segundos. Em nosso exemplo de ECG, a forma de onda possuía um intervalo de amostra de canal de 0,004 segundos (obtido a partir do menu de utilidade de média móvel) e um período de forma de onda foi medido para espaçar 0,388 segundos. Dividindo o período de forma de onda pelo intervalo de amostra de canais nos deu um fator de suavização de 97. Uma vez que é a deriva de linha de base que estamos interessados ​​em eliminar, aplicamos um fator de suavização negativo (-97) ao algoritmo de média móvel. Isto, com efeito, subtraiu o resultado médio móvel do sinal original da forma de onda, que eliminou a deriva da linha de base sem alterar a informação da forma de onda. Quaisquer que sejam as aplicações, a razão universal para a aplicação de um filtro de média móvel é quotsmooth outquot as aberrações altas e baixas e revelam um valor de forma de onda intermediário mais representativo. Ao fazer isso, o software não deve comprometer outros recursos da forma de onda original no processo de geração de uma forma de onda média movimentada. Por exemplo, o software deve ajustar automaticamente as informações de calibração associadas ao arquivo de dados original, de modo que a forma de onda média móvel esteja nas unidades de engenharia apropriadas quando geradas. Os desafios enfrentados pelos algoritmos de HFT concorrentes Jacob Loveless, Sasha Stoikov e Rolf Waeber HFT (negociação de alta freqüência) emergiu como uma força poderosa no mercado financeiro moderno Mercados. Apenas 20 anos atrás, a maior parte do volume negociado ocorreu em bolsas como a Bolsa de Valores de Nova York, onde os humanos vestidos com roupas coloridas gesticulariam e gritariam suas intenções comerciais. Hoje em dia, a negociação ocorre principalmente em servidores eletrônicos em data centers, onde os computadores comunicam suas intenções comerciais através de mensagens de rede. Esta transição de trocas físicas para plataformas eletrônicas tem sido particularmente lucrativa para as empresas de HFT, que investiram pesadamente na infra-estrutura deste novo ambiente. Embora a aparência do local e seus participantes tenha mudado drasticamente, o objetivo de todos os comerciantes, seja ele eletrônico ou humano, permanece o mesmo: comprar um ativo de um operador de localização e vendê-lo a outro localizador por um preço mais alto. A diferença determinante entre um operador humano e um HFT é que este último pode reagir mais rapidamente, com maior frequência e tem períodos de detenção de carteira muito curtos. Um algoritmo HFT típico opera na escala de tempo sub-milissegundo, onde os comerciantes humanos não podem competir, como o piscar de um olho humano leva aproximadamente 300 milissegundos. Como algoritmos HFT competir uns com os outros, eles enfrentam dois desafios: touro Eles recebem grandes quantidades de dados a cada microssegundo. Bull Eles devem ser capazes de agir extremamente rápido sobre os dados recebidos, como a rentabilidade dos sinais que estão observando decai muito rapidamente. Algoritmos online fornecem uma classe natural de algoritmos adequados para aplicações HFT. Em um problema on-line, novas variáveis ​​de entrada são reveladas seqüencialmente. Depois de cada entrada nova o algoritmo necessita fazer um decisionmdashfor o exemplo, se ou não submeter um comércio. Isso está em contraste com um problema offline, que pressupõe que todos os dados de entrada estão disponíveis no momento da tomada de decisão. Muitos problemas de otimização prática abordados em ciência da computação e aplicações de pesquisa de operações são problemas on-line. 1 Além de resolver um problema on-line, algoritmos HFT também precisam reagir extremamente rápido às atualizações do mercado. Para garantir um tempo de reação rápido, o gerenciamento eficiente da memória é uma necessidade para um algoritmo de negociação ao vivo. Mantendo uma grande quantidade de dados na memória vai abrandar qualquer CPU, por isso é importante que um algoritmo usa apenas uma quantidade mínima de dados e parâmetros, que podem ser armazenados em memória de acesso rápido, como o cache L1. Além disso, esses fatores devem refletir o estado atual do mercado e devem ser atualizados em tempo real quando novos pontos de dados forem observados. Em resumo, quanto menor o número de fatores que precisam ser mantidos na memória e quanto mais simples a computação necessária para atualizar cada fator, mais rápido um algoritmo é capaz de reagir às atualizações do mercado. Com base na exigência de velocidade e na natureza on-line dos problemas de HFT, a classe de algoritmos de uma passagem é especialmente adequada para aplicações HFT. Esses algoritmos recebem um ponto de dados de cada vez e usam-no para atualizar um conjunto de fatores. Após a atualização, o ponto de dados é descartado e somente os fatores atualizados são mantidos na memória. Três problemas podem surgir em algoritmos HFT. A primeira é a estimativa de uma média corrente de liquidez que pode ser útil para um HFT na determinação do tamanho de uma ordem que é provável executar com sucesso em uma troca eletrônica particular. O segundo problema é uma estimativa de volatilidade corrente, que pode ajudar a quantificar o risco de curto prazo de uma posição. O terceiro problema é uma regressão linear em execução, que pode ser usada em pares comerciais de ativos relacionados. Cada um desses problemas pode ser resolvido de forma eficiente usando um algoritmo one-pass on-line. Neste artigo nós backtest o desempenho de algoritmos one-pass em dados de livro de ordem-limite para ETFs altamente líquidos (fundos negociados em bolsa) e descrever como calibrar esses algoritmos na prática. Algoritmos Online em HFT A única vantagem que HFT tem sobre os outros participantes do mercado é a velocidade de reação. As empresas de HFT são capazes de ver cada ação no marketmdashthat é, as informações contidas na ordem de limite bookmdashand reagem dentro de microssegundos. Embora alguns algoritmos HFT possam basear suas ações em uma fonte de informação fora do mercado (digamos, analisando relatórios de notícias, medindo a temperatura ou avaliando o sentimento do mercado), a maioria baseia suas decisões apenas nas mensagens que chegam ao mercado. De acordo com algumas estimativas, há aproximadamente 215.000 atualizações de cotações por segundo na Bolsa de Valores de Nova York. 4 O desafio para HFTs é processar esses dados de uma forma que lhes permita tomar decisões, como quando entrar posições ou reduzir risco. Os exemplos usados ​​neste artigo pressupõem que os HFTs podem observar cada atualização nos melhores preços de lances e pedidos, incluindo os melhores tamanhos de lances e pedidos. Este subconjunto de informações contidas no livro de ordens de limite é muitas vezes referido como as informações do livro de pedidos de Nível-I. Os seguintes três exemplos de algoritmos on-line, cada um motivado com uma aplicação em HFT, são descritos em detalhes neste artigo: bull Online médio algoritmo. Ilustrado pela construção de um fator que prediz a liquidez disponível, definida como a soma dos tamanhos na melhor oferta e na melhor opção, em um horizonte fixo no futuro. Essa quantidade pode ser útil para estimar qual tamanho de ordem é provável que seja executado nas melhores cotações em uma dada latência. Algoritmo de variação online. Ilustrado pela construção de um fator que prediz a volatilidade realizada sobre um horizonte fixo no futuro. Esta quantidade pode ser útil para estimar o risco de curto prazo de manter o estoque. Bull Algoritmo de regressão online. Ilustrado pela construção de um fator que prevê o PNL esperado (lucro e prejuízo) de uma posição comprada e curta em dois ativos relacionados. Isto pode ser útil na construção de um sinal indicando quando é provável que uma posição longa-curta seja rentável. Em todos os três casos, o algoritmo tem um único parâmetro, alfa, que controla a taxa na qual as informações antigas são esquecidas. A Figura 1 representa a medida de liquidez bruta (tamanho da oferta mais o tamanho da solicitação) em azul. Vermelho e verde representam o fator de liquidez on-line, com alpha0.9 e alpha0.99, respectivamente. Observe que, à medida que o alfa se aproxima de um valor de 1, o sinal fica mais suave e rastreia eficientemente a tendência nos dados subjacentes. A Figura 2 representa a medida de volatilidade online para vários valores de alfa. Mais uma vez, note que a medida é mais suave para alfa maior. Embora um alfa maior forneça um sinal mais liso, retarda-se ainda mais atrás da tendência subjacente porque dá muito peso aos dados mais velhos. Como discutido mais tarde, a escolha de um valor para alfa traduz-se em um tradeoff entre um sinal suave e um menor atraso da tendência. Para ilustrar o algoritmo de regressão on-line, nós olhamos para a série temporal de preços médios para SPY e SSO, dois ETFs altamente relacionados (SSO é a versão de dupla alavancagem de SPY). Conforme mostrado na figura 3, a relação entre os dois ativos parece muito próxima de linear ao longo de um dia. A Figura 4 representa a média on-line eo intercepto para dois valores de alfa. Algoritmos de uma passagem Como indicado por seu nome, um algoritmo de uma passagem lê cada variável de entrada exatamente uma vez e, em seguida, descarta-la. Este tipo de algoritmo é muito eficiente em termos de manipulação de memória, uma vez que requer apenas uma quantidade mínima de dados a serem armazenados na memória. Esta seção apresenta três exemplos importantes de algoritmos one-pass on-line: a média móvel exponencial, a variância ponderada exponencialmente e a regressão ponderada exponencialmente. A próxima seção descreve a aplicação desses algoritmos para HFT. Primeiro, vamos olhar brevemente para a média móvel simples de uma série de tempo. Esta é uma estimativa da média de uma série de tempo sobre uma janela em movimento de um tamanho fixo. Em finanças, é frequentemente utilizado para detectar tendências de preço, em especial através da comparação de duas médias móveis simples: uma sobre uma janela longa e uma sobre uma janela curta. Em outra aplicação, o volume médio negociado nos últimos cinco minutos pode servir como uma previsão do volume negociado no minuto seguinte. Em contraste com a média móvel exponencial, a média móvel simples não pode ser resolvida com um algoritmo de uma passagem. Seja (X t) t X 0, X 1, X 2. Ser a sequência observada de variáveis ​​de entrada. Em qualquer momento t queremos prever o próximo resultado X t1. Para M gt ​​0 e t ge M. A média móvel simples com tamanho de janela M é definida como a média das últimas M observações na série de tempo (X t) t mdash que é,. A média móvel também pode ser calculada através da seguinte recursão: Embora este seja um algoritmo on-line, não é um algoritmo de uma passagem, pois ele precisa acessar cada ponto de dados de entrada exatamente duas vezes: uma vez para adicioná-lo à média móvel e depois Novamente para descartá-lo da estimativa da média móvel. Tal algoritmo é referido como um algoritmo de duas passagens e requer manter uma matriz inteira de tamanho M na memória. Exemplo 1: Média ponderada exponencial de uma passagem Em contraste com a média regular, a média ponderada exponencial atribui um peso exponencialmente decrescente a observações mais antigas: Aqui alfa é um parâmetro de ponderação escolhido pelo usuário e precisa satisfazer 0 lt alfa 1 Esta média ponderada exponencial dá mais importância a uma entrada mais recente comparada com pontos dados mais velhos, é considerada frequentemente ser uma aproximação boa da média movente simples. Comparado com a média móvel simples, a média ponderada exponencial leva em consideração todos os dados anteriores, não apenas as últimas M observações. Para comparar a média móvel simples ea média ponderada exponencial, a figura 5 mostra quantos pontos de dados recebem 80, 90, 95, 99 e 99,9 por cento do peso na estimativa em função de alfa. Por exemplo, se alfa 0.95, então os últimos M 90 pontos de dados observados contribuem para 99 por cento do valor estimado. Como advertência, se a série temporal (X t) t tem caudas muito pesadas, então a média suavizada exponencial pode ser dominada por uma observação extrema, enquanto que a média móvel é menos propensa a observações extremas que eventualmente caem fora da janela de observação . A reinicialização freqüente do procedimento de estimação pode resolver este efeito de memória de longo prazo da suavização exponencial. A razão para favorecer a média móvel exponencial sobre a média móvel simples em HFT é que ela pode ser eficientemente resolvida usando um algoritmo de uma passagem, inicialmente introduzido em Brown (1956). 3 Esta fórmula também fornece uma interpretação simples do parâmetro alfa como um controle de quanto peso é dado à observação mais recente, em comparação com todas as observações anteriores. Exemplo 2: Variância Exponencialmente Ponderada de Uma Passo A suavização exponencial descrita na secção anterior estima uma média móvel de uma série temporal. Em finanças, a volatilidade de uma série de tempo é frequentemente um fator importante também. Em termos gerais, a volatilidade deve captar o quanto uma série temporal flutua em torno de sua média. Não há uma definição amplamente aceita de volatilidade para dados financeiros de alta frequência. Esta seção considera a volatilidade como o desvio padrão (raiz quadrada de variância) de um ponto de dados na série de tempo (X t) t. Similar à média móvel exponencialmente ponderada da seção anterior, pode-se construir um algoritmo on-line de uma passagem que estima a volatilidade da série temporal (Xt) t com um esquema de ponderação exponencial. A variação de uma variável aleatória é definida como Var (X) E X - E X) 2. A estimativa da variância exponencial ponderada da série temporal requer dois estimadores: um que estima a média EX e um que estima a variância: O desvio padrão do próximo ponto de medição X t1 é então estimado como. Novamente, o parâmetro de entrada alfa isin (0,1) é escolhido pelo usuário e reflete quanto peso é atribuído a pontos de dados mais antigos comparados com a entrada de dados observada mais recente. Aqui, inicializamos o estimador da variância com 1, que é uma escolha bastante arbitrária. Outra maneira é ter um período de burn-in inicial para o qual a série de tempo (X t) t é observada e um estimador de variância padrão da série sobre esta janela de tempo de queima pode ser usado para inicializar o estimador. É claro que um método semelhante pode ser usado para inicializar o estimador do estimador exponencial ponderado. Exemplo 3: Algoritmo de passagem única para regressão linear ponderada exponencialmente O último exemplo é um algoritmo on-line de uma passagem para o modelo de regressão linear ponderado exponencialmente. Este modelo é semelhante à regressão linear ordinária, mas novamente dá mais importância (de acordo com uma ponderação exponencial) para observações recentes do que para observações mais antigas. Como já mostrado, tais métodos de regressão são muito úteis em estratégias de HFT para estimar a relação de diferentes ativos, que podem ser, por exemplo, explorados na criação de estratégias de negociação em pares. Neste modelo consideramos uma série de tempo bidimensional (X t, Y t) t e conjecturamos que as variáveis ​​X e Y estão relacionadas através de uma relação linear que é corrompida por um termo de ruído epsilon t com média zero. Isto é, a variável Y é referida como a variável de resposta, enquanto que X é chamada de variável explicativa. Para simplificar, vamos assumir apenas uma variável explicativa aqui, mas a extensão de várias variáveis ​​explicativas é direta. Na abordagem off-line padrão para regressão linear, os parâmetros beta 0 e beta 1 são calibrados após todos os pontos de dados serem observados. Esses pontos de dados são coletados em um vetor Y (Y0, Y1, Yt) T e uma matriz A coluna de uns na matriz X corresponde à interceptação na equação 3. Se escrevermos mais adiante os parâmetros beta 0 e beta 1 Como um vectormdashthat é, beta (beta 0, beta 1) T mdashthen a relação entre Y e X pode ser convenientemente escrito em notação matricial como onde epsilon é um vetor de termos de ruído estocástico, e cada um desses termos de erro tem zero média. A abordagem mais comum para estimar o parâmetro beta é a utilização de mínimos quadrados ordinários, ou seja, o beta é escolhido de modo a minimizar a soma dos resíduos quadrados. A solução para este problema de minimização é. Como nas estimativas de médias e variâncias, pontos de dados mais recentes devem ser mais importantes para a estimação do parâmetro beta. Além disso, um algoritmo de uma passagem para beta é necessário para computação rápida. Em seguida, vamos considerar um método recursivo que atualiza seqüencialmente beta e minimiza. Novamente, o parâmetro alfa precisa estar no intervalo (0,1) e é escolhido pelo usuário. Os parâmetros beta 0 e beta 1 da estimativa dos mínimos quadrados ponderados podem ser calculados com um eficiente algoritmo one-pass on-line. Em cada etapa do algoritmo, uma matriz 2 vezes 2 M t e um vetor 2 vezes 1 V t precisam ser salvas na memória e atualizadas com um novo ponto de dados de acordo com a seguinte recursividade: Como para o estimador de média e variância, a inicialização Da recursividade pode ser feito usando um período de burn-in. Finalmente, após o tempo t. A melhor estimativa de beta é. Na literatura esse método também é chamado de mínimos quadrados recursivos com esquecimento exponencial. 2 Estimativa de Alfa Como se decide sobre o valor ótimo de alfa, o único parâmetro de todos esses modelos on-line Nossa abordagem para os três modelos é definir uma função de resposta que pretendemos prever e minimizar o erro quadrático entre a resposta ri e Nosso fator fi. Esse método localiza o alpha ideal em uma série de tempo histórica. Outra abordagem seria estimar o óptimo alfa online também. Isso, no entanto, requer mais trabalho e vai além do escopo deste artigo. Agora fornecemos os detalhes sobre os estimadores on-line descritos e estimamos o alfa ótimo em um dado conjunto de dados. 1. O estimador de liquidez médio é definido como onde o índice i representa o tempo de cotação. A resposta é definida como a liquidez em 10 segundos: onde bs i (10) representa o tamanho da oferta 10 segundos após a citação i-ésima. Executar uma rotina de otimização sobre alfa mostra que o alfa ideal para os dados dados é 0,97, exibido na figura 6 como um gráfico de dispersão do fator e da resposta. 2. O estimador de volatilidade é definido como onde o índice i representa o tempo real em segundos. A resposta é definida como a volatilidade realizada no próximo minuto: Novamente, a busca por diferentes valores de alfa produz um alfa ótimo de 0,985 para o dado conjunto de dados. A Figura 7 exibe um gráfico de dispersão do fator e da resposta. 3. O estimador de regressão de negociação de pares é definido como onde o índice i representa o tempo de cotação. O fator representa o valor de SPY relativo a SSOmdash que é, se a quantidade é positiva, então SPY é relativamente barato e um comércio que é SPY longo é provável ser rentável. A resposta é definida como o PNL sobre o próximo minuto de um comércio que é longa uma ação de SPY e curto beta partes de SSO: onde representa o preço de SPY 60 segundos depois. A resposta r i representa o PNL da seguinte estratégia de longo prazo: Compre 1 ação de SPY e venda ações beta de SSO no momento i. Sair da posição após 60 segundos. No conjunto de dados analisados, o alfa óptimo revela-se 0,996. A Figura 8 é um gráfico de dispersão do factor e da resposta. Conclusão Online one-pass algoritmos são instrumentais em alta freqüência de negociação, onde recebem grandes quantidades de dados a cada microssegundo e deve ser capaz de agir extremamente rápido sobre os dados recebidos. Este artigo abordou três problemas que enfrentam os algoritmos HFT: a estimativa de uma média corrente de liquidez, que pode ser útil na determinação do tamanho de uma ordem que é provável executar com sucesso em uma determinada troca eletrônica uma estimativa de volatilidade em funcionamento, o que pode ajudar Quantificar o risco de curto prazo de uma posição e uma regressão linear em curso, que pode ser utilizada em pares comerciais de activos relacionados. Os algoritmos one-pass online podem ajudar a resolver cada um desses problemas. Referências 1. Albers, S. 2003. Algoritmos online: uma pesquisa. Programação Matemática 97 (1-2): 3-26. 2. Astrom, A. Wittenmark, B. 1994. Controle adaptativo, segunda edição. Addison Wesley. 3. Brown, R. G. 1956. Suavização Exponencial para Prever a Demanda. Arthur D. Little Inc. p. 15 AME-O, ODEIE-NOS CONHEÇA JACOB LOVELESS é o CEO de Lucera e ex-chefe de negociação de alta freqüência para Cantor Fitzgerald. O Sr. Loveless trabalhou tanto para grupos de negociação de alta freqüência como para trocas nos últimos 10 anos em quase todos os ativos eletrônicos. Antes de uma vida em finanças, o Sr. Loveless era um contratado especial para o Departamento de Defesa dos EUA, com foco na análise heurística de coisas que não podem ser discutidas. Antes disso, ele foi o CTO e fundador da Data Scientific, um pioneiro na análise de sistemas distribuídos. SASHA STOIKOV é associado sênior de pesquisa na Cornell Financial Engineering Manhattan (CFEM) e ex-vice-presidente do grupo de negociação de alta freqüência da Cantor Fitzgerald. Ele trabalhou como consultor no Galleon Group e Morgan Stanley e foi instrutor no Courant Institute of NYU e no departamento de Columbias IEOR. Ele possui um Ph. D. Da Universidade do Texas e uma BS do MIT. ROLF WAEBER é um Associado de Pesquisa Quantitativa na Lucera e anteriormente desempenhou o cargo de Pesquisador Quantitativo no Cantor Fitzgeralds High Frequency Trading Group. Participou em estudos sobre ajustes de risco de liquidez dentro dos marcos regulatórios de Basileia IIIII no Deutsche Bundesbank. Rolf ganhou seu Ph. D. Em Pesquisa de Operações e Engenharia de Informação da Universidade de Cornell em 2017. Ele possui uma licenciatura e um mestrado em Matemática da ETH Zurique, Suíça. Cópia 2017 ACM 1542-7730130800 10.00 Originalmente publicado em Queue vol. 11, n�. 8 8212 ver este item na Biblioteca Digital ACM Ivar Jacobson, Ian Spence, Ed Seidewitz - A escala industrial Agile - do artesanato à essência de engenharia é fundamental para mover o desenvolvimento de software em direção a uma verdadeira disciplina de engenharia. Andre Medeiros - Dinâmica da Mudança: Por que a Reatividade é Importante Domine a dinâmica da mudança centralizando cada preocupação em seu próprio módulo. Brendan Gregg - The Flame Graph Esta visualização da execução de software é uma nova necessidade para o desempenho de perfis e depuração. Ivar Jacobson, Ian Spence, Brian Kerr - Caso de Uso 2.0 O Hub de Desenvolvimento de Software você também troca Fri, 05 Aug 2017 19:07:59 UTC se você também negociação mal estar interessado em se juntar a você Brandon Sun, 08 de maio de 2017 21 : 39: 10 UTC Atualmente estou preso calculando os estimadores de média e variância usados ​​para calcular beta. O artigo diz: Em cada passo do algoritmo, uma matriz 2 2 Mt e um vetor 2 1 Vt precisam ser salvos na memória e atualizados com um novo ponto de dados de acordo com a seguinte recursividade. Quanto ao estimador de média e variância, a inicialização da recursividade pode ser feita usando um período de burn-in. O problema que estou tendo é que não tenho certeza quais valores os parâmetros M e V devem ser inicializados para usar um período de burn-in. Eu não sei quais valores a matriz 2x2 ou o vetor 2x1 deve ser. Mperez Fri, 08 Jan 2017 21:47:19 UTC Por que, ao medir a volatilidade, eles calculam o desvio padrão em vez de apenas usar a variância Eles perdem tempo ao calcular a raiz quadrada. Xxx Seg, 21 Oct 2017 07:48:57 UTC Nome do autor, sem amor. Eu estou tentando encontrar uma maneira de calcular uma média cumulativa móvel sem armazenar a contagem e dados totais que são recebidos até agora. Eu vim para cima com dois algoritmos, mas ambos precisam armazenar a contagem: nova média (dados antigos de contagem antiga) próxima contagem nova média média antiga (próximos dados - média antiga) próxima contagem O problema com esses métodos é que a contagem Obtém maior e maior resultando em perda de precisão na média resultante. O primeiro método usa a contagem antiga ea contagem seguinte que são obviamente 1 à parte. Isso me fez pensar que talvez haja uma maneira de remover a contagem, mas infelizmente eu havent encontrado ainda. Ele fez me um pouco mais longe, porém, resultando no segundo método, mas ainda contar está presente. É possível, ou estou apenas procurando o impossível perguntado Sep 28 12 at 8:46