[PF-1] 순차 중요 샘플링 (Sequential Importance Sampling)

베이즈 필터(Bayes filter) 문제는 측정값의 시퀀스 ${\mathbf{z}}_{0:t}$ 와 제어입력의 시퀀스 ${\mathbf{u}}_{0:t-1}$ 을 조건으로 한 상태변수 ${\mathbf{x}}_t$ 의 조건부 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 을 계산하는 문제였다.

 

 

상태변수 ${\mathbf{x}}_t$ 의 사후(posterior) 조건부 확률밀도함수$p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 이 주어지면 다양한 종류의 상태변수 추정이 가능하다. 예를 들어 칼만필터(Kalman filter)는 최적 MMSE(minimum mean-square error) 추정값을 계산하는 필터로서 상태변수${\mathbf{x}}_t$ 의 추정값을 ${\hat{\mathbf{x}}}_t=\mathbb{E}[{\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})$ 을 계산할 수 있는 경우는 극히 제한적이다. 따라서 수치적인 계산 방법이 필요한데 그 중의 하나가 샘플링(sampling)을 이용하는 방법이다.

디랙 델타(Dirac delta) 함수 $\delta (\mathbf{x})$ 를 이용하면 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 을 다음과 같이 근사화 할 수 있다.

 

$$\begin{array}{}\text{(1)}& 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}$$

 

여기서 ${\mathbf{x}}_t^{(i)}$ 는 확률밀도함수가 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 인 모집단에서 추출한 샘플(또는 파티클)이다. $N$ 개의 샘플이 독립적이고 공평하게 추출됐다면(iid 샘플) 각 샘플이 추출될 확률 $w_t^{(i)}$ 는 다음과 같이 동일하게 주어진다.

 

$$\begin{array}{}\text{(2)}& w_t^{(i)}=P\{{\mathbf{x}}_t={\mathbf{x}}_t^{(i)}\}=\frac{1}{N}\end{array}$$

 

그러면 ${\mathbf{x}}_t$ 의 함수인 $\mathbf{f}({\mathbf{x}}_t)$ 의 기댓값 $\mathbb{E}[\mathbf{f}({\mathbf{x}}_t)|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}]$ 는 다음과 같이 샘플 평균(sample mean)으로 추정할 수 있다.

 

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

 

여기서 문제는 사후 확률밀도함수인 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 로부터 샘플을 추출할 수 있는가이다. 보통 임의의 확률밀도함수에서 샘플을 직접 추출하는 것은 사실상 불가능하다. 그래서 대신 쉽게 샘플을 추출할 수 있는 확률밀도함수인 중요분포(importance distribution)함수 $q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 도입한다.

중요 샘플링(importance sampling)에 의하면 ${\mathbf{x}}_t$ 의 기댓값은 다음과 같이 표현할 수 있다.

 

$$\begin{array}{r}\text{(4)}& & {\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}]\\ & ={\int }_{{\mathbf{x}}_t}{\mathbf{x}}_{t}p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})d{\mathbf{x}}_t\\ \\ & ={\int }_{{\mathbf{x}}_t}{\mathbf{x}}_{t}p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})\frac{q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}{q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}d{\mathbf{x}}_t\\ \\ & ={\int }_{{\mathbf{x}}_t}\left({\mathbf{x}}_t\frac{p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}{q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}\right)q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})d{\mathbf{x}}_t\\ \\ & ={\mathbb{E}}_{{\mathbf{x}}_t\sim q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}[\left({\mathbf{x}}_t\frac{p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}{q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}\right)|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}]\end{array}$$

 

