Na Internet, inclusive no Habré, você pode encontrar muitas informações sobre o filtro Kalman. Mas é difícil encontrar uma derivação facilmente digerível das próprias fórmulas. Sem uma conclusão, toda essa ciência é percebida como uma espécie de xamanismo, as fórmulas parecem um conjunto de símbolos sem rosto e, o mais importante, muitas declarações simples que estão na superfície de uma teoria estão além da compreensão. O objetivo deste artigo será falar sobre esse filtro na linguagem mais acessível possível.
O filtro Kalman é uma ferramenta poderosa de filtragem de dados. Seu princípio básico é que, ao filtrar, sejam utilizadas informações sobre a física do próprio fenômeno. Por exemplo, se você estiver filtrando dados do velocímetro de um carro, a inércia do carro lhe dará o direito de perceber saltos muito rápidos de velocidade como um erro de medição. O filtro de Kalman é interessante porque, de certa forma, é o melhor filtro. Discutiremos com mais detalhes abaixo o que exatamente as palavras "o melhor" significam. No final do artigo, mostrarei que em muitos casos as fórmulas podem ser simplificadas a ponto de quase nada sobrar delas.

Programa educacional

Antes de me familiarizar com o filtro de Kalman, proponho recordar algumas definições e fatos simples da teoria da probabilidade.

Valor aleatório

Quando eles dizem que uma variável aleatória é dada, eles querem dizer que essa quantidade pode assumir valores aleatórios. Ele assume valores diferentes com probabilidades diferentes. Quando você rola, digamos, um dado, um conjunto discreto de valores desaparecerá :. Quando se trata, por exemplo, da velocidade de uma partícula errante, então, obviamente, é preciso lidar com um conjunto contínuo de valores. Iremos denotar os valores "descartados" de uma variável aleatória por, mas às vezes, usaremos a mesma letra, que usamos para denotar uma variável aleatória :.
No caso de um conjunto contínuo de valores, a variável aleatória é caracterizada pela densidade de probabilidade, que nos dita que a probabilidade de a variável aleatória "cair" em uma pequena vizinhança de um ponto com comprimento é igual a. Como podemos ver na imagem, essa probabilidade é igual à área do retângulo sombreado sob o gráfico:

Muitas vezes na vida, as variáveis ​​aleatórias são gaussianas quando a densidade de probabilidade é igual.

Vemos que a função tem o formato de um sino centrado em um ponto e com largura característica da ordem.
Já que estamos falando da distribuição gaussiana, seria um pecado não mencionar de onde ela veio. Assim como os números estão firmemente estabelecidos na matemática e ocorrem nos lugares mais inesperados, a distribuição gaussiana teve raízes profundas na teoria da probabilidade. Uma declaração notável que explica parcialmente a onipresença gaussiana é a seguinte:
Suponha que haja uma variável aleatória com uma distribuição arbitrária (na verdade, existem algumas restrições a essa arbitrariedade, mas elas não são estritas). Vamos realizar experimentos e calcular a soma dos valores "descartados" da variável aleatória. Vamos fazer muitos desses experimentos. É claro que a cada vez receberemos um valor diferente do valor. Em outras palavras, essa soma é ela própria uma variável aleatória com sua própria lei de distribuição certa. Acontece que, para grande o suficiente, a lei de distribuição dessa soma tende para a distribuição gaussiana (a propósito, a largura característica do "sino" aumenta como). Leia mais na Wikipedia: Teorema do Limite Central. Na vida, muitas vezes há quantidades que são compostas por um grande número de variáveis ​​aleatórias independentes igualmente distribuídas e, portanto, são distribuídas de acordo com a Gaussiana.

Quer dizer

O valor médio de uma variável aleatória é o que obtemos no limite se realizarmos muitos experimentos e calcularmos a média aritmética dos valores eliminados. A média é denotada de maneiras diferentes: os matemáticos gostam de denotar por (expectativa) e os matemáticos estrangeiros por (expectativa). Os físicos estão terminados ou. Nós designaremos de forma estrangeira :.
Por exemplo, para uma distribuição gaussiana, a média é.

Dispersão

No caso da distribuição gaussiana, vemos claramente que a variável aleatória prefere cair em alguma vizinhança de seu valor médio. Como pode ser visto no gráfico, a dispersão característica dos valores do pedido. Como podemos estimar essa dispersão de valores para uma variável aleatória arbitrária, se sabemos sua distribuição. Você pode desenhar um gráfico de sua densidade de probabilidade e estimar a largura característica a olho nu. Mas preferimos seguir o caminho algébrico. Você pode encontrar o comprimento médio do desvio (módulo) da média :. Este valor será uma boa estimativa da dispersão característica dos valores. Mas você e eu sabemos muito bem que usar módulos em fórmulas é uma dor de cabeça, então essa fórmula raramente é usada para estimar a propagação característica.
Uma maneira mais fácil (simples em termos de cálculos) é encontrar. Este valor é denominado variância e é frequentemente referido como. A raiz da variação é chamada de desvio padrão. O desvio padrão é uma boa estimativa da propagação de uma variável aleatória.
Por exemplo, para uma distribuição gaussiana, podemos calcular que a variância definida acima é exatamente igual, o que significa que o desvio padrão é igual, o que concorda muito bem com nossa intuição geométrica.
Na verdade, existe uma pequena fraude escondida aqui. O fato é que na definição da distribuição gaussiana, sob o expoente está a expressão. Este dois no denominador é precisamente para que o desvio padrão fosse igual ao coeficiente. Ou seja, a própria fórmula de distribuição gaussiana é escrita de uma forma especialmente aguçada para que possamos considerar seu desvio padrão.

Variáveis ​​aleatórias independentes

Variáveis ​​aleatórias são dependentes e não. Imagine que você está jogando uma agulha em um avião e anotando as coordenadas de ambas as extremidades. Essas duas coordenadas são dependentes, estão relacionadas pela condição de que a distância entre elas é sempre igual ao comprimento da agulha, embora sejam valores aleatórios.
As variáveis ​​aleatórias são independentes se o resultado da primeira delas for completamente independente do resultado da segunda. Se as variáveis ​​aleatórias são independentes, o valor médio de seu produto é igual ao produto de seus valores médios:

Prova

