# 粒子濾波器

## 滤波问题

### 目标

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

### 近似貝式計算模型

${\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}$

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

### 非線性濾波方程

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

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

{\displaystyle {\begin{aligned}p(x_{k}|y_{0},\cdots ,y_{k-1})&{\stackrel {\text{updating}}{\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{aligned}}}

(Eq. 1)

### 費曼-卡茲公式

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

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

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

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

## 非線性貝葉斯追蹤

${\displaystyle x_{k}=f_{k}(x_{k-1},v_{k-1})}$

${\displaystyle y_{k}=h_{k}(x_{k},n_{k})}$

### 預測

{\displaystyle {\begin{aligned}p(x_{k}\mid y_{1:k-1})&=\int p(x_{k},x_{k-1}\mid y_{1:k-1})d{x_{k-1}}\\&=\int p(x_{k}\mid x_{k-1},y_{1:k-1})p(x_{k-1}\mid y_{1:k-1})d{x_{k-1}}\\&=\int p(x_{k}\mid x_{k-1})p(x_{k-1}\mid y_{1:k-1})d{x_{k-1}}\\\end{aligned}}}

### 更新

${\displaystyle p(x_{k}\mid y_{1:k})={p(y_{k}\mid x_{k})p(x_{k}\mid y_{1:k-1}) \over p(y_{k}\mid y_{1:k-1})}}$

${\displaystyle p(y_{k}\mid y_{1:k-1})=\int p(y_{k}\mid x_{k})p(x_{k}\mid y_{1:k-1})dx_{k}}$

## 序列重要性重採樣(Sequential Importance Resampling, SIR)

### 序列重要性採樣(Sequential Importance Sampling, SIS)

SIR是由SIS加上重採樣(resampling)改良而來，在SIS中，我們將後驗機率${\displaystyle p(x_{k}\mid y_{1:k})}$${\displaystyle N}$個隨機採樣的樣本(稱為粒子)與各自的權重表示為

${\displaystyle {\{x_{k}^{(i)},w_{k}^{(i)}\}}_{i=1}^{N}}$

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

SIS是將重要性採樣遞迴執行的一種方法，根據重要性採樣的理論，一個函數${\displaystyle f}$的期望值可以用加權平均來近似

${\displaystyle \int f(x_{k})p(x_{k}\mid y_{1:k})dx_{k}\approx \sum _{i=1}^{N}w_{k}^{(i)}f(x_{k}^{(i)})=1}$

${\displaystyle x^{(i)}\sim q(x),}$ ${\displaystyle i=1,...,N}$

${\displaystyle w_{k}^{(i)}\propto {p(x_{k}^{(i)}\mid y_{1:k}) \over q(x_{k}^{(i)}\mid y_{1:k})}}$

${\displaystyle q(x_{k}\mid y_{1:k})=q(x_{k}\mid x_{k-1},y_{1:k})q(x_{k-1}\mid y_{1:k-1})}$

{\displaystyle {\begin{aligned}p(x_{k}\mid y_{1:k})&={p(y_{k}\mid x_{k},y_{1:k-1})p(x_{k}\mid y_{1:k-1}) \over p(y_{k}\mid y_{1:k-1})}\\&={p(y_{k}\mid x_{k},y_{1:k-1})p(x_{k}\mid x_{k-1},y_{1:k-1})p(x_{k-1}\mid y_{1:k-1}) \over p(y_{k}\mid y_{1:k-1})}\\&={p(y_{k}\mid x_{k})p(x_{k}\mid x_{k-1})p(x_{k-1}\mid y_{1:k-1}) \over p(y_{k}\mid y_{1:k-1})}\\&\propto p(y_{k}\mid x_{k})p(x_{k}\mid x_{k-1})p(x_{k-1}\mid y_{1:k-1})\\\end{aligned}}}

{\displaystyle {\begin{aligned}w_{k}^{(i)}&\propto {p(y_{k}\mid x_{k}^{(i)})p(x_{k}^{(i)}\mid x_{k-1}^{(i)})p(x_{k-1}^{(i)}\mid y_{1:k-1}) \over q(x_{k}^{(i)}\mid x_{k-1}^{(i)},y_{1:k})q(x_{k-1}^{(i)}\mid y_{1:k-1})}\\&=w_{k-1}^{(i)}{p(y_{k}\mid x_{k}^{(i)})p(x_{k}^{(i)}\mid x_{k-1}^{(i)}) \over q(x_{k}^{(i)}\mid x_{k-1}^{(i)},y_{1:k})}\\\end{aligned}}}

### 重採樣（resampling）

SIS可能會造成退化問題（degeneracy problem），也就是在經過幾次遞迴後，很多粒子的權重都變小到可以忽略不計，只剩少數粒子的權重較大，如此會浪費大量的計算量在幾乎沒有作用的粒子上，而使估計性能下降。由於在遞迴過程中，權重的變異數只會愈來愈大，因此退化問題無法被避免。

${\displaystyle {\widehat {N_{eff}}}={1 \over \sum _{i=1}^{N}(w_{k}^{(i)})^{2}}}$

## 參考文獻

1. 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.
2. 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
3. A. Doucet, "On sequential Monte Carlo methods for Bayesian filtering." Dept. Eng., Univ. Cambridge, UK, Tech. Rep., 1998.
1. ^ 可观测性. [2020-04-29].