Filtr cząstek - Particle filter

Filtry cząstek lub metody sekwencyjne Monte Carlo to zestaw algorytmów Monte Carlo używanych do rozwiązywania problemów filtrowania pojawiających się w przetwarzaniu sygnałów i wnioskowaniu statystycznym Bayesa . Filtrowania Problem polega szacowania stanów wewnętrznych systemach dynamicznych , gdy częściowe obserwacje wykonane i przypadkowe zaburzenia występują w czujnikach, a także w system dynamicznego. Celem jest obliczenie rozkładów a posteriori stanów pewnego procesu Markowa przy pewnych obserwacjach zaszumionych i cząstkowych. Termin „filtry cząstek” został po raz pierwszy ukuty w 1996 roku przez Del Morala w odniesieniu do metod oddziałujących na cząstki średniego pola stosowanych w mechanice płynów od początku lat sześćdziesiątych. Termin „Sekwencyjne Monte Carlo” został ukuty przez Liu i Chen w 1998 roku.

Filtrowanie cząstek wykorzystuje zestaw cząstek (zwanych również próbkami) do reprezentowania a posteriori rozkładu jakiegoś procesu stochastycznego przy zaszumionych i/lub częściowych obserwacjach. Model w przestrzeni stanów może być nieliniowy, a rozkłady stanu początkowego i szumu mogą przybierać dowolną wymaganą formę. Techniki filtrowania cząstek zapewniają ugruntowaną metodologię generowania próbek z wymaganej dystrybucji bez wymagania założeń dotyczących modelu przestrzeni stanów lub rozkładów stanów. Jednak metody te nie sprawdzają się dobrze, gdy są stosowane do systemów o bardzo dużych wymiarach.

Filtry cząstek aktualizują swoje przewidywania w sposób przybliżony (statystyczny). Próbki z rozkładu są reprezentowane przez zbiór cząstek; każda cząstka ma przypisaną wagę prawdopodobieństwa, która reprezentuje prawdopodobieństwo pobrania próbki tej cząstki z funkcji gęstości prawdopodobieństwa. Dysproporcja wagi prowadząca do spadku wagi jest częstym problemem napotykanym w tych algorytmach filtrowania; jednak można to złagodzić, włączając etap ponownego próbkowania, zanim wagi staną się zbyt nierówne. Można zastosować kilka adaptacyjnych kryteriów ponownego próbkowania, w tym wariancję wag i względną entropię w odniesieniu do rozkładu równomiernego. Na etapie ponownego próbkowania cząstki o znikomej masie są zastępowane nowymi cząstkami w pobliżu cząstek o większej masie.

Ze statystycznego i probabilistycznego punktu widzenia filtry cząstek można interpretować jako interpretacje cząstek średniego pola miar prawdopodobieństwa Feynmana-Kaca . Te techniki integracji cząstek zostały opracowane w chemii molekularnej i fizyce obliczeniowej przez Theodore'a E. Harrisa i Hermana Kahna w 1951 r., Marshalla N. Rosenblutha i Ariannę W. Rosenbluth w 1955 r., a ostatnio przez Jacka H. Hetheringtona w 1984 r. W fizyce obliczeniowej te techniki Metody integracji ścieżki cząstek typu Feynman-Kac są również stosowane w Quantum Monte Carlo , a dokładniej w metodach dyfuzyjnych Monte Carlo . Metody cząstek oddziałujących Feynmana-Kaca są również silnie powiązane z algorytmami genetycznymi selekcji mutacji, używanymi obecnie w obliczeniach ewolucyjnych do rozwiązywania złożonych problemów optymalizacji.

Metodologia filtra cząstek jest wykorzystywana do rozwiązywania problemów z ukrytym modelem Markowa (HMM) i nieliniowego filtrowania . Z godnym uwagi wyjątkiem modeli liniowej obserwacji sygnału Gaussa ( filtr Kalmana ) lub szerszych klas modeli (filtr Benesa) Mireille Chaleyat-Maurel i Dominique Michel udowodnili w 1984 roku, że sekwencja rozkładów a posteriori losowych stanów sygnału obserwacje (inaczej filtr optymalny) nie mają skończenie rekurencyjnej rekurencji. Różne inne metody numeryczne oparte na aproksymacjach siatek stałych, technikach Markowa Chain Monte Carlo , konwencjonalnej linearyzacji, rozbudowanych filtrach Kalmana , czy wyznaczaniu najlepszego systemu liniowego (w sensie oczekiwanego kosztu-błędu) nie radzą sobie z systemami o dużej skali, niestabilnymi procesami, lub gdy nieliniowości nie są wystarczająco gładkie.

Filtry cząstek i metodologie cząstek Feynman-Kac znajdują zastosowanie w przetwarzaniu sygnałów i obrazów , wnioskowaniu bayesowskim , uczeniu maszynowym , analizie ryzyka i próbkowaniu zdarzeń rzadkich , inżynierii i robotyce , sztucznej inteligencji , bioinformatyce , filogenetyce , informatyce , ekonomii i finansach matematycznych , chemii molekularnej , fizyka obliczeniowa , farmakokinetyka i inne dziedziny.

Historia

Algorytmy heurystyczne

Ze statystycznego i probabilistycznego punktu widzenia filtry cząstek należą do klasy algorytmów typu rozgałęziającego / genetycznego oraz metodologii cząstek oddziałujących typu średniego pola. Interpretacja tych metod cząstek zależy od dyscypliny naukowej. W Evolutionary Computing , uśrednione pole typu genetycznego cząstek metodologie są często stosowane jako heurystycznego naturalnych i algorytmy do wyszukiwania (czyli metaheurystyka ). W fizyce obliczeniowej i chemii molekularnej są one wykorzystywane do rozwiązywania problemów integracji ścieżek Feynmana-Kaca lub do obliczania miar Boltzmanna-Gibbsa, najwyższych wartości własnych i stanów podstawowych operatorów Schrödingera . W biologii i genetyce reprezentują one również ewolucję populacji osobników lub genów w pewnym środowisku.

Początki ewolucyjnych technik obliczeniowych typu średniego pola można prześledzić w latach 1950 i 1954 dzięki przełomowym pracom Alana Turinga na temat maszyn uczących selekcji mutacji typu genetycznego oraz artykułom Nilsa Aalla Barricelli w Institute for Advanced Study w Princeton, New Jersey . Pierwsze ślady filtrów cząstek stałych w metodologii statystycznej sięgają połowy lat pięćdziesiątych; „Monte Carlo biednego człowieka”, zaproponowane przez Hammersleya i in. w 1954 r., zawierało wskazówki dotyczące stosowanych dzisiaj metod filtrowania cząstek typu genetycznego. W 1963 Nils Aall Barricelli symulował algorytm typu genetycznego, aby naśladować zdolność osób do grania w prostą grę. W literaturze komputerowej ewolucyjne algorytmy selekcji mutacji typu genetycznego stały się popularne dzięki przełomowej pracy Johna Hollanda we wczesnych latach 70., a zwłaszcza jego książce opublikowanej w 1975 roku.

W Biology and Genetics australijski genetyk Alex Fraser opublikował również w 1957 serię artykułów na temat symulacji typu genetycznego sztucznej selekcji organizmów. Komputerowa symulacja ewolucji przez biologów stała się bardziej powszechna we wczesnych latach sześćdziesiątych, a metody zostały opisane w książkach Frasera i Burnella (1970) oraz Crosby'ego (1973). Symulacje Frasera obejmowały wszystkie istotne elementy nowoczesnych algorytmów cząstek genetycznych do selekcji mutacji.

