Filtro de partícula - Particle filter

Filtros de partículas ou métodos Sequential Monte Carlo são um conjunto de algoritmos de Monte Carlo usados ​​para resolver problemas de filtragem que surgem no processamento de sinais e inferência estatística Bayesiana . O problema de filtragem consiste em estimar os estados internos em sistemas dinâmicos quando observações parciais são feitas, e perturbações aleatórias estão presentes nos sensores, bem como no sistema dinâmico. O objetivo é calcular as distribuições posteriores dos estados de alguns processos de Markov , dadas algumas observações ruidosas e parciais. O termo "filtros de partículas" foi cunhado pela primeira vez em 1996 por Del Moral em referência aos métodos de partículas interagentes de campo médio usados ​​na mecânica dos fluidos desde o início da década de 1960. O termo "Monte Carlo Sequencial" foi cunhado por Liu e Chen em 1998.

A filtragem de partículas usa um conjunto de partículas (também chamadas de amostras) para representar a distribuição posterior de algum processo estocástico com observações ruidosas e / ou parciais. O modelo de espaço de estado pode ser não linear e o estado inicial e as distribuições de ruído podem assumir qualquer forma necessária. As técnicas de filtro de partículas fornecem uma metodologia bem estabelecida para gerar amostras da distribuição necessária sem exigir suposições sobre o modelo de espaço de estado ou as distribuições de estado. No entanto, esses métodos não funcionam bem quando aplicados a sistemas de dimensões muito altas.

Os filtros de partículas atualizam sua previsão de maneira aproximada (estatística). As amostras da distribuição são representadas por um conjunto de partículas; cada partícula tem um peso de probabilidade atribuído a ela que representa a probabilidade dessa partícula ser amostrada a partir da função de densidade de probabilidade. A disparidade de peso que leva ao colapso de peso é um problema comum encontrado nesses algoritmos de filtragem; no entanto, pode ser atenuado incluindo uma etapa de reamostragem antes que os pesos se tornem muito desiguais. Vários critérios de reamostragem adaptativa podem ser usados, incluindo a variância dos pesos e a entropia relativa com respeito à distribuição uniforme. Na etapa de reamostragem, as partículas com pesos desprezíveis são substituídas por novas partículas na proximidade das partículas com pesos maiores.

Do ponto de vista estatístico e probabilístico, os filtros de partículas podem ser interpretados como interpretações de partículas de campo médio das medidas de probabilidade de Feynman-Kac . Essas técnicas de integração de partículas foram desenvolvidas em química molecular e física computacional por Theodore E. Harris e Herman Kahn em 1951, Marshall N. Rosenbluth e Arianna W. Rosenbluth em 1955 e mais recentemente por Jack H. Hetherington em 1984. Na física computacional, Os métodos de integração de partículas de caminho do tipo Feynman-Kac também são usados ​​em Quantum Monte Carlo e, mais especificamente, em métodos de Difusão Monte Carlo . Os métodos de partículas interagentes de Feynman-Kac também estão fortemente relacionados aos algoritmos genéticos de seleção de mutação atualmente usados ​​em computação evolucionária para resolver problemas complexos de otimização.

A metodologia do filtro de partículas é usada para resolver problemas de modelo oculto de Markov (HMM) e de filtragem não linear . Com a notável exceção de modelos de observação de sinais lineares Gaussianos ( filtro de Kalman ) ou classes mais amplas de modelos (filtro de Benes), Mireille Chaleyat-Maurel e Dominique Michel provaram em 1984 que a sequência de distribuições posteriores dos estados aleatórios do sinal dada a as observações (também conhecidas como filtro ideal) não têm recursão recursiva finita. Vários outros métodos numéricos baseados em aproximações de grade fixa, técnicas de Markov Chain Monte Carlo , linearização convencional, filtros de Kalman estendidos ou determinação do melhor sistema linear (no sentido de custo-erro esperado) são incapazes de lidar com sistemas de grande escala, processos instáveis, ou quando as não linearidades não são suficientemente suaves.

Filtros de partículas e metodologias de partículas de Feynman-Kac encontram aplicação em processamento de sinais e imagens , inferência bayesiana , aprendizado de máquina , análise de risco e amostragem de eventos raros , engenharia e robótica , inteligência artificial , bioinformática , filogenética , ciência computacional , economia e finanças matemáticas , química molecular , física computacional , farmacocinética e outros campos.

História

Algoritmos como heurísticos

Do ponto de vista estatístico e probabilístico, os filtros de partículas pertencem à classe de algoritmos de ramificação / tipo genético e metodologias de partículas de interação do tipo de campo médio. A interpretação desses métodos de partículas depende da disciplina científica. Em Computação Evolutiva , as metodologias de partículas do tipo genético de campo médio são frequentemente usadas como algoritmos de busca heurística e natural (também conhecido como Metaheurística ). Em física computacional e química molecular, eles são usados ​​para resolver problemas de integração de caminhos de Feynman-Kac, ou eles calculam medidas de Boltzmann-Gibbs, principais valores próprios e estados fundamentais de operadores de Schrödinger . Em Biologia e Genética, eles também representam a evolução de uma população de indivíduos ou genes em algum ambiente.

As origens das técnicas computacionais evolutivas do tipo de campo médio podem ser rastreadas até 1950 e 1954 com o trabalho seminal de Alan Turing sobre máquinas de aprendizagem de seleção de mutação de tipo genético e os artigos de Nils Aall Barricelli no Institute for Advanced Study em Princeton, New Jersey . O primeiro vestígio de filtros de partículas na metodologia estatística data de meados da década de 1950; o 'Poor Man's Monte Carlo', que foi proposto por Hammersley et al., em 1954, continha sugestões dos métodos de filtragem de partículas do tipo genético usados ​​hoje. Em 1963, Nils Aall Barricelli simulou um algoritmo de tipo genético para imitar a capacidade dos indivíduos de jogar um jogo simples. Na literatura de computação evolucionária , os algoritmos de seleção de mutação de tipo genético se tornaram populares por meio do trabalho seminal de John Holland no início dos anos 1970 e, particularmente, de seu livro publicado em 1975.

Em Biology and Genetics , o geneticista australiano Alex Fraser também publicou em 1957 uma série de artigos sobre a simulação do tipo genético da seleção artificial de organismos. A simulação computacional da evolução por biólogos se tornou mais comum no início dos anos 1960, e os métodos foram descritos nos livros de Fraser e Burnell (1970) e Crosby (1973). As simulações de Fraser incluíram todos os elementos essenciais dos modernos algoritmos de partícula genética de seleção de mutação.

Do ponto de vista matemático, a distribuição condicional dos estados aleatórios de um sinal dadas algumas observações parciais e ruidosas é descrita por uma probabilidade de Feynman-Kac nas trajetórias aleatórias do sinal ponderado por uma sequência de funções potenciais de verossimilhança. Quantum Monte Carlo e, mais especificamente, os métodos de Difusão Monte Carlo também podem ser interpretados como uma aproximação de partícula do tipo genético de campo médio de integrais de caminho de Feynman-Kac. As origens dos métodos Quantum Monte Carlo são frequentemente atribuídas a Enrico Fermi e Robert Richtmyer, que desenvolveram em 1948 uma interpretação de partícula de campo médio de reações em cadeia de nêutrons, mas o primeiro algoritmo de partícula do tipo heurístico e genético (também conhecido como Reamostragem ou Reconfiguração Monte Carlo métodos) para estimar as energias do estado fundamental de sistemas quânticos (em modelos de matriz reduzida) é devido a Jack H. Hetherington em 1984. Também se pode citar os primeiros trabalhos seminais de Theodore E. Harris e Herman Kahn em física de partículas, publicado em 1951, usando métodos genéticos de campo médio, mas heurísticos, para estimar as energias de transmissão de partículas. Na química molecular, o uso de metodologias de partículas semelhantes às heurísticas genéticas (também conhecidas como estratégias de poda e enriquecimento) pode ser rastreado até 1955 com o trabalho seminal de Marshall. N. Rosenbluth e Arianna. W. Rosenbluth.

O uso de algoritmos de partículas genéticas em processamento avançado de sinais e inferência bayesiana é mais recente. Em janeiro de 1993, Genshiro Kitagawa desenvolveu um "filtro Monte Carlo", uma versão ligeiramente modificada deste artigo que apareceu em 1996. Em abril de 1993, Gordon et al., Publicaram em seu trabalho seminal uma aplicação de algoritmo de tipo genético em inferência estatística Bayesiana. Os autores chamaram seu algoritmo de 'filtro de bootstrap' e demonstraram que, em comparação com outros métodos de filtragem, seu algoritmo de bootstrap não requer nenhuma suposição sobre aquele espaço de estado ou o ruído do sistema. Independentemente, os de Pierre Del Moral e Himilcon Carvalho, Pierre Del Moral, André Monin e Gérard Salut sobre filtros de partículas publicados em meados da década de 1990. Filtros de partículas também foram desenvolvidos em processamento de sinal no início de 1989-1992 por P. Del Moral, JC Noyer, G. Rigal e G. Salut no LAAS-CNRS em uma série de relatórios de pesquisa restritos e classificados com STCAN (Técnica de Serviço des Constructions et Armes Navales), a empresa de TI DIGILOG e o LAAS-CNRS (Laboratório de Análise e Arquitetura de Sistemas) sobre problemas de processamento de sinais RADAR / SONAR e GPS.

Fundamentos matemáticos

De 1950 a 1996, todas as publicações sobre filtros de partículas, algoritmos genéticos, incluindo os métodos de poda e reamostragem de Monte Carlo introduzidos na física computacional e na química molecular, apresentam algoritmos naturais e heurísticos aplicados a diferentes situações sem uma única prova de sua consistência, nem uma discussão sobre o viés das estimativas e sobre algoritmos baseados em árvore genealógica e ancestral.

Os fundamentos matemáticos e a primeira análise rigorosa desses algoritmos de partículas são devidos a Pierre Del Moral em 1996. O artigo também contém uma prova das propriedades imparciais de uma partícula, aproximações de funções de verossimilhança e medidas de probabilidade condicional não normalizadas . O estimador de partículas imparciais das funções de verossimilhança apresentado neste artigo é usado hoje em inferência estatística Bayesiana.