Por exemplo, ter olhos azuis e terminar o ensino médio com uma medalha de ouro são variáveis ​​aleatórias independentes. Se têm olhos azuis, digamos, medalhistas de ouro, então medalhistas de olhos azuis. Este exemplo nos diz que se as variáveis ​​aleatórias são dadas por suas densidades de probabilidade e, então, a independência desses valores é expressa no fato de que a densidade de probabilidade ( o primeiro valor foi eliminado e o segundo) é encontrado pela fórmula:

Segue-se imediatamente disto que:

Como você pode ver, a prova é realizada para variáveis ​​aleatórias que possuem um espectro contínuo de valores e são dadas por sua densidade de probabilidade. Em outros casos, a ideia de prova é semelhante.

Filtro de Kalman

Formulação do problema

Vamos denotar pelo valor que mediremos e, em seguida, filtraremos. Isso pode ser coordenada, velocidade, aceleração, umidade, fedor, temperatura, pressão, etc.
Comecemos com um exemplo simples que nos levará a formular um problema geral. Imagine que temos um carro controlado por rádio que só pode ir e vir. Conhecendo o peso do carro, forma, superfície da estrada, etc., calculamos como o joystick de controle afeta a velocidade do movimento.

Então a coordenada do carro mudará de acordo com a lei:

Na vida real, não podemos levar em conta em nossos cálculos pequenas perturbações agindo sobre o carro (vento, solavancos, pedrinhas na estrada), então a velocidade real do carro será diferente da calculada. Uma variável aleatória é adicionada ao lado direito da equação escrita:

Temos um sensor GPS instalado em uma máquina de escrever que tenta medir a verdadeira coordenada do carro e, claro, não consegue medi-la exatamente, mas mede com um erro, que também é uma variável aleatória. Como resultado, recebemos dados errados do sensor:

A tarefa é que, conhecendo as leituras erradas do sensor, encontre uma boa aproximação para a verdadeira coordenada do carro.
Na formulação da tarefa geral, qualquer coisa pode ser responsável pela coordenada (temperatura, umidade ...), e o termo responsável por controlar o sistema de fora será denotado por (no exemplo com uma máquina). As equações para as leituras de coordenadas e sensores serão semelhantes a estas:

Vamos discutir em detalhes o que sabemos:

É importante notar que a tarefa de filtragem não é uma tarefa de suavização de serrilhado. Não estamos tentando suavizar os dados do sensor, estamos tentando obter o valor mais próximo da coordenada real.

Algoritmo de Kalman

Vamos argumentar por indução. Imagine que na ª etapa já encontramos o valor filtrado do sensor, que se aproxima da coordenada verdadeira do poço do sistema. Não se esqueça de que conhecemos a equação que controla a mudança na coordenada desconhecida:

portanto, ainda não recebendo o valor do sensor, podemos supor que em uma etapa o sistema está evoluindo de acordo com essa lei e o sensor mostrará algo próximo a. Infelizmente, não podemos dizer nada mais preciso até agora. Por outro lado, em uma etapa, teremos uma leitura imprecisa do sensor em nossas mãos.
A ideia de Kalman é a seguinte. Para obter a melhor aproximação da coordenada verdadeira, devemos escolher o meio-termo entre a leitura de um sensor impreciso e nossa previsão do que esperamos dele. Daremos peso à leitura do sensor e o peso permanecerá no valor previsto:

O coeficiente é denominado coeficiente de Kalman. Depende do passo da iteração, portanto seria mais correto escrevê-lo, mas por enquanto, para não atrapalhar as fórmulas de cálculo, omitiremos seu índice.
Devemos escolher o coeficiente de Kalman para que o valor da coordenada ótima resultante seja o mais próximo do verdadeiro. Por exemplo, se sabemos que nosso sensor é muito preciso, então confiaremos mais em sua leitura e daremos ao valor mais peso (perto de um). Se o sensor, ao contrário, for totalmente impreciso, então vamos nos concentrar mais no valor teoricamente previsto.
Em geral, para encontrar o valor exato do coeficiente de Kalman, você só precisa minimizar o erro:

Usamos as equações (1) (aquelas na caixa com um fundo azul) para reescrever a expressão para o erro:

Prova

Agora é a hora de discutir o que significa a expressão minimizar o erro? Afinal, o erro, como podemos ver, é ele próprio uma variável aleatória e cada vez assume valores diferentes. Na verdade, não existe uma abordagem universal para definir o que significa que o erro é mínimo. Assim como no caso da variância de uma variável aleatória, quando tentamos estimar a largura característica de sua dispersão, então escolheremos aqui o critério mais simples para os cálculos. Vamos minimizar a média do erro quadrático:

Vamos escrever a última expressão:

Prova

Do fato de que todas as variáveis ​​aleatórias incluídas na expressão para são independentes, segue-se que todos os termos "cruzados" são iguais a zero:

Usamos o fato de que então a fórmula de variância parece muito mais simples :.

Esta expressão assume um valor mínimo quando (igualamos a derivada a zero):

Aqui já escrevemos uma expressão para o coeficiente de Kalman com o índice da etapa, portanto, enfatizamos que depende da etapa de iteração.
Substituímos o valor ótimo obtido na expressão para, que minimizamos. Nós recebemos;

Nossa tarefa foi cumprida. Temos uma fórmula iterativa para calcular o coeficiente de Kalman.
Vamos resumir nosso conhecimento adquirido em um quadro:

Exemplo

Código Matlab

Limpar tudo; N = 100% número de amostras a = 0,1% de aceleração sigmaPsi = 1 sigmaEta = 50; k = 1: N x = k x (1) = 0 z (1) = x (1) + normrnd (0, sigmaEta); para t = 1: (N-1) x (t + 1) = x (t) + a * t + normrnd (0, sigmaPsi); z (t + 1) = x (t + 1) + normrnd (0, sigmaEta); fim; % filtro Kalman xOpt (1) = z (1); eOpt (1) = sigmaEta; para t = 1: (N-1) eOpt (t + 1) = sqrt ((sigmaEta ^ 2) * (eOpt (t) ^ 2 + sigmaPsi ^ 2) / (sigmaEta ^ 2 + eOpt (t) ^ 2 + sigmaPsi ^ 2)) K (t + 1) = (eOpt (t + 1)) ^ 2 / sigmaEta ^ 2 xOpt (t + 1) = (xOpt (t) + a * t) * (1-K (t +1)) + K (t + 1) * z (t + 1) extremidade; plot (k, xOpt, k, z, k, x)