Z matematycznego punktu widzenia warunkowy rozkład losowych stanów sygnału przy niektórych obserwacjach cząstkowych i zaszumionych jest opisany prawdopodobieństwem Feynmana-Kaca na losowych trajektoriach sygnału ważonych sekwencją funkcji potencjału wiarygodności. Metody kwantowego Monte Carlo , a dokładniej metody dyfuzyjnego Monte Carlo, mogą być również interpretowane jako przybliżenie cząstek typu średniego pola genetycznego całek ścieżki Feynmana-Kaca. Początki metod Quantum Monte Carlo są często przypisywane Enrico Fermi i Robertowi Richtmyerowi, którzy opracowali w 1948 roku interpretację cząstek średniego pola reakcji łańcuchów neutronów, ale pierwszy algorytm cząstek typu heurystycznego i genetycznego (znany również jako Resampled lub Reconfiguration Monte Carlo). metodami) do szacowania energii stanu podstawowego układów kwantowych (w modelach zredukowanych macierzy) opracował Jack H. Hetherington w 1984 roku. Można też zacytować wcześniejsze przełomowe prace Theodore'a E. Harrisa i Hermana Kahna z fizyki cząstek elementarnych, opublikowane w 1951 roku, przy użyciu metod genetycznych średniego pola, ale heurystycznych, do szacowania energii transmisji cząstek. W chemii molekularnej wykorzystanie genetycznych metodologii cząstek podobnych do heurystyki (inaczej strategii przycinania i wzbogacania) można prześledzić wstecz do 1955 r. dzięki przełomowej pracy Marshalla. N. Rosenblutha i Arianny. W. Rosenblutha.

Zastosowanie algorytmów cząstek genetycznych w zaawansowanym przetwarzaniu sygnałów i wnioskowaniu bayesowskim jest nowsze. W styczniu 1993 r. Genshiro Kitagawa opracował „filtr Monte Carlo”, nieco zmodyfikowaną wersję tego artykułu, która pojawiła się w 1996 r. W kwietniu 1993 r. Gordon i wsp. opublikowali w swojej przełomowej pracy zastosowanie algorytmu typu genetycznego w Bayesowskim wnioskowaniu statystycznym. Autorzy nazwali swój algorytm „filtrem ładowania początkowego” i wykazali, że w porównaniu z innymi metodami filtrowania, ich algorytm ładowania początkowego nie wymaga żadnych założeń dotyczących tej przestrzeni stanów ani szumu systemu. Niezależnie od tego, te autorstwa Pierre'a Del Morala i Himilcona Carvalho, Pierre'a Del Morala, André Monina i Gérarda Saluta o filtrach cząstek opublikowane w połowie lat dziewięćdziesiątych. Filtry cząstek zostały również opracowane w przetwarzaniu sygnałów na początku 1989-1992 przez P. Del Moral, JC Noyer, G. Rigal i G. Salut w LAAS-CNRS w serii zastrzeżonych i sklasyfikowanych raportów badawczych z STCAN (Technika Serwisowa des Constructions et Armes Navales), firma informatyczna DIGILOG oraz LAAS -CNRS (Laboratorium Analizy i Architektury Systemów) zajmujące się problemami przetwarzania sygnałów RADAR/SONAR i GPS.

Podstawy matematyczne

Od 1950 do 1996 roku wszystkie publikacje dotyczące filtrów cząstek, algorytmów genetycznych, w tym metody przycinania i resample Monte Carlo wprowadzone do fizyki obliczeniowej i chemii molekularnej, prezentują naturalne i heurystyczne algorytmy stosowane w różnych sytuacjach bez jednego dowodu ich spójności, ani dyskusji na temat stronniczości szacunków oraz algorytmów opartych na drzewach genealogicznych i przodków.

Podstawy matematyczne i pierwsza rygorystyczna analiza tych algorytmów cząstek zostały opracowane przez Pierre'a Del Morala w 1996 roku. Artykuł zawiera również dowód na nieobciążone właściwości przybliżeń cząstek funkcji wiarygodności i nieznormalizowanych miar prawdopodobieństwa warunkowego . Nieobciążony estymator cząstek funkcji wiarogodności przedstawiony w tym artykule jest obecnie używany we wnioskowaniu statystycznym bayesowskim.

Metodologie cząstek typu rozgałęzionego o różnej wielkości populacji zostały również opracowane pod koniec lat 90. przez Dan Crisan, Jessica Gaines i Terry Lyons oraz Dan Crisan, Pierre Del Moral i Terry Lyons. Dalsze osiągnięcia w tej dziedzinie zostały opracowane w 2000 r. przez P. Del Morala, A. Guionneta i L. Miclo. Pierwsze centralne twierdzenia graniczne pochodzą od Pierre'a Del Morala i Alice Guionnet w 1999 r. oraz Pierre'a Del Morala i Laurenta Miclo w 2000 r. Pierwsze jednorodne wyniki zbieżności w odniesieniu do parametru czasu dla filtrów cząstek zostały opracowane pod koniec lat 90. przez Pierre'a Del Moral i Alice Guionnet. Pierwsza rygorystyczna analiza wygładzaczy filtrów cząstek opartych na drzewie genealogicznym została przeprowadzona przez P. Del Morala i L. Miclo w 2001 r.

Teoria dotycząca metodologii cząstek Feynmana-Kaca i powiązanych algorytmów filtrów cząstek została opracowana w latach 2000 i 2004 w książkach. Te abstrakcyjne modele probabilistyczne zawierają algorytmy typu genetycznego, filtry cząstek i filtrów ładowania początkowego, współdziałające filtry Kalmana (inaczej filtr cząstek Rao-Blackwellized), techniki filtrowania cząstek w stylu ważności próbkowania i ponownego próbkowania, w tym metodologie oparte na drzewie genealogicznym i metodologii wstecznej cząstek do rozwiązywania problemów filtrowania i wygładzania. Inne klasy metodologii filtrowania cząstek obejmują modele oparte na drzewie genealogicznym, wsteczne modele cząstek Markowa, adaptacyjne modele cząstek średniego pola, modele cząstek typu wyspowego oraz metodologie Monte Carlo łańcuchów cząstek Markowa.

Problem z filtrowaniem

Cel

Celem filtra cząstek jest oszacowanie gęstości a posteriori zmiennych stanu przy danych zmiennych obserwacji. Filtr cząstek jest zaprojektowany dla ukrytego modelu Markowa , w którym system składa się zarówno ze zmiennych ukrytych, jak i obserwowalnych. Zmienne obserwowalne (proces obserwacji) są powiązane ze zmiennymi ukrytymi (proces stanu) przez pewną znaną formę funkcjonalną. Podobnie znany jest probabilistycznie układ dynamiczny opisujący ewolucję zmiennych stanu.

Ogólny filtr cząstek szacuje rozkład a posteriori stanów ukrytych przy użyciu procesu pomiaru obserwacji. Rozważ przestrzeń stanów pokazaną na poniższym diagramie.

${\ Displaystyle {\ zacząć {tablicę} {cccccccccc} X_ {0}& \ do & X_ {1}& \ do & X_ {2}& \ do & X_ {3}& \ do & \ cdots & {\ tekst {sygnał} }\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{obserwacja}}\end{ szyk}}}$

Problemem z filtrowaniem jest sekwencyjne oszacowanie wartości stanów ukrytych , biorąc pod uwagę wartości procesu obserwacji w dowolnym kroku czasowym k . ${\ Displaystyle X_ {k}}$${\displaystyle Y_{0},\cdots,Y_{k},}$

Wszystkie bayesowskie szacunki wynikają z gęstości a posteriori . Metodologia filtra cząstek zapewnia przybliżenie tych prawdopodobieństw warunkowych przy użyciu miary empirycznej związanej z algorytmem cząstek typu genetycznego. W przeciwieństwie do tego, metoda Monte Carlo z łańcuchem Markowa lub próbkowanie znaczenia pozwoliłoby modelować cały a posteriori . ${\ 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})}$

Model obserwacji sygnału

Metody cząstek często zakładają, a obserwacje można modelować w tej postaci: ${\ Displaystyle X_ {k}}$${\ Displaystyle Y_ {k}}$

• ${\displaystyle X_{0},X_{1},\cdots}$jest procesem Markowa na (dla niektórych ), który ewoluuje zgodnie z gęstością prawdopodobieństwa przejścia . Model ten jest również często pisany w sposób syntetyczny, jak ${\ 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})}$

z początkową gęstością prawdopodobieństwa .${\displaystyle p(x_{0})}$