Metodologias de partículas do tipo ramificado com tamanhos variados de população também foram desenvolvidas no final da década de 1990 por Dan Crisan, Jessica Gaines e Terry Lyons, e por Dan Crisan, Pierre Del Moral e Terry Lyons. Outros desenvolvimentos neste campo foram desenvolvidos em 2000 por P. Del Moral, A. Guionnet e L. Miclo. Os primeiros teoremas do limite central são devidos a Pierre Del Moral e Alice Guionnet em 1999 e Pierre Del Moral e Laurent Miclo em 2000. Os primeiros resultados de convergência uniforme com respeito ao parâmetro de tempo para filtros de partículas foram desenvolvidos no final da década de 1990 por Pierre Del Moral e Alice Guionnet. A primeira análise rigorosa de filtros de partículas baseados em árvore genealógica é devida a P. Del Moral e L. Miclo em 2001

A teoria sobre as metodologias de partículas de Feynman-Kac e algoritmos de filtros de partículas relacionados foi desenvolvida em 2000 e 2004 nos livros. Esses modelos probabilísticos abstratos encapsulam algoritmos de tipo genético, filtros de partícula e bootstrap, filtros de Kalman interagentes (também conhecidos como filtro de partículas Rao-Blackwellized), amostragem de importância e técnicas de filtro de partículas de estilo de reamostragem, incluindo árvore genealógica e metodologias retrógradas de partículas para resolver problemas de filtragem e suavização. Outras classes de metodologias de filtragem de partículas incluem modelos baseados em árvore genealógica, modelos de partículas de Markov retroativos, modelos de partículas de campo médio adaptativos, modelos de partículas do tipo ilha e metodologias Monte Carlo de cadeia de Markov de partículas.

O problema de filtragem

Objetivo

O objetivo de um filtro de partículas é estimar a densidade posterior das variáveis ​​de estado dadas as variáveis ​​de observação. O filtro de partículas é projetado para um modelo de Markov oculto , onde o sistema consiste em variáveis ​​ocultas e observáveis. As variáveis ​​observáveis ​​(processo de observação) estão relacionadas às variáveis ​​ocultas (estado-processo) por alguma forma funcional que é conhecida. Da mesma forma, o sistema dinâmico que descreve a evolução das variáveis ​​de estado também é conhecido probabilisticamente.

Um filtro de partículas genérico estima a distribuição posterior dos estados ocultos usando o processo de medição de observação. Considere um espaço de estado mostrado no diagrama abaixo.

${\ displaystyle {\ begin {array} {cccccccccc} X_ {0} & \ to & X_ {1} & \ to & X_ {2} & \ to & X_ {3} & \ to & \ cdots & {\ text {signal} } \\\ downarrow && \ downarrow && \ downarrow && \ downarrow && \ cdots & \\ Y_ {0} && Y_ {1} && Y_ {2} && Y_ {3} && \ cdots & {\ text {observação}} \ end { variedade}}}$

O problema de filtragem é estimar sequencialmente os valores dos estados ocultos , dados os valores do processo de observação em qualquer etapa de tempo k . ${\ displaystyle X_ {k}}$${\ displaystyle Y_ {0}, \ cdots, Y_ {k},}$

Todas as estimativas bayesianas de seguem a partir da densidade posterior . A metodologia de filtro de partículas fornece uma aproximação dessas probabilidades condicionais usando a medida empírica associada a um algoritmo de partícula de tipo genético. Em contraste, a Cadeia de Markov Monte Carlo ou abordagem de amostragem de importância modelaria o posterior completo . ${\ displaystyle X_ {k}}$ ${\ displaystyle p (x_ {k} | y_ {0}, y_ {1}, ..., y_ {k})}$${\ displaystyle p (x_ {0}, x_ {1}, ..., x_ {k} | y_ {0}, y_ {1}, ..., y_ {k})}$

O modelo de observação de sinais

Os métodos de partículas geralmente assumem e as observações podem ser modeladas desta forma: ${\ displaystyle X_ {k}}$${\ displaystyle Y_ {k}}$

• ${\ displaystyle X_ {0}, X_ {1}, \ cdots}$é um processo de Markov em (para alguns ) que evolui de acordo com a densidade de probabilidade de transição . Este modelo também é frequentemente escrito de forma sintética como ${\ displaystyle \ mathbb {R} ^ {d_ {x}}}$${\ displaystyle d_ {x} \ geqslant 1}$${\ displaystyle p (x_ {k} | x_ {k-1})}$

  ${\ displaystyle X_ {k} | X_ {k-1} = x_ {k} \ sim p (x_ {k} | x_ {k-1})}$

com uma densidade de probabilidade inicial .${\ displaystyle p (x_ {0})}$

• As observações assumem valores em algum espaço de estado em (para alguns ) e são condicionalmente independentes, desde que sejam conhecidos. Em outras palavras, cada um depende apenas de . Além disso, assumimos que a distribuição condicional para dados é absolutamente contínua e, de forma sintética, temos ${\ displaystyle Y_ {0}, Y_ {1}, \ cdots}$${\ displaystyle \ mathbb {R} ^ {d_ {y}}}$${\ displaystyle d_ {y} \ geqslant 1}$${\ displaystyle X_ {0}, X_ {1}, \ cdots}$${\ displaystyle Y_ {k}}$${\ displaystyle X_ {k}}$${\ displaystyle Y_ {k}}$${\ displaystyle X_ {k} = x_ {k}}$

  ${\ displaystyle Y_ {k} | X_ {k} = y_ {k} \ sim p (y_ {k} | x_ {k})}$

Um exemplo de sistema com essas propriedades é:

${\ displaystyle X_ {k} = g (X_ {k-1}) + W_ {k-1}}$

${\ displaystyle Y_ {k} = h (X_ {k}) + V_ {k}}$

onde e são sequências mutuamente independentes com funções de densidade de probabilidade conhecidas e g e h são funções conhecidas. Essas duas equações podem ser vistas como equações de espaço de estado e são semelhantes às equações de espaço de estado do filtro de Kalman. Se as funções g e h no exemplo acima são lineares, e se ambos e são Gaussiana , o filtro de Kalman encontra a distribuição exacta filtragem Bayesiano. Caso contrário, os métodos baseados no filtro de Kalman são uma aproximação de primeira ordem ( EKF ) ou uma aproximação de segunda ordem ( UKF em geral, mas se a distribuição de probabilidade for Gaussiana, uma aproximação de terceira ordem é possível). ${\ displaystyle W_ {k}}$${\ displaystyle V_ {k}}$${\ displaystyle W_ {k}}$${\ displaystyle V_ {k}}$

A suposição de que a distribuição inicial e as transições da cadeia de Markov são absolutamente contínuas em relação à medida de Lebesgue pode ser relaxada. Para projetar um filtro de partículas, simplesmente precisamos assumir que podemos amostrar as transições da cadeia de Markov e calcular a função de verossimilhança (veja, por exemplo, a descrição da mutação de seleção genética do filtro de partículas fornecida abaixo). A suposição absolutamente contínua nas transições de Markov é usada apenas para derivar de uma forma informal (e um tanto abusiva) fórmulas diferentes entre distribuições posteriores usando a regra de Bayes para densidades condicionais. ${\ displaystyle X_ {k-1} \ a X_ {k}}$${\ displaystyle X_ {k},}$${\ displaystyle x_ {k} \ mapsto p (y_ {k} | x_ {k})}$${\ displaystyle X_ {k}}$

Modelos aproximados de computação bayesiana

Em alguns problemas, a distribuição condicional das observações dados os estados aleatórios do sinal pode não ter uma densidade ou pode ser impossível ou muito complexa para calcular. Nessa situação, precisamos recorrer a um nível adicional de aproximação. Uma estratégia é substituir o sinal pela cadeia de Markov e introduzir uma observação virtual da forma ${\ displaystyle X_ {k}}$${\ displaystyle {\ mathcal {X}} _ {k} = \ left (X_ {k}, Y_ {k} \ right)}$

${\ displaystyle {\ mathcal {Y}} _ {k} = Y_ {k} + \ epsilon {\ mathcal {V}} _ {k} \ quad {\ mbox {para algum parâmetro}} \ quad \ epsilon \ in [0,1]}$

para alguma sequência de sequências independentes com funções de densidade de probabilidade conhecidas . A ideia central é observar que

${\ displaystyle {\ text {Law}} \ left (X_ {k} | {\ mathcal {Y}} _ {0} = y_ {0}, \ cdots, {\ mathcal {Y}} _ {k} = y_ {k} \ right) \ approx _ {\ epsilon \ downarrow 0} {\ text {Law}} \ left (X_ {k} | Y_ {0} = y_ {0}, \ cdots, Y_ {k} = y_ {k} \ right)}$

O filtro de partículas associado ao processo de Markov, dadas as observações parciais, é definido em termos de partículas que evoluem com uma função de verossimilhança fornecida com alguma notação abusiva óbvia de . Essas técnicas probabilísticas estão intimamente relacionadas à Computação Bayesiana Aproximada (ABC). No contexto dos filtros de partículas, essas técnicas de filtragem de partículas ABC foram introduzidas em 1998 por P. Del Moral, J. Jacod e P. Protter. Eles foram desenvolvidos por P. Del Moral, A. Doucet e A. Jasra. ${\ displaystyle {\ mathcal {X}} _ {k} = \ left (X_ {k}, Y_ {k} \ right)}$${\ displaystyle {\ mathcal {Y}} _ {0} = y_ {0}, \ cdots, {\ mathcal {Y}} _ {k} = y_ {k},}$${\ displaystyle \ mathbb {R} ^ {d_ {x} + d_ {y}}}$${\ displaystyle p ({\ mathcal {Y}} _ {k} | {\ mathcal {X}} _ {k})}$

A equação de filtragem não linear

A regra de Bayes para probabilidade condicional fornece:

${\ displaystyle p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ frac {p (y_ {0}, \ cdots, y_ {k} | x_ {0}, \ cdots, x_ {k}) p (x_ {0}, \ cdots, x_ {k})} {p (y_ {0}, \ cdots, y_ {k})}}}$