식 (4)에 의하면 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 을 ${\mathbf{x}}_t^{(i)}\sim q({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에서 추출한 샘플을 이용하여 다음과 같이 근사화할 수 있다.

 

$$\begin{array}{}\text{(5)}& 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}$$

 

여기서 $w_t^{(i)}$ 를 중요 가중치(importance weights)라고 하며 다음과 같이 계산한다.

 

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

 

식 (5)에서 근사화된 확률밀도함수도 확률밀도함수의 성질을 가져야 하므로 중요 가중치 $w_t^{(i)}$ 는 항상 정규화 되어야 한다. 즉,

 

$$\begin{array}{}\text{(7)}& \sum _{i=1}^N{w}_t^{(i)}=1\end{array}$$

 

식 (4), (5)와 (6)에 의하면 ${\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{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 과 그 샘플의 중요도를 나타내는 중요 가중치 $w_t^{(i)}$ 를 이용하여 다음과 같이 근사적으로 계산할 수 있다.

 

$$\begin{array}{}\text{(8)}& {\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}$$

 

 

 

한편, 순차 중요 샘플링(SIS, sequential importance sampling)은 중요 샘플링의 순차적인 버전이다. SIS는 베이즈 필터에서 고려했던 상태변수 ${\mathbf{x}}_t$ 의 조건부 확률밀도함수인 사후 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 대신에 이를 시간스텝 0부터 t까지의 전체 상태변수 시퀀스 ${\mathbf{x}}_{0:t}$ 로 확장시킨 전체 조건부 확률밀도함수 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 을 다룬다.

이 확률밀도함수를 근사화 하기 위해서 중요 샘플링에서 했던 것과 같이 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t}^{(i)}$ 를 샘플링해야 하는데, 시간스텝이 증가할 때 마다 새로운 시퀀스를 다시 샘플링하는 것이 아니라 한 시간스텝 전까지 샘플링된 시퀀스 ${\mathbf{x}}_{0:t-1}^{(i)}$ 에다가 현재 시간스텝 $t$ 에서 추가적으로 샘플링한 $N$ 개의 샘플 ${\mathbf{x}}_t^{(i)}$ 를 덧붙여서 샘플링 시퀀스 ${\mathbf{x}}_{0:t}^{(i)}$ 를 만드는 방법을 사용한다. 즉 '순차적인 버전' 이란 시간스텝 $t$ 가 증가하면서 순차적으로 샘플링한다는 의미다.

 

$${\mathbf{x}}_{0:t}^{(i)}=\{{\mathbf{x}}_{0:t-1}^{(i)},{\mathbf{x}}_t^{(i)}\}$$

 

 

 

전체 조건부 확률밀도함수 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 을 전개해 보자.

 

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

 

여기서 $\eta =\frac{1}{p({\mathbf{z}}_t|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-1})}$ 는 정규화 항이고, 베이즈 필터에서 사용한 마르코프 시퀀스와 비메모리 측정 모델 가정을 이용하였다.

 

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

 

중요 샘플링 방법과 마찬가지로 중요분포함수 $q({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에서 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t}^{(i)}$ 를 샘플링한다면 중요 가중치는 다음과 같이 계산할 수 있다.

 

$$\begin{array}{}\text{(11)}& 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})p({\mathbf{x}}_{0:t-1}^{(i)}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})}{q({\mathbf{x}}_{0:t}^{(i)}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}\end{array}$$

 

여기서 중요분포함수에 다음과 같은 가정을 한다.

 

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

 

식 (12)는 순차적인 샘플링을 가능하게 하는 가정이다(중요분포함수를 한 스텝 전개하면 $q({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})=q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})q({\mathbf{x}}_{0:t-1}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 가 되나 $q({\mathbf{x}}_{0:t-1}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})=q({\mathbf{x}}_{0:t-1}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})$로 가정한 것이다. 중요분포함수는 설계자의 선택의 문제이므로 타당한 가정이다). 식 (12)를 반복하면 다음과 같은 연쇄적인 식을 얻을 수 있다.

 

$$\begin{array}{}\text{(13)}& q({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})=q({\mathbf{x}}_0)\prod _{k=1}^{t}q({\mathbf{x}}_k|{\mathbf{x}}_{0:k-1},{\mathbf{z}}_{0:k},{\mathbf{u}}_{0:k-1})\end{array}$$

 

식 (13)에 의하면 $q({\mathbf{x}}_{0:t-1}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})$ 에서 샘플링한 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t-1}^{(i)}$ 에 중요분포인 $q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에서 샘플링한 $N$ 개의 샘플 ${\mathbf{x}}_t^{(i)}$ 를 합치면 $q({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에서 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t}^{(i)}$ 를 샘플링 한 것이 된다.

식 (12)를 식 (11)에 대입하면 중요 가중치는 다음과 같이 된다.

 

$$\begin{array}{}\text{(14)}& 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})}\frac{p({\mathbf{x}}_{0:t-1}^{(i)}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})}{q({\mathbf{x}}_{0:t-1}^{(i)}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})}\end{array}$$

 