• Obserwacje przyjmują wartości w pewnej przestrzeni stanów na (dla niektórych ) i są warunkowo niezależne pod warunkiem, że są znane. Innymi słowy, każdy zależy tylko od . Dodatkowo zakładamy, że rozkłady warunkowe dla danych są absolutnie ciągłe i w sposób syntetyczny mamy ${\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})}$

Przykładem systemu z tymi właściwościami jest:

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

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

gdzie oba i są wzajemnie niezależnymi sekwencjami o znanych funkcjach gęstości prawdopodobieństwa, a g i h są znanymi funkcjami. Te dwa równania mogą być postrzegane jako równania w przestrzeni stanów i wyglądają podobnie do równań w przestrzeni stanów dla filtru Kalmana. Jeśli funkcje g i h w powyższym przykładzie są liniowe, a jeśli obie i są Gaussian , filtr Kalmana znajduje dokładny rozkład filtrowania Bayesa. Jeśli nie, metody oparte na filtrze Kalmana są przybliżeniem pierwszego rzędu ( EKF ) lub przybliżeniem drugiego rzędu ( ogólnie UKF , ale jeśli rozkład prawdopodobieństwa jest Gaussa, możliwe jest przybliżenie trzeciego rzędu). ${\ Displaystyle W_ {k}}$${\ Displaystyle V_ {k}}$${\ Displaystyle W_ {k}}$${\ Displaystyle V_ {k}}$

Można rozluźnić założenie, że rozkład początkowy i przejścia łańcucha Markowa są absolutnie ciągłe względem miary Lebesgue'a. Aby zaprojektować filtr cząstek, musimy po prostu założyć, że możemy próbkować przejścia łańcucha Markowa i obliczyć funkcję prawdopodobieństwa (patrz na przykład opis mutacji selekcji genetycznej filtra cząstek podany poniżej). Absolutnie ciągłe założenie o przejściach Markowa jest używane tylko do wyprowadzania w nieformalny (i raczej obraźliwy) sposób różnych wzorów między rozkładami a posteriori przy użyciu reguły Bayesa dla warunkowych gęstości. ${\ Displaystyle X_ {k-1} \ do X_ {k}}$${\ Displaystyle X_ {k},}$${\ Displaystyle x_ {k} \ mapsto p (y_ {k} | x_ {k})}$${\ Displaystyle X_ {k}}$

Przybliżone bayesowskie modele obliczeniowe

W niektórych problemach warunkowy rozkład obserwacji ze względu na losowe stany sygnału może nie mieć gęstości lub może być niemożliwy lub zbyt złożony do obliczenia. W tej sytuacji musimy uciec się do dodatkowego poziomu zbliżenia. Jedną ze strategii jest zastąpienie sygnału łańcuchem Markowa i wprowadzenie wirtualnej obserwacji formy ${\ Displaystyle X_ {k}}$${\ Displaystyle {\ mathcal {X}} _ {k} = \ lewo (X_ {k}, Y_ {k} \ po prawej)}$

${\ Displaystyle {\ mathcal {Y}} _ {k} = Y_ {k} + \ epsilon {\ mathcal {V}} _ {k} \ quad {\ mbox {dla jakiegoś parametru}} \ quad \ epsilon \ w [0,1]}$

dla pewnego ciągu niezależnych ciągów o znanych funkcjach gęstości prawdopodobieństwa . Główną ideą jest obserwowanie tego

${\ Displaystyle {\ tekst {prawo}} \ lewo (X_ {k} | {\ mathcal {Y}} _ {0}= Y_ {0}, \ cdots, {\ mathcal {Y}} _ {k} = y_{k}\right)\ok _{\epsilon \downarrow 0}{\text{Prawo}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}= y_{k}\prawo)}$

Filtr cząstek związany z procesem Markowa, biorąc pod uwagę obserwacje cząstkowe, jest zdefiniowany w kategoriach cząstek ewoluujących z funkcją wiarygodności podaną z pewnym oczywistym nadużyciem przez . Te probabilistyczne techniki są ściśle związane z przybliżonym obliczeniem bayesowskim (ABC). W kontekście filtrów cząstek, te techniki filtrowania cząstek ABC zostały wprowadzone w 1998 r. przez P. Del Moral, J. Jacod i P. Protter. Zostały one rozwinięte przez P. Del Morala, A. Douceta i A. Jasrę. ${\ Displaystyle {\ mathcal {X}} _ {k} = \ lewo (X_ {k}, Y_ {k} \ po prawej)}$${\ 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})}$

Nieliniowe równanie filtrowania

Reguła Bayesa dla prawdopodobieństwa warunkowego daje:

${\ 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})}}}$

gdzie

${\ Displaystyle {\ zacząć {wyrównany} p (y_ {0}, \ cdots, y_ {k}) i = \ 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{wyrównany}}}$

Filtry cząstek są również przybliżeniem, ale przy wystarczającej liczbie cząstek mogą być znacznie dokładniejsze. Nieliniowe równanie filtrowania jest podane przez rekursję

${\ Displaystyle {\ zacząć {wyrównany} p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) i {\ stos {\ tekst {aktualizacja}} {\ 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{prediction}}{\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{wyrównany}}}$

(Równanie 1)

z konwencją dla k = 0. Problem filtrowania nieliniowego polega na sekwencyjnym obliczaniu tych rozkładów warunkowych. ${\ Displaystyle p (x_ {0}| y_ {0}, \ cdots, y_ {k-1}) = p (x_ {0})}$

Formuła Feynmana-Kaca

Ustalamy horyzont czasowy n i ciąg obserwacji , a dla każdego k = 0, ..., n ustalamy: ${\ Displaystyle Y_ {0}= Y_ {0}, \ cdots, Y_ {n} = Y_ {n}}$

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

W tym zapisie, dla dowolnej ograniczonej funkcji F na zbiorze trajektorii od początku k = 0 do czasu k = n , mamy wzór Feynmana-Kaca ${\ Displaystyle X_ {k}}$

${\ Displaystyle {\ zacząć {wyrównany} \ 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})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}} \end{wyrównany}}}$

Te modele integracji ścieżek Feynmana-Kaca powstają w różnych dyscyplinach naukowych, w tym w fizyce obliczeniowej, biologii, teorii informacji i informatyce. Ich interpretacje zależą od dziedziny aplikacji. Na przykład, jeśli wybierzemy funkcję wskaźnika pewnego podzbioru przestrzeni stanów, reprezentują one warunkowy rozkład łańcucha Markowa, biorąc pod uwagę, że pozostaje on w danej rurze; czyli mamy: ${\ Displaystyle G_ {n} (x_ {n}) = 1 _ {A} (x_ {n})}$

${\ Displaystyle E \ lewo (F (X_ {0}, \ cdots, X_ {n}) | X_ {0} \ w A \ cdots, X_ {n} \ w A \ po prawej) = {\ 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)}}}$

i

${\ Displaystyle P \ lewo (X_ {0} \ w A \ cdots, X_ {n} \ w A \ po prawej) = E \ lewo (\ prod \ limity _ {k = 0} ^ {n} G_ {k }(X_{k})\prawo)}$

gdy tylko stała normalizująca jest ściśle dodatnia.

Filtry cząstek

Algorytm cząstek typu genetycznego

Początkowo zaczynamy od N niezależnych zmiennych losowych o wspólnej gęstości prawdopodobieństwa . Algorytm genetyczny przejścia selekcja-mutacja ${\ Displaystyle \ lewo (\ X _ {0} ^ {i} \ po prawej) _ {1 \ leqslant i \ leqslant N}}$${\displaystyle p(x_{0})}$