Onde

${\ displaystyle {\ begin {alinhados} p (y_ {0}, \ cdots, y_ {k}) & = \ int p (y_ {0}, \ cdots, y_ {k} | x_ {0}, \ cdots , x_ {k}) p (x_ {0}, \ cdots, x_ {k}) dx_ {0} \ cdots dx_ {k} \\ p (y_ {0}, \ cdots, y_ {k} | x_ { 0}, \ cdots, x_ {k}) & = \ prod _ {l = 0} ^ {k} p (y_ {l} | x_ {l}) \\ p (x_ {0}, \ cdots, x_ {k}) & = p_ {0} (x_ {0}) \ prod _ {l = 1} ^ {k} p (x_ {l} | x_ {l-1}) \ end {alinhado}}}$

Os filtros de partículas também são uma aproximação, mas com partículas suficientes, eles podem ser muito mais precisos. A equação de filtragem não linear é dada pela recursão

${\ displaystyle {\ begin {alinhados} p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) & {\ stackrel {\ text {update}} {\ longrightarrow}} p (x_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ frac {p (y_ {k} | x_ {k}) p (x_ {k} | y_ {0}, \ cdots, y_ {k-1})} {\ int p (y_ {k} | x '_ {k}) p (x' _ {k} | y_ {0}, \ cdots, y_ {k-1}) dx ' _ {k}}} \\ & {\ stackrel {\ text {previsão}} {\ longrightarrow}} p (x_ {k + 1} | y_ {0}, \ cdots, y_ {k}) = \ int p (x_ {k + 1} | x_ {k}) p (x_ {k} | y_ {0}, \ cdots, y_ {k}) dx_ {k} \ end {alinhado}}}$

(Eq. 1)

com a convenção para k = 0. O problema da filtragem não linear consiste em computar essas distribuições condicionais sequencialmente. ${\ displaystyle p (x_ {0} | y_ {0}, \ cdots, y_ {k-1}) = p (x_ {0})}$

Formulação de Feynman-Kac

Fixamos um horizonte de tempo n e uma sequência de observações , e para cada k = 0, ..., n definimos: ${\ displaystyle Y_ {0} = y_ {0}, \ cdots, Y_ {n} = y_ {n}}$

${\ displaystyle G_ {k} (x_ {k}) = p (y_ {k} | x_ {k}).}$

Nesta notação, para qualquer função limitada F no conjunto de trajetórias da origem k = 0 até o tempo k = n , temos a fórmula de Feynman-Kac ${\ displaystyle X_ {k}}$

${\ displaystyle {\ begin {alinhados} \ int F (x_ {0}, \ cdots, x_ {n}) p (x_ {0}, \ cdots, x_ {n} | y_ {0}, \ cdots, y_ {n}) dx_ {0} \ cdots dx_ {n} & = {\ frac {\ int F (x_ {0}, \ cdots, x_ {n}) \ left \ {\ prod \ limits _ {k = 0 } ^ {n} p (y_ {k} | x_ {k}) \ right \} p (x_ {0}, \ cdots, x_ {n}) dx_ {0} \ cdots dx_ {n}} {\ int \ left \ {\ prod \ limits _ {k = 0} ^ {n} p (y_ {k} | x_ {k}) \ right \} p (x_ {0}, \ cdots, x_ {n}) dx_ {0} \ cdots dx_ {n}}} \\ & = {\ frac {E \ left (F (X_ {0}, \ cdots, X_ {n}) \ prod \ limits _ {k = 0} ^ { n} G_ {k} (X_ {k}) \ direita)} {E \ esquerda (\ prod \ limits _ {k = 0} ^ {n} G_ {k} (X_ {k}) \ direita)}} \ end {alinhado}}}$

Esses modelos de integração de caminhos de Feynman-Kac surgem em uma variedade de disciplinas científicas, incluindo física computacional, biologia, teoria da informação e ciências da computação. Suas interpretações dependem do domínio do aplicativo. Por exemplo, se escolhermos a função indicadora de algum subconjunto do espaço de estados, eles representam a distribuição condicional de uma cadeia de Markov, dado que ela permanece em um determinado tubo; ou seja, temos: ${\ displaystyle G_ {n} (x_ {n}) = 1_ {A} (x_ {n})}$

${\ displaystyle E \ left (F (X_ {0}, \ cdots, X_ {n}) | X_ {0} \ in A, \ cdots, X_ {n} \ in A \ right) = {\ frac {E \ left (F (X_ {0}, \ cdots, X_ {n}) \ prod \ limits _ {k = 0} ^ {n} G_ {k} (X_ {k}) \ right)} {E \ left (\ prod \ limits _ {k = 0} ^ {n} G_ {k} (X_ {k}) \ right)}}}$

e

${\ displaystyle P \ left (X_ {0} \ in A, \ cdots, X_ {n} \ in A \ right) = E \ left (\ prod \ limits _ {k = 0} ^ {n} G_ {k } (X_ {k}) \ right)}$

assim que a constante de normalização for estritamente positiva.

Filtros de partículas

Um algoritmo de partícula do tipo genético

Inicialmente, começamos com N variáveis ​​aleatórias independentes com densidade de probabilidade comum . As transições de seleção-mutação do algoritmo genético ${\ displaystyle \ left (\ xi _ {0} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$${\ displaystyle p (x_ {0})}$

${\ displaystyle \ xi _ {k}: = \ left (\ xi _ {k} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N} {\ stackrel {\ text {selection}} {\ longrightarrow }} {\ widehat {\ xi}} _ {k}: = \ left ({\ widehat {\ xi}} _ {k} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N} {\ stackrel {\ text {mutation}} {\ longrightarrow}} \ xi _ {k + 1}: = \ left (\ xi _ {k + 1} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N }}$

imitar / aproximar as transições de atualização-previsão da evolução ótima do filtro ( Eq. 1 ):

• Durante a transição de seleção-atualização , amostramos N (condicionalmente) variáveis ​​aleatórias independentes com distribuição comum (condicional)${\ displaystyle {\ widehat {\ xi}} _ {k}: = \ left ({\ widehat {\ xi}} _ {k} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$

${\ displaystyle \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k} ^ {i})} {\ sum _ {j = 1} ^ {N } p (y_ {k} | \ xi _ {k} ^ {j})}} \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k})}$

onde representa a medida de Dirac em um determinado estado a. ${\ displaystyle \ delta _ {a}}$

• Durante a transição de predição de mutação, de cada partícula selecionada , amostramos independentemente uma transição${\ displaystyle {\ widehat {\ xi}} _ {k} ^ {i}}$

${\ displaystyle {\ widehat {\ xi}} _ {k} ^ {i} \ longrightarrow \ xi _ {k + 1} ^ {i} \ sim p (x_ {k + 1} | {\ widehat {\ xi }} _ {k} ^ {i}), \ qquad i = 1, \ cdots, N.}$

Nas fórmulas exibidas acima representa a função de verossimilhança avaliada em e representa a densidade condicional avaliada em . ${\ displaystyle p (y_ {k} | \ xi _ {k} ^ {i})}$${\ displaystyle x_ {k} \ mapsto p (y_ {k} | x_ {k})}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ displaystyle p (x_ {k + 1} | {\ widehat {\ xi}} _ {k} ^ {i})}$${\ displaystyle p (x_ {k + 1} | x_ {k})}$${\ displaystyle x_ {k} = {\ widehat {\ xi}} _ {k} ^ {i}}$

A cada tempo k , temos as aproximações de partículas

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k}): = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {{\ widehat {\ xi}} _ {k} ^ {i}} (dx_ {k}) \ approx _ {N \ uparrow \ infty} p (dx_ {k} | y_ {0 }, \ cdots, y_ {k}) \ approx _ {N \ uparrow \ infty} \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k} ^ {i})} {\ sum _ {i = 1} ^ {N} p (y_ {k} | \ xi _ {k} ^ {j})}} \ delta _ {\ xi _ {k} ^ { i}} (dx_ {k})}$

e

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ frac {1} {N}} \ sum _ {i = 1 } ^ {N} \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k}) \ approx _ {N \ uparrow \ infty} p (dx_ {k} | y_ {0}, \ cdots , y_ {k-1})}$

Em algoritmos genéticos e na comunidade de computação evolutiva , a cadeia de Markov de seleção de mutação descrita acima é freqüentemente chamada de algoritmo genético com seleção proporcional. Diversas variantes de ramificação, inclusive com tamanhos populacionais aleatórios, também foram propostas nos artigos.

Princípios de Monte Carlo

Métodos de partículas, como todas as abordagens baseadas em amostragem (por exemplo, Markov Chain Monte Carlo), geram um conjunto de amostras que se aproximam da densidade de filtragem

${\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k}).}$

Por exemplo, podemos ter N amostras da distribuição posterior aproximada de , onde as amostras são rotuladas com sobrescritos como ${\ displaystyle X_ {k}}$

${\ displaystyle {\ widehat {\ xi}} _ {k} ^ {1}, \ cdots, {\ widehat {\ xi}} _ {k} ^ {N}.}$

Então, as expectativas com relação à distribuição de filtragem são aproximadas por

${\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ cdots, y_ {k}) \, dx_ {k} \ approx _ {N \ uparrow \ infty} {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} f \ left ({\ widehat {\ xi}} _ {k} ^ {i} \ right) = \ int f (x_ { k}) {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k})}$

(Eq. 2)

com

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ frac {1} {N}} \ sum _ {i = 1} ^ { N} \ delta _ {{\ widehat {\ xi}} _ {k} ^ {i}} (dx_ {k})}$

onde representa a medida de Dirac em um determinado estado a. A função f , da maneira usual para Monte Carlo, pode dar todos os momentos, etc. da distribuição até algum erro de aproximação. Quando a equação de aproximação ( Eq. 2 ) é satisfeita para qualquer função limitada f , escrevemos ${\ displaystyle \ delta _ {a}}$