Análise

Se rastrearmos como o coeficiente de Kalman muda com a etapa de iteração, pode ser mostrado que ele sempre se estabiliza em um determinado valor. Por exemplo, quando os erros rms do sensor e do modelo se relacionam entre si como dez para um, o gráfico do coeficiente de Kalman dependendo da etapa de iteração se parece com este:

No próximo exemplo, discutiremos como isso pode tornar nossa vida muito mais fácil.

Segundo exemplo

Na prática, muitas vezes acontece que não sabemos absolutamente nada sobre o modelo físico do que estamos filtrando. Por exemplo, você deseja filtrar as leituras de seu acelerômetro favorito. Você não sabe com antecedência por qual lei pretende girar o acelerômetro. O máximo de informações que você pode obter é a variação do erro do sensor. Em tal situação difícil, toda ignorância do modelo de movimento pode ser direcionada para uma variável aleatória:

Mas, falando francamente, tal sistema não satisfaz de forma alguma as condições que impusemos à variável aleatória, porque agora toda a física do movimento desconhecida para nós está escondida lá e, portanto, não podemos dizer que em diferentes momentos do tempo o modelo os erros são independentes uns dos outros e seus valores médios são zero. Nesse caso, em geral, a teoria do filtro de Kalman não é aplicável. Mas, não vamos prestar atenção a esse fato, mas, estupidamente, aplicar todo o colosso de fórmulas, escolhendo os coeficientes a olho, para que os dados filtrados fiquem bonitos.
Mas você pode seguir um caminho diferente, muito mais simples. Como vimos acima, o coeficiente de Kalman sempre se estabiliza em direção a um valor com aumento. Portanto, em vez de escolher os coeficientes e encontrar o coeficiente de Kalman usando fórmulas complexas, podemos considerar esse coeficiente como sempre constante e selecionar apenas essa constante. Essa suposição não estraga quase nada. Em primeiro lugar, já estamos usando ilegalmente a teoria de Kalman e, em segundo lugar, o coeficiente de Kalman se estabiliza rapidamente para uma constante. Como resultado, tudo ficará muito simplificado. Em geral, não precisamos de nenhuma fórmula da teoria de Kalman, precisamos apenas encontrar um valor aceitável e inseri-lo na fórmula iterativa:

O gráfico a seguir mostra os dados de um sensor fictício filtrado de duas maneiras diferentes. Desde que não saibamos nada sobre a física do fenômeno. A primeira forma é honesta, com todas as fórmulas da teoria de Kalman. E o segundo é simplificado, sem fórmulas.

Como podemos ver, os métodos são quase os mesmos. Uma pequena diferença é observada apenas no início, quando o coeficiente de Kalman ainda não se estabilizou.

Discussão

Como vimos, a ideia principal do filtro de Kalman é encontrar um coeficiente tal que o valor filtrado

em média, seria o menos diferente do valor real da coordenada. Podemos ver que o valor filtrado é uma função linear da leitura do sensor e do valor filtrado anterior. E o valor filtrado anterior é, por sua vez, uma função linear da leitura do sensor e o valor filtrado anterior. E assim por diante, até que a corrente se desenrole totalmente. Ou seja, o valor filtrado depende de de tudo leituras anteriores do sensor linearmente:

Portanto, o filtro de Kalman é chamado de filtro linear.
Pode-se provar que o filtro de Kalman é o melhor de todos os filtros lineares. Melhor no sentido de que o quadrado médio do erro do filtro é mínimo.

Caso multidimensional

Toda a teoria do filtro de Kalman pode ser generalizada para o caso multidimensional. As fórmulas ali parecem um pouco mais assustadoras, mas a própria ideia de sua derivação é a mesma que no caso unidimensional. Você pode vê-los neste excelente artigo: http://habrahabr.ru/post/140274/.
E neste maravilhoso vídeo um exemplo de como usá-los é analisado.

Os filtros Wiener são mais adequados para processos de processamento ou seções de processos em geral (processamento de bloco). Para o processamento sequencial, é necessária uma estimativa atual do sinal em cada ciclo de clock, levando em consideração as informações que entram na entrada do filtro durante o processo de observação.

Com a filtragem Wiener, cada nova amostra de sinal exigiria um recálculo de todos os pesos do filtro. Atualmente, os filtros adaptativos se espalharam, nos quais a nova informação recebida é usada para corrigir continuamente a avaliação do sinal feita anteriormente (rastreamento de alvos no radar, sistemas de controle automático no controle, etc.). De particular interesse são os filtros adaptativos do tipo recursivo conhecido como filtro de Kalman.

Esses filtros são amplamente usados ​​em malhas de controle em sistemas automáticos de regulação e controle. Foi a partir daí que surgiram, como evidenciado por uma terminologia tão específica usada para descrever o seu trabalho como o espaço de estados.

Uma das principais tarefas a serem resolvidas na prática da computação neural é a obtenção de algoritmos rápidos e confiáveis ​​para o aprendizado de redes neurais. Nesse sentido, pode ser útil usar filtros lineares no circuito de feedback. Como os algoritmos de treinamento são iterativos por natureza, tal filtro deve ser um estimador recursivo sequencial.

Problema de estimativa de parâmetro

Um dos problemas da teoria das decisões estatísticas, de grande importância prática, é o problema de estimar os vetores de estado e os parâmetros dos sistemas, que é formulado da seguinte maneira. Suponha que seja necessário estimar o valor do parâmetro vetorial $ X $, que é inacessível à medição direta. Em vez disso, outro parâmetro $ Z $ é medido, dependendo de $ X $. O problema de estimativa é responder à pergunta: o que pode ser dito sobre $ X $, sabendo $ Z $. No caso geral, o procedimento para a avaliação ótima do vetor $ X $ depende do critério aceito de qualidade da avaliação.

Por exemplo, a abordagem bayesiana do problema de estimativa de parâmetros requer informações a priori completas sobre as propriedades probabilísticas do parâmetro sendo estimado, o que muitas vezes é impossível. Nestes casos, recorrem ao método dos mínimos quadrados (OLS), que requer muito menos informações a priori.

