[PF-2] SIS에서 파티클 필터로

전체 조건부 확률밀도함수 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 순차 샘플링 ${\mathbf{x}}_{0:t}^{(i)}$ 로 다음과 같이 근사화 할 수 있었다.

 

$$\begin{array}{}\text{(1)}& p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})\approx \sum _{i=1}^N{w}_t^{(i)}\delta ({\mathbf{x}}_{0:t}-{\mathbf{x}}_{0:t}^{(i)})\end{array}$$

 

베이즈 필터는 상태변수 ${\mathbf{x}}_t$ 의 조건부 확률밀도함수인 사후 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 계산하기 위한 것이므로 식 (1)에서 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 유도해 낼 필요가 있다.

 

 

$p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 는 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 의 한계밀도함수이므로 다음 식이 성립한다.

 

$$\begin{array}{r}\text{(2)}& p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})& ={\int }_{{\mathbf{x}}_{0:t-1}}p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})d{\mathbf{x}}_{0:t-1}\\ & \approx {\int }_{{\mathbf{x}}_{0:t-1}}\sum _{i=1}^N{w}_t^{(i)}\delta ({\mathbf{x}}_{0:t}-{\mathbf{x}}_{0:t}^{(i)})d{\mathbf{x}}_{0:t-1}\\ \\ & =\sum _{i=1}^N{w}_t^{(i)}{\int }_{{\mathbf{x}}_{0:t-1}}\delta ({\mathbf{x}}_{0:t}-{\mathbf{x}}_{0:t}^{(i)})d{\mathbf{x}}_{0:t-1}\end{array}$$

 

여기서 디랙 델타(Dirac delta) 함수 $\delta ({\mathbf{x}}_{0:t})$ 를 전개하면 다음과 같으므로,

 

$$\begin{array}{}\text{(3)}& \delta ({\mathbf{x}}_{0:t})=\delta ({\mathbf{x}}_0)\delta ({\mathbf{x}}_1)\cdots \delta ({\mathbf{x}}_t)\end{array}$$

 

식 (2)는 다음과 같이 된다.

 

$$\begin{array}{}\text{(4)}& p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})\approx \sum _{i=1}^N{w}_t^{(i)}\delta ({\mathbf{x}}_t-{\mathbf{x}}_t^{(i)})\end{array}$$

 

그러면 ${\mathbb{E}}_{{\mathbf{x}}_t\sim p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}[{\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}]$ 는 순차 샘플 ${\mathbf{x}}_t^{(i)}\sim q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1}^{(i)},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 과 중요 가중치 $w_t^{(i)}$ 를 이용하여 다음과 같이 근사적으로 계산할 수 있다.

 

$$\begin{array}{}\text{(5)}& {\mathbb{E}}_{{\mathbf{x}}_t\sim p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}[{\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}]\approx \sum _{i=1}^N{w}_t^{(i)}{\mathbf{x}}_t^{(i)}\end{array}$$

 

여기서 중요 가중치 $w_t^{(i)}$ 는 순차 중요 샘플링(SIS, sequential importance sampling) 알고리즘으로 주어진다.

 

$$\begin{array}{}\text{(6)}& w_t^{(i)}\propto \frac{p({\mathbf{z}}_t|{\mathbf{x}}_t^{(i)})p({\mathbf{x}}_t^{(i)}|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1})}{q({\mathbf{x}}_t^{(i)}|{\mathbf{x}}_{0:t-1}^{(i)},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}{w}_{t-1}^{(i)}\end{array}$$

 

파티클 필터(PF, particle filter)의 기본 알고리즘은 SIS를 이용한 상태변수의 샘플링과 중요 가중치 계산을 반복하는 재귀식으로 구성되어 있다.

식 (6)에서 중요밀도함수는 샘플(또는 파티클)을 추출할 수 있는 밀도함수이며 이 샘플로 중요 가중치(importance weight) $w_t^{(i)}$ 를 계산하기 때문에 이 중요밀도함수의 선정은 파티클 필터의 성능을 좌우하는 중요한 문제다. 몇 가지 선택 방법에 대해서 알아본다.

 

 

먼저 가장 간단한 방법으로서 중요밀도함수를 다음과 같이 선정하는 방법이 있다.

 

$$\begin{array}{}\text{(7)}& q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})=p({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})\end{array}$$

 

여기서 $p({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})$ 는 시스템의 모델을 나타낸다. 만약 시스템 모델이 다음과 같이 주어졌다면,

 

$$\begin{array}{}\text{(8)}& {\mathbf{x}}_t=\mathbf{f}({\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1},{\mathbf{w}}_{t-1}),{\mathbf{w}}_{t-1}\sim N(0,Q_{t-1})\end{array}$$

 

프로세스 노이즈 ${\mathbf{w}}_{t-1}\sim N(0,Q_{t-1})$ 를 먼저 샘플링 한 후, 샘플 ${\mathbf{x}}_t^{(i)}=\mathbf{f}({\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1},{\mathbf{w}}_{t-1}^{i)})$ 을 계산할 수 있다. 또는 노이즈가 덧셈형으로 주어진 시스템이라면

 

$$\begin{array}{}\text{(9)}& {\mathbf{x}}_t=\mathbf{f}({\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})+{\mathbf{w}}_{t-1},{\mathbf{w}}_{t-1}\sim N(0,Q_{t-1})\end{array}$$

 