${\ displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k}): = p (x_ {k} | y_ {0}, \ cdots, y_ {k}) dx_ {k} \ aproximadamente _ {N \ uparrow \ infty} {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ frac {1} {N}} \ sum _ { i = 1} ^ {N} \ delta _ {{\ widehat {\ xi}} _ {k} ^ {i}} (dx_ {k})}$

Os filtros de partículas podem ser interpretados como um algoritmo de partículas do tipo genético que evolui com mutações e transições de seleção. Podemos acompanhar as linhas ancestrais

${\ displaystyle \ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, {\ widehat {\ xi}} _ {1, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {k-1, k} ^ {i}, {\ widehat {\ xi}} _ {k, k} ^ {i} \ right)}$

das partículas . Os estados aleatórios , com os índices mais baixos l = 0, ..., k, representam o ancestral do indivíduo no nível l = 0, ..., k. Nesta situação, temos a fórmula de aproximação ${\ displaystyle i = 1, \ cdots, N}$${\ displaystyle {\ widehat {\ xi}} _ {l, k} ^ {i}}$${\ displaystyle {\ widehat {\ xi}} _ {k, k} ^ {i} = {\ widehat {\ xi}} _ {k} ^ {i}}$

${\ displaystyle {\ begin {alinhados} \ int F (x_ {0}, \ cdots, x_ {k}) p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k}) \, dx_ {0} \ cdots dx_ {k} & \ approx _ {N \ uparrow \ infty} {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, {\ widehat {\ xi}} _ {1, k} ^ {i}, \ cdots, {\ widehat {\ xi }} _ {k, k} ^ {i} \ right) \\ & = \ int F (x_ {0}, \ cdots, x_ {k}) {\ widehat {p}} (d (x_ {0} , \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \ end {alinhado}}}$

(Eq. 3)

com a medida empírica

${\ displaystyle {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}): = {\ frac {1} {N }} \ sum _ {i = 1} ^ {N} \ delta _ {\ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, {\ widehat {\ xi}} _ { 1, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {k, k} ^ {i} \ right)} (d (x_ {0}, \ cdots, x_ {k}) )}$

Aqui, F representa qualquer função fundada no espaço do caminho do sinal. Em uma forma mais sintética ( Eq. 3 ) é equivalente a

${\ displaystyle {\ begin {alinhados} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) &: = p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k}) \, dx_ {0} \ cdots dx_ {k} \\ & \ approx _ {N \ uparrow \ infty} {\ widehat { p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ &: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {k , k} ^ {i} \ right)} (d (x_ {0}, \ cdots, x_ {k})) \ end {alinhado}}}$

Os filtros de partículas podem ser interpretados de muitas maneiras diferentes. Do ponto de vista probabilístico, eles coincidem com uma interpretação de partículas de campo médio da equação de filtragem não linear. As transições de atualização-previsão da evolução do filtro ideal também podem ser interpretadas como as transições de seleção-mutação de tipo genético clássico de indivíduos. A técnica de reamostragem de importância sequencial fornece outra interpretação das transições de filtragem acoplando a amostragem de importância com a etapa de reamostragem de bootstrap. Por último, mas não menos importante, os filtros de partículas podem ser vistos como uma metodologia de aceitação-rejeição equipada com um mecanismo de reciclagem.

Simulação de partículas de campo médio

O princípio probabilístico geral

A evolução da filtragem não linear pode ser interpretada como um sistema dinâmico no conjunto de medidas de probabilidade da seguinte forma, onde representa algum mapeamento do conjunto de distribuição de probabilidade em si mesmo. Por exemplo, a evolução do preditor ótimo de uma etapa${\ displaystyle \ eta _ {n + 1} = \ Phi _ {n + 1} \ left (\ eta _ {n} \ right)}$${\ displaystyle \ Phi _ {n + 1}}$${\ displaystyle \ eta _ {n} (dx_ {n}) = p (x_ {n} | y_ {0}, \ cdots, y_ {n-1}) dx_ {n}}$

satisfaz uma evolução não linear começando com a distribuição de probabilidade . Uma das maneiras mais simples de aproximar essas medidas de probabilidade é começar com N variáveis ​​aleatórias independentes com distribuição de probabilidade comum . Suponha que tenhamos definido uma sequência de N variáveis ​​aleatórias de forma que ${\ displaystyle \ eta _ {0} (dx_ {0}) = p (x_ {0}) dx_ {0}}$${\ displaystyle \ left (\ xi _ {0} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$${\ displaystyle \ eta _ {0} (dx_ {0}) = p (x_ {0}) dx_ {0}}$${\ displaystyle \ left (\ xi _ {n} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$

${\ displaystyle {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ xi _ {n} ^ {i}} (dx_ {n}) \ approx _ { N \ uparrow \ infty} \ eta _ {n} (dx_ {n})}$

Na próxima etapa, amostramos N (condicionalmente) variáveis ​​aleatórias independentes com common law. ${\ displaystyle \ xi _ {n + 1}: = \ left (\ xi _ {n + 1} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$

${\ displaystyle \ Phi _ {n + 1} \ left ({\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ xi _ {n} ^ {i} } \ right) \ approx _ {N \ uparrow \ infty} \ Phi _ {n + 1} \ left (\ eta _ {n} \ right) = \ eta _ {n + 1}}$

Uma interpretação de partículas da equação de filtragem

Ilustramos este princípio de partícula de campo médio no contexto da evolução dos preditores ótimos de uma etapa

${\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k} \ to p (x_ {k + 1} | y_ {0}, \ cdots, y_ { k}) = \ int p (x_ {k + 1} | x '_ {k}) {\ frac {p (y_ {k} | x_ {k}') p (x '_ {k} | y_ { 0}, \ cdots, y_ {k-1}) dx '_ {k}} {\ int p (y_ {k} | x' '_ {k}) p (x' '_ {k} | y_ { 0}, \ cdots, y_ {k-1}) dx '' _ {k}}}}$

(Eq. 4)

Para k = 0, usamos a convenção . ${\ displaystyle p (x_ {0} | y_ {0}, \ cdots, y _ {- 1}): = p (x_ {0})}$

Pela lei dos grandes números, temos

${\ displaystyle {\ widehat {p}} (dx_ {0}) = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ xi _ {0} ^ {i}} (dx_ {0}) \ approx _ {N \ uparrow \ infty} p (x_ {0}) dx_ {0}}$

no sentido de que

${\ displaystyle \ int f (x_ {0}) {\ widehat {p}} (dx_ {0}) = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} f ( \ xi _ {0} ^ {i}) \ approx _ {N \ uparrow \ infty} \ int f (x_ {0}) p (dx_ {0}) dx_ {0}}$

para qualquer função limitada . Além disso, assumimos que construímos uma sequência de partículas em alguma classificação k tal que ${\ displaystyle f}$${\ displaystyle \ left (\ xi _ {k} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ frac {1} {N}} \ sum _ {i = 1 } ^ {N} \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k}) \ approx _ {N \ uparrow \ infty} ~ p (x_ {k} ~ | ~ y_ {0} , \ cdots, y_ {k-1}) dx_ {k}}$

no sentido de que para qualquer função limitada , temos ${\ displaystyle f}$

${\ displaystyle \ int f (x_ {k}) {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}) = {\ frac {1} {N} } \ sum _ {i = 1} ^ {N} f (\ xi _ {k} ^ {i}) \ approx _ {N \ uparrow \ infty} \ int f (x_ {k}) p (dx_ {k } | y_ {0}, \ cdots, y_ {k-1}) dx_ {k}}$

Nesta situação, substituindo pela medida empírica na equação de evolução do filtro ótimo de uma etapa declarado na ( Eq. 4 ), descobrimos que ${\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k}}$ ${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$

${\ displaystyle p (x_ {k + 1} | y_ {0}, \ cdots, y_ {k}) \ approx _ {N \ uparrow \ infty} \ int p (x_ {k + 1} | x '_ { k}) {\ frac {p (y_ {k} | x_ {k} ') {\ widehat {p}} (dx' _ {k} | y_ {0}, \ cdots, y_ {k-1}) } {\ int p (y_ {k} | x '' _ {k}) {\ widehat {p}} (dx '' _ {k} | y_ {0}, \ cdots, y_ {k-1}) }}}$

Observe que o lado direito da fórmula acima é uma mistura de probabilidade ponderada

${\ displaystyle \ int p (x_ {k + 1} | x '_ {k}) {\ frac {p (y_ {k} | x_ {k}') {\ widehat {p}} (dx '_ { k} | y_ {0}, \ cdots, y_ {k-1})} {\ int p (y_ {k} | x '' _ {k}) {\ widehat {p}} (dx '' _ { k} | y_ {0}, \ cdots, y_ {k-1})}} = \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k} ^ {i})} {\ sum _ {i = 1} ^ {N} p (y_ {k} | \ xi _ {k} ^ {j})}} p (x_ {k + 1} | \ xi _ {k} ^ {i}) =: {\ widehat {q}} (x_ {k + 1} | y_ {0}, \ cdots, y_ {k})}$

onde representa a densidade avaliada em , e meios a densidade avaliada em para${\ displaystyle p (y_ {k} | \ xi _ {k} ^ {i})}$${\ displaystyle p (y_ {k} | x_ {k})}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ displaystyle p (x_ {k + 1} | \ xi _ {k} ^ {i})}$${\ displaystyle p (x_ {k + 1} | x_ {k})}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ displaystyle i = 1, \ cdots, N.}$

Em seguida, amostramos N variáveis ​​aleatórias independentes com densidade de probabilidade comum para que ${\ displaystyle \ left (\ xi _ {k + 1} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}$${\ displaystyle {\ widehat {q}} (x_ {k + 1} | y_ {0}, \ cdots, y_ {k})}$

${\ displaystyle {\ widehat {p}} (dx_ {k + 1} | y_ {0}, \ cdots, y_ {k}): = {\ frac {1} {N}} \ sum _ {i = 1 } ^ {N} \ delta _ {\ xi _ {k + 1} ^ {i}} (dx_ {k + 1}) \ approx _ {N \ uparrow \ infty} {\ widehat {q}} (x_ { k + 1} | y_ {0}, \ cdots, y_ {k}) dx_ {k + 1} \ approx _ {N \ uparrow \ infty} p (x_ {k + 1} | y_ {0}, \ cdots , y_ {k}) dx_ {k + 1}}$

Iterando este procedimento, projetamos uma cadeia de Markov de forma que

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ frac {1} {N}} \ sum _ {i = 1 } ^ {N} \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k}) \ approx _ {N \ uparrow \ infty} p (dx_ {k} | y_ {0}, \ cdots , y_ {k-1}): = p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k}}$