${\ Displaystyle \ xi _ {k}: = \ lewo (\ xi _ {k} ^ {i} \ prawej) _ {1 \ leqslant i \ leqslant N} {\ stackrel {\ tekst {wybór}} {\ 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 }}$

naśladować/przybliżyć przejścia aktualizacja-predykcja optymalnej ewolucji filtra ( Równanie 1 ):

• Podczas przejścia selekcji uaktualniający że próbka N (warunkowo) niezależnymi zmiennymi losowymi ze wspólnym (warunkowych) rozkład${\ Displaystyle {\ widehat {\ xi }} _ {k}: = \ lewo ({\ widehat {\ xi }} _ {k} ^ {i} \ prawej) _ {1 \ leqslant i \ leqslant N}}$

${\ Displaystyle \ suma _ {i = 1} ^ {N} {\ Frac {p (y_ {k} | \ xi _ {k} ^ {i})} {\ suma _ {j = 1} ^ {N }p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

gdzie oznacza miarę Diraca w danym stanie a. ${\ Displaystyle \ delta _ {a}}$

• Podczas przejścia mutacja-przewidywanie, z każdej wybranej cząstki pobieramy niezależnie przejście${\ 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.}$

W przedstawionych powyżej wzorach oznacza funkcję prawdopodobieństwa oszacowaną na , a oznacza gęstość warunkową oszacowaną na . ${\ 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}}$

Za każdym razem k mamy przybliżenia cząstek

${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k}): = {\ Frac {1} {N}} \ suma _ {i = 1} ^ {N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\około _{N\uparrow \infty }p(dx_{k}|y_{0 },\cdots ,y_{k})\około _{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}^{ ja}}(dx_{k})}$

i

${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ Frac {1} {N}} \ suma _ {i = 1 }^{N}\delta _{\xi _{k}^{i}}(dx_{k})\około _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

W algorytmach genetycznych i społeczności komputerów ewolucyjnych , opisany powyżej łańcuch Markowa selekcji mutacji jest często nazywany algorytmem genetycznym z selekcją proporcjonalną. W artykułach zaproponowano również kilka wariantów rozgałęzień, w tym z losową liczebnością populacji.

Zasady Monte Carlo

Metody cząsteczkowe, podobnie jak wszystkie podejścia oparte na próbkowaniu (np. Markov Chain Monte Carlo), generują zestaw próbek, który przybliża gęstość filtrowania

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

Na przykład możemy mieć N próbek z przybliżonego rozkładu a posteriori , gdzie próbki są oznaczone indeksami górnymi jako ${\ Displaystyle X_ {k}}$

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

Następnie oczekiwania względem rozkładu filtrowania są aproksymowane przez

${\ Displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ cdots, y_ {k}) \, dx_ {k} \ około _ {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})}$

(Równanie 2)

z

${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ Frac {1} {N}} \ suma _ {i = 1} ^ { N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

gdzie oznacza miarę Diraca w danym stanie a. Funkcja f , w zwykły sposób dla Monte Carlo, może podać wszystkie momenty itp. rozkładu aż do pewnego błędu aproksymacji. Gdy równanie aproksymacyjne ( równanie 2 ) jest spełnione dla dowolnej ograniczonej funkcji f piszemy ${\ Displaystyle \ delta _ {a}}$

${\ Displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k}): = p (x_ {k} | y_ {0}, \ cdots, y_ {k}) dx_ {k} \ około _{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})}$

Filtry cząstek mogą być interpretowane jako algorytm cząstek typu genetycznego ewoluujący wraz z przejściami mutacji i selekcji. Możemy śledzić linie przodków

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

cząstek . Stany losowe o niższych wskaźnikach l=0,...,k oznaczają przodka osobnika na poziomie l=0,...,k. W tej sytuacji mamy do czynienia z formułą aproksymacyjną ${\displaystyle i=1,\cdots,N}$${\ Displaystyle {\ widehat {\ xi}} _ {l, k} ^ {i}}$${\ Displaystyle {\ widehat {\ xi }} _ {k, k} ^ {i} = {\ widehat {\ xi}} _ {k} ^ {i}}$

${\ Displaystyle {\ zacząć {wyrównany} \ int F (x_ {0}, \ cdots, x_ {k}) p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k})\,dx_{0}\cdots dx_{k}&\około _{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{aligned}}}$

(Równanie 3)

z miarą empiryczną

${\ 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}) )}$

Tutaj F oznacza każdą założoną funkcję w przestrzeni ścieżki sygnału. W bardziej syntetycznej formie ( równanie 3 ) jest równoważne

${\ Displaystyle {\ zacząć {wyrównany} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) i: = p (x_ {0}, \cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\ok _{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{aligned}}}$

Filtry cząstek można interpretować na wiele różnych sposobów. Z probabilistycznego punktu widzenia pokrywają się one z interpretacją cząstek o średnim polu nieliniowego równania filtrowania. Przejścia aktualizacja-przewidywanie optymalnej ewolucji filtra mogą być również interpretowane jako klasyczne przejścia selekcja-mutacja typu genetycznego osobników. Technika ponownego próbkowania o ważności sekwencyjnej zapewnia inną interpretację przejść filtrowania łączących próbkowanie ważności z etapem ponownego próbkowania z ładowaniem początkowym. Wreszcie, co nie mniej ważne, filtry cząstek mogą być postrzegane jako metodologia akceptacji i odrzucenia wyposażona w mechanizm recyklingu.

Symulacja cząstek średniego pola

Ogólna zasada probabilistyczna

Ewolucję filtrowania nieliniowego można interpretować jako układ dynamiczny w zbiorze miar prawdopodobieństwa o następującej postaci, gdzie oznacza pewne odwzorowanie ze zbioru rozkładu prawdopodobieństwa na siebie. Na przykład ewolucja jednostopniowego optymalnego predyktora${\ Displaystyle \ eta _ {n + 1} = \ Phi _ {n + 1} \ lewo (\ eta _ {n} \ po prawej)}$${\ Displaystyle \ Phi _ {n + 1}}$${\ Displaystyle \ eta _ {n} (dx_ {n}) = p (x_ {n} | y_ {0}, \ cdots, y_ {n-1}) dx_ {n}}$

spełnia nieliniową ewolucję rozpoczynającą się od rozkładu prawdopodobieństwa . Jednym z najprostszych sposobów przybliżenia tych miar prawdopodobieństwa jest rozpoczęcie od N niezależnych zmiennych losowych o wspólnym rozkładzie prawdopodobieństwa . Załóżmy, że zdefiniowaliśmy sekwencję N zmiennych losowych taką, że ${\ Displaystyle \ eta _ {0} (dx_ {0}) = p (x_ {0}) dx_ {0}}$${\ Displaystyle \ lewo (\ X _ {0} ^ {i} \ po prawej) _ {1 \ leqslant i \ leqslant N}}$${\ Displaystyle \ eta _ {0} (dx_ {0}) = p (x_ {0}) dx_ {0}}$${\ Displaystyle \ lewo (\ X _ {n} ^ {i} \ po prawej) _ {1 \ leqslant i \ leqslant N}}$

${\ Displaystyle {\ Frac {1} {N}} \ suma _ {i = 1} ^ {N} \ delta _ {\ X _ {n} ^ {i}} (dx_ {n}) \ około _ { N\uparrow \infty }\eta _{n}(dx_{n})}$

W kolejnym kroku próbkujemy N (warunkowo) niezależnych zmiennych losowych za pomocą common law . ${\ Displaystyle \ xi _ {n + 1}: = \ lewo (\ xi _ {n + 1} ^ {i} \ prawo) _ {1 \ leqslant i \ leqslant N}}$

${\ Displaystyle \ Phi _ {n + 1} \ lewo ({\ Frac {1} {N}} \ suma _ {i = 1} ^ {N} \ delta _ {\ xi _ {n} ^ {i} }\right)\ok _{N\uparrow \infty }\Phi _{n+1}\left(\eta _{n}\right)=\eta _{n+1}}$

Interpretacja cząstek równania filtrowania

Ilustrujemy tę zasadę cząstki średniego pola w kontekście ewolucji jednostopniowych optymalnych predyktorów

${\ Displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k} \ do 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}}}}$

(Równanie 4)

Dla k = 0 używamy konwencji . ${\ Displaystyle p (x_ {0}| y_ {0}, \ cdots, y_ {-1}): = p (x_ {0})}$

Zgodnie z prawem wielkich liczb mamy

