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

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

 

\[ 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)} ) \tag{1} \]

 

베이즈 필터는 상태변수 \(\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{align} 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} \tag{2} \\ \\ & \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{align} \]

 

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

 

\[ \delta (\mathbf{x}_{0:t} ) = \delta (\mathbf{x}_0 ) \delta (\mathbf{x}_1 ) \cdots \delta (\mathbf{x}_t ) \tag{3} \]

 

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

 

\[ 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)} ) \tag{4} \]

 

그러면 \(\mathbb{E}_{\mathbf{x}_t \sim p(\mathbf{x}_t | \mathbf{z}_{0:t}, \mathbf{u}_{0:t-1})} \left[ \mathbf{x}_t | \mathbf{z}_{0:t}, \mathbf{u}_{0:t-1} \right] \) 는 순차 샘플 \(\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) }\) 를 이용하여 다음과 같이 근사적으로 계산할 수 있다.

 

\[ \mathbb{E}_{\mathbf{x}_t \sim p(\mathbf{x}_t | \mathbf{z}_{0:t}, \mathbf{u}_{0:t-1})} \left[ \mathbf{x}_t | \mathbf{z}_{0:t}, \mathbf{u}_{0:t-1} \right] \approx \sum_{i=1}^N w_t^{(i)} \mathbf{x}_t^{(i)} \tag{5} \]

 

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

 

\[ 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)} \tag{6} \]

 

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

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

 

 

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

 

\[ 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}) \tag{7} \]

 

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

 

\[ \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}) \tag{8} \]

 

프로세스 노이즈 \(\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)})\) 을 계산할 수 있다. 또는 노이즈가 덧셈형으로 주어진 시스템이라면

 

\[ \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}) \tag{9} \]

 

\(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)에 대입하면 중요 가중치는 다음과 같이 전파된다.

 

\[ w_t^{(i) } \propto p(\mathbf{z}_t | \mathbf{x}_t^{(i) } ) \ w_{t-1}^{(i)} \tag{10} \]

 

이 방법은 간단한 반면에 시간스텝 \(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)은 다음과 같이 쓸 수 있다.

 

\[ w_t^{(i) } \propto p(\mathbf{z}_t | \mathbf{x}_t^{(i) } ) \tag{11} \]

 

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

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

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

 

\[ \begin{align} & 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} ) \tag{12} \\ \\ & \ \ \ \ \ \ \ \ \ \ = 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{align} \]

 

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

 

\[ w_t^{(i) } \propto p(\mathbf{z}_t | \mathbf{x}_{t-1}^{(i)}, \mathbf{u}_{t-1}) \ w_{t-1}^{(i)} \tag{13} \]

 

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

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

 

\[ 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 \tag{14} \]

 

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

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