Observe que o filtro ideal é aproximado em cada etapa de tempo k usando as fórmulas de Bayes

${\ displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k}) \ approx _ {N \ uparrow \ infty} {\ frac {p (y_ {k} | x_ {k}) { \ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})} {\ int p (y_ {k} | x '_ {k}) {\ widehat {p }} (dx '_ {k} | y_ {0}, \ cdots, y_ {k-1})}} = \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k} ^ {i})} {\ sum _ {j = 1} ^ {N} p (y_ {k} | \ xi _ {k} ^ {j})}} ~ \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k})}$

A terminologia "aproximação de campo médio" vem do fato de que substituímos a cada passo de tempo a medida de probabilidade pela aproximação empírica . A aproximação de partículas de campo médio do problema de filtragem está longe de ser única. Várias estratégias são desenvolvidas nos livros. ${\ displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$

Alguns resultados de convergência

A análise da convergência dos filtros de partículas foi iniciada em 1996 e em 2000 no livro e na série de artigos. Desenvolvimentos mais recentes podem ser encontrados nos livros, Quando a equação de filtragem é estável (no sentido de que corrige qualquer condição inicial errônea), o viés e a variância das estimativas de partículas de partículas

${\ displaystyle I_ {k} (f): = \ int f (x_ {k}) p (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}) \ approx _ {N \ uparrow \ infty} {\ widehat {I}} _ {k} (f): = \ int f (x_ {k}) {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$

são controlados pelas estimativas uniformes não assintóticas

${\ displaystyle \ sup _ {k \ geqslant 0} \ left \ vert E \ left ({\ widehat {I}} _ {k} (f) \ right) -I_ {k} (f) \ right \ vert \ leqslant {\ frac {c_ {1}} {N}}}$

${\ displaystyle \ sup _ {k \ geqslant 0} E \ left (\ left [{\ widehat {I}} _ {k} (f) -I_ {k} (f) \ right] ^ {2} \ right ) \ leqslant {\ frac {c_ {2}} {N}}}$

para qualquer função f limitada por 1, e para algumas constantes finitas Além disso, para qualquer : ${\ displaystyle c_ {1}, c_ {2}.}$${\ displaystyle x \ geqslant 0}$

${\ displaystyle \ mathbf {P} \ left (\ left | {\ widehat {I}} _ {k} (f) -I_ {k} (f) \ right | \ leqslant c_ {1} {\ frac {x } {N}} + c_ {2} {\ sqrt {\ frac {x} {N}}} \ land \ sup _ {0 \ leqslant k \ leqslant n} \ left | {\ widehat {I}} _ { k} (f) -I_ {k} (f) \ right | \ leqslant c {\ sqrt {\ frac {x \ log (n)} {N}}} \ right)> 1-e ^ {- x} }$

para algumas constantes finitas relacionadas à tendência assintótica e variância da estimativa de partícula, e alguma constante finita c . Os mesmos resultados são satisfeitos se substituirmos o preditor ótimo de uma etapa pela aproximação de filtro ideal. ${\ displaystyle c_ {1}, c_ {2}}$

Árvores genealógicas e propriedades de imparcialidade

Suavização de partículas com base em árvore genealógica

Traçando de volta no tempo as linhas ancestrais

${\ displaystyle \ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, {\ widehat {\ xi}} _ {1, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {k-1, k} ^ {i}, {\ widehat {\ xi}} _ {k, k} ^ {i} \ right), \ quad \ left (\ xi _ {0 , k} ^ {i}, \ xi _ {1, k} ^ {i}, \ cdots, \ xi _ {k-1, k} ^ {i}, \ xi _ {k, k} \ right) }$

dos indivíduos e em cada etapa de tempo k , também temos as aproximações de partículas ${\ displaystyle {\ widehat {\ xi}} _ {k} ^ {i} \ left (= {\ widehat {\ xi}} _ {k, k} ^ {i} \ right)}$${\ displaystyle \ xi _ {k} ^ {i} \ left (= {\ xi} _ {k, k} ^ {i} \ right)}$

${\ displaystyle {\ begin {align} {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) &: = { \ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {0, k} ^ {i} \ right)} (d (x_ {0}, \ cdots, x_ {k})) \\ & \ approx _ {N \ uparrow \ infty} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ & \ approx _ {N \ uparrow \ infty} \ sum _ { i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k, k} ^ {i})} {\ sum _ {j = 1} ^ {N} p (y_ { k} | \ xi _ {k, k} ^ {j})}} \ delta _ {\ left (\ xi _ {0, k} ^ {i}, \ cdots, \ xi _ {0, k} ^ {i} \ right)} (d (x_ {0}, \ cdots, x_ {k})) \\ & \ \\ {\ widehat {p}} (d (x_ {0}, \ cdots, x_ { k}) | y_ {0}, \ cdots, y_ {k-1}) &: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ left (\ xi _ {0, k} ^ {i}, \ cdots, \ xi _ {k, k} ^ {i} \ right)} (d (x_ {0}, \ cdots, x_ {k})) \\ & \ approx _ {N \ uparrow \ infty} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ &: = p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {0}, \ cdots, dx_ {k} \ end {alinhado}}}$

Essas aproximações empíricas são equivalentes às aproximações integrais de partícula

${\ displaystyle {\ begin {alinhados} \ int F (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) &: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {0, k} ^ {i} \ right) \\ & \ approx _ {N \ uparrow \ infty} \ int F (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ & \ aproximadamente _ {N \ uparrow \ infty} \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | \ xi _ {k, k} ^ {i})} {\ sum _ {j = 1} ^ {N} p (y_ {k} | \ xi _ {k, k} ^ {j})}} F \ left (\ xi _ {0, k} ^ {i}, \ cdots , \ xi _ {k, k} ^ {i} \ right) \\ & \ \\\ int F (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) &: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left (\ xi _ {0, k} ^ {i}, \ cdots, \ xi _ {k, k} ^ {i} \ right) \\ & \ approx _ {N \ uparrow \ infty } \ int F (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1} ) \ end {alinhado}}}$

para qualquer função limitada F nas trajetórias aleatórias do sinal. Como mostrado na evolução da árvore genealógica coincide com uma interpretação de partícula de campo médio das equações de evolução associadas com as densidades posteriores das trajetórias de sinal. Para obter mais detalhes sobre esses modelos de espaço de caminho, consulte os livros.

Estimativas imparciais de partículas de funções de verossimilhança

Usamos a fórmula do produto

${\ displaystyle p (y_ {0}, \ cdots, y_ {n}) = \ prod _ {k = 0} ^ {n} p (y_ {k} | y_ {0}, \ cdots, y_ {k- 1})}$

com

${\ displaystyle p (y_ {k} | y_ {0}, \ cdots, y_ {k-1}) = \ int p (y_ {k} | x_ {k}) p (dx_ {k} | y_ {0 }, \ cdots, y_ {k-1})}$

e as convenções e para k = 0. Substituindo pela aproximação empírica${\ displaystyle p (y_ {0} | y_ {0}, \ cdots, y _ {- 1}) = p (y_ {0})}$${\ displaystyle p (x_ {0} | y_ {0}, \ cdots, y _ {- 1}) = p (x_ {0}),}$${\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k}}$

${\ displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ frac {1} {N}} \ sum _ {i = 1 } ^ {N} \ delta _ {\ xi _ {k} ^ {i}} (dx_ {k}) \ approx _ {N \ uparrow \ infty} p (dx_ {k} | y_ {0}, \ cdots , y_ {k-1})}$

na fórmula exibida acima, projetamos a seguinte aproximação de partícula imparcial da função de verossimilhança

${\ displaystyle p (y_ {0}, \ cdots, y_ {n}) \ approx _ {N \ uparrow \ infty} {\ widehat {p}} (y_ {0}, \ cdots, y_ {n}) = \ prod _ {k = 0} ^ {n} {\ widehat {p}} (y_ {k} | y_ {0}, \ cdots, y_ {k-1})}$

com

${\ displaystyle {\ widehat {p}} (y_ {k} | y_ {0}, \ cdots, y_ {k-1}) = \ int p (y_ {k} | x_ {k}) {\ widehat { p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}) = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} p (y_ {k} | \ xi _ {k} ^ {i})}$

onde representa a densidade avaliada em . O desenho desta estimativa de partícula e a propriedade de imparcialidade foram provados em 1996 no artigo. As estimativas de variância refinadas podem ser encontradas em e. ${\ displaystyle p (y_ {k} | \ xi _ {k} ^ {i})}$${\ displaystyle p (y_ {k} | x_ {k})}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$

Suavizadores de partícula para trás

Usando a regra de Bayes, temos a fórmula

${\ displaystyle p (x_ {0}, \ cdots, x_ {n} | y_ {0}, \ cdots, y_ {n-1}) = p (x_ {n} | y_ {0}, \ cdots, y_ {n-1}) p (x_ {n-1} | x_ {n}, y_ {0}, \ cdots, y_ {n-1}) \ cdots p (x_ {1} | x_ {2}, y_ {0}, y_ {1}) p (x_ {0} | x_ {1}, y_ {0})}$

Notar que