${\ Displaystyle {\ widehat {p}} (dx_ {0}) = {\ Frac {1} {N}} \ suma _ {i = 1} ^ {N} \ delta _ {\ X _ {0} ^ {i}}(dx_{0})\ok _{N\uparrow \infty }p(x_{0})dx_{0}}$

w tym sensie, że

${\ Displaystyle \ int f (x_ {0}) {\ widehat {p}} (dx_ {0}) = {\ Frac {1} {N}} \ suma _ {i = 1} ^ {N} f ( \xi _{0}^{i})\około _{N\uparrow \infty }\int f(x_{0})p(dx_{0})dx_{0}}$

dla dowolnej funkcji ograniczonej . Dalej zakładamy, że skonstruowaliśmy sekwencję cząstek o pewnej randze k, taką, że ${\displaystyle f}$${\ Displaystyle \ lewo (\ xi _ {k} ^ {i} \ po prawej) _ {1 \ leqslant ja \ leqslant N}}$

${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ Frac {1} {N}} \ suma _ {i = 1 }^{N}\delta _{\xi _{k}^{i}}(dx_{k})\ok _{N\uparrow \infty }~p(x_{k}~|~y_{0} ,\cdots ,y_{k-1})dx_{k}}$

w tym sensie, że dla dowolnej funkcji ograniczonej mamy ${\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})\około _{N\uparrow \infty }\int f(x_{k})p(dx_{k }|y_{0},\cdots ,y_{k-1})dx_{k}}$

W tej sytuacji, zastąpienie przez środek empirycznych w równaniu ewolucji optymalnego filtru jednoetapowy podanej w ( równ. 4 ) znajdujemy, że ${\ 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}) \ ok _ {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}) }}}$

Zauważ, że prawa strona powyższego wzoru to ważona mieszanina prawdopodobieństwa

${\ 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})}}=\suma _{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})}$

gdzie oznacza gęstość ocenianej na , i oznacza gęstość ocenianego na za${\ Displaystyle p (y_ {k} | \ xi _ {k} ^ {i})}$${\ Displaystyle p (y_ {k} | x_ {k})}$${\ Displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\ Displaystyle p (x_ {k + 1} | \ x _ {k} ^ {i})}$${\ Displaystyle p (x_ {k + 1} | x_ {k})}$${\ Displaystyle x_ {k} = \ xi _ {k} ^ {i}}$${\displaystyle i=1,\cdots, n.}$

Następnie próbkujemy N niezależnej zmiennej losowej o wspólnej gęstości prawdopodobieństwa tak, że ${\ Displaystyle \ lewo (\ xi _ {k + 1} ^ {i} \ po prawej) _ {1 \ leqslant ja \ 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}} \ suma _ {i = 1 }^{N}\delta _{\xi _{k+1}^{i}}(dx_{k+1})\ok _{N\uparrow \infty }{\widehat {q}}(x_{ k+1}|y_{0},\cdots ,y_{k})dx_{k+1}\ok _{N\uparrow \infty }p(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}}$

Powtarzając tę ​​procedurę, projektujemy łańcuch Markowa taki, że

${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1}): = {\ Frac {1} {N}} \ suma _ {i = 1 }^{N}\delta _{\xi _{k}^{i}}(dx_{k})\około _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1}):=p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

Zauważ, że optymalny filtr jest aproksymowany w każdym kroku czasowym k przy użyciu formuł Bayesa

${\ Displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k}) \ około _ {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})}$

Terminologia „aproksymacja pola średniego” wynika z tego, że w każdym kroku zastępujemy miarę prawdopodobieństwa przybliżeniem empirycznym . Aproksymacja problemu filtrowania cząstek średniego pola nie jest unikatowa. W książkach opracowano kilka strategii. ${\ Displaystyle p (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$${\ Displaystyle {\ widehat {p}} (dx_ {k} | y_ {0}, \ cdots, y_ {k-1})}$

Niektóre wyniki konwergencji

Analizę zbieżności filtrów cząstek stałych rozpoczęto w 1996 i 2000 roku w książce i serii artykułów. Nowsze osiągnięcia można znaleźć w książkach: Gdy równanie filtrowania jest stabilne (w tym sensie, że koryguje wszelkie błędne warunki początkowe), obciążenie i wariancja szacunków cząstek

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

są kontrolowane przez nieasymptotyczne jednolite oszacowania

${\ Displaystyle \ sup _ {k \ geqslant 0} \ lewo \ vert E \ lewo ({\ widehat {ja}} _ {k} (f) \ po prawej) -I_ {k} (f) \ po prawej \ vert \ odpowiednik {\frac {c_{1}}{N}}}$

${\ Displaystyle \ sup _ {k \ geqslant 0} E \ lewo (\ lewo [{\ widehat {ja}} _ {k} (f) -I_ {k} (f) \ prawej] ^ {2} \ prawej )\leqslant {\frac {c_{2}}{N}}}$

dla dowolnej funkcji f ograniczonej przez 1 i dla niektórych stałych skończonych Dodatkowo dla dowolnych : ${\displaystyle c_{1},c_{2}.}$${\displaystyle x\geqslant 0}$

${\ Displaystyle \ mathbf {P} \ lewo (\ lewo | {\ widehat {ja}} _ {k} (f)-I_ {k} (f) \ prawo | \ 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} }$

dla pewnych skończonych stałych związanych z asymptotycznym obciążeniem i wariancją oszacowania cząstki oraz dla pewnej skończonej stałej c . Te same wyniki są spełnione, jeśli zastąpimy jednostopniowy optymalny predyktor optymalnym przybliżeniem filtra. ${\displaystyle c_{1},c_{2}}$

Drzewa genealogiczne i własności bezstronności

Wygładzanie cząstek oparte na drzewie genealogicznym

Cofanie się w czasie linii przodków

${\ Displaystyle \ lewo ({\ 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) }$

indywiduów i w każdym kroku k , mamy również przybliżenia cząstek ${\ Displaystyle {\ widehat {\ xi}} _ {k} ^ {i} \ lewo (= {\ widehat {\ xi}} _ {k, k} ^ {i} \ prawej)}$${\ Displaystyle \ xi _ {k} ^ {i} \ lewo (= {\ xi} _ {k, k} ^ {i} \ prawej)}$

${\ Displaystyle {\ zacząć {wyrównany} {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) i: = { \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}))\\&\ok _{N\uparrow \ infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\ok _{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})) \\&\ok _{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{aligned}}}$

Te przybliżenia empiryczne są równoważne przybliżeniom całki cząstkowej

${\ Displaystyle {\ zacząć {wyrównany} \ 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)\\&\ok _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\ około _{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\lewo(\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)\\&\ok _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1} )\end{wyrównany}}}$

dla dowolnej ograniczonej funkcji F na losowych trajektoriach sygnału. Jak pokazano w ewolucji drzewa genealogicznego zbiega się z interpretacją cząstek średniego pola równań ewolucji związanych z gęstościami tylnymi trajektorii sygnału. Więcej szczegółów na temat tych modeli przestrzeni ścieżek można znaleźć w książkach.

Nieobciążone szacunki cząstek funkcji wiarygodności

Używamy formuły produktu

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

z

${\ 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})}$

i konwencje i dla k = 0. Wymiana przez empiryczne zbliżania ${\ 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}} \ suma _ {i = 1 }^{N}\delta _{\xi _{k}^{i}}(dx_{k})\około _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

w przedstawionym powyżej wzorze projektujemy następujące przybliżenie nieobciążonej cząstki funkcji wiarogodności

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

z

${\ 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})}$

gdzie oznacza gęstość ocenianą w . Projekt oszacowania tej cząstki i własność bezstronności został udowodniony w 1996 roku w artykule. Dopracowane szacunki wariancji można znaleźć w i. ${\ Displaystyle p (y_ {k} | \ xi _ {k} ^ {i})}$${\ Displaystyle p (y_ {k} | x_ {k})}$${\ Displaystyle x_ {k} = \ xi _ {k} ^ {i}}$

Wygładzacze cząstek do tyłu