$p({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})=N(\mathbf{f}({\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1}),Q_{t-1})$ 이므로 쉽게 샘플 ${\mathbf{x}}_t^{(i)}\sim p({\mathbf{x}}_t|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1})=N(\mathbf{f}({\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1}),Q_{t-1})$ 을 추출할 수 있다.

식 (7)을 (6)에 대입하면 중요 가중치는 다음과 같이 전파된다.

 

$$\begin{array}{}\text{(10)}& w_t^{(i)}\propto p({\mathbf{z}}_t|{\mathbf{x}}_t^{(i)})w_{t-1}^{(i)}\end{array}$$

 

이 방법은 간단한 반면에 시간스텝 $t$ 에서 ${\mathbf{x}}_t^{(i)}$ 를 샘플링할 때 최신 측정값 ${\mathbf{z}}_t$ 에 관한 정보를 이용하지 않기 때문에 식 (9)로 중요 가중치를 계산할 때 빈도함수(likelihood) $p({\mathbf{z}}_t|{\mathbf{x}}_t)$ 의 범위 내에 있는 몇 개의 샘플만 큰 가중치를 가질 수 있다. 따라서 중요 가중치의 분산이 매우 커질 수 있다.

 

 

두번째는 가장 인기있는 방법으로서 부트스트랩 필터(bootstrap filter)로 알려진 방법이다. 샘플링은 첫번째 방법과 동일하게 한다. 그러면 식 (10)으로 주어지는 중요 가중치 전파식을 얻을 수 있다. 부트스트랩 방법은 여기서 더 나아가 모든 시간스텝에서 재샘플링(resampling)을 수행한다. 그러면 $w_{t-1}^{(i)}=\frac{1}{N},i=1,...,N$ 이 되기 때문에 식 (10)은 다음과 같이 쓸 수 있다.

 

$$\begin{array}{}\text{(11)}& w_t^{(i)}\propto p({\mathbf{z}}_t|{\mathbf{x}}_t^{(i)})\end{array}$$

 

식 (11)이 의미하는 바는 첫번째 방법과는 달리 중요 가중치가 다음 시간스텝으로 전파되지 않는다는 것이다. 이 방법의 단점은 첫번째 방법과 마찬가지로 시간스텝 $t$ 에서 ${\mathbf{x}}_t^{(i)}$ 를 샘플링할 때 최신 측정값 ${\mathbf{z}}_t$ 에 관한 정보를 이용하지 않기 때문에 중요 가중치의 분산이 매우 커질 수 있다는 것과 또한 매 시간스텝마다 재샘플링하기 때문에 파티클의 다양성을 상실할 수 있다는 점이다. 사실 재샘플링은 순차 중요 샘플링(SIS) 방법에서는 피할 수 없는 과정이다. 이에 대해서는 다음에 논하기로 한다.

부트스트랩 방법의 장점으로는 중요 가중치를 쉽게 계산할 수 있다는 것과 샘플링이 쉽다는 것이다.

세번째 방법은 최적 중요 확률밀도함수를 선택하는 것이다. 최적 중요 확률밀도함수란 중요 가중치의 분산을 최소로 만드는 밀도함수로서 본래 샘플링하고자 하는 확률밀도함수와 동일하게 정하는 것이다.

 

$$\begin{array}{r}\text{(12)}& & q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})=q({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{z}}_t,{\mathbf{u}}_{t-1})\\ & =p({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{z}}_t,{\mathbf{u}}_{t-1})\\ \\ & =\frac{p({\mathbf{z}}_t|{\mathbf{x}}_t,{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})p({\mathbf{x}}_t|{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})}{p({\mathbf{z}}_t|{\mathbf{x}}_{t-1},{\mathbf{u}}_{t-1})}\end{array}$$

 

식 (12)를 식 (6)에 대입하면 다음과 같다.

 

$$\begin{array}{}\text{(13)}& w_t^{(i)}\propto p({\mathbf{z}}_t|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1})w_{t-1}^{(i)}\end{array}$$

 

식 (13)에 의하면 시간스텝 $t$ 에서 중요 가중치는 샘플이 시간스텝 $t$ 로 전파되기 전에 계산할 수 있다.

이 방법을 사용하게 위해서는 먼저 $p({\mathbf{x}}_t|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{z}}_t,{\mathbf{u}}_{t-1})$ 에서 샘플을 추출할 수 있어야 한다. 그리고 다음 적분식을 풀 수 있어야 한다.

 

$$\begin{array}{}\text{(14)}& p({\mathbf{z}}_t|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1})={\int }_{{\mathbf{x}}_t}p({\mathbf{z}}_t|{\mathbf{x}}_t)p({\mathbf{x}}_t|{\mathbf{x}}_{t-1}^{(i)},{\mathbf{u}}_{t-1})d{\mathbf{x}}_t\end{array}$$

 

특별한 경우를 제외하고는 두가지를 충족하기가 쉽지 않다. 하지만 이 부분에 주목하여 언센티드 파티클필터(Unscented Particle Filter)등 여러가지 새로운 필터가 개발되었다.

이제, 중요 가중치를 계산하는 방법과 샘플링을 하기 위한 중요밀도함수까지 정했으므로 파티클 필터의 알고리즘이 완성된 된 것 같지만, 아직 해결해야 할 중요한 문제가 남아있다. 바로 퇴화(degeneracy), 곤궁(impoverishment) 또는 샘플 마모(sample attrition)로 불리는 문제다. 이에 대해서는 다음에 논하기로 한다.