${\ displaystyle {\ begin {alinhados} p (x_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) & \ propto p (x_ {k} | x_ {k-1}) p (x_ {k-1} | (y_ {0}, \ cdots, y_ {k-1})) \\ p (x_ {k-1} | (y_ {0}, \ cdots, y_ {k-1}) & \ propto p (y_ {k-1} | x_ {k-1}) p (x_ {k-1} | (y_ {0}, \ cdots, y_ {k -2}) \ end {alinhado}}}$

Isso implica que

${\ displaystyle p (x_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) = {\ frac {p (y_ {k-1} | x_ { k-1}) p (x_ {k} | x_ {k-1}) p (x_ {k-1} | y_ {0}, \ cdots, y_ {k-2})} {\ int p (y_ {k-1} | x '_ {k-1}) p (x_ {k} | x' _ {k-1}) p (x '_ {k-1} | y_ {0}, \ cdots, y_ {k-2}) dx '_ {k-1}}}}$

Substituindo os preditores ótimos de uma etapa pelas medidas empíricas de partículas${\ displaystyle p (x_ {k-1} | (y_ {0}, \ cdots, y_ {k-2})) dx_ {k-1}}$

${\ displaystyle {\ widehat {p}} (dx_ {k-1} | (y_ {0}, \ cdots, y_ {k-2})) = {\ frac {1} {N}} \ sum _ { i = 1} ^ {N} \ delta _ {\ xi _ {k-1} ^ {i}} (dx_ {k-1}) \ left (\ approx _ {N \ uparrow \ infty} p (dx_ { k-1} | (y_ {0}, \ cdots, y_ {k-2})): = {p} (x_ {k-1} | (y_ {0}, \ cdots, y_ {k-2} )) dx_ {k-1} \ right)}$

nós encontramos isso

${\ displaystyle {\ begin {align} p (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) & \ approx _ {N \ uparrow \ infty } {\ widehat {p}} (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) \\ &: = {\ frac {p (y_ {k-1} | x_ {k-1}) p (x_ {k} | x_ {k-1}) {\ widehat {p}} (dx_ {k-1} | y_ {0}, \ cdots, y_ {k-2})} {\ int p (y_ {k-1} | x '_ {k-1}) ~ p (x_ {k} | x' _ {k-1}) {\ widehat { p}} (dx '_ {k-1} | y_ {0}, \ cdots, y_ {k-2})}} \\ & = \ sum _ {i = 1} ^ {N} {\ frac { p (y_ {k-1} | \ xi _ {k-1} ^ {i}) p (x_ {k} | \ xi _ {k-1} ^ {i})} {\ sum _ {j = 1} ^ {N} p (y_ {k-1} | \ xi _ {k-1} ^ {j}) p (x_ {k} | \ xi _ {k-1} ^ {j})}} \ delta _ {\ xi _ {k-1} ^ {i}} (dx_ {k-1}) \ end {alinhado}}}$

Concluimos que

${\ displaystyle p (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) \ approx _ {N \ uparrow \ infty} {\ widehat {p}} _ {backward} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}$

com a aproximação de partícula para trás

${\ displaystyle {\ begin {align} {\ widehat {p}} _ {backward} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n- 1})) = {\ widehat {p}} (dx_ {n} | (y_ {0}, \ cdots, y_ {n-1})) {\ widehat {p}} (dx_ {n-1} | x_ {n}, (y_ {0}, \ cdots, y_ {n-1})) \ cdots {\ widehat {p}} (dx_ {1} | x_ {2}, (y_ {0}, y_ { 1})) {\ widehat {p}} (dx_ {0} | x_ {1}, y_ {0}) \ end {alinhado}}}$

A medida de probabilidade

${\ displaystyle {\ widehat {p}} _ {backward} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}$

é a probabilidade dos caminhos aleatórios de uma cadeia de Markov correr para trás no tempo do tempo k = n ao tempo k = 0, e evoluir a cada passo de tempo k no espaço de estado associado com a população de partículas${\ displaystyle \ left (\ mathbb {X} _ {k, n} ^ {\ flat} \ right) _ {0 \ leqslant k \ leqslant n}}$${\ displaystyle \ xi _ {k} ^ {i}, i = 1, \ cdots, N.}$

• Inicialmente (no tempo k = n), a cadeia escolhe aleatoriamente um estado com a distribuição${\ displaystyle \ mathbb {X} _ {n, n} ^ {\ flat}}$

${\ displaystyle {\ widehat {p}} (dx_ {n} | (y_ {0}, \ cdots, y_ {n-1})) = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ xi _ {n} ^ {i}} (dx_ {n})}$

• Do tempo k para o tempo (k-1), a cadeia começando em algum estado para algum no tempo k se move no tempo (k-1) para um estado aleatório escolhido com a probabilidade ponderada discreta${\ displaystyle \ mathbb {X} _ {k, n} ^ {\ flat} = \ xi _ {k} ^ {i}}$${\ displaystyle i = 1, \ cdots, N}$${\ displaystyle \ mathbb {X} _ {k-1, n} ^ {\ flat}}$

${\ displaystyle {\ widehat {p}} (dx_ {k-1} | \ xi _ {k} ^ {i}, (y_ {0}, \ cdots, y_ {k-1})) = \ sum _ {j = 1} ^ {N} {\ frac {p (y_ {k-1} | \ xi _ {k-1} ^ {j}) p (\ xi _ {k} ^ {i} | \ xi _ {k-1} ^ {j})} {\ sum _ {l = 1} ^ {N} p (y_ {k-1} | \ xi _ {k-1} ^ {l}) p (\ xi _ {k} ^ {i} | \ xi _ {k-1} ^ {l})}} ~ \ delta _ {\ xi _ {k-1} ^ {j}} (dx_ {k-1} )}$

Na fórmula exibida acima, representa a distribuição condicional avaliada em . Na mesma linha, e representam as densidades condicionais e avaliadas em e Esses modelos permitem reduzir a integração em relação às densidades em termos de operações de matriz em relação às transições de Markov da cadeia descrita acima. Por exemplo, para qualquer função , temos as estimativas de partículas ${\ displaystyle {\ widehat {p}} (dx_ {k-1} | \ xi _ {k} ^ {i}, (y_ {0}, \ cdots, y_ {k-1}))}$${\ displaystyle {\ widehat {p}} (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1}))}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ displaystyle p (y_ {k-1} | \ xi _ {k-1} ^ {j})}$${\ displaystyle p (\ xi _ {k} ^ {i} | \ xi _ {k-1} ^ {j})}$${\ displaystyle p (y_ {k-1} | x_ {k-1})}$${\ displaystyle p (x_ {k} | x_ {k-1})}$${\ displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ displaystyle x_ {k-1} = \ xi _ {k-1} ^ {j}.}$${\ displaystyle p ((x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}$${\ displaystyle f_ {k}}$

${\ displaystyle {\ begin {alinhados} \ int p (d (x_ {0}, \ cdots, x_ {n}) & | (y_ {0}, \ cdots, y_ {n-1})) f_ {k } (x_ {k}) \\ & \ approx _ {N \ uparrow \ infty} \ int {\ widehat {p}} _ {backward} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) f_ {k} (x_ {k}) \\ & = \ int {\ widehat {p}} (dx_ {n} | (y_ {0 }, \ cdots, y_ {n-1})) {\ widehat {p}} (dx_ {n-1} | x_ {n}, (y_ {0}, \ cdots, y_ {n-1})) \ cdots {\ widehat {p}} (dx_ {k} | x_ {k + 1}, (y_ {0}, \ cdots, y_ {k})) f_ {k} (x_ {k}) \\ & = \ underbrace {\ left [{\ tfrac {1} {N}}, \ cdots, {\ tfrac {1} {N}} \ right]} _ {N {\ text {times}}} \ mathbb {M } _ {n-1} \ cdots \ mathbb {M} _ {k} {\ begin {bmatrix} f_ {k} (\ xi _ {k} ^ {1}) \\\ vdots \\ f_ {k} (\ xi _ {k} ^ {N}) \ end {bmatrix}} \ end {alinhado}}}$

Onde

${\ displaystyle \ mathbb {M} _ {k} = (\ mathbb {M} _ {k} (i, j)) _ {1 \ leqslant i, j \ leqslant N}: \ qquad \ mathbb {M} _ {k} (i, j) = {\ frac {p (\ xi _ {k} ^ {i} | \ xi _ {k-1} ^ {j}) ~ p (y_ {k-1} | \ xi _ {k-1} ^ {j})} {\ sum \ limits _ {l = 1} ^ {N} p (\ xi _ {k} ^ {i} | \ xi _ {k-1} ^ {l}) p (y_ {k-1} | \ xi _ {k-1} ^ {l})}}}$

Isso também mostra que se

${\ displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ frac {1} {n + 1}} \ sum _ {k = 0} ^ {n} f_ {k} (x_ {k})}$

então

${\ displaystyle {\ begin {alinhados} \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) & \ approx _ {N \ uparrow \ infty} \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n} ) {\ widehat {p}} _ {backward} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) \\ & = {\ frac {1} {n + 1}} \ sum _ {k = 0} ^ {n} \ underbrace {\ left [{\ tfrac {1} {N}}, \ cdots, {\ tfrac {1} {N}} \ right]} _ {N {\ text {times}}} \ mathbb {M} _ {n-1} \ mathbb {M} _ {n-2} \ cdots \ mathbb {M} _ { k} {\ begin {bmatrix} f_ {k} (\ xi _ {k} ^ {1}) \\\ vdots \\ f_ {k} (\ xi _ {k} ^ {N}) \ end {bmatrix }} \ end {alinhado}}}$

Alguns resultados de convergência

Devemos supor que a equação de filtragem é estável, no sentido de que corrige qualquer condição inicial errônea.

Nesta situação, as aproximações de partículas das funções de verossimilhança são imparciais e a variância relativa é controlada por

${\ displaystyle E \ left ({\ widehat {p}} (y_ {0}, \ cdots, y_ {n}) \ right) = p (y_ {0}, \ cdots, y_ {n}), \ qquad E \ left (\ left [{\ frac {{\ widehat {p}} (y_ {0}, \ cdots, y_ {n})} {p (y_ {0}, \ cdots, y_ {n})} } -1 \ right] ^ {2} \ right) \ leqslant {\ frac {cn} {N}},}$

para alguma constante finita c . Além disso, para qualquer : ${\ displaystyle x \ geqslant 0}$

${\ displaystyle \ mathbf {P} \ left (\ left \ vert {\ frac {1} {n}} \ log {{\ widehat {p}} (y_ {0}, \ cdots, y_ {n})} - {\ frac {1} {n}} \ log {p (y_ {0}, \ cdots, y_ {n})} \ right \ vert \ leqslant c_ {1} {\ frac {x} {N}} + c_ {2} {\ sqrt {\ frac {x} {N}}} \ right)> 1-e ^ {- x}}$