Korzystając z reguły Bayesa, mamy wzór

${\ 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})}$

Zauważ, że

${\ Displaystyle {\ zacząć {wyrównany} p (x_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) i \ 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{wyrównany}}}$

To daje do zrozumienia ze

${\ 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}}}}$

Zastąpienie jednostopniowych optymalnych predyktorów miarami empirycznymi cząstek${\ 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}} \ suma _ { i=1}^{N}\delta _{\xi _{k-1}^{i}}(dx_{k-1})\left(\około _{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}\prawo)}$

znaleźliśmy to

${\ Displaystyle {\ zacząć {wyrównany} p (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1}})) i \ około _ {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{wyrównany}}}$

Dochodzimy do wniosku, że

${\ Displaystyle p (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) \ około _ {N \ uparrow \ infty} {\ widehat {p}}_{wstecz}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))}$

z przybliżeniem cząstki wstecznej

${\ Displaystyle {\ zacząć {wyrównany} {\ widehat {p}} _ {do tyłu} (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{wyrównany}}}$

Miara prawdopodobieństwa

${\ Displaystyle {\ widehat {p}} _ {do tyłu} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}$

jest prawdopodobieństwem, że losowe ścieżki łańcucha Markowa biegną wstecz w czasie od czasu k=n do czasu k=0 i ewoluują w każdym kroku czasowym k w przestrzeni stanów związanej z populacją cząstek${\ Displaystyle \ lewo (\ mathbb {X} _ {k, n} ^ {\ płaskie} \ prawej) _ {0 \ leqslant k \ leqslant n}}$${\ Displaystyle \ xi _ {k} ^ {i}, i = 1 \ cdots, N.}$

• Początkowo (w czasie k=n) łańcuch wybiera losowo stan o rozkładzie${\ Displaystyle \ mathbb {X} _ {n, n} ^ {\ mieszkanie}}$

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

• Od czasu k do czasu (k-1), łańcuch rozpoczynający się w pewnym stanie przez jakiś czas w czasie k przemieszcza się w czasie (k-1) do losowego stanu wybranego z dyskretnym prawdopodobieństwem ważonym${\ Displaystyle \ mathbb {X} _ {k, n} ^ {\ płaskie} = \ X _ {k} ^ {i}}$${\displaystyle i=1,\cdots,N}$${\ Displaystyle \ mathbb {X} _ {k-1, n} ^ {\ mieszkanie}}$

${\ Displaystyle {\ widehat {p}} (dx_ {k-1} | \ xi _ {k} ^ {i}, (y_ {0}, \ cdots, y_ {k-1})) = \ suma _ {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} )}$

W powyższym wzorze oznacza rozkład warunkowy oceniany na . W tym samym duchu i reprezentują gęstości warunkowe i oceniane w i Modele te pozwalają na zmniejszenie integracji w odniesieniu do gęstości w zakresie operacji macierzowych w odniesieniu do przejść Markowa w łańcuchu opisanym powyżej. Na przykład dla dowolnej funkcji mamy oszacowania cząstek ${\ 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} | \ x _ {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 {\ zacząć {wyrównany} \ int p (d (x_ {0}, \ cdots, x_ {n}) i | (y_ {0}, \ cdots, y_ {n-1})) f_ {k }(x_{k})\\&\ok _{N\uparrow \infty }\int {\widehat {p}}_{wstecz}(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{ razy}}}\mathbb {M } _{n-1}\cdots \mathbb {M} _{k}{\begin{bmatrix}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k} (\xi _{k}^{N})\end{bmatryca}}\end{wyrównany}}}$

gdzie

${\ Displaystyle \ mathbb {M} _ {k} = (\ mathbb {M} _ {k} (i, j)) _ {1 \ leqslant ja, 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})}}}$

Pokazuje to również, że jeśli

${\ Displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ Frac {1} {n + 1}} \ suma _ {k = 0} ^ {n} f_{k}(x_{k})}$

następnie

${\ Displaystyle {\ zacząć {wyrównany} \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {n}) | (y_{0},\cdots ,y_{n-1}))&\ok _{N\uparrow \infty }\int {\overline {F}}(x_{0},\cdots ,x_{n} ){\widehat {p}}_{wstecz}(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{ razy}}}\mathbb {M} _{n-1}\mathbb {M} _{n-2}\cdots \mathbb {M} _{ k}{\begin{bmacierz}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k}(\xi _{k}^{N})\end{bmacierz }}\end{wyrównany}}}$

Niektóre wyniki konwergencji

Przyjmiemy, że równanie filtrowania jest stabilne, w tym sensie, że koryguje wszelkie błędne warunki początkowe.

W tej sytuacji przybliżenia cząstek funkcji wiarygodności są nieobciążone, a względna wariancja jest kontrolowana przez

${\ Displaystyle E \ lewo ({\ widehat {p}} (y_ {0}, \ cdots, y_ {n}) \ prawej) = 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}},}$

dla pewnej skończonej stałej c . Ponadto dla każdego : ${\displaystyle x\geqslant 0}$

${\ Displaystyle \ mathbf {P} \ lewo (\ lewo \ 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}}$

dla pewnych stałych skończonych związanych z asymptotycznym obciążeniem i wariancją oszacowania cząstki oraz dla pewnej skończonej stałej c . ${\displaystyle c_{1},c_{2}}$

Stronniczość i wariancja szacunków cząstek cząstek na podstawie linii przodków drzew genealogicznych

${\ Displaystyle {\ zacząć {wyrównany} I_ {k} ^ {ścieżka} (F) i: = \ int F (x_ {0}, \ cdots, x_ {k}) p (d (x_ {0}, \) cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&\ok _{N\uparrow \infty }{\widehat {I}}_{k}^{ścieżka }(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{wyrównany}}}$

są kontrolowane przez nieasymptotyczne jednolite oszacowania

${\ Displaystyle \ lewo | e \ lewo ({\ widehat {ja}} _ {k} ^ {ścieżka} (f) \ prawo) - ja_ {k} ^ {ścieżka} (f) \ prawo | \ leqslant {\ szczelina {c_{1}k}{N}},\qquad E\left(\left[{\widehat {I}}_{k}^{ścieżka}(F)-I_{k}^{ścieżka}( F)\right]^{2}\right)\leqslant {\frac {c_{2}k}{N}},}$

dla dowolnej funkcji F ograniczonej przez 1 i dla niektórych stałych skończonych Dodatkowo dla dowolnych : ${\displaystyle c_{1},c_{2}.}$${\displaystyle x\geqslant 0}$

${\ Displaystyle \ mathbf {P} \ lewo (\ lewo | {\ widehat {ja}} _ {k} ^ {ścieżka} (F) -I_ {k} ^ {ścieżka} (F) \ prawo | \ Leqslant c_ {1}{\frac {kx}{N}}+c_{2}{\sqrt {\frac {kx}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{ \widehat {I}}_{k}^{ścieżka}(F)-I_{k}^{ścieżka}(F)\right|\leqslant c{\sqrt {\frac {xn\log(n)}{ N}}}\right)>1-e^{-x}}$

dla pewnych stałych skończonych związanych z asymptotycznym obciążeniem i wariancją oszacowania cząstki oraz dla pewnej skończonej stałej c . Ten sam rodzaj oszacowań odchylenia i wariancji dotyczy wygładzaczy cząstek wstecznych. Dla funkcjonałów addytywnych postaci ${\displaystyle c_{1},c_{2}}$

${\ Displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ Frac {1} {n + 1}} \ suma _ {0 \ leqslant k \ leqslant n} f_{k}(x_{k})}$

z

${\ Displaystyle I_ {n} ^ {ścieżka} ({\ nadkreślenie {F}}) \ około _ {N \ uparrow \ infty} I_ {n} ^ {\ płaska, ścieżka} ({\ nadkreślenie {F}}) :=\int {\overline {F}}(x_{0},\cdots ,x_{n}){\widehat {p}}_{wstecz}(d(x_{0},\cdots ,x_{n })|(y_{0},\cdots ,y_{n-1}))}$

z funkcjami ograniczonymi przez 1, mamy ${\displaystyle f_{k}}$

${\ Displaystyle \ sup _ {n \ geqslant 0} {\ lewo \ vert E \ lewo ({\ widehat {ja}} _ {n} ^ {\ płaska, ścieżka} ({\ overline {F}}) \ po prawej )-I_{n}^{ścieżka}({\overline {F}})\right\vert }\leqslant {\frac {c_{1}}{N}}}$

i

${\ Displaystyle E \ lewo (\ lewo [{\ widehat {ja}} _ {n} ^ {\ płaskie, ścieżka} (F) -I_ {n} ^ {ścieżka} (F) \ prawej] ^ {2} \right)\leqslant {\frac {c_{2}}{nN}}+{\frac {c_{3}}{N^{2}}}}$

dla niektórych stałych skończonych Bardziej wyrafinowane szacunki, w tym wykładniczo małe prawdopodobieństwo błędów, opracowano w. ${\displaystyle c_{1},c_{2},c_{3}.}$

Sekwencyjne Ponowne Próbkowanie Ważności (SIR)

Filtr Monte Carlo i filtr ładowania początkowego

Ponowne próbkowanie o znaczeniu sekwencyjnym (SIR) , filtrowanie Monte Carlo (Kitagawa 1993) i algorytm filtrowania bootstrap (Gordon i in. 1993) są również powszechnie stosowanymi algorytmami filtrowania, które przybliżają gęstość prawdopodobieństwa filtrowania za pomocą ważonego zestawu N próbek ${\ Displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k})}$

${\ Displaystyle \ lewo \ {\ lewo (w_ {k} ^ {(i)}, x_ {k} ^ {(i)} \ prawej) \ : \ ja \ w \ {1, \ cdots, N \} \dobrze\}.}$

Te ciężary znaczenie stanowią przybliżenia względnego prawdopodobieństwa a posteriori (lub gęstość) próbek takie, że ${\ Displaystyle w_ {k} ^ {(i)}}$

${\ Displaystyle \ suma _ {i = 1} ^ {N} w_ {k} ^ {(i)} = 1.}$

Próbkowanie według ważności sekwencyjnej (SIS) jest sekwencyjną (tj. rekurencyjną) wersją próbkowania według ważności . Podobnie jak w przypadku próbkowania ważności, oczekiwanie funkcji f można aproksymować jako średnią ważoną

${\ Displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ kropki, y_ {k}) dx_ {k} \ w przybliżeniu \ suma _ {i = 1} ^ {N} w_{k}^{(i)}f(x_{k}^{(i)}).}$