Vamos considerar a aplicação de OLS para o caso em que o vetor de observação $ Z $ está relacionado ao vetor de estimativa de parâmetros $ X $ por um modelo linear, e a observação contém ruído $ V $, não correlacionado com o parâmetro estimado:

$ Z = HX + V $, (1)

onde $ H $ é uma matriz de transformação que descreve a relação entre as quantidades observadas e os parâmetros estimados.

A estimativa $ X $ minimizando o erro quadrático é escrita da seguinte forma:

$ X_ (оц) = (H ^ TR_V ^ (- 1) H) ^ (- 1) H ^ TR_V ^ (- 1) Z $, (2)

Que o ruído $ V $ não seja correlacionado, neste caso a matriz $ R_V $ é apenas a matriz identidade, e a equação para a estimativa torna-se mais simples:

$ X_ (ots) = (H ^ TH) ^ (- 1) H ^ TZ $, (3)

Escrever na forma de matriz economiza muito papel, mas pode ser incomum para alguns. O exemplo a seguir, retirado da monografia de Yu M. Korshunov, "Mathematical Foundations of Cybernetics", ilustra tudo isso.
O seguinte circuito elétrico está disponível:

Os valores observados neste caso são as leituras dos dispositivos $ A_1 = 1 A, A_2 = 2 A, V = 20 B $.

Além disso, a resistência $ R = 5 $ Ohm é conhecida. Deve-se estimar da melhor maneira, do ponto de vista do critério do quadrado médio mínimo do erro, os valores das correntes $ I_1 $ e $ I_2 $. O mais importante aqui é que haja alguma relação entre os valores observados (leituras do instrumento) e os parâmetros estimados. E essa informação é trazida de fora.

Nesse caso, são as leis de Kirchhoff, no caso da filtragem (que será discutida mais adiante) - um modelo autoregressivo de uma série temporal, que assume a dependência do valor atual dos anteriores.

Assim, o conhecimento das leis de Kirchhoff, que nada tem a ver com a teoria das decisões estatísticas, permite estabelecer uma ligação entre os valores observados e os parâmetros estimados (quem estudou engenharia elétrica - pode verificar, o resto terá acreditar na sua palavra):

$$ z_1 = A_1 = I_1 + \ xi_1 = 1 $$

$$ z_2 = A_2 = I_1 + I_2 + \ xi_2 = 2 $$

$$ z_2 = V / R = I_1 + 2 * I_2 + \ xi_3 = 4 $$

Está em forma vetorial:

$$ \ begin (vmatrix) z_1 \\ z_2 \\ z_3 \ end (vmatrix) = \ begin (vmatrix) 1 & 0 \\ 1 & 1 \\ 1 & 2 \ end (vmatrix) \ begin (vmatrix) I_1 \ \ I_2 \ end (vmatrix) + \ begin (vmatrix) \ xi_1 \\ \ xi_2 \\ \ xi_3 \ end (vmatrix) $$

Ou $ Z = HX + V $, onde

$$ Z = \ begin (vmatrix) z_1 \\ z_2 \\ z_3 \ end (vmatrix) = \ begin (vmatrix) 1 \\ 2 \\ 4 \ end (vmatrix); H = \ begin (vmatrix) 1 & 0 \\ 1 & 1 \\ 1 & 2 \ end (vmatrix); X = \ begin (vmatrix) I_1 \\ I_2 \ end (vmatrix); V = \ begin (vmatrix) \ xi_1 \\ \ xi_2 \\ \ xi_3 \ end (vmatrix) $$

Considerando os valores da interferência não correlacionados entre si, encontramos a estimativa de I 1 e I 2 pelo método dos mínimos quadrados de acordo com a fórmula 3:

$ H ^ TH = \ begin (vmatrix) 1 & 1 & 1 \\ 0 & 1 & 2 \ end (vmatrix) \ begin (vmatrix) 1 & 0 \\ 1 & 1 \\ 1 & 2 \ end (vmatrix) = \ begin (vmatrix) 3 & 3 \\ 3 & 5 \ end (vmatrix); (H ^ TH) ^ (- 1) = \ frac (1) (6) \ begin (vmatrix) 5 & -3 \\ -3 & 3 \ end (vmatrix) $;

$ H ^ TZ = \ begin (vmatrix) 1 & 1 & 1 \\ 0 & 1 & 2 \ end (vmatrix) \ begin (vmatrix) 1 \\ 2 \\ 4 \ end (vmatrix) = \ begin (vmatrix) 7 \ \ 10 \ end (vmatrix); X (ots) = \ frac (1) (6) \ begin (vmatrix) 5 & -3 \\ -3 & 3 \ end (vmatrix) \ begin (vmatrix) 7 \\ 10 \ end (vmatrix) = \ frac (1) (6) \ begin (vmatrix) 5 \\ 9 \ end (vmatrix) $;

Portanto, $ I_1 = 5/6 = 0,833 A $; $ I_2 = 9/6 = 1,5 A $.

Tarefa de filtração

Em contraste com o problema de estimar parâmetros que possuem valores fixos, no problema de filtragem é necessário estimar os processos, isto é, encontrar as estimativas atuais de um sinal variável no tempo, distorcido por interferência e, portanto, inacessível à medição direta. Em geral, o tipo de algoritmos de filtragem depende das propriedades estatísticas do sinal e do ruído.

Assumiremos que o sinal útil é uma função de tempo que varia lentamente e a interferência é um ruído não correlacionado. Usaremos o método dos mínimos quadrados, novamente devido à falta de informações a priori sobre as características probabilísticas do sinal e da interferência.

Primeiro, obtemos uma estimativa do valor atual de $ x_n $ com base nos $ k $ disponíveis dos últimos valores da série temporal $ z_n, z_ (n-1), z_ (n-2) \ dots z_ (n- (k-1)) $. O modelo de observação é o mesmo que no problema de estimativa de parâmetros:

É claro que $ Z $ é um vetor coluna que consiste nos valores observados da série temporal $ z_n, z_ (n-1), z_ (n-2) \ pontos z_ (n- (k-1)) $, $ V $ - vetor-coluna de interferência $ \ xi _n, \ xi _ (n-1), \ xi_ (n-2) \ dots \ xi_ (n- (k-1)) $, distorcendo o verdadeiro sinal. O que significam os símbolos $ H $ e $ X $? Sobre o que, por exemplo, o vetor coluna $ X $ podemos falar se tudo o que é necessário é fornecer uma estimativa do valor atual da série temporal? E o que se entende por matriz de transformação $ H $ não é nada claro.