para algumas constantes finitas relacionadas à tendência assintótica e variância da estimativa de partícula, e para alguma constante finita c . ${\ displaystyle c_ {1}, c_ {2}}$

O viés e a variância das estimativas de partículas de partículas com base nas linhas ancestrais das árvores genealógicas

${\ displaystyle {\ begin {alinhados} I_ {k} ^ {path} (F) &: = \ int F (x_ {0}, \ cdots, x_ {k}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ & \ approx _ {N \ uparrow \ infty} {\ widehat {I}} _ {k} ^ {caminho } (F) \\ &: = \ int F (x_ {0}, \ cdots, x_ {k}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ & = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left (\ xi _ {0 , k} ^ {i}, \ cdots, \ xi _ {k, k} ^ {i} \ right) \ end {alinhado}}}$

são controlados pelas estimativas uniformes não assintóticas

${\ displaystyle \ left | E \ left ({\ widehat {I}} _ {k} ^ {path} (F) \ right) -I_ {k} ^ {path} (F) \ right | \ leqslant {\ frac {c_ {1} k} {N}}, \ qquad E \ left (\ left [{\ widehat {I}} _ {k} ^ {path} (F) -I_ {k} ^ {path} ( F) \ right] ^ {2} \ right) \ leqslant {\ frac {c_ {2} k} {N}},}$

para qualquer função F limitada por 1, e para algumas constantes finitas Além disso, para qualquer : ${\ displaystyle c_ {1}, c_ {2}.}$${\ displaystyle x \ geqslant 0}$

${\ displaystyle \ mathbf {P} \ left (\ left | {\ widehat {I}} _ {k} ^ {path} (F) -I_ {k} ^ {path} (F) \ right | \ leqslant c_ {1} {\ frac {kx} {N}} + c_ {2} {\ sqrt {\ frac {kx} {N}}} \ land \ sup _ {0 \ leqslant k \ leqslant n} \ left | { \ widehat {I}} _ {k} ^ {path} (F) -I_ {k} ^ {path} (F) \ right | \ leqslant c {\ sqrt {\ frac {xn \ log (n)} { N}}} \ right)> 1-e ^ {- x}}$

para algumas constantes finitas relacionadas à tendência assintótica e variância da estimativa de partícula, e para alguma constante finita c . O mesmo tipo de estimativa de tendência e variância é válido para os suavizadores de partículas reversas. Para funcionais aditivos da forma ${\ displaystyle c_ {1}, c_ {2}}$

${\ displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ frac {1} {n + 1}} \ sum _ {0 \ leqslant k \ leqslant n} f_ {k} (x_ {k})}$

com

${\ displaystyle I_ {n} ^ {path} ({\ overline {F}}) \ approx _ {N \ uparrow \ infty} I_ {n} ^ {\ flat, path} ({\ overline {F}}) : = \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} _ {para trás} (d (x_ {0}, \ cdots, x_ {n }) | (y_ {0}, \ cdots, y_ {n-1}))}$

com funções limitadas por 1, temos ${\ displaystyle f_ {k}}$

${\ displaystyle \ sup _ {n \ geqslant 0} {\ left \ vert E \ left ({\ widehat {I}} _ {n} ^ {\ flat, path} ({\ overline {F}}) \ right ) -I_ {n} ^ {path} ({\ overline {F}}) \ right \ vert} \ leqslant {\ frac {c_ {1}} {N}}}$

e

${\ displaystyle E \ left (\ left [{\ widehat {I}} _ {n} ^ {\ flat, path} (F) -I_ {n} ^ {path} (F) \ right] ^ {2} \ direita) \ leqslant {\ frac {c_ {2}} {nN}} + {\ frac {c_ {3}} {N ^ {2}}}}$

para algumas constantes finitas Estimativas mais refinadas, incluindo probabilidade exponencialmente pequena de erros, são desenvolvidas em. ${\ displaystyle c_ {1}, c_ {2}, c_ {3}.}$

Reamostragem de Importância Sequencial (SIR)

Filtro Monte Carlo e filtro bootstrap

Reamostragem de importância sequencial (SIR) , filtragem de Monte Carlo (Kitagawa 1993) e o algoritmo de filtragem bootstrap (Gordon et al. 1993) também são algoritmos de filtragem comumente aplicados, que aproximam a densidade de probabilidade de filtragem por um conjunto ponderado de N amostras ${\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k})}$

${\ displaystyle \ left \ {\ left (w_ {k} ^ {(i)}, x_ {k} ^ {(i)} \ right) \: \ i \ in \ {1, \ cdots, N \} \direito\}.}$

Os pesos de importância são aproximações às probabilidades (ou densidades) posteriores relativas das amostras, de modo que ${\ displaystyle w_ {k} ^ {(i)}}$

${\ displaystyle \ sum _ {i = 1} ^ {N} w_ {k} ^ {(i)} = 1.}$

Amostragem de importância sequencial (SIS) é uma versão sequencial (isto é, recursiva) da amostragem de importância . Como na amostragem de importância, a expectativa de uma função f pode ser aproximada como uma média ponderada

${\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ dots, y_ {k}) dx_ {k} \ approx \ sum _ {i = 1} ^ {N} w_ {k} ^ {(i)} f (x_ {k} ^ {(i)}).}$

Para um conjunto finito de amostras, o desempenho do algoritmo depende da escolha da distribuição da proposta

${\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) \,}$.

A distribuição " ótima" da proposta é dada como a distribuição alvo

${\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}, y_ {k}) = {\ frac {p (y_ {k} | x_ {k})} {\ int p (y_ {k} | x_ {k}) p (x_ {k} | x_ {k-1}) dx_ {k}}} ~ p (x_ {k} | x_ {k-1}).}$

Esta escolha particular de transição proposta foi proposta por P. Del Moral em 1996 e 1998. Quando é difícil amostrar transições de acordo com a distribuição, uma estratégia natural é usar a seguinte aproximação de partícula ${\ displaystyle p (x_ {k} | x_ {k-1}, y_ {k})}$

${\ displaystyle {\ begin {alinhados} {\ frac {p (y_ {k} | x_ {k})} {\ int p (y_ {k} | x_ {k}) p (x_ {k} | x_ { k-1}) dx_ {k}}} p (x_ {k} | x_ {k-1}) dx_ {k} & \ simeq _ {N \ uparrow \ infty} {\ frac {p (y_ {k} | x_ {k})} {\ int p (y_ {k} | x_ {k}) {\ widehat {p}} (dx_ {k} | x_ {k-1})}} {\ widehat {p} } (dx_ {k} | x_ {k-1}) \\ & = \ sum _ {i = 1} ^ {N} {\ frac {p (y_ {k} | X_ {k} ^ {i} ( x_ {k-1}))} {\ sum _ {j = 1} ^ {N} p (y_ {k} | X_ {k} ^ {j} (x_ {k-1}))}} \ delta _ {X_ {k} ^ {i} (x_ {k-1})} (dx_ {k}) \ end {alinhado}}}$

com a aproximação empírica

${\ displaystyle {\ widehat {p}} (dx_ {k} | x_ {k-1}) = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ { X_ {k} ^ {i} (x_ {k-1})} (dx_ {k}) ~ \ simeq _ {N \ uparrow \ infty} p (x_ {k} | x_ {k-1}) dx_ { k}}$

associado a N (ou qualquer outro grande número de amostras) amostras aleatórias independentes com a distribuição condicional do estado aleatório dado . A consistência do filtro de partículas resultante desta aproximação e outras extensões são desenvolvidas em. Na exibição acima representa a medida de Dirac em um determinado estado a. ${\ displaystyle X_ {k} ^ {i} (x_ {k-1}), i = 1, \ cdots, N}$${\ displaystyle X_ {k}}$${\ displaystyle X_ {k-1} = x_ {k-1}}$${\ displaystyle \ delta _ {a}}$

No entanto, a distribuição de probabilidade anterior de transição é frequentemente usada como função de importância, uma vez que é mais fácil desenhar partículas (ou amostras) e realizar cálculos de peso de importância subsequentes:

${\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}).}$

Filtros de Reamostragem de Importância Sequencial (SIR) com distribuição de probabilidade de transição anterior como função de importância são comumente conhecidos como filtro de bootstrap e algoritmo de condensação .

A reamostragem é utilizada para evitar o problema de degenerescência do algoritmo, ou seja, evitar que todos os pesos de importância, exceto um, sejam próximos de zero. O desempenho do algoritmo também pode ser afetado pela escolha adequada do método de reamostragem. A amostragem estratificada proposta por Kitagawa (1993) é ótima em termos de variância.

Uma única etapa de reamostragem de importância sequencial é a seguinte:

1) Para tirar amostras da distribuição da proposta${\ displaystyle i = 1, \ cdots, N}$

${\ displaystyle x_ {k} ^ {(i)} \ sim \ pi (x_ {k} | x_ {0: k-1} ^ {(i)}, y_ {0: k})}$

2) Para atualizar os pesos de importância até uma constante de normalização: ${\ displaystyle i = 1, \ cdots, N}$

${\ displaystyle {\ hat {w}} _ {k} ^ {(i)} = w_ {k-1} ^ {(i)} {\ frac {p (y_ {k} | x_ {k} ^ { (i)}) p (x_ {k} ^ {(i)} | x_ {k-1} ^ {(i)})} {\ pi (x_ {k} ^ {(i)} | x_ {0 : k-1} ^ {(i)}, y_ {0: k})}}.}$

Observe que quando usamos a distribuição de probabilidade anterior de transição como a função de importância,

${\ displaystyle \ pi (x_ {k} ^ {(i)} | x_ {0: k-1} ^ {(i)}, y_ {0: k}) = p (x_ {k} ^ {(i )} | x_ {k-1} ^ {(i)}),}$

isso simplifica o seguinte:

${\ displaystyle {\ hat {w}} _ {k} ^ {(i)} = w_ {k-1} ^ {(i)} p (y_ {k} | x_ {k} ^ {(i)} ),}$