W przypadku skończonego zestawu próbek wydajność algorytmu zależy od wyboru rozkładu propozycji

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

„ Optymalna” dystrybucja propozycji jest podana jako dystrybucja docelowa

${\ Displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}, y_ {k}) = {\ szczelina {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}).}$

Ten szczególny wybór propozycji przejścia został zaproponowany przez P. Del Morala w 1996 i 1998 roku. Gdy trudno jest próbkować przejścia zgodnie z rozkładem, naturalną strategią jest zastosowanie następującego przybliżenia cząstek ${\ Displaystyle p (x_ {k} | x_ {k-1}, y_ {k})}$

${\ Displaystyle {\ zacząć {wyrównany} {\ 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{wyrównany}}}$

z przybliżeniem empirycznym

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

związane z N (lub dowolną inną dużą liczbą próbek) niezależnych losowych próbek z podanym warunkowym rozkładem stanu losowego . Konsystencja wynikowego filtra cząstek tego przybliżenia i innych rozszerzeń jest rozwijana w. Na powyższym wyświetlaczu oznacza miarę Diraca w danym stanie 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}}$

Jednak rozkład prawdopodobieństwa przejścia a priori jest często używany jako funkcja ważności, ponieważ łatwiej jest narysować cząstki (lub próbki) i wykonać kolejne obliczenia wagi ważności:

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

Filtry SIR ( Sequential Importance Resampling ) z rozkładem prawdopodobieństwa przejścia jako funkcją ważności są powszechnie znane jako filtr ładowania początkowego i algorytm kondensacji .

Ponowne próbkowanie służy do uniknięcia problemu degeneracji algorytmu, czyli uniknięcia sytuacji, w której wszystkie wagi ważności poza jednym są bliskie zeru. Na działanie algorytmu może mieć również wpływ odpowiedni dobór metody resamplingu. Losowanie warstwowe proponowany przez Kitagawa (1993) jest optymalny pod względem wariancji.

Pojedynczy krok ponownego próbkowania ważności sekwencyjnej jest następujący:

1) Do losowania próbek z dystrybucji propozycji${\displaystyle i=1,\cdots,N}$

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

2) W celu aktualizacji wag ważności aż do stałej normalizacyjnej: ${\displaystyle i=1,\cdots,N}$

${\ Displaystyle {\ kapelusz {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})}}.}$

Zauważ, że gdy używamy rozkładu prawdopodobieństwa a priori przejścia jako funkcji ważności,

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

upraszcza to do następujących:

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

3) Aby obliczyć znormalizowane wagi ważności: ${\displaystyle i=1,\cdots,N}$

${\ Displaystyle w_ {k} ^ {(i)} = {\ Frac {{\ kapelusz {w}} _ {k} ^ {(i)}} {\ suma _ {j = 1} ^ {N} \hat {w}}_{k}^{(j)}}}}$

4) Oblicz oszacowanie efektywnej liczby cząstek jako

${\ Displaystyle {\ kapelusz {N}} _ {\ mathit {eff}} = {\ Frac {1} {\ suma _ {i = 1} ^ {N} \ lewo (w_ {k} ^ {(i) }\prawo)^{2}}}}$

Kryterium to odzwierciedla wariancję wag, inne kryteria można znaleźć w artykule, w tym ich rygorystyczną analizę i centralne twierdzenia graniczne.

5) Jeżeli efektywna liczba cząstek jest mniejsza od podanego progu , należy przeprowadzić resampling: ${\ Displaystyle {\ kapelusz {N}} _ {\ mathit {eff}} < N_ {thr}}$

a) Narysuj N cząstek z bieżącego zbioru cząstek z prawdopodobieństwami proporcjonalnymi do ich wag. Zastąp obecny zestaw cząsteczek nowym.

b) Do zestawu${\displaystyle i=1,\cdots,N}$${\ Displaystyle w_ {k} ^ {(i)} = 1 / N.}$

Określenie „Sampling Znaczenie Ponowne próbkowanie” jest również czasem używane w odniesieniu do filtrów sir, ale termin Znaczenie Ponowne próbkowanie jest bardziej dokładne, ponieważ słowo „resampling” zakłada, że początkowy próbkowania zostało już zrobione.

Próbkowanie o znaczeniu sekwencyjnym (SIS)

• To to samo, co sekwencyjny resampling ważności, ale bez etapu resamplingu.

Algorytm „wersja bezpośrednia”

Algorytm „wersja bezpośrednia” jest dość prosty (w porównaniu do innych algorytmów filtrowania cząstek) i wykorzystuje skład i odrzucanie. Aby wygenerować pojedynczą próbkę x w k z : ${\ Displaystyle p_ {x_ {k} | y_ {1: k}} (x | y_ {1: k})}$

1) Ustaw n=0 (To zliczy liczbę cząstek wygenerowanych do tej pory)

2) Jednostajnie wybierz wskaźnik i z zakresu${\displaystyle \{1,...,N\}}$

3) Wygeneruj test z dystrybucji za pomocą${\displaystyle {\kapelusz {x}}}$${\ Displaystyle p (x_ {k} | x_ {k-1})}$${\ Displaystyle x_ {k-1} = x_ {k-1 | k-1} ^ {(i)}}$

4) Generowanie prawdopodobieństwo użyciem z którym jest wartość mierzona${\displaystyle {\kapelusz {y}}}$${\displaystyle {\kapelusz {x}}}$${\ Displaystyle p (y_ {k} | x_ {k}), ~ {\ mbox {z}} ~ x_ {k} = {\ kapelusz {x}}}$${\displaystyle y_{k}}$