Todas essas questões podem ser respondidas apenas se o conceito de um modelo de geração de sinal for introduzido em consideração. Ou seja, algum modelo do sinal original é necessário. Isso é compreensível, na ausência de informações a priori sobre as características probabilísticas do sinal e da interferência, tudo o que resta é fazer suposições. Você pode chamar de adivinhação sobre o pó de café, mas os especialistas preferem uma terminologia diferente. Em seu "secador de cabelo" é chamado de modelo paramétrico.

Nesse caso, os parâmetros desse modelo específico são estimados. Ao escolher um modelo de geração de sinal adequado, lembre-se de que qualquer função analítica pode ser expandida em uma série de Taylor. Uma propriedade surpreendente da série de Taylor é que a forma de uma função em qualquer distância finita $ t $ de algum ponto $ x = a $ é determinada exclusivamente pelo comportamento da função em uma vizinhança infinitamente pequena do ponto $ x = a $ (estamos falando sobre seus derivados de primeira ordem e ordens superiores).

Assim, a existência de séries de Taylor significa que a função analítica possui uma estrutura interna com um acoplamento muito forte. Se, por exemplo, nos restringirmos a três membros da série Taylor, o modelo de geração de sinal será semelhante a este:

$ x_ (n-i) = F _ (- i) x_n $, (4)

$$ X_n = \ begin (vmatrix) x_n \\ x "_n \\ x" "_ n \ end (vmatrix); F _ (- i) = \ begin (vmatrix) 1 & -i & i ^ 2/2 \\ 0 & 1 & -i \\ 0 & 0 & 1 \ end (vmatrix) $$

Ou seja, a fórmula 4, para uma dada ordem do polinômio (no exemplo, é 2) estabelece uma conexão entre o $ n $ -ésimo valor do sinal na seqüência de tempo e $ (n-i) $ -ésimo. Assim, o vetor de estado estimado, neste caso, inclui, além do valor real estimado, a primeira e a segunda derivadas do sinal.

Na teoria do controle automático, tal filtro seria chamado de filtro de astatismo de 2ª ordem. A matriz de transformação $ H $ para este caso (a estimativa é realizada com base nas amostras atuais e $ k-1 $ anteriores) é semelhante a esta:

$$ H = \ begin (vmatrix) 1 & -k & k ^ 2/2 \\ - & - & - \\ 1 & -2 & 2 \\ 1 & -1 & 0.5 \\ 1 & 0 & 0 \ fim (vmatrix) $$

Todos esses números são obtidos a partir da série de Taylor sob a suposição de que o intervalo de tempo entre os valores adjacentes observados é constante e igual a 1.

Portanto, a tarefa de filtragem de acordo com nossas suposições foi reduzida à tarefa de estimar parâmetros; neste caso, são estimados os parâmetros do modelo de geração de sinal adotado. E a estimativa dos valores do vetor de estado $ X $ é realizada de acordo com a mesma fórmula 3:

$$ X_ (ots) = (H ^ TH) ^ (- 1) H ^ TZ $$

Essencialmente, implementamos um processo de estimativa paramétrica baseado em um modelo autoregressivo do processo de geração de sinal.

A Fórmula 3 pode ser facilmente implementada de forma programática, para isso você precisa preencher a matriz $ H $ e a coluna do vetor de observações $ Z $. Esses filtros são chamados filtros de memória finita, já que eles usam as últimas $ k $ observações para obter a estimativa atual de $ X_ (nоц) $. A cada novo ciclo de observação, um novo é adicionado ao conjunto atual de observações e o antigo é descartado. Este processo de obtenção de notas é denominado janela deslizante.

Filtros de memória crescentes

Filtros com memória finita têm como principal desvantagem que a cada nova observação é necessário refazer um recálculo completo de todos os dados armazenados na memória. Além disso, o cálculo das estimativas só pode ser iniciado após os resultados das primeiras $ k $ observações terem sido acumulados. Ou seja, esses filtros têm um longo tempo transiente.

Para combater esta desvantagem, é necessário mudar de um filtro de memória persistente para um filtro com memória crescente... Nesse filtro, o número de valores observados para os quais a estimativa é feita deve coincidir com o número n da observação atual. Isso permite obter estimativas a partir do número de observações igual ao número de componentes do vetor estimado $ X $. E isso é determinado pela ordem do modelo adotado, ou seja, quantos termos da série de Taylor são utilizados no modelo.

Ao mesmo tempo, com o aumento de n, as propriedades de suavização do filtro melhoram, ou seja, a precisão das estimativas aumenta. No entanto, a implementação direta desta abordagem está associada a um aumento nos custos computacionais. Portanto, os filtros de memória crescente são implementados como recorrente.

O fato é que no momento n já temos uma estimativa $ X _ ((n-1) оц) $, que contém informações sobre todas as observações anteriores $ z_n, z_ (n-1), z_ (n-2) \ pontos z_ (n- (k-1)) $. A estimativa $ X_ (nоц) $ é obtida a partir da próxima observação $ z_n $ usando a informação armazenada na estimativa $ X _ ((n-1)) (\ mbox (оц)) $. Este procedimento é chamado de filtragem recorrente e consiste no seguinte:

• de acordo com a estimativa $ X _ ((n-1)) (\ mbox (оц)) $ prever a estimativa de $ X_n $ de acordo com a fórmula 4 com $ i = 1 $: $ X _ (\ mbox (nоtsapriori)) = F_1X _ ((n-1) sc) $. Esta é uma estimativa a priori;
• de acordo com os resultados da observação atual $ z_n $, esta estimativa a priori é convertida em verdadeira, ou seja, a posteriori;
• este procedimento é repetido a cada etapa, a partir de $ r + 1 $, onde $ r $ é a ordem do filtro.

A fórmula final para filtragem recorrente se parece com esta:

$ X _ ((n-1) оц) = X _ (\ mbox (nоtsapriori)) + (H ^ T_nH_n) ^ (- 1) h ^ T_0 (z_n - h_0 X _ (\ mbox (nоtsapriori))) $ , (6)

onde para o nosso filtro de segunda ordem:

Um filtro de memória crescente baseado na Fórmula 6 é um caso especial de um algoritmo de filtragem conhecido como filtro de Kalman.