3) Para calcular os pesos de importância normalizados: ${\ displaystyle i = 1, \ cdots, N}$

${\ displaystyle w_ {k} ^ {(i)} = {\ frac {{\ hat {w}} _ {k} ^ {(i)}} {\ sum _ {j = 1} ^ {N} { \ hat {w}} _ {k} ^ {(j)}}}}$

4) Calcule uma estimativa do número efetivo de partículas como

${\ displaystyle {\ hat {N}} _ {\ mathit {eff}} = {\ frac {1} {\ sum _ {i = 1} ^ {N} \ left (w_ {k} ^ {(i) } \ right) ^ {2}}}}$

Este critério reflete a variância dos pesos, outros critérios podem ser encontrados no artigo, incluindo sua análise rigorosa e teoremas do limite central.

5) Se o número efetivo de partículas for inferior a um determinado limite , execute a reamostragem: ${\ displaystyle {\ hat {N}} _ {\ mathit {eff}} <N_ {thr}}$

a) Extraia N partículas do conjunto de partículas atual com probabilidades proporcionais aos seus pesos. Substitua o conjunto de partículas atual por este novo.

b) Para conjunto${\ displaystyle i = 1, \ cdots, N}$${\ displaystyle w_ {k} ^ {(i)} = 1 / N.}$

O termo "Reamostragem de Importância da Amostragem" também é algumas vezes usado quando se refere aos filtros SIR, mas o termo Reamostragem de Importância é mais preciso porque a palavra "reamostragem" implica que a amostragem inicial já foi feita.

Amostragem de importância sequencial (SIS)

• É o mesmo que reamostragem de importância sequencial, mas sem o estágio de reamostragem.

Algoritmo de "versão direta"

O algoritmo de "versão direta" é bastante simples (em comparação com outros algoritmos de filtragem de partículas) e usa composição e rejeição. Para gerar uma única amostra x em k a partir de : ${\ displaystyle p_ {x_ {k} | y_ {1: k}} (x | y_ {1: k})}$

1) Defina n = 0 (isso contará o número de partículas geradas até agora)

2) Escolha uniformemente um índice i da faixa${\ displaystyle \ {1, ..., N \}}$

3) Gere um teste da distribuição com${\ displaystyle {\ hat {x}}}$${\ displaystyle p (x_ {k} | x_ {k-1})}$${\ displaystyle x_ {k-1} = x_ {k-1 | k-1} ^ {(i)}}$

4) Gere a probabilidade de uso de onde está o valor medido${\ displaystyle {\ hat {y}}}$${\ displaystyle {\ hat {x}}}$${\ displaystyle p (y_ {k} | x_ {k}), ~ {\ mbox {com}} ~ x_ {k} = {\ hat {x}}}$${\ displaystyle y_ {k}}$

5) Gere outro u uniforme de onde${\ displaystyle [0, m_ {k}]}$${\ displaystyle m_ {k} = \ sup _ {x_ {k}} p (y_ {k} | x_ {k})}$

6) Compare u e ${\ displaystyle p \ left ({\ hat {y}} \ right)}$

6a) Se u for maior, repita a partir da etapa 2

6b) Se u for menor, salve como e incremente n${\ displaystyle {\ hat {x}}}$${\ displaystyle x_ {k | k} ^ {(i)}}$

7) Se n == N, então saia

O objetivo é gerar P "partículas" em k usando apenas as partículas de . Isso requer que uma equação de Markov possa ser escrita (e calculada) para gerar um baseado apenas em . Este algoritmo usa a composição das partículas P de para gerar uma partícula em k e repete (etapas 2–6) até que as partículas P sejam geradas em k . ${\ displaystyle k-1}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k-1}}$${\ displaystyle k-1}$

Isso pode ser mais facilmente visualizado se x for visto como uma matriz bidimensional. Uma dimensão é k e as outras dimensões é o número da partícula. Por exemplo, seria a ^iésima partícula em e também pode ser escrita (como feito acima no algoritmo). A etapa 3 gera um potencial baseado em uma partícula escolhida aleatoriamente ( ) no momento e rejeita ou aceita na etapa 6. Em outras palavras, os valores são gerados a partir do gerado anteriormente . ${\ displaystyle x (k, i)}$${\ displaystyle k}$${\ displaystyle x_ {k} ^ {(i)}}$ ${\ displaystyle x_ {k}}$${\ displaystyle x_ {k-1} ^ {(i)}}$${\ displaystyle k-1}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k-1}}$

Outros filtros de partículas

• Filtro Exponencial de Partículas Naturais
• Filtro de partícula auxiliar
• Filtro de partícula auxiliar regularizado
• Filtro de partícula gaussiana
• Filtro de partículas sem cheiro
• Filtro de partículas Gauss-Hermite
• Filtro de partículas de referência de custo
• Filtro de partículas hierárquico / escalonável
• Filtro de partículas Rao-Blackwell
• Filtro de partículas ideal baseado em amostragem de rejeição
• Filtro de partícula inclinado
• Metodologias de partículas de campo médio e Feynman-Kac
• Particle Markov-Chain Monte-Carlo, veja, por exemplo, o algoritmo pseudo-marginal Metropolis-Hastings .

Veja também

• Métodos de partículas de campo médio
• Algoritmo genético
• Filtro de conjunto Kalman
• Filtragem generalizada
• Estimativa de horizonte móvel
• Estimativa Bayesiana Recursiva
• Localização Monte Carlo

Referências

Bibliografia

• Del Moral, Pierre (1996). "Non Linear Filtering: Interacting Particle Solution" (PDF) . Processos de Markov e campos relacionados . 2 (4): 555–580.
• Del Moral, Pierre (2004). Fórmulas de Feynman-Kac. Aproximações genealógicas e de partículas interagentes . Springer. p. 575. "Série: Probabilidade e Aplicações"
• Del Moral, Pierre (2013). Simulação de campo médio para integração de Monte Carlo . Chapman & Hall / CRC Press. p. 626. "Monografias sobre Estatística e Probabilidade Aplicada"
• Cappe, O .; Moulines, E .; Ryden, T. (2005). Inferência em modelos ocultos de Markov . Springer.
• Liu, JS; Chen, R. (1998). "Métodos de Monte Carlo sequenciais para sistemas dinâmicos" (PDF) . Journal of the American Statistical Association . 93 (443): 1032–1044. doi : 10.1080 / 01621459.1998.10473765 .
• Liu, JS (2001). Estratégias de Monte Carlo em Computação Científica . Springer.
• Kong, A .; Liu, JS; Wong, WH (1994). "Imputações sequenciais e problemas de dados perdidos Bayesianos" (PDF) . Journal of the American Statistical Association . 89 (425): 278–288. doi : 10.1080 / 01621459.1994.10476469 .
• Liu, JS; Chen, R. (1995). "Desconvolução cega via imputações sequenciais" (PDF) . Journal of the American Statistical Association . 90 (430): 567–576. doi : 10.2307 / 2291068 . JSTOR  2291068 .
• Ristic, B .; Arulampalam, S .; Gordon, N. (2004). Além do filtro Kalman: Filtros de partículas para aplicativos de rastreamento . Artech House.
• Doucet, A .; Johansen, AM (dezembro de 2008). "Um tutorial sobre filtragem e suavização de partículas: quinze anos depois" (PDF) . Relatório Técnico .
• Doucet, A .; Godsill, S .; Andrieu, C. (2000). "Sobre métodos de amostragem sequencial de Monte Carlo para filtragem Bayesiana". Estatística e computação . 10 (3): 197–208. doi : 10.1023 / A: 1008935410038 . S2CID  16288401 .
• Arulampalam, MS; Maskell, S .; Gordon, N .; Clapp, T. (2002). "Um tutorial sobre filtros de partículas para rastreamento Bayesiano não linear / não gaussiano online". Transações IEEE no processamento de sinais . 50 (2): 174–188. Bibcode : 2002ITSP ... 50..174A . CiteSeerX  10.1.1.471.8617 . doi : 10.1109 / 78.978374 .
• Cappe, O .; Godsill, S .; Moulines, E. (2007). "Uma visão geral dos métodos existentes e avanços recentes em Monte Carlo sequencial". Atas do IEEE . 95 (5): 899–924. doi : 10.1109 / JPROC.2007.893250 . S2CID  3081664 .
• Kitagawa, G. (1996). "Filtro Monte carlo e mais suave para modelos de espaço de estado não lineares não gaussianos". Journal of Computational and Graphical Statistics . 5 (1): 1–25. doi : 10.2307 / 1390750 . JSTOR  1390750 .
• Kotecha, JH; Djuric, P. (2003). "Filtragem de partículas gaussianas". Transações IEEE no processamento de sinais . 51 (10).
• Haug, AJ (2005). "Um tutorial sobre estimativa bayesiana e técnicas de rastreamento aplicáveis ​​a processos não lineares e não gaussianos" (PDF) . The MITER Corporation, EUA, Tech. Rep., Fev . Página visitada em 06/05/2008 .
• Pitt, MK; Shephard, N. (1999). "Filtragem por simulação: Filtros de partículas auxiliares" . Journal of the American Statistical Association . 94 (446): 590–591. doi : 10.2307 / 2670179 . JSTOR  2670179 . Página visitada em 06/05/2008 .
• Gordon, NJ; Salmond, DJ; Smith, AFM (1993). "Nova abordagem para estimativa de estado bayesiano não linear / não gaussiano". IEE Proceedings F - Radar and Signal Processing . 140 (2): 107-113. doi : 10.1049 / ip-f-2.1993.0015 .
• Chen, Z. (2003). "Filtragem Bayesiana: Dos Filtros de Kalman aos Filtros de Partículas e Mais". CiteSeerX  10.1.1.107.7415 . Citar diário requer |journal=( ajuda )
• Vaswani, N .; Rathi, Y .; Yezzi, A .; Tannenbaum, A. (2007). "Rastreamento de objetos deformadores usando filtragem de partículas para contornos geométricos ativos" . IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (8): 1470–1475. doi : 10.1109 / tpami.2007.1081 . PMC  3663080 . PMID  17568149 .

links externos