그런데 여기서

 

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

 

이므로 시간스텝 $t$ 에서의 중요 가중치와 시간스텝 $t-1$ 에서의 중요 가중치는 다음과 같이 재귀(recursive)식 (보통 재귀식이라고 번역하는데 순 우리말인 도돌이식이라고 번역하는 것도 괜찮을 것 같다)을 만족하게 된다.

 

$$\begin{array}{}\text{(16)}& 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}$$

 

정리하면 $q({\mathbf{x}}_{0:t-1}|{\mathbf{z}}_{0:t-1},{\mathbf{u}}_{0:t-2})$ 에서 샘플링한 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t-1}^{(i))}$ 의 중요 가중치가 $w_{t-1}^{(i)}$ 라고 할 때, $q({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$에서 샘플링한 $N$ 개의 시퀀스 ${\mathbf{x}}_{0:t}^{(i))}$ 와 중요 가중치 $w_t^{(i)}$ 를 계산하려면 시간스텝 $t$ 에서 ${\mathbf{x}}_t^{(i)}\sim q({\mathbf{x}}_t^{(i)}|{\mathbf{x}}_{0:t-1}^{(i)},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 샘플링하고 식 (16)으로 그 때의 중요 가중치를 계산하면 된다. 이것이 순차 중요 샘플링 또는 SIS 알고리즘이다.

SIS 알고리즘을 정리하면 다음과 같다.

[1] $N$ 개의 샘플 ${\mathbf{x}}_0^{(i)}$ 를 추출한다.

 

$${\mathbf{x}}_0^{(i)}\sim p({\mathbf{x}}_0),i=1,...,N$$

 

      중요 가중치는 $w_0^{(i)}=\frac{1}{N}$ 으로 한다.

[2] 시간스텝 $t=1,...,T$ 동안 다음을 수행한다.

      1. 중요분포에서 샘플 ${\mathbf{x}}_t^{(i)}$ 를 추출한다.

 

$${\mathbf{x}}_t^{(i)}\sim q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1}^{(i)},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}),i=1,...,N$$

 

      2. 중요 가중치를 다음 식으로 계산하고,

 

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

 

        정규화 시킨다.

여기서 중요분포 $q({\mathbf{x}}_t|{\mathbf{x}}_{0:t-1},{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에 마르코프 시퀀스적인 가정을 도입한다면,

 

$$\begin{array}{}\text{(17)}& 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})\end{array}$$

 

중요밀도함수는 ${\mathbf{x}}_{t-1},{\mathbf{z}}_t,{\mathbf{u}}_{t-1}$ 에만 의존적이 되므로 SIS 알고리즘에서 상태변수의 전체 시퀀스 샘플 ${\mathbf{x}}_{0:t-1}^{(i)}$ 와 측정값의 시퀀스 ${\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}{}\text{(18)}& 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}$$

 

또한 ${\mathbb{E}}_{{\mathbf{x}}_{0:t}\sim p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})}[{\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1}]$ 는 샘플 ${\mathbf{x}}_{0:t}^{(i)}$ 와 그 샘플의 중요도를 나타내는 중요 가중치 $w_t^{(i)}$ 를 이용하여 다음과 같이 근사적으로 계산할 수 있다.

 

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

 

그런데 식 (18)과 (19)는 상태변수 ${\mathbf{x}}_t$ 의 조건부 확률밀도함수인 사후 확률밀도함수 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 가 아니라 시간스텝 $0$ 부터 $t$ 까지의 전체 상태변수 시퀀스 ${\mathbf{x}}_{0:t}$ 로 확장시킨 전체 조건부 확률밀도함수 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에 관한 것이다.

그렇다면 $p({\mathbf{x}}_{0:t}|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 에서 $p({\mathbf{x}}_t|{\mathbf{z}}_{0:t},{\mathbf{u}}_{0:t-1})$ 를 어떻게 계산할 수 있을까.