5) Wygeneruj kolejny mundur u skąd${\ Displaystyle [0,m_{k}]}$${\ Displaystyle m_ {k} = \ sup _ {x_ {k}} p (y_ {k} | x_ {k})}$

6) Porównaj ciebie i ${\ Displaystyle p \ po lewej ({\ kapelusz {y}} \ po prawej)}$

6a) Jeśli u jest większe, powtórz od kroku 2

6b) Jeśli u jest mniejsze, zapisz jako i zwiększ n${\displaystyle {\kapelusz {x}}}$${\ Displaystyle x_ {k | k} ^ {(i)}}$

7) Jeśli n == N to zakończ

Celem jest wygenerowanie „cząstek” P w k przy użyciu tylko cząstek z . Wymaga to zapisania (i obliczenia) równania Markowa w celu wygenerowania opartego tylko na . Algorytm ten wykorzystuje kompozycję cząstek P od do wygenerowania cząstki w k i powtarza (kroki 2–6), aż cząstki P zostaną wygenerowane w k . ${\ Displaystyle k-1}$${\displaystyle x_{k}}$${\displaystyle x_{k-1}}$${\ Displaystyle k-1}$

Można to łatwiej zwizualizować, jeśli x jest postrzegane jako dwuwymiarowa tablica. Jeden wymiar to k, a drugi wymiar to liczba cząstek. Na przykład, byłby i- ^tą cząstką i może być również zapisany (jak to zrobiono powyżej w algorytmie). Krok 3 generuje potencjał na podstawie losowo wybranej cząstki ( ) w czasie i odrzuca go lub akceptuje w kroku 6. Innymi słowy, wartości są generowane przy użyciu wcześniej wygenerowanego . ${\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}}$

Inne filtry cząstek stałych

• Wykładniczy naturalny filtr cząstek
• Pomocniczy filtr cząstek
• Znormalizowany dodatkowy filtr cząstek stałych
• Filtr cząstek Gaussa
• Bezzapachowy filtr cząstek
• Filtr cząstek Gaussa-Hermita
• Koszt referencyjny filtr cząstek stałych
• Hierarchiczny/skalowalny filtr cząstek
• Filtr cząstek Rao-Blackwellized
• Optymalny filtr cząstek oparty na próbkowaniu odrzucającym
• Szturchany filtr cząstek
• Feynman-Kac i metodologia cząstek średniego pola
• Cząstka Markowa-Chain Monte-Carlo, patrz np. pseudomarginalny algorytm Metropolis-Hastings .

Zobacz też

• Metody cząstek średniego pola
• Algorytm genetyczny
• Zespół filtra Kalmana
• Uogólnione filtrowanie
• Estymacja ruchomego horyzontu
• Rekurencyjna estymacja bayesowska
• Lokalizacja w Monte Carlo

Bibliografia

Bibliografia

• Del Moralny, Pierre (1996). „Filtrowanie nieliniowe: rozwiązanie interakcji cząstek” (PDF) . Procesy Markowa i pola pokrewne . 2 (4): 555–580.
• Del Moral, Pierre (2004). Wzory Feynmana-Kaca. Przybliżenia cząstek genealogicznych i oddziałujących . Skoczek. str. 575. „Seria: Prawdopodobieństwo i zastosowania”
• Del Moral, Pierre (2013). Symulacja pola średniego dla całkowania Monte Carlo . Chapman & Hall/CRC Press. str. 626. „Monografie statystyk i prawdopodobieństwa stosowanego”
• Cappe, O.; Muliny, E.; Ryden, T. (2005). Wnioskowanie w ukrytych modelach Markowa . Skoczek.
• Liu, JS; Chen, R. (1998). „Sekwencyjne metody Monte Carlo dla układów dynamicznych” (PDF) . Dziennik Amerykańskiego Towarzystwa Statystycznego . 93 (443): 1032-1044. doi : 10.1080/01621459.1998.10473765 .
• Liu, JS (2001). Strategie Monte Carlo w informatyce naukowej . Skoczek.
• Kong, A.; Liu, JS; Wong, WH (1994). „Imputacje sekwencyjne i problemy z brakiem danych Bayesa” (PDF) . Dziennik Amerykańskiego Towarzystwa Statystycznego . 89 (425): 278-288. doi : 10.1080/01621459.1994.10476469 .
• Liu, JS; Chen, R. (1995). „Ślepa dekonwolucja przez sekwencyjne imputacje” (PDF) . Dziennik Amerykańskiego Towarzystwa Statystycznego . 90 (430): 567-576. doi : 10.2307/291068 . JSTOR  2291068 .
• Ristic, B.; Arulampalam, S.; Gordon, N. (2004). Poza filtrem Kalmana: filtry cząstek do aplikacji śledzących . Dom Artech.
• Doucet, A.; Johansen, AM (grudzień 2008). „Samouczek na temat filtrowania i wygładzania cząstek: piętnaście lat później” (PDF) . Raport techniczny .
• Doucet, A.; Godsill, S.; Andrieu, C. (2000). „Na sekwencyjnych metodach pobierania próbek Monte Carlo dla filtrowania Bayesa”. Statystyka i informatyka . 10 (3): 197–208. doi : 10.1023/A:1008935410038 . S2CID  16288401 .
• Arulampalam, MS; Maskell S.; Gordon, N.; Clapp, T. (2002). „Samouczek dotyczący filtrów cząstek do nieliniowego / niegaussowskiego śledzenia Bayesa w trybie online”. Transakcje IEEE dotyczące przetwarzania sygnałów . 50 (2): 174–188. Kod bib : 2002ITSP...50..174A . CiteSeerX  10.1.1.471.8617 . doi : 10.1109/78.978374 .
• Cappe, O.; Godsill, S.; Moulines, E. (2007). „Przegląd istniejących metod i ostatnich postępów w sekwencyjnym Monte Carlo”. Postępowanie IEEE . 95 (5): 899-924. doi : 10.1109/JPROC.2007.893250 . S2CID  3081664 .
• Kitagawa, G. (1996). „Filtr Monte Carlo i gładsza dla niegaussowskich nieliniowych modeli przestrzeni stanów”. Czasopismo Statystyki Obliczeniowej i Graficznej . 5 (1): 1–25. doi : 10.2307/1390750 . JSTOR  1390750 .
• Kotecha, JH; Djuric, P. (2003). „Filtrowanie cząstek Gaussa”. Transakcje IEEE dotyczące przetwarzania sygnałów . 51 (10).
• Haug, AJ (2005). „Samouczek na temat technik szacowania i śledzenia Bayesa mających zastosowanie do procesów nieliniowych i niegaussowskich” (PDF) . Korporacja MITER, USA, Tech. Rep., luty . Źródło 2008-05-06 .
• Pitta, MK; Shephard, N. (1999). „Filtrowanie przez symulację: pomocnicze filtry cząstek” . Dziennik Amerykańskiego Towarzystwa Statystycznego . 94 (446): 590-591. doi : 10.2307/2670179 . JSTOR  2670179 . Źródło 2008-05-06 .
• Gordona, NJ; Łosoś, DJ; Smith, AFM (1993). „Nowe podejście do nieliniowego / niegaussowskiego szacowania stanu Bayesa”. Postępowanie IEE F - Radar i przetwarzanie sygnałów . 140 (2): 107–113. doi : 10.1049/ip-f-2.1993.0015 .
• Chen, Z. (2003). „Filtrowanie bayesowskie: od filtrów Kalmana do filtrów cząstek i nie tylko”. CiteSeerX  10.1.1.107.7415 . Cytowanie dziennika wymaga |journal=( pomoc )
• Vaswani, N .; Rathi, Y.; Yezzi, A.; Tannenbauma, A. (2007). „Śledzenie deformujących się obiektów za pomocą filtrowania cząstek dla aktywnych geometrycznych konturów” . Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej . 29 (8): 1470-1475. doi : 10.1109/tpami.2007.1081 . PMC  3663080 . PMID  17568149 .

Linki zewnętrzne