Na implementação prática desta fórmula, deve-se lembrar que a estimativa a priori nela incluída é determinada pela fórmula 4, e o valor $ h_0 X _ (\ mbox (notspriori)) $ é o primeiro componente do vetor $ X _ (\ mbox (notspriori)) $.

O filtro de memória crescente tem um recurso importante. Se você olhar a fórmula 6, a pontuação final é a soma do vetor de pontuação prevista e o termo de correção. Essa correção é grande para $ n $ pequenos e diminui com o aumento de $ n $, tendendo a zero como $ n \ rightarrow \ infty $. Ou seja, com um aumento em n, as propriedades de suavização do filtro aumentam e o modelo inerente a ele começa a dominar. Mas o sinal real pode corresponder ao modelo apenas em certas áreas, portanto, a precisão da previsão se deteriora.

Para combater isso, a partir de cerca de $ n $, é imposta uma proibição de redução adicional do prazo de correção. Isso equivale a alterar a largura de banda do filtro, ou seja, para n pequeno o filtro é mais largo (menos inercial), para n grande ele se torna mais inercial.

Compare a Figura 1 com a Figura 2. Na primeira figura, o filtro tem uma grande memória, embora suavize bem, mas devido à banda estreita, a trajetória estimada fica atrás da real. Na segunda figura, a memória do filtro é menor, suaviza pior, mas segue melhor a trajetória real.

Literatura

1. YM Korshunov "Fundamentos matemáticos da cibernética"
2. A.V. Balakrishnan "teoria de filtração de Kalman"
3. VNFomin "Estimativa recorrente e filtragem adaptativa"
4. C.F.N. Cowen, P.M. Conceda "Filtros Adaptáveis"

Random Forest é um dos meus algoritmos de mineração de dados favoritos. Em primeiro lugar, é incrivelmente versátil e pode ser usado para resolver problemas de regressão e classificação. Procure anomalias e selecione preditores. Em segundo lugar, este é um algoritmo realmente difícil de aplicar incorretamente. Simplesmente porque, ao contrário de outros algoritmos, possui poucos parâmetros configuráveis. Também é surpreendentemente simples em seu núcleo. E ao mesmo tempo, é notável por sua precisão.

Qual é a ideia por trás de um algoritmo tão maravilhoso? A ideia é simples: digamos que temos algum algoritmo muito fraco, digamos. Se fizermos muitos modelos diferentes usando esse algoritmo fraco e fizermos a média do resultado de suas previsões, o resultado final será muito melhor. Este é o chamado treinamento conjunto em ação. O algoritmo Random Forest é, portanto, chamado de "Random Forest", pois os dados obtidos criam muitas árvores de decisão e, em seguida, calcula a média do resultado de suas previsões. Um ponto importante aqui é o elemento de aleatoriedade na criação de cada árvore. Afinal, está claro que, se criarmos muitas árvores idênticas, o resultado de sua média terá a precisão de uma árvore.

Como ele trabalha? Suponha que temos alguns dados de entrada. Cada coluna corresponde a algum parâmetro, cada linha corresponde a algum elemento de dados.

Podemos selecionar aleatoriamente um certo número de colunas e linhas de todo o conjunto de dados e construir uma árvore de decisão com base nelas.

Quinta-feira, 10 de maio de 2012

Quinta-feira, 12 de janeiro de 2012

Isso é tudo. O vôo de 17 horas acabou, a Rússia foi deixada no exterior. E pela janela de um aconchegante apartamento de 2 quartos em São Francisco, o famoso Vale do Silício, Califórnia, EUA está olhando para nós. Sim, essa é a razão pela qual praticamente não tenho escrito ultimamente. Nos mudamos.

Tudo começou em abril de 2011, quando eu estava dando uma entrevista por telefone na Zynga. Então tudo parecia uma espécie de jogo que não tinha nada a ver com a realidade, e eu não conseguia nem imaginar no que isso resultaria. Em junho de 2011, Zynga veio a Moscou e conduziu uma série de entrevistas, cerca de 60 candidatos aprovados em entrevistas por telefone foram considerados e cerca de 15 deles foram selecionados (não sei o número exato, alguém depois mudou de ideia, alguém imediatamente recusou). A entrevista acabou sendo surpreendentemente simples. Nenhuma tarefa de programação, nenhuma pergunta complicada sobre a forma das hachuras, principalmente a capacidade de bater papo foi testada. E o conhecimento, na minha opinião, foi avaliado apenas superficialmente.

E então o truque começou. Primeiro, esperamos os resultados, depois a oferta, depois a aprovação da LCA, depois a aprovação da petição de visto, depois os documentos dos EUA, depois a fila na embaixada, depois um cheque adicional, depois o visto. Às vezes, parecia-me que estava pronto para largar tudo e marcar. Às vezes, duvido que precisemos dessa América, afinal, também não é ruim na Rússia. Todo o processo demorou cerca de seis meses, por isso, em meados de dezembro recebemos os vistos e começamos a preparar a partida.

Segunda-feira foi meu primeiro dia de trabalho. O escritório tem todas as condições não só para trabalhar, mas também para habitar. Pequenos-almoços, almoços e jantares dos nossos próprios chefs, um monte de comidas variadas amontoadas por todo o lado, ginásio, massagens e até cabeleireiro. Tudo isso totalmente gratuito para os colaboradores. Muitas pessoas vão para o trabalho de bicicleta e há várias salas para guardar os veículos. Em geral, nunca encontrei nada parecido com isso na Rússia. Tudo, porém, tem seu preço, fomos imediatamente avisados ​​que teríamos que trabalhar muito. O que é "muito", pelos padrões deles, não é muito claro para mim.

Espero, entretanto, apesar da quantidade de trabalho, ser capaz de retomar o blog em um futuro previsível e talvez contar a você algo sobre a vida americana e o trabalho como programador na América. Espere e veja. Nesse ínterim, parabenizo a todos pelo próximo Ano Novo e Natal e até breve!

Para um exemplo de uso, imprimiremos o rendimento de dividendos das empresas russas. Como preço base, consideramos o preço de fechamento de uma ação no dia do fechamento do registro. Por alguma razão, esta informação não está no site da troika, mas é muito mais interessante do que os valores absolutos dos dividendos.
Atenção! O código leva muito tempo para ser executado, porque para cada promoção, é necessário fazer um pedido aos servidores do finam e obter o seu valor.

