Részecske szűrő
A részecske szűrők , más néven a módszerek Monte Carlo szekvenciális , kifinomult technikák becslésére a modellek alapján szimuláció .
A részecskeszűrőket általában a bayesi hálózatok becslésére használják, és ezek olyan on-line módszereket alkotnak, amelyek analógak a Markov-láncok Monte-Carlo módszereivel, amelyek „off-line” módszerek (tehát a posteriori ) és gyakran hasonlóak a preferenciális mintavételi módszerekhez .
Helyes tervezés esetén a részecskeszűrők gyorsabbak lehetnek, mint a Monte Carlo Markov lánc módszerek. Gyakran alternatívát jelentenek a kiterjesztett Kalman-szűrőknek azzal az előnnyel, hogy elegendő mintával megközelítik az optimális Bayes-becslést. Ezért pontosabbak lehetnek, mint a Kalman-szűrők. A megközelítések Kalman-szűrővel is kombinálhatók, mint eloszlási javaslat a részecskeszűrőhöz.
Cél
A cél a részecske szűrő felbecsülni a hátsó sűrűsége az állapotváltozók figyelembe véve a megfigyelési változók. A részecskeszűrőt egy rejtett Markov-modellhez tervezték , ahol a rendszer rejtett és megfigyelhető változókból áll. A megfigyelhető változókat (megfigyelési folyamat) egy ismert funkcionális forma kapcsolja össze a rejtett változókkal (állapot-folyamat). Hasonlóképpen, az állapotváltozók evolúcióját leíró dinamikus rendszer is valószínűségi módon ismert.
Egy általános részecskeszűrő megbecsüli a rejtett állapotok hátsó eloszlását a megfigyelési mérési módszer segítségével. Vegyünk egy állapotteret, amelyet az alábbi ábra mutat
x0⟶x1⟶x2⟶x3⟶...séngnemnál néll↓↓↓...Y0Y1Y2Y3...observnál nélténonem{\ displaystyle {\ begin {mátrix} X_ {0} & \ longrightarrow & X_ {1} & \ longrightarrow & X_ {2} & \ longrightarrow & X_ {3} & \ longrightarrow & ... & signal \\\ downarrow && \ downarrow && \ downarrow && ... \\ Y_ {0} && Y_ {1} && Y_ {2} && Y_ {3} && ... & megfigyelés \ end {mátrix}}}
A szűrési probléma abból áll, hogy a rejtett állapotok értékeit bármely szakaszban egymás után becsüljük meg , figyelembe véve a megfigyelési folyamat értékeit .
xk{\ displaystyle X_ {k}}Y0,...,Yk{\ displaystyle Y_ {0}, ..., Y_ {k}}k{\ displaystyle k}
A hátsó sűrűség összes bayesi becslése következik . A részecskeszűrő módszertan ezen feltételes valószínűségek közelítését biztosítja egy genetikai típusú algoritmushoz kapcsolódó empirikus mérés segítségével. Másrészt Markov vagy a fontossági láncok által végzett Monte-Carlo módszer mintavételi megközelítés modellezné a teljes hátulról .
xk{\ displaystyle X_ {k}}o(xk∣y0,y1,...,yk){\ displaystyle p (x_ {k} \ y y {0}, y_ {1}, ..., y_ {k})}o(x0,x1,...,xk∣y0,y1,...,yk){\ displaystyle p (x_ {0}, x_ {1}, ..., x_ {k} \ y y {0}, y_ {1}, ..., y_ {k})}
A jelmegfigyelési modell
A részecskemódszerek gyakran feltételezik, hogy a megfigyelések ebben a formában modellezhetők:
xk{\ displaystyle X_ {k}}Yk{\ displaystyle Y_ {k}}
-
x0,x1,...{\ displaystyle X_ {0}, X_ {1}, ...}egy Markov-folyamat a (néhány ), amely fejlődik szerint sűrűsége átmeneti valószínűség . Ezt a modellt gyakran szintetikusan is írjákRdx{\ displaystyle \ mathbb {R} ^ {d_ {x}}}dx⩾1{\ displaystyle d_ {x} \ geqslant 1}o(xk|xk-1){\ displaystyle p (x_ {k} | x_ {k-1})}
xk|xk-1=xk∼o(xk|xk-1){\ displaystyle X_ {k} | X_ {k-1} = x_ {k} \ sim p (x_ {k} | x_ {k-1})}Kezdeti valószínűségi sűrűséggel .o(x0){\ displaystyle p (x_ {0})}
- A megfigyelések egy bizonyos állapottérben (egyesek számára ) értékeket feltételesen függetlenek, feltéve, hogy ismertek. Más szavakkal, mindegyik csak attól függ . Feltételezzük továbbá, hogy egy adott feltételes eloszlás abszolút folyamatos, és szintetikusan meg is van
Y0,Y1,⋯{\ displaystyle Y_ {0}, Y_ {1}, \ cdots}Rdy{\ displaystyle \ mathbb {R} ^ {d_ {y}}}dy⩾1{\ displaystyle d_ {y} \ geqslant 1}x0,x1,⋯{\ displaystyle X_ {0}, X_ {1}, \ cdots}Yk{\ displaystyle Y_ {k}}xk{\ displaystyle X_ {k}}Yk{\ displaystyle Y_ {k}}xk=xk{\ displaystyle X_ {k} = x_ {k}}Yk|xk=yk∼o(yk|xk){\ displaystyle Y_ {k} | X_ {k} = y_ {k} \ sim p (y_ {k} | x_ {k})}
Az ilyen tulajdonságokkal rendelkező rendszerre példa:
xk=g(xk-1)+Wk{\ displaystyle X_ {k} = g (X_ {k-1}) + W_ {k}}
Yk=h(xk)+Vk{\ displaystyle Y_ {k} = h (X_ {k}) + V_ {k}}
Ahol a kettő és egymástól független szekvencia az s valószínűségi sűrűségfüggvénnyel és az ismert ismert funkciók. Ez a két egyenlet állapottéregyenletnek tekinthető, és hasonlít a Kalman-szűrő állapottéregyenleteire. Ha a funkciók g és h a fenti példában lineáris, és mindkét és a Gauss , a Kalman-féle szűrő úgy találja, a pontos Bayes szűrő eloszlása. Egyébként a Kalman-szűrőn alapuló módszerek elsőrendű közelítés (EKF) vagy másodrendű közelítés (általában UKF, de ha a valószínűségeloszlás Gauss-féle, akkor harmadrendű közelítés lehetséges).
Wk{\ displaystyle W_ {k}}Vk{\ displaystyle V_ {k}}g{\ displaystyle g}h{\ displaystyle h}Wk{\ displaystyle W_ {k}}Vk{\ displaystyle V_ {k}}
Könnyebb lehet feltételezni, hogy a kezdeti eloszlás és a Markov-lánc átmenetei abszolút folytonosak a Lebesgue-mértékhez képest. A részecskeszűrő megtervezéséhez csak azt kell feltételeznünk, hogy mintavételezhetjük a Markov-lánc átmeneteit, és kiszámíthatjuk a Funkció valószínűségét (lásd például a részecskeszűrő genetikai szelekciójának alább ismertetett leírását). A Markov-átmenetekkel kapcsolatos abszolút folyamatos hipotézis csak arra szolgál, hogy informálisan (és inkább visszaélésszerűen) különböző képleteket nyújtson a hátsó eloszlások között, Bayes-féle feltételes sűrűségre vonatkozó szabályát alkalmazva.
xk-1→xk{\ displaystyle X_ {k-1} \ rightarrow X_ {k}}xk,{\ displaystyle X_ {k},}xk↦o(yk|xk){\ displaystyle x_ {k} \ mapsto p (y_ {k} | x_ {k})}xk{\ displaystyle X_ {k}}
Modellezés
A részecskeszűrők feltételezik, hogy az állapotok és a megfigyelések a következő formában modellezhetők:
xk{\ displaystyle x_ {k}}yk{\ displaystyle y_ {k}}
- A paraméterek sorrendje egy elsőrendű Markov-láncot alkot , olyannak és kezdeti eloszlású .x0,x1,...{\ displaystyle x_ {0}, x_ {1}, \ dots}xk|xk-1∼oxk|xk-1(x|xk-1){\ displaystyle x_ {k} | x_ {k-1} \ sim p_ {x_ {k} | x_ {k-1}} (x | x_ {k-1})}o(x0){\ displaystyle p (x_ {0})}
- A megfigyelések feltételektől függetlenek, amennyiben ismeretesek. Más szavakkal, minden megfigyelés csak a paramétertől függ :y0,y1,...{\ displaystyle y_ {0}, y_ {1}, \ dots}x0,x1,...{\ displaystyle x_ {0}, x_ {1}, \ dots}yk{\ displaystyle y_ {k}}xk{\ displaystyle x_ {k}}yk|xk∼oy|x(y|xk){\ displaystyle y_ {k} | x_ {k} \ sim p_ {y | x _ {}} (y | x_ {k})}
Példa erre a forgatókönyvre {xk=f(xk-1)+vkyk=h(xk)+wk{\ displaystyle \ left \ {{\ begin {mátrix} x_ {k} = f (x_ {k-1}) + v_ {k} \\ y_ {k} = h (x_ {k}) + w_ {k } \ end {mátrix}} \ right.}
ahol mindkét és kölcsönösen független és azonos eloszlású szekvenciákat ismert sűrűségfüggvényeket , és ahol , és ismert funkciók. Ez a két egyenlet állapottéregyenletnek tekinthető, és hasonlít a Kalman-szűrőre .
vk{\ displaystyle v_ {k}}wk{\ displaystyle w_ {k}}f(⋅){\ displaystyle f (\ cdot)}h(⋅){\ displaystyle h (\ cdot)}
Ha a funkciók és a lineáris volt, és ha mind , és voltak Gauss , a Kalman-szűrő találja a pontos Bayes- szűrés forgalmazás . Ellenkező esetben a Kalman szűrőalapú módszerek adnak első rendű becslést. A részecskeszűrők is adnak közelítéseket, de elegendő részecske mellett az eredmények még pontosabbak lehetnek.
f(⋅){\ displaystyle f (\ cdot)}h(⋅){\ displaystyle h (\ cdot)}vk{\ displaystyle v_ {k}}wk{\ displaystyle w_ {k}}
Monte-Carlo közelítés
A részecskemódszerek, mint minden mintavételen alapuló módszer (például az MCMC ), minták készítését hozzák létre, amelyek közelítik a szűrési eloszlást . Így a mintáknál a szűrési eloszlás várható értékeit a következővel közelítjük meg:
hol van az (L) részecske pillanatnyilag ; és a Monte Carlo módszerek szokásos módon az eloszlás összes adatait ( momentumokat stb.) meg tudja adni egy bizonyos fokú közelítésig.
o(xk|y0,...,yk){\ displaystyle p (x_ {k} | y_ {0}, \ pontok, y_ {k})}P{\ displaystyle P}∫f(xk)o(xk|y0,...,yk)dxk≈1P∑L=1Pf(xk(L)){\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ pontok, y_ {k}) dx_ {k} \ kb {\ frac {1} {P}} \ összeg _ {L = 1} ^ {P} f (x_ {k} ^ {(L)})}xk(L){\ displaystyle x_ {k} ^ {(L)}}k{\ displaystyle k}f(⋅){\ displaystyle f (\ cdot)}
Általánosságban elmondható, hogy az algoritmust ismételten ismételjük meg egy adott számú értéknél (amelyet megjegyezünk ).
k{\ displaystyle k}NEM{\ displaystyle N}
Az Inicializálás az összes részecske számára kiindulási pozíciót biztosít a létrehozáshoz , amely felhasználható létrehozásra , felhasználható létrehozásra stb .
xk=0|k=0{\ displaystyle x_ {k} = 0 | _ {k = 0}}x1{\ displaystyle x_ {1}}x2{\ displaystyle x_ {2}}x3{\ displaystyle x_ {3}}k=NEM{\ displaystyle k = N}
Ha ez megtörtént, az átlagos az egész részecske (vagy ) megközelítőleg a valós értékét .
xk{\ displaystyle x_ {k}}1P∑L=1Pxk(L){\ displaystyle {\ frac {1} {P}} \ sum _ {L = 1} ^ {P} x_ {k} ^ {(L)}}xk{\ displaystyle x_ {k}}
Mintavétel fontosság szerinti újramintavétellel (SIR)
Az újramintavétel fontosságú mintavétel vagy a mintavételi fontosság újravételezése (SIR) egy nagyon gyakran használt szűrési algoritmus. Közeledik a szűrés eloszlás szerint egy súlyozott részecskék: .
o(xk|y0,...,yk){\ displaystyle p (x_ {k} | y_ {0}, \ ldots, y_ {k})}{(wk(L),xk(L)) : L=1,...,P}{\ displaystyle \ {(w_ {k} ^ {(L)}, x_ {k} ^ {(L)}) ~: ~ L = 1, \ ldots, P \}}
A fontossági súlyok a részecskék relatív hátsó valószínűségének (vagy sűrűségének) közelítői, mint pl .
wk(L){\ displaystyle w_ {k} ^ {(L)}}∑L=1Pwk(L)=1{\ displaystyle \ sum _ {L = 1} ^ {P} w_ {k} ^ {(L)} = 1}
A SIR algoritmus a fontossági mintavétel rekurzív változata . A fontossági mintavételhez hasonlóan a függvény várakozása súlyozott átlagként közelíthető meg:f(⋅){\ displaystyle f (\ cdot)}∫f(xk)o(xk|y0,...,yk)dxk≈∑L=1Pw(L)f(xk(L)).{\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ pontok, y_ {k}) dx_ {k} \ kb \ sum _ {L = 1} ^ {P} w ^ {(L)} f (x_ {k} ^ {(L)}).}
Az előadás az algoritmus függ a választás a disztribúció nagyságának : .
π(xk|x0:k-1,y0:k){\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k})}
Az optimális fontossági eloszlás a következő:π(xk|x0:k-1,y0:k)=o(xk|xk-1,yk).{\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}, y_ {k}).}
Az átmenet valószínűségét azonban gyakran használják fontossági függvényként, mivel könnyebb kiszámítani, és egyszerűsíti a későbbi fontossági súlyok számítását is:
π(xk|x0:k-1,y0:k)=o(xk|xk-1).{\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}).}
A szűrők fontosság szerinti újramintavételezése (CRS) az átmenet valószínűségével, mint fontossági függvény, általában primer szűrőként ( bootstrap szűrők) vagy kondenzációs algoritmusként ismert .
Az újramintavétellel elkerülhető az algoritmus degenerációjának problémája. Ezzel elkerülhetők azok a helyzetek, amikor az összes fontossági súly kivételével az összes nullához közelít. Az algoritmus teljesítményét a megfelelő újramintavételi módszer megválasztása is befolyásolhatja. A variancia szempontjából optimális a Kitagawa (1996) által javasolt rétegzett újravétel .
A szekvenciális fontosságú újramintavétel egyetlen lépése a következő:
- Mert felhívjuk a fontosság eloszlásának mintáit :L=1,...,P{\ displaystyle L = 1, \ ldots, P}xk(L)∼π(xk|x0:k-1(L),y0:k){\ displaystyle x_ {k} ^ {(L)} \ sim \ pi (x_ {k} | x_ {0: k-1} ^ {(L)}, y_ {0: k})}
- A normalizálási állandóval értékeljük a fontossági súlyokat:L=1,...,P{\ displaystyle L = 1, \ ldots, P}w^k(L)=wk-1(L)o(yk|xk(L))o(xk(L)|xk-1(L))π(xk(L)|x0:k-1(L),y0:k).{\ displaystyle {\ hat {w}} _ {k} ^ {(L)} = w_ {k-1} ^ {(L)} {\ frac {p (y_ {k} | x_ {k} ^ { (L)}) p (x_ {k} ^ {(L)} | x_ {k-1} ^ {(L)})} {\ pi (x_ {k} ^ {(L)} | x_ {0 : k-1} ^ {(L)}, y_ {0: k})}}.}
- A normalizált fontossági súlyok kiszámításához:L=1,...,P{\ displaystyle L = 1, \ ldots, P}wk(L)=w^k(L)∑J=1Pw^k(J){\ displaystyle w_ {k} ^ {(L)} = {\ frac {{\ hat {w}} _ {k} ^ {(L)}} {\ sum _ {J = 1} ^ {P} { \ hat {w}} _ {k} ^ {(J)}}}}
- Kiszámítjuk a részecskék tényleges számának becslését as NEM^eff=1∑L=1P(wk(L))2{\ displaystyle {\ hat {N}} _ {\ mathit {eff}} = {\ frac {1} {\ sum _ {L = 1} ^ {P} \ balra (w_ {k} ^ {(L) } \ right) ^ {2}}}}
- Ha a tényleges részecskeszám kisebb, mint egy adott küszöbérték , akkor az újramintavételt:
NEM^eff<NEMthr{\ displaystyle {\ hat {N}} _ {\ mathit {eff}} <N_ {thr}}
- Rajzoljon részecskéket az aktuális részecskekészletből a súlyukkal arányos valószínűséggel, majd cserélje le az áramrészecskék halmazát erre az új halmazra.P{\ displaystyle P}
- Az egészért .L=1,...,P{\ displaystyle L = 1, \ ldots, P}wk(L)=1/P{\ displaystyle w_ {k} ^ {(L)} = 1 / P}
A szekvenciális fontosságú resampling (Sequential Importance Resampling) kifejezést néha használják a SIR szűrőkre is.
Szekvenciális fontosságú mintavétel (SIS)
A méret szerinti szekvenciális mintavétel vagy a szekvenciális fontosságú mintavétel (SIS) hasonló az újramintavétel fontosságú mintavételhez (SIR), de az újramintavételi lépés nélkül.
Az algoritmus közvetlen változata
Az algoritmus egyszerű verziója viszonylag egyszerű a többi részecskeszűrő algoritmushoz képest, és összetételt és elutasítást használ. Előállítani egy mintát , hogy a :
x{\ displaystyle x}k{\ displaystyle k}oxk|y1:k(x|y1:k){\ displaystyle p_ {x_ {k} | y_ {1: k}} (x | y_ {1: k})}
(1) Állítsa be a p = 1 értéket
(2)
Legyen egyenletesen L-ből
{1,...,P}{\ displaystyle \ {1, ..., P \}}
(3) Hozzon létre egy tesztet annak terjesztéséből
x^{\ displaystyle {\ hat {x}}}oxk|xk-1(x|xk-1|k-1(L)){\ displaystyle p_ {x_ {k} | x_ {k-1}} (x | x_ {k-1 | k-1} ^ {(L)})}
(4) létrehozása a valószínűségek alkalmazásával a , ahol a mért érték
y^{\ displaystyle {\ hat {y}}}x^{\ displaystyle {\ hat {x}}}oy|x(yk|x^){\ displaystyle p_ {y | x} (y_ {k} | {\ hat {x}})}yk{\ displaystyle y_ {k}}
(5) Hozzon létre egy másik
egyenletesen u-t
[0,mk]{\ displaystyle [0, m_ {k}]}
(6) Hasonlítsa össze az u és a
y^{\ displaystyle {\ hat {y}}}
(a) Ha u nagyobb, akkor ismételje meg a (2) lépéstől
(b) Ha u kisebb, akkor mentse el a következőt: és növelje a p oldalt
x^{\ displaystyle {\ hat {x}}}xk|k(o){\ displaystyle x {k | k} ^ {(p)}}
(c) Ha p> P, akkor álljon meg
A cél P- részecskék létrehozása a lépésben , csak a lépés részecskéinek felhasználásával . Ehhez meg kell adni egy Markov-egyenletet (és kiszámítani), hogy csak ezen alapuljon . Ez az algoritmus a P részecskék összetételét használja fel a létrehozásig .
k{\ displaystyle k}k-1{\ displaystyle k-1}xk{\ displaystyle x_ {k}}xk-1{\ displaystyle x_ {k-1}}k-1{\ displaystyle k-1}k{\ displaystyle k}
Ez könnyebben megjeleníthető, ha kétdimenziós tömbnek tekintjük. Az egyik dimenzió a másik dimenzió a részecskék száma. Például lépésben az L- es részecske lenne , ezért írható (ahogy az algoritmusban korábban tettük).
x{\ displaystyle x}k{\ displaystyle k}x(k,L){\ displaystyle x (k, L)}k{\ displaystyle k}xk(L){\ displaystyle x_ {k} ^ {(L)}}
A (3) lépés egy véletlenszerűen kiválasztott részecske ( ) alapján egy potenciált hoz létre időben, és a (6) lépésben elutasítja vagy elfogadja ezt a részecskét. Más szavakkal, az értékeket a korábban kiszámolt felhasználásával számítják ki.
xk{\ displaystyle x_ {k}}xk-1(L){\ displaystyle x_ {k-1} ^ {(L)}}k-1{\ displaystyle k-1}xk{\ displaystyle x_ {k}}xk-1{\ displaystyle x_ {k-1}}
Megjegyzések és hivatkozások
-
(in) Sanjeev Arulampalam úr, " Oktatóanyag a részecskeszűrőkről az online nemlineáris / nem-Gauss-féle Bayes- követéshez " , IEEE-TRANZAKCIÓK A JELI FELDOLGOZÁSON, VOL. 50, NO. 2 ,2002. február
-
(en) " Részecskeszűrők "
-
Lásd is
Bibliográfia
-
Szekvenciális Monte Carlo módszerek a gyakorlatban , szerző: A Doucet, N de Freitas és N Gordon. Írta: Springer.
-
A szekvenciális Monte Carlo mintavételi módszerekről a Bayes- szűréshez, A Doucet, C Andrieu és S. Godsill, Statistics and Computing, vol. 10. sz. 3. o. 197-208 , 2000 CiteSeer link
-
Oktató részecskeszűrőkről on-line nemlineáris / nem-Gauss Bayes-követéshez (2001) ; S. Arulampalam, S. Maskell, N. Gordon és T. Clapp; CiteSeer link
Külső linkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">