粒子濾波器(英語:particle filter)是一種使用蒙特卡羅方法的遞迴濾波器,透過一組具有權重的隨機樣本(粒子)來表示隨機事件的後驗機率,從含有雜訊或不完整的觀測序列,估計出動態系統的狀態,粒子濾波器可以運用在任何狀態空間的模型上。粒子濾波器是卡爾曼濾波器的一般化方法,卡爾曼濾波器建立在線性的狀態空間和高斯分布的雜訊上;而粒子濾波器的狀態空間模型可以是非線性,且雜訊分布可以是任何型式。
| 本條目存在以下問題,請協助 改善本條目或在 討論頁針對議題發表看法。
|
從統計和機率的角度來看,粒子濾波器屬於遺傳算法分支過程的類別,並且是指平均場類型相互作用的粒子方法。 這些粒子方法的解釋取決於科學專業。 在進化計算中,平均場遺傳類型粒子方法通常用作啟發式和自然搜索算法(也稱為元啟發算法)。在計算物理學和分子化學中,它們用於解決費曼-卡茲(Feynman-Kac)路徑積分問題,或者用於計算玻爾茲曼-吉布斯(Boltzmann-Gibbs)度量,薛丁格算子的最高特徵值和基態。在生物學與遺傳學中,它們還代表了某些環境中一群個體或基因的進化。
平均場類型進化計算技術的起源於1950年艾倫·圖靈在遺傳類型突變選擇學習機上的開創性工作,以及1954年紐澤西州普林斯頓高級研究所的尼爾斯·艾爾·巴里切利(Nils Aall Barricelli)的文章。統計學中的粒子濾波器最早可追溯到1950年代中期。哈默斯利(Hammersley)等人在1954年提出的「窮人的蒙地卡羅」法暗示了當今使用的遺傳類型粒子過濾方法。 1963年,尼爾斯·艾爾·巴里切利(Nils Aall Barricelli)模擬了一種遺傳類型算法,以模仿個人玩簡單遊戲的能力。在進化計算文獻中,遺傳類型突變選擇算法通過1970年代初期約翰·霍蘭德(John Holland)的開創性工作而流行,特別是1975年出版的著作。
在生物學與遺傳學中,澳大利亞遺傳學家亞歷克斯·弗雷澤(Alex Fraser)在1957年還發表了一系列有關人工選擇生物的遺傳類型模擬的論文。 由生物學家進行的進化計算機模擬在1960年代初變得更加普遍,並且該方法在弗雷澤和伯內爾(Burnell)(1970)和克羅斯比(Crosby)(1973)的書中進行了描述。弗雷澤的模擬包括了現代突變選擇遺傳粒子算法的所有基本要素。
從數學觀點來看,給定一些部分和雜訊觀測結果的信號隨機狀態的條件分布,是由信號的隨機軌跡上的費曼-卡茲(Feynman-Kac)機率描述的,該機率由一系列概似勢函數加權。量子蒙地卡羅法,更具體地說是擴散蒙地卡羅法,也可以解釋為費曼-卡茲路徑積分的平均場遺傳類型粒子近似。量子蒙特卡羅方法的起源通常歸因於恩里科·費米(Enrico Fermi)和羅伯特·里克特邁耶(Robert Richtmyer),他們於1948年開發了一種中子鏈反應的均值場粒子解釋方法,但它是第一個類似啟發式和遺傳類型的粒子算法(又名「重採樣」或「重新配置」蒙地卡羅方法)是在1984年由Jack H. Hetherington提出的用於估計量子系統(在簡化的矩陣模型中)的基態能量的方法。還可以引用1951年出版的西奧多·愛德華·哈里斯(Theodore E. Harris)和赫爾曼·康恩(Herman Kahn)的開創性著作,該著作使用平均場,但類似於啟發式遺傳方法,用於估計粒子傳輸能量。在分子化學中,遺傳啟發式粒子方法(又名修剪和富集策略)的使用可以追溯到1955年馬歇爾·N·羅森布魯斯(Marshall N. Rosenbluth)和阿里安娜·W·羅森布盧斯(Arianna W. Rosenbluth)的開創性工作。
遺傳粒子算法在高級信號處理和貝氏推論中的使用是最近的。1993年1月,北川源四郎開發了「蒙特卡羅濾波器」,該文在1996年出現了輕微修改。1993年4月,戈登等人在他們的開創性著作中發表了遺傳類型算法在貝氏統計推斷中的應用。作者將其算法命名為「自舉濾波器」,並證明與其他濾波方法相比,其自舉算法不需要對該狀態空間或系統噪聲進行任何假設。獨立的是皮埃爾·德爾·莫拉爾(Pierre Del Moral)和希米爾孔·卡瓦略(Himilcon Carvalho),皮埃爾·德爾·莫拉爾(Pierre Del Moral),安德烈·莫寧(André Monin)和熱拉爾·薩魯特(Gérard Salut)在1990年代中期發表的有關粒子過濾器的論文。 1989-1992年初,皮埃爾·德爾·莫拉爾(P.Del Moral),J.C.諾耶(J.C. Noyer),G.Rigal和G.Salut在LAAS-CNRS中也開發了信號處理技術,並通過STCAN(服務技術)進行了一系列受限和分類研究des Constructions and Armes Navales),IT公司DIGILOG和LAAS-CNRS(系統分析和體系結構實驗室)來解決RADAR/SONAR和GPS信號處理問題。
從1950年到1996年,所有有關粒子過濾器、遺傳算法的出版物,包括在計算物理和分子化學中引入的修剪和重採樣蒙地卡羅方法,都提出了適用於不同情況的類似於自然和啟發式算法,而沒有任何證據證明它們的一致性,也沒有討論估計的偏差以及基於族譜和祖先樹的算法。
這些粒子算法的數學基礎和首次嚴格的分析是由皮埃爾·德爾·莫拉爾(Pierre Del Moral)在1996年提出的。他的著作[1]還包含了概似函數和未標準化的條件機率測度的粒子近似的不偏性質的證明。文章介紹的概似函數的不偏粒子估計器如今已用於貝式統計推理中。
到1990年代末,Dan Crisan、Jessica Gaines、Terry Lyons、Pierre Del Moral等人提出了具有不同種群大小的分支類型粒子方法。P. Del Moral,A。Guionnet和L. Miclo在2000年開發了該領域的進一步發展。第一個中央極限定理是由Pierre Del Moral和Alice Guionnet於1999年以及Pierre Del Moral和Laurent Miclo於2000年提出的。Pierre於1990年代末提出了關於粒子過濾器
時間參數的第一個統一收斂結果。 Del Moral和Alice Guionnet。 2001年,P。Del Moral和L. Miclo首次對基於族譜樹的粒子濾波器平滑器進行了嚴格的分析。
關於Feynman-Kac粒子方法論的理論和相關的粒子過濾器算法已在2000年和2004年的書中得到發展。這些抽象的機率模型封裝了遺傳類型算法,粒子和自舉濾波器,交互的卡爾曼濾波器(又稱Rao–Blackwellized粒子濾波器),重要性採樣和重採樣樣式的粒子濾波器技術,包括基於族譜樹的方法和用於解決濾波和平滑問題的粒子後向方法。其他類別的粒子濾波方法包括基於族譜樹的模型、後向馬可夫粒子模型、自適應平均場粒子模型、島型粒子模型和粒子馬可夫鏈蒙特卡羅方法。
粒子濾波器的目標是通過觀測值估計狀態變量的事後機率。粒子濾波器是針對隱藏式馬可夫模型設計的,系統中既包含隱藏的變量,也包含可觀測的變量[2]。可觀測變量(觀測過程)與隱藏變量(狀態過程)通過某種已知的函數關係相關聯。類似地,定義狀態變量演化的動態系統的機率描述是已知的。
一個通用粒子濾波器通過觀察測量過程估計隱藏狀態的事後分布。考察下圖所示的狀態空間:
![{\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{observation}}\end{array}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/971ba2fee7722578604c8636ff2a4c67bd1ee8eb)
濾波問題是要通過給定的觀測過程
在任意時刻 k 的值,依次估計隱藏狀態
的值。
所有的對
的貝氏估計服從事後分布
。粒子濾波器方法使用經驗測量和通用粒子算法,提供了這些條件機率的近似值。與之對比,馬可夫鏈蒙地卡羅(MCMC)或重要性採樣方式會對整個事後機率
進行建模。
粒子濾波器能夠從一系列含有雜訊或不完整的觀測值中,估計出動態系統的內部狀態。在動態系統的分析中,需要兩個模型,一個用來描述狀態隨時間的變化(系統模型),另一個用來描述每個狀態下觀測到的雜訊(觀測模型),將這兩個模型都用機率來表示。
在許多情況下,每得到一個新的觀測值時,都必須對系統做出一次估計,利用遞迴濾波器,能夠有效地達到這樣的目的。遞迴濾波器會對得到的資料做連續處理,而非分批處理,因此不需要將完整的資料儲存起來,也不需要在得到新的觀測值時,將現有的資料重新做處理。遞迴濾波器包含兩個步驟:
預測:利用系統模型,由前一個狀態的資訊預測下一個狀態的機率密度函數。
更新:利用最新的觀測值,修改預測出的機率密度函數。
藉由貝氏推論(Baysian inference),我們可以描述出狀態空間的機率,並在得到新的觀測值時,對系統做出更新,因而達成上述目的。
在某些問題中,在信號的隨機狀態下,觀測值的條件分布可能不具有密度,或者不可能或太複雜而無法計算。在這種狀況下,我們需要求近似值。其中一個策略是藉由馬可夫鏈
來取代信號
,採用虛擬觀測的形式
![{\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}](//wikimedia.org/api/rest_v1/media/math/render/svg/cd574394a51021cd10cac7714851c3b8c30f92f7)
對於具有已知機率密度函數的獨立序列中的某些序列,核心的概念是觀測下式
![{\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)}](//wikimedia.org/api/rest_v1/media/math/render/svg/eb81125ad1030efe33be7233fd8b25d0328b01a2)
在部分的觀測
之下,粒子濾波器是和馬可夫鏈
有相關的,定義為根據演化出的
,在一些明顯的濫用性符號
下,帶有概似函數的粒子。這些機率性的技術跟近似貝式計算非常相關。在量子濾波器中,這些近似貝式量子濾波器的技術在1998年被皮埃爾·德爾·莫拉爾(P. Del Moral), 讓·雅各德(J. Jacod)和菲力普·普羅特(P. Protter)所採用。且被皮埃爾·德爾·莫拉爾,阿諾·杜斯(A. Doucet)和阿傑·賈斯拉(A. Jasra)更進一步發展。
藉由貝式定理在條件機率中可以得出
![{\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})}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/5ed482f85c12019fe67bb1b1ac36cbe8bc2f0185)
當
![{\displaystyle {\begin{aligned}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{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/d4f050e6c7cac1d097f94e571f015737574fdd67)
粒子濾波器也是一個近似值,當有足夠的粒子時,結果會更加的準確。非線性濾波方程式可以藉由遞迴得出
| | Eq. 1 |
依照慣例
在k=0時。非線性濾波方程式問題的關鍵在於依序計算這些條件機率分布。
固定一個時間範圍和一個序列的觀測
,在k=0....n,我們定義:
![{\displaystyle G_{k}(x_{k})=p(y_{k}|x_{k}).}](//wikimedia.org/api/rest_v1/media/math/render/svg/2d35ac2407ebd85e6efbc182966d4f298d1feaab)
在這種表示法中,對於從原點k = 0到時間k = n的 軌跡集合上的任何有界函數F,我們都可以用費曼-卡茲公式來表示
![{\displaystyle {\begin{aligned}\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{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/8026f95ac44c997eb1235a345dd7f66c2a3ae17e)
這些費曼-卡茲路徑積分模型出現在各種科學學科中,包括計算物理、生物學、資訊理論和計算機科學。他們的解釋取決於應用領域。舉例來說,如果我們選擇狀態空間某些子集的指標函數
,它們代表馬可夫鏈在給定管中的條件分布。我們會得到
![{\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)}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0a4298ccc9a9b657df1ab9f1a1446e7af603d6a0)
和
![{\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)}](//wikimedia.org/api/rest_v1/media/math/render/svg/7fc7d9d96ab4e029ab34bdeebef6a0ef978b97a2)
只要標準化常數嚴格為正。
在動態系統中,我們常常需要對物體做追蹤。假設有一動態系統,已知其狀態序列
定義為
其中
是狀態轉移函數,可以是非線性的函數,
是一個獨立且相同分布(i.i.d.)的過程雜訊序列,
和
分別代表狀態和過程雜訊向量的維度,
為自然數的集合。追蹤的目標是要遞迴地從觀測值
估計出
,而觀測值
定義為
其中
是觀測函數,可以是非線性的函數,
是一個獨立且相同分布(i.i.d.)的觀測雜訊序列,
和
分別代表觀測值和觀測雜訊向量的維度。
從貝氏定理的觀點來看,追蹤問題是要根據到時間
為止的已知資訊
,遞迴地計算出時間
的狀態
的可信度,這個可信度用機率密度函數
來表示。假設初始機率密度函數
(稱為先驗機率)為已知,則利用「預測」和「更新」兩個步驟就能遞迴地計算出機率密度函數
。
在此假設在時間
的機率密度函數
為已知。
SIR是由SIS加上重採樣(resampling)改良而來,在SIS中,我們將後驗機率
用
個隨機採樣的樣本(稱為粒子)與各自的權重表示為
其中的權重是根據重要性採樣的規則產生,且必須符合
SIS是將重要性採樣遞迴執行的一種方法,根據重要性採樣的理論,一個函數
的期望值可以用加權平均來近似
在每一次遞迴過程中,我們希望由前一次採樣的權重,計算出下一次採樣的權重。假設採樣的樣本分布可以表示為
其中
稱為重要性密度(importance density)。若樣本
是由重要性密度
抽取出來,則權重可表示為
我們將重要性密度分解為
再將後驗機率表示為
則權重的遞迴式可以表示為
SIS可能會造成退化問題(degeneracy problem),也就是在經過幾次遞迴後,很多粒子的權重都變小到可以忽略不計,只剩少數粒子的權重較大,如此會浪費大量的計算量在幾乎沒有作用的粒子上,而使估計性能下降。由於在遞迴過程中,權重的變異數只會愈來愈大,因此退化問題無法被避免。
為了評估退化問題,我們定義有效粒子數為
在進行SIS時,若有效粒子數小於某一閾值,則對粒子做重採樣,即可減緩退化問題。重採樣的概念是去除權重過小的粒子,專注於權重較大的粒子。進行重採樣時,要由現有的粒子分布取樣,產生一組新的粒子
,由於產生出的新樣本為獨立且相同分布(i.i.d.),因此將權重重新設定為
。
- M. S. Arulampalam, S. Maskell, N. Gordon and T. Clapp, "A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking." In IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174-188, Feb 2002.
- A. Doucet, N. de Freitas, N. Gordon, "An Introduction to Sequential Monte Carlo Methods." In A. Doucet, N. de Freitas, N. Gordon (eds.) Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science. Springer, New York, NY, 2001
- A. Doucet, "On sequential Monte Carlo methods for Bayesian filtering." Dept. Eng., Univ. Cambridge, UK, Tech. Rep., 1998.
可观测性. [2020-04-29]. (原始內容存檔於2020-11-22).