Resultado<- NULL for(i in (1:length(divs[,1]))){ d <- divs if (d$Divs>0) (experimente ((aspas<- getSymbols(d$Symbol, src="Finam", from="2010-01-01", auto.assign=FALSE) if (!is.nan(quotes)){ price <- Cl(quotes) if (length(price)>0) (dd<- d$Divs result <- rbind(result, data.frame(d$Symbol, d$Name, d$RegistryDate, as.numeric(dd)/as.numeric(price), stringsAsFactors=FALSE)) } } }, silent=TRUE) } } colnames(result) <- c("Symbol", "Name", "RegistryDate", "Divs") result

Da mesma forma, você pode criar estatísticas dos anos anteriores.

O filtro de Kalman é provavelmente o algoritmo de filtragem mais popular usado em muitos campos da ciência e tecnologia. Por sua simplicidade e eficiência, pode ser encontrado em receptores GPS, processadores de leituras de sensores, na implementação de sistemas de controle, etc.

Existem muitos artigos e livros sobre o filtro de Kalman na Internet (principalmente em inglês), mas esses artigos têm um limite de entrada bastante grande, existem muitos lugares vagos, embora na verdade seja um algoritmo muito claro e transparente. Vou tentar falar sobre isso em uma linguagem simples, com um aumento gradual na complexidade.

Para que serve?

Qualquer dispositivo de medição tem algum erro, ele pode ser influenciado por um grande número de influências externas e internas, o que leva ao fato de que a informação dele é ruidosa. Quanto mais ruidosos forem os dados, mais difícil será o processamento dessas informações.

Um filtro é um algoritmo de processamento de dados que remove ruído e informações desnecessárias. No filtro de Kalman, é possível definir informações a priori sobre a natureza do sistema, a relação das variáveis ​​e, com base nisso, construir uma estimativa mais precisa, mas mesmo no caso mais simples (sem inserir informações a priori ) dá excelentes resultados.

Vamos considerar o exemplo mais simples - suponha que precisamos controlar o nível de combustível no tanque. Para fazer isso, um sensor capacitivo é instalado no tanque, é muito fácil de manter, mas tem algumas desvantagens - por exemplo, dependência do combustível sendo reabastecido (a constante dielétrica do combustível depende de muitos fatores, por exemplo, na temperatura), uma grande influência da "ondulação" no tanque. Como resultado, as informações dele representam uma "serra" típica com uma amplitude decente. Esses tipos de sensores são frequentemente instalados em equipamentos pesados ​​de mineração (não se confunda com o volume do tanque):

Filtro de Kalman

Vamos divagar um pouco e nos familiarizar com o algoritmo em si. O filtro de Kalman usa um modelo dinâmico do sistema (por exemplo, a lei física do movimento), ações de controle conhecidas e muitas medições sucessivas para formar uma estimativa de estado ideal. O algoritmo consiste em duas fases repetidas: previsão e correção. No primeiro, a previsão do estado no próximo momento no tempo é calculada (levando em consideração a imprecisão de sua medição). No segundo, a nova informação do sensor corrige o valor previsto (levando-se em consideração a imprecisão e o ruído dessas informações):

As equações são apresentadas em forma de matriz, se você não conhece álgebra linear - tudo bem, então haverá uma versão simplificada sem matrizes para o caso com uma variável. No caso de uma variável, as matrizes degeneram em valores escalares.

Vamos primeiro entender a notação: o subscrito denota o momento no tempo: k - atual, (k-1) - anterior, o sinal de menos no sobrescrito significa que é previsto valor intermediário.

As descrições das variáveis ​​são apresentadas nas seguintes imagens:

É possível descrever por muito tempo e de maneira tediosa o que significam todas essas misteriosas matrizes de transição, mas é melhor, na minha opinião, tentar aplicar o algoritmo usando um exemplo real - para que valores abstratos adquiram um significado real.

Vamos tentar em ação

Voltemos ao exemplo com o sensor de nível de combustível, uma vez que o estado do sistema é representado por uma variável (o volume de combustível no tanque), as matrizes degeneram nas equações usuais:

Definindo um modelo de processo

Para aplicar o filtro, é necessário determinar as matrizes / valores das variáveis ​​que determinam a dinâmica do sistema e as dimensões F, B e H:

F- uma variável que descreve a dinâmica do sistema, no caso do combustível - pode ser um coeficiente que determina o consumo de combustível em marcha lenta durante o tempo de amostragem (o tempo entre as etapas do algoritmo). Porém, além do consumo de combustível, há também o reabastecimento ... portanto, para simplificar, tomaremos essa variável igual a 1 (ou seja, indicamos que o valor previsto será igual ao estado anterior).

B- a variável que determina a aplicação da ação de controle. Se tivéssemos informações adicionais sobre a rotação do motor ou o grau de pressão do pedal do acelerador, este parâmetro determinaria como o consumo de combustível mudará durante o tempo de amostragem. Como não há ações de controle em nosso modelo (não há informações sobre elas), consideramos B = 0.

H- uma matriz que determina a relação entre as medidas e o estado do sistema, por enquanto, sem explicação, tomaremos essa variável também igual a 1.

Definindo propriedades de suavização

R- o erro de medição pode ser determinado testando instrumentos de medição e determinando o erro de sua medição.

Q- A determinação do ruído do processo é uma tarefa mais difícil, pois é necessária para determinar a variância do processo, o que nem sempre é possível. Em qualquer caso, você pode escolher este parâmetro para fornecer o nível de filtragem necessário.

Implementando no código

Para dissipar a incompreensibilidade restante, vamos implementar um algoritmo simplificado em C # (sem matrizes e ações de controle):

classe KalmanFilterSimple1D
{
public double X0 (get; private set;) // estado previsto
public double P0 (get; private set;) // covariância prevista

Public double F (get; private set;) // fator do valor real para o valor real anterior
public double Q (get; private set;) // ruído de medição
public double H (get; private set;) // fator do valor medido para o valor real
public double R (get; private set;) // ruído ambiente

Estado duplo público (get; private set;)
covariância dupla pública (obter; conjunto privado;)

KalmanFilterSimple1D público (duplo q, duplo r, duplo f = 1, duplo h = 1)
{
Q = q;
R = r;
F = f;
H = h;
}

Public void SetState (estado duplo, covariância dupla)
{
Estado = estado;
Covariância = covariância;
}

Vazio público correto (dados duplos)
{
// atualização de tempo - previsão
X0 = F * Estado;
P0 = F * Covariância * F + Q;

// atualização de medição - correção
var K = H * P0 / (H * P0 * H + R);
Estado = X0 + K * (dados - H * X0);
Covariância = (1 - K * H) * F;
}
}

