粒子濾波器

粒子濾波器來表示隨機事件的後驗機率，從含有雜訊或不完整的觀測序列，估計出動態系統的狀態，粒子濾波器可以運用在任何狀態空間的模型上。粒子濾波器是卡爾曼濾波器的一般化方法，卡爾曼濾波器建立線上性的狀態空間和高斯分佈的雜訊上；而粒子濾波器的狀態空間模型可以是非線性，且雜訊分佈可以是任何型式。歷史.啟發式演演算法.從統計和機率的角度來看，粒子濾波器屬於遺傳演算法分支過程的類別，並且是指平均場型別相互作用的粒子方法。 這些粒子方法的解釋取決於科學專業。 在進化計算中，平均場遺傳型別粒子方法通常用作啟發式和自然搜尋演算法。在計算物理學和分子化學中，它們用於解決費曼-卡茲(Feynman-Kac)路徑積分問題，或者用於計算玻爾茲曼-吉布斯(Boltzmann-Gibbs)度量，薛丁格運算元的最高特徵值和基態。在生物學與遺傳學中，它們還代表了某些環境中一群個體或基因的進化。平均場型別進化計算技術的起源可以追溯到1950年和1954年，這是艾倫·圖靈在遺傳型別突變選擇學習機上的開創性工作，以及紐澤西州普林斯頓高階研究所的尼爾斯·艾爾·巴里切利(Nils Aall Barricelli)的文章。統計學中的粒子濾波器最早可追溯到1950年代中期。哈默斯利(Hammersley)等人在1954年提出的“窮人的蒙特卡洛”法暗示了當今使用的遺傳型別粒子過濾方法。 1963年，尼爾斯·艾爾·巴里切利(Nils Aall Barricelli)模擬了一種遺傳型別演算法，以模仿個人玩簡單遊戲的能力。在進化計算，遺傳型別突變選擇演算法透過1970年代初期約翰·霍蘭德(John Holland)的開創性工作而流行，特別是1975年出版的著作。在生物學與遺傳學中，澳大利亞遺傳學家亞歷克斯·弗雷澤的書中進行了描述。弗雷澤的模擬包括了現代突變選擇遺傳粒子演算法的所有基本要素。從數學觀點來看，給定一些部分和雜訊觀測結果的訊號隨機狀態的條件分佈，是由訊號的隨機軌跡上的費曼-卡茲(Feynman-Kac)機率描述的，該機率由一系列似然勢函式加權。量子蒙特卡洛法，更具體地說是擴散蒙特卡洛法，也可以解釋為費曼-卡茲路徑積分的平均場遺傳型別粒子近似。量子蒙特卡羅方法的起源通常歸因於恩里科·費米(Enrico Fermi)和羅伯特·里克特邁耶(Robert Richtmyer)，他們於1948年開發了一種中子鏈反應的均值場粒子解釋方法，但它是第一個類似啟發式和遺傳型別的粒子演算法和阿里安娜·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來解決RADAR / SONAR和GPS訊號處理問題。數學基礎.從1950年到1996年，所有有關粒子過濾器，遺傳演算法的出版物，包括在計算物理和分子化學中引入的修剪和重取樣蒙特卡洛方法，都提出了適用於不同情況的類似於自然和啟發式演算法，而沒有任何證據證明它們的一致性，也沒有討論估計的偏差以及基於族譜和祖先樹的演算法。這些粒子演算法的數學基礎和首次嚴格的分析是由皮埃爾·德爾·莫拉爾(Pierre Del Moral)在1996年提出的。本文還包含了似然函式和未標準化的條件機率測度的粒子近似的無偏性質的證明。本文介紹的似然函式的無偏粒子估計器如今已用於貝式統計推理中。到1990年代末，Dan Crisan，Jessica Gaines和Terry Lyons以及Dan Crisan，Pierre Del Moral和Terry Lyons也開發了具有不同種群大小的分支型別粒子方法。 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年的書中得到發展。這些抽象的機率模型封裝了遺傳型別演算法，粒子和自舉濾波器，互動的卡爾曼濾波器，重要性取樣和重取樣樣式的粒子濾波器技術，包括基於族譜樹的方法和用於解決濾波和平滑問題的粒子後向方法。其他類別的粒子濾波方法包括基於族譜樹的模型，後向馬爾可夫粒子模型，自適應平均場粒子模型，島型粒子模型和粒子馬爾可夫鏈蒙特卡羅方法。濾波問題.目標.粒子濾波器的目標是透過觀測值估計狀態變數的後驗機率。粒子濾波器是針對隱馬爾可夫模型設計的，系統中既包含隱藏的變數，也包含可觀測的變數。可觀測變數透過某種已知的函式關係相關聯。類似地，描述狀態變數演化的動態系統也是機率學上已知的。一個通用粒子濾波器透過觀察測量過程估計隱藏狀態的後驗分佈。考察下圖所示的狀態空間：formula_1濾波問題是要透過給定的觀測過程 formula_2 在任意時刻 "k" 的值，序列地估計隱藏狀態 formula_3 的值。所有的對 formula_3 的貝葉斯估計服從後驗分佈 "p"("x""k" | "y"0,"y"1,…,"y""k") 。粒子濾波器方法使用經驗測量和通用粒子演算法，提供了這些條件機率的近似值。與之對比，馬爾可夫鏈蒙特卡洛或重要性取樣方式會對整個後驗機率 "p"("x"0,"x"1,…,"x""k" | "y"0,"y"1,…,"y""k") 進行建模。訊號-觀測模型.粒子濾波器能夠從一系列含有雜訊或不完整的觀測值中，估計出動態系統的內部狀態。在動態系統的分析中，需要兩個模型，一個用來描述狀態隨時間的變化(系統模型)，另一個用來描述每個狀態下觀測到的雜訊(觀測模型)，將這兩個模型都用機率來表示。在許多情況下，每得到一個新的觀測值時，都必須對系統做出一次估計，利用遞迴濾波器，能夠有效地達到這樣的目的。遞迴濾波器會對得到的資料做連續處理，而非分批處理，因此不需要將完整的資料儲存起來，也不需要在得到新的觀測值時，將現有的資料重新做處理。遞迴濾波器包含兩個步驟：預測：利用系統模型，由前一個狀態的資訊預測下一個狀態的機率密度函式。更新：利用最新的觀測值，修改預測出的機率密度函式。藉由貝葉斯推論(Baysian inference)，我們可以描述出狀態空間的機率，並在得到新的觀測值時，對系統做出更新，因而達成上述目的。近似貝式計算模型.在某些問題中，在訊號的隨機狀態下，觀測值的條件分佈可能不具有密度，或者不可能或太複雜而無法計算。在這種狀況下，我們需要求近似值。其中一個策略是藉由馬爾可夫鏈formula_5來取代訊號 formula_3 ，採用虛擬觀測的形式formula_7對於具有已知機率密度函式的獨立序列中的某些序列，核心的概念是觀測此式子(公式)formula_8在部分的觀測 formula_9 之下，粒子濾波器是和馬爾可夫鏈 formula_5 有相關的，定義為根據演化出的 formula_11 ，在一些明顯的濫用性符號 formula_12 下，帶有似然函式的粒子。這些機率性的技術跟近似貝式計算非常相關。在量子濾波器中，這些近似貝式量子濾波器的技術在1998年被皮埃爾·德爾·莫拉爾(P. Del Moral), 讓·雅各德(J. Jacod)和菲力普·普羅特(P. Protter)所採用。且被皮埃爾·德爾·莫拉爾, 阿諾·杜斯(A. Doucet)和 阿傑·賈斯拉(A. Jasra)更進一步發展。非線性濾波方程.藉由貝式定理在條件機率中可以得出formula_13當formula_14粒子濾波器也是一個近似值，當有足夠的粒子時，結果會更加的準確。非線性濾波方程可以藉由遞迴得出&amp;\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{align}依照慣例 formula_15 在k=0時。非線性濾波方程問題的關鍵在於依序計算這些條件機率分佈。費曼-卡茲公式.固定一個時間範圍和一個序列的觀測 formula_16 ，在k=0...n，我們定義:formula_17在這種表示法中，對於從原點k = 0到時間k = n的 軌跡集合上的任何有界函式F，我們都可以用費曼-卡茲公式來表示formula_18這些費曼-卡茲路徑積分模型出現在各種科學學科中，包括計算物理，生物學，資訊理論和電腦科學。他們的解釋取決於應用領域。舉例來說，如果我們選擇狀態空間某些子集的指標函式formula_19，它們代表馬爾可夫鏈在給定管中的條件分佈。我們會得到:formula_20和formula_21只要標準化常數嚴格為正。非線性貝葉斯追蹤.在動態系統中，我們常常需要對物體做追蹤。假設有一動態系統，已知其狀態序列formula_22定義為formula_23其中formula_24是狀態轉移函式，可以是非線性的函式，formula_25是一個獨立且相同分佈(i.i.d.)的過程雜訊序列，formula_26和formula_27分別代表狀態和過程雜訊向量的維度，formula_28為自然數的集合。追蹤的目標是要遞迴地從觀測值formula_29估計出formula_30，而觀測值formula_29定義為formula_32其中formula_33是觀測函式，可以是非線性的函式，formula_34是一個獨立且相同分佈(i.i.d.)的觀測雜訊序列，formula_35和formula_36分別代表觀測值和觀測雜訊向量的維度。從貝葉斯理論的觀點來看，追蹤問題是要根據到時間formula_37為止的已知資訊formula_38，遞迴地計算出時間formula_37的狀態formula_30的可信度，這個可信度用機率密度函式formula_41來表示。假設初始機率密度函式formula_42(稱為先驗機率)為已知，則利用「預測」和「更新」兩個步驟就能遞迴地計算出機率密度函式formula_41。在此假設在時間formula_44的機率密度函式formula_45為已知。預測.利用查普曼-科爾莫戈羅夫等式(Chapman–Kolmogorov equation)，可以由狀態轉移函式與時間formula_44的機率密度函式formula_45，計算出時間formula_37的先驗機率formula_49formula_50其中，由於狀態轉移模型被假設為一階馬可夫過程，時間formula_44的狀態只由時間formula_37決定，因此formula_53。機率模型formula_54由狀態轉移函式formula_23和formula_56的統計值得到。更新.在時間formula_37，我們得到觀測值formula_29，因此可以利用貝氏定理，由先驗機率formula_49得到後驗機率formula_41，也就是考慮觀測值後得到的機率。formula_61其中的歸一化常數為formula_62其中的似然函式formula_63由觀測函式formula_32和formula_65的統計值得到。上述「預測」與「更新」的遞迴關係，是貝葉斯最佳解的基本概念，然而公式中運用到的積分，對於一般非線性、非高斯的系統，難以得到解析解，因此需要利用蒙地卡羅方法來近似貝葉斯最佳解。序列重要性重取樣(Sequential Importance Resampling, SIR).序列重要性取樣(Sequential Importance Sampling, SIS).SIR是由SIS加上重取樣(resampling)改良而來，在SIS中，我們將後驗機率formula_41用formula_28個隨機取樣的樣本(稱為粒子)與各自的權重表示為formula_68其中的權重是根據重要性取樣的規則產生，且必須符合formula_69SIS是將重要性取樣遞迴執行的一種方法，根據重要性取樣的理論，一個函式formula_70的期望值可以用加權平均來近似formula_71在每一次遞迴過程中，我們希望由前一次取樣的權重，計算出下一次取樣的權重。假設取樣的樣本分佈可以表示為formula_72 formula_73其中formula_74稱為重要性密度(importance density)。若樣本formula_75是由重要性密度formula_76抽取出來，則權重可表示為formula_77我們將重要性密度分解為formula_78再將後驗機率表示為formula_79則權重的遞迴式可以表示為formula_80重取樣.SIS可能會造成退化問題，也就是在經過幾次遞迴後，很多粒子的權重都變小到可以忽略不計，只剩少數粒子的權重較大，如此會浪費大量的計算量在幾乎沒有作用的粒子上，而使估計效能下降。由於在遞迴過程中，權重的變異數只會愈來愈大，因此退化問題無法被避免。為了評估退化問題，我們定義有效粒子數為formula_81在進行SIS時，若有效粒子數小於某一閾值，則對粒子做重取樣，即可減緩退化問題。重取樣的概念是去除權重過小的粒子，專注於權重較大的粒子。進行重取樣時，要由現有的粒子分佈取樣，產生一組新的粒子formula_82，由於產生出的新樣本為獨立且相同分佈(i.i.d.)，因此將權重重新設定為formula_83。