// Aplicativo ...

Var fuelData = GetData ();
var filtrada = nova lista ();

Var kalman = novo KalmanFilterSimple1D (f: 1, h: 1, q: 2, r: 15); // definir F, H, Q e R
kalman.SetState (fuelData, 0,1); // Defina os valores iniciais para Estado e Covariância
foreach (var d em fuelData)
{
kalman.Correct (d); // Aplicar o algoritmo

Filtered.Add (kalman.State); // Salve o estado atual
}

O resultado da filtragem com esses parâmetros é mostrado na figura (para ajustar o grau de suavização - você pode alterar os parâmetros Q e R):

O mais interessante é deixado fora do escopo do artigo - aplicar o filtro de Kalman para várias variáveis, definir a relação entre elas e exibir automaticamente os valores para as variáveis ​​não observáveis. Tentarei continuar o assunto assim que houver tempo.

Espero que a descrição não seja muito tediosa e complicada, se você tiver alguma dúvida ou esclarecimento - bem-vindo aos comentários)

No processo de automação de processos tecnológicos para controlar mecanismos e unidades, deve-se lidar com medições de várias grandezas físicas. Pode ser a pressão e a taxa de fluxo de um líquido ou gás, velocidade, temperatura e muito mais. A medição das grandezas físicas é realizada por meio de sensores analógicos. Um sinal analógico é um sinal de dados em que cada um dos parâmetros representativos é descrito por uma função de tempo e um conjunto contínuo de valores possíveis. Da continuidade do espaço de valor, segue-se que qualquer interferência introduzida no sinal é indistinguível do sinal desejado. Portanto, o valor incorreto da quantidade física necessária será enviado para a entrada analógica do dispositivo de controle. Portanto, é necessário filtrar o sinal proveniente do sensor.

Um dos algoritmos de filtragem eficientes é o filtro de Kalman. O filtro de Kalman é um filtro recursivo que estima o vetor de estado de um sistema dinâmico usando uma série de medições incompletas e com ruído. O filtro de Kalman usa um modelo dinâmico do sistema (por exemplo, a lei física do movimento), ações de controle e muitas medições sequenciais para formar uma estimativa de estado ideal. O algoritmo consiste em duas fases repetidas: previsão e correção. No primeiro estágio, a previsão do estado no próximo momento no tempo é calculada (levando em consideração a imprecisão de sua medição). Na segunda, a nova informação do sensor corrige o valor previsto (levando em consideração também a imprecisão e o ruído dessas informações).

Na fase de previsão, ocorre o seguinte:

1. Previsão do estado do sistema:

onde está a previsão do estado do sistema no momento atual; - matriz de transição entre estados (modelo dinâmico do sistema); - previsão do estado do sistema no momento anterior; - matriz de aplicação da ação de controle; - controlar a ação no momento anterior.

1. Prevendo covariância de erro:

onde está a previsão do erro; - erro no momento anterior; - covariância do ruído do processo.

Na fase de ajuste, ocorre o seguinte:

1. Cálculo do ganho de Kalman:

onde está o ganho de Kalman; - uma matriz de medições mostrando a relação entre medições e estados; - covariância de ruído de medição.

onde está a medição no momento atual.

1. Atualização de erro de covariância:

onde está a matriz de identidade.

Se o estado do sistema é descrito por uma variável, então = 1, e as matrizes degeneram em equações ordinárias.

Para demonstrar claramente a eficácia do filtro Kalman, foi realizado um experimento com o sensor de volume AVR PIC KY-037, que está conectado ao microcontrolador Arduino Uno. A Figura 1 mostra um gráfico das leituras do sensor sem filtro (linha 1). Flutuações caóticas na saída do sensor indicam a presença de ruído.

Figura 1. Gráfico de leituras do sensor sem filtro

Para aplicar o filtro, é necessário definir os valores das variáveis, e, que determinam a dinâmica do sistema e dimensões. Consideremos e igual a 1 e igual a 0, uma vez que não há ações de controle no sistema. Para determinar as propriedades de suavização do filtro, é necessário calcular o valor da variável, bem como selecionar o valor do parâmetro.

A variável será calculada no Microsoft Excel 2010. Para isso, é necessário calcular o desvio padrão para a amostra das leituras do sensor. = 0,62. é selecionado dependendo do nível de filtragem necessário, consideramos = 0,001. Na Figura 2, a segunda linha mostra o gráfico das leituras do sensor com o filtro aplicado.

Figura 2. Gráfico de leituras do sensor usando filtro de Kalman

A partir do gráfico, podemos concluir que o filtro lidou com a tarefa de filtrar a interferência, uma vez que no estado estacionário as flutuações nas leituras dos sensores que passaram pela filtragem são insignificantes.

No entanto, o filtro de Kalman tem uma desvantagem significativa. Se o valor medido do sensor puder mudar rapidamente, a leitura do sensor filtrado não mudará tão rapidamente quanto o valor medido. A Figura 3 mostra a resposta do filtro de Kalman a um salto no valor medido.

Figura 3. Reação do filtro de Kalman a um salto no valor medido

A resposta do filtro a um salto no valor medido foi considerada insignificante. Se o valor medido mudar significativamente e depois não retornar ao valor anterior, as leituras do sensor filtrado corresponderão ao valor real do valor medido somente após um período de tempo significativo, o que é inaceitável para sistemas de controle automático que requerem alto desempenho .

A partir do experimento realizado, pode-se concluir que o filtro de Kalman é aconselhável para filtrar as leituras dos sensores em sistemas de baixa velocidade.

Bibliografia:

1. GOST 17657-79. Transferência de dados. Termos e definições. - Moscou: Editora de padrões, 2005. - 2 p.
2. Filtro de Kalman // Wikipedia. ... Data de atualização: 26.04.2017. URL: http://ru.wikipedia.org/?oldid=85061599 (data de acesso: 21/05/2017).