L5 · Monte Carlo and Particles

시리즈: Bayes and Particle Filters · 이전: L4 · 다음: L6

이 강의는 belief를 함수 대신 sample 묶음으로 들고 갈 때 정확히 무엇이 성립하는지 답합니다. Sample을 뽑는다는 말의 뜻, sample 평균이 expectation을 근사하는 이유, particle을 transition model에 통과시키면 prediction step이 되는 이유까지 다룹니다.

형광펜: 정의·핵심 · 직관·메커니즘 · 조건·주의

목차

• 1. 분포 전체 대신 sample을 들고 간다
• 2. Sample한다는 것의 정확한 뜻
• 3. Expectation
• 4. Monte Carlo estimator
• 5. Particle은 어디서 오는가
• 6. Propagation이 prediction을 대신하는 이유
• 7. 아직 빠진 것
• 이해 확인
• 답

---

1. 분포 전체 대신 sample을 들고 간다

L4의 Bayes filter는 다음 두 식을 반복합니다.

두 식이 주고받는 것은 숫자 하나가 아니라 state space 전체 위에 정의된 함수입니다. State가 로봇의 1차원 위치라면 가능한 모든 $x_t$에 대해 $\mathrm{bel}_t(x_t)$ 값을 알고 있어야 합니다.

1차원 belief가 Gaussian이라면 mean과 variance 두 숫자로 함수 전체가 정해집니다. 예를 들어 $\mathcal N(3.2,\,0.4^2)$는 mean 3.2와 standard deviation 0.4 (variance 0.16)만으로 정해집니다. 하지만 똑같이 생긴 복도 두 곳 중 어디에 있는지 모르는 로봇의 belief는 $x\approx 2$ 근처와 $x\approx 8$ 근처에 mode가 하나씩 있습니다 (bimodal). 이런 모양은 Gaussian 하나로 표현되지 않습니다.

Gaussian이 아닌 모양도 담으려면 state를 칸으로 나누고 칸마다 확률 값을 저장하는 grid를 쓸 수 있습니다. 하지만 L4 §7에서 본 것처럼 칸 수가 $M^n$으로 늘어납니다.

이 강의는 세 번째 방법을 봅니다. Belief에서 뽑은 점 $N$개 $x^{(1)},\dots,x^{(N)}$을 저장하고, belief에 대한 계산을 이 점들에 대한 평균으로 바꿉니다. 이 점을 일반적으로 sample이라고 하고, particle filter에서는 particle이라고 부릅니다.

다만 sample 표현이 dimension 문제를 없애 준다는 뜻은 아닙니다. §4에서 오차가 줄어드는 속도와 그 전제를 보고, particle filter에만 생기는 어려움은 L7 §2에서 다룹니다.

---

2. Sample한다는 것의 정확한 뜻

표기 읽기

이 식은 "$i$번째 sample $x^{(i)}$는 distribution $p(x)$를 따른다", 또는 "$x^{(i)}$를 $p(x)$에서 뽑았다"라고 읽습니다. 위첨자 $(i)$는 몇 번째 sample인지 나타내는 번호이고 거듭제곱이 아닙니다. 시간이 들어가면 $x_t^{(i)}$처럼 아래첨자 $t$가 시각, 위첨자 $(i)$가 particle 번호를 맡습니다.

$\sim$은 "근사적으로 같다"는 뜻이 아닙니다. $X\sim p$는 random variable $X$의 distribution이 $p$라는 선언이고, $x^{(i)}\sim p$는 그 distribution을 따르는 random experiment를 한 번 실행해서 나온 값이 $x^{(i)}$라는 뜻입니다. 근사는 따로 $\approx$로 씁니다.

이산 예시

$X\in\{A,B,C\}$이고 $p=[0.1,\,0.7,\,0.2]$라고 합시다. 여기서 한 번 sample한다는 것은 $A$가 0.1, $B$가 0.7, $C$가 0.2의 확률로 나오는 실험을 한 번 실행하는 것입니다.

실제로 10번 뽑았더니 $C,C,B,B,A,B,B,A,A,C$가 나왔습니다. $A$ 3개, $B$ 4개, $C$ 3개이므로 비율은 $[0.3,\,0.4,\,0.3]$입니다. $[0.1,\,0.7,\,0.2]$와 꽤 다르고, $N$이 작으면 이런 일이 흔합니다. 아래 표는 $N$을 바꿔 가며 따로 뽑은 결과입니다.

Sample 하나하나는 random이지만, 많이 모은 sample의 비율은 원래 확률에 가까워집니다. 이 성질이 sample 묶음으로 distribution을 대신할 수 있는 근거입니다. 어떤 조건에서 성립하는지는 §4에서 정확히 씁니다.

연속 예시

$X\sim\mathcal N(0,1)$에서 다섯 번 뽑으면 $0.35,\ 0.82,\ 0.33,\ -1.30,\ 0.91$ 같은 실수가 나옵니다. L1 §7에서 본 것처럼 $X$가 density를 가지므로 $P(X=0.35)=0$입니다. 확률 0은 미리 정해 둔 한 점에 대한 이야기이고, 실험을 실행하면 매번 어떤 점이든 하나는 나옵니다.

그래서 연속에서는 점 대신 영역을 봅니다. 100,000개를 뽑았더니 구간 $(-0.5,\,0.5)$에 들어간 비율이 0.3856이었고, 정확한 값 $P(-0.5<X<0.5)$는 0.3829입니다. 구간 $(3.5,\,4.5)$에 들어간 비율은 0.00027이었고 정확한 값은 0.00023입니다. Density는 $x=0$에서 0.399, $x=4$에서 0.000134입니다.

한 점의 확률은 0이어도, 폭이 같은 두 영역이라면 density가 높은 쪽에 sample이 떨어질 확률이 더 크므로 sample이 모인 정도가 density의 모양을 따라갑니다. 정확히 말하면 구간 $[a,b]$에 떨어지는 sample의 비율이 $\int_a^b p(x)\,dx$에 가까워집니다. 아래 그림은 mode가 두 개인 density에서 $N$을 늘려 가며 뽑은 결과입니다.

$p(x)=0.7\,\mathcal N(2,0.8^2)+0.3\,\mathcal N(8,1^2)$에서 seed를 고정해 뽑은 sample의 histogram이고, 아래 눈금은 sample 위치입니다. $x^{(i)}<5$인 비율은 $N=20$에서 0.750, $N=200$에서 0.755로 오히려 멀어졌다가 $N=5000$에서 0.703으로 정확한 값 $P(X<5)\approx 0.700$에 가까워지는데, 한 번 뽑은 결과이므로 $N$을 늘릴 때마다 단조롭게 가까워지지는 않습니다.

코드에서 sample은 random number generator 호출이다

컴퓨터에서 sample을 뽑는 방법은 해당 distribution용 random number generator를 부르는 것입니다.

# Gaussian N(0, 1)
for i = 1..N:
    x[i] = sample_normal(mean = 0, std = 1)

# discrete p = [0.1, 0.7, 0.2] on {A, B, C}
for i = 1..N:
    x[i] = sample_categorical(values = [A, B, C],
                              probs = [0.1, 0.7, 0.2])

# transition model x_t = f(x_{t-1}) + w,  w ~ N(0, Q)
for i = 1..N:
    w = sample_normal(mean = 0, cov = Q)
    x_next[i] = f(x_prev[i]) + w

Library 안에서는 $[0,1]$ 위의 uniform random number를 원하는 distribution으로 변환합니다. 이산 distribution이면 누적합 $C_i$를 만들고 $U\sim\mathrm{Uniform}(0,1)$에 대해 $I=\min\{i : U\le C_i\}$를 고르며, 이 방법은 L7 §4에서 다시 씁니다. Sample한다는 것은 추상적인 동작이 아니라, 해당 distribution을 따르도록 만든 random number generator를 한 번 호출하는 것입니다.

---

3. Expectation

이산

$X\in\{1,2,3\}$이고 $p(1)=0.2$, $p(2)=0.5$, $p(3)=0.3$이라고 합시다. Expectation의 정의는 다음과 같습니다.

$\mathbb E_p[f(X)]$는 "$p$ 아래에서 $f(X)$의 expectation"이라고 읽습니다. 합은 $x$를 없애므로 결과는 $x$의 함수가 아니라 숫자 하나입니다.

$f(X)=X$로 두고 계산합니다.

2.1은 $X$가 가질 수 있는 값이 아니지만 문제가 없습니다. Expectation은 가능한 값마다 그 값의 확률을 곱해 더한 weighted average입니다. 1, 2, 3의 단순 평균은 2인데, 3이 1보다 확률이 크므로 평균이 3 쪽으로 당겨져 2.1이 됩니다.

한 가지 특수한 경우를 봐 둡니다. $f(x)=\mathbf 1\{x\in S\}$ ($x$가 집합 $S$에 들어가면 1, 아니면 0)로 두면 $\mathbb E_p[\mathbf 1\{X\in S\}]=\sum_{x\in S}p(x)=P(X\in S)$입니다. 확률도 expectation의 한 종류이므로, §2의 "비율이 확률에 가까워진다"는 §4의 결과에 포함됩니다.

연속

Continuous variable에서는 PMF 대신 density로 적분합니다.

여기서 $p(x)$는 확률이 아니라 density이고, $dx$는 $x$를 없앱니다. Signals & Systems에서 적분을 Riemann sum으로 본 것처럼 폭 $\Delta x$인 칸으로 나누면 의미가 보입니다.

$p(x_k)\Delta x$는 $X$가 $k$번째 칸에 떨어질 확률의 근사이므로, 각 항은 "칸의 값 × 칸의 확률"입니다. 이산의 weighted average가 그대로 연속으로 넘어간 것입니다.

Variance

§4에서 오차의 크기를 말하려면 variance가 필요합니다. $\mu=\mathbb E_p[f(X)]$라고 두고 정의에서 전개합니다.

위 예시에서 $\mathbb E_p[X^2]=1(0.2)+4(0.5)+9(0.3)=4.9$이므로 $\mathrm{Var}_p(X)=4.9-2.1^2=0.49$이고, standard deviation은 0.7입니다.

---

4. Monte Carlo estimator

적분 대신 평균

원하는 값이 $\mathbb E_p[f(X)]=\int f(x)\,p(x)\,dx$인데 이 적분을 식으로 풀기 어렵다고 합시다. 대신 $x^{(1)},\dots,x^{(N)}\sim p$를 뽑고 평균을 냅니다.

$\hat I_N$은 "sample마다 $f$를 계산해서 산술평균한 값"이라고 읽습니다. 이것을 Monte Carlo estimator라고 합니다. 식에 $p(x^{(i)})$ 값이 한 번도 곱해지지 않습니다. $p$의 정보는 곱셈이 아니라 sample이 어디에 많이 떨어지는지를 통해 들어갑니다.

빈도로 묶어 보기

§3의 $p=[0.2,\,0.5,\,0.3]$에서 100,000개를 뽑았더니 1이 19,982개, 2가 49,990개, 3이 30,028개 나왔습니다. $f(X)=X$의 sample 평균을 같은 값끼리 묶어 씁니다.

셋째 줄은 §3의 $1(0.2)+2(0.5)+3(0.3)=2.1$과 모양이 같고, 확률 자리에 빈도가 들어가 있습니다. 이산 $X$에서 $N_x$를 값이 $x$인 sample 수라고 하면 $\frac1N\sum_i f(x^{(i)})=\sum_x f(x)\,\frac{N_x}{N}$이고, sample 평균이 expectation을 근사하는 이유는 빈도 $N_x/N$이 확률 $p(x)$를 대신하기 때문입니다. 연속 $X$에서는 같은 값이 거의 반복되지 않으므로, 칸으로 묶으면 같은 논리가 근사적으로 성립합니다.

Law of large numbers와 조건

위 설명을 정확한 정리로 쓰면 다음과 같습니다. $x^{(i)}$들이 independent하고 모두 같은 $p$를 따르며 (i.i.d.), $\mathbb E_p\lvert f(X)\rvert<\infty$일 때 $N\to\infty$에서 $\hat I_N$은 확률 1로 $\mathbb E_p[f(X)]$에 수렴합니다. 이것이 strong law of large numbers입니다.

두 조건은 이 정리의 전제입니다. Sample끼리 의존하면 이 정리를 그대로 쓸 수 없고, 수렴하는지는 따로 보여야 합니다. 이 절 끝에서 볼 particle filter가 그런 경우입니다. $\mathbb E_p\lvert f(X)\rvert<\infty$가 깨지는 예로, Cauchy distribution에서 $f(x)=x$로 두면 expectation이 존재하지 않고 sample 평균은 $N$을 늘려도 한 값으로 모이지 않습니다.

오차는 1/√N으로 줄어든다

$\hat I_N$은 sample에 따라 달라지는 random variable입니다. 같은 실험을 여러 번 반복했을 때 estimator의 평균이 참값에서 벗어난 정도가 bias이고, 흩어진 정도가 variance입니다 (Bias and Variance). 먼저 expectation을 계산합니다.

따라서 Monte Carlo estimator는 unbiased입니다. 다음은 variance이고, 여기서는 $\mathrm{Var}_p(f(X))<\infty$라고 가정합니다.

§3의 예시는 $\mathrm{Var}_p(X)=0.49$이므로 standard deviation이 $N=100$에서 $0.7/10=0.07$, $N=10{,}000$에서 $0.007$입니다. 실제로 각 $N$마다 estimator를 2,000번 다시 계산해 보면 흩어짐이 0.0701과 0.0068로 나옵니다. Sample을 100배 늘려야 오차가 10배 줄어듭니다.

이 식에는 $x$의 dimension $n$이 직접 들어가지 않고, 이 점이 grid의 $M^n$과 다릅니다. 하지만 필요한 $N$이 dimension과 무관하다는 뜻은 아닙니다. $1/\sqrt N$ 앞의 상수는 문제마다 다르고, particle filter에서 필요한 $N$은 state dimension이 클수록, belief가 넓게 퍼질수록 크게 늘어납니다. Uniform에 가까운 belief는 좁은 영역에 모인 belief보다 훨씬 많은 particle이 필요합니다.

또 이 식은 $p$에서 i.i.d. sample을 직접 뽑을 수 있다는 전제 위에 있습니다. 이 전제를 만족할 수 없을 때가 L6 §1의 출발점입니다.

Particle filter에서 resampling을 거친 particle들은 서로 independent가 아니므로, 위의 law of large numbers가 particle filter의 수렴을 그대로 보장하지는 않습니다. Particle filter의 수렴은 서로 영향을 주는 particle 집합에 대한 별도의 정리로 증명됩니다. 이 강의에서는 Monte Carlo가 왜 되는지에 대한 근거로만 씁니다.

---

5. Particle은 어디서 오는가

Particle 묶음이 belief를 나타낸다는 뜻

Particle filter는 함수 $\mathrm{bel}_t(x)$를 저장하지 않고 $x_t^{(1)},\dots,x_t^{(N)}$을 저장합니다. §1의 복도 예시에서 belief의 mass가 $x\approx 2$ 근처에 70%, $x\approx 8$ 근처에 30% 있고 particle을 이 belief에서 뽑았다면, particle 1,000개 중 대략 700개가 2 근처에, 300개가 8 근처에 있게 됩니다. §2 그림의 $N=5000$ 패널에서 $x^{(i)}<5$인 particle이 3514개(0.703)였던 것이 같은 상황입니다.

"대략"이라고 쓴 이유는 개수 자체가 random이기 때문입니다. Particle 묶음이 belief를 나타낸다는 말은, $\int\lvert f(x)\rvert\,\mathrm{bel}_t(x)\,dx<\infty$인 $f$ (예: bounded $f$)에 대해 $\frac1N\sum_i f(x_t^{(i)})\approx\int f(x)\,\mathrm{bel}_t(x)\,dx$가 성립한다는 뜻입니다. 영역의 확률은 $f$가 indicator인 경우이므로, 확률이 큰 영역일수록 particle이 많이 모여 있게 됩니다.

Particle 하나는 distribution이 아닙니다. $x_t^{(17)}=3.42$는 "현재 state가 3.42일 수 있다"는 가설 하나일 뿐이고, 여러 particle이 모여야 distribution을 나타냅니다. 나중에 weight가 붙으면 $\{x_t^{(i)},\,w_t^{(i)}\}$ 묶음이 distribution을 나타내며, 이것은 L6 §5에서 다룹니다.

초기 particle

Bayes filter는 초기 belief $p(x_0)$가 있어야 시작합니다 (L2 §6). Particle filter도 같습니다. 초기 particle은 $p(x_0)$에서 직접 뽑습니다.

이산 예시로 $X_0\in\{1,2,3\}$, $p(x_0)=[0.2,\,0.6,\,0.2]$에서 $N=10$개를 뽑았더니 $[2,3,2,2,3,2,2,2,1,2]$가 나왔습니다. 1이 1개, 2가 7개, 3이 2개이므로 빈도는 $[0.1,\,0.7,\,0.2]$입니다. $[0.2,\,0.6,\,0.2]$와 정확히 같지 않은 것은 sampling이 random이기 때문이고, $N$이 작으면 이 정도 차이는 흔합니다. 이 10개가 그대로 초기 belief의 particle 표현입니다.

위치를 $[0,10]$ 안이라는 것 말고는 모른다면 $p(x_0)=\mathrm{Uniform}(0,10)$으로 두고 $x_0^{(i)}\sim\mathrm{Uniform}(0,10)$을 뽑습니다. 예를 들어 $2.6,\ 3.0,\ 8.1,\ 0.9,\ 6.0,\dots$이 나옵니다. Particle filter가 prior를 대신 만들어 주지는 않습니다. Prior는 여전히 설계자가 가정으로 정하고, 바뀌는 것은 그 prior를 함수 대신 sample로 표현한다는 점뿐입니다.

다음 시각의 particle: propagation

시각 $t-1$의 particle $x_{t-1}^{(1)},\dots,x_{t-1}^{(N)}$이 있다고 합시다. 각 particle마다 transition model에서 다음 값을 하나씩 뽑습니다.

이 식은 "$i$번째 particle의 시각 $t$ 값은, 같은 particle의 시각 $t-1$ 값 $x_{t-1}^{(i)}$를 조건으로 한 transition distribution에서 뽑는다"라고 읽습니다. 조건에 들어가는 것은 belief 전체가 아니라 그 particle이 가진 숫자 하나입니다.

숫자로 해 봅니다. 1차원 로봇이 한 step에 약 $+1$씩 움직이고 $x_t=x_{t-1}+1+\epsilon_t$, $\epsilon_t\sim\mathcal N(0,\,0.2^2)$라고 합시다. L3 §3에서처럼 이 식은 $p(x_t\mid x_{t-1})=\mathcal N(x_t;\,x_{t-1}+1,\,0.2^2)$를 정합니다. 이전 particle이 2.0, 2.2, 5.0이고 noise가 다음처럼 뽑혔다고 합시다.

Particle 1과 2가 같은 값 3.08에 도착한 것은 표의 noise 값을 그렇게 되도록 고른 예시이기 때문입니다. Continuous noise에서 두 particle이 정확히 같은 값에 떨어질 확률은 0입니다. 이 예시에서 볼 점은, particle마다 noise를 따로 뽑으므로 가까이서 출발한 particle끼리는 도착 위치가 매우 가까워지거나 순서가 바뀔 수 있다는 것입니다. 코드로는 다음과 같습니다.

# particles at t-1
input : x_prev[1..N]
for i = 1..N:
    eps  = sample_normal(mean = 0, std = 0.2)
    # x[i] ~ p(x_t | x_prev[i])
    x[i] = x_prev[i] + 1 + eps
# particles at t
output: x[1..N]

Propagation은 particle을 만드는 별도의 알고리즘이 아니라, transition model을 random simulator로 보고 particle마다 한 번씩 실행하는 것입니다. 이 단계에서는 $p(x_t\mid x_{t-1})$의 값을 계산할 필요가 없고, 그 distribution에서 뽑을 수만 있으면 됩니다.

---

6. Propagation이 prediction을 대신하는 이유

§5에서 만든 cloud가 왜 predicted belief $\overline{\mathrm{bel}}_t=p(x_t\mid y_{1:t-1})$를 나타내는지 보입니다. 전제는 시각 $t-1$의 particle들이 $\mathrm{bel}_{t-1}$을 나타내는 같은 weight의 sample이라는 것입니다. $t=1$에서는 $x_0^{(i)}\sim p(x_0)=\mathrm{bel}_0$이므로 이 전제가 정확히 성립하고, 이후 시각에는 L6의 weighting과 L7의 resampling이 이 전제를 근사적으로 다시 만들어 줍니다.

이산 예시로 먼저 확인

State가 $A,B$ 두 개이고 $\mathrm{bel}_{t-1}$이 $P(A)=0.3$, $P(B)=0.7$이며, transition이 $P(B\mid A)=0.2$, $P(B\mid B)=0.9$라고 합시다. L4 §2에서 합으로 계산한 정확한 prediction은 다음과 같았습니다.

이제 particle 1,000개 중 300개가 $A$, 700개가 $B$에 있다고 합시다. $A$의 particle은 각각 0.2의 확률로 $B$로 가므로, $B$에 도착하는 개수의 expectation은 $300\times0.2=60$개입니다. $B$의 particle은 각각 0.9의 확률로 $B$에 남으므로, 남는 개수의 expectation은 $700\times0.9=630$개입니다. 두 expectation을 더하면 690개이고, 비율로는 0.69입니다.

이 0.69는 L3 §6과 L4 §2에서 합으로 얻은 숫자와 같습니다. 같은 숫자가 나오는 이유는 particle을 transition으로 한 번씩 보내는 과정이 합 $\sum_{x_{t-1}}P(B\mid x_{t-1})\,P(x_{t-1})$의 각 항을 개수로 세는 과정이기 때문입니다. 여기서는 particle 비율 300/700이 belief 0.3/0.7과 정확히 같게 잡혀 있어서 expectation이 정확히 일치했습니다.

실제 개수는 random입니다. 한 번 실행해 보니 $B$에 696개가 도착했습니다 ($A$에서 온 것 69개, $B$에 남은 것 627개). 개수의 standard deviation은 $\sqrt{300(0.2)(0.8)+700(0.9)(0.1)}\approx 10.5$입니다.

일반식: prediction 적분은 expectation이다

$x_t$ 값 하나를 고정하면, prediction 적분은 $x_{t-1}$에 대한 함수 $p(x_t\mid x_{t-1})$의 expectation입니다. 그래서 §4의 Monte Carlo estimator를 그대로 쓸 수 있습니다.

마지막 줄은 particle마다 하나씩 있는 transition density $N$개를 $1/N$씩 섞은 mixture입니다. 이것을 $\hat p(x_t\mid y_{1:t-1})$로 씁니다. 적분이 $dx_{t-1}$로 없애던 $x_{t-1}$을, 이 식에서는 particle에 대한 합이 없앱니다.

Mixture에서 뽑는 두 단계

Mixture에서 sample 하나를 뽑으려면 두 단계를 거칩니다. 먼저 ancestor (조상) index $J$를 particle 값과 무관하게 $\{1,\dots,N\}$에서 균등하게 고르고, 다음에 $x_t\sim p(x_t\mid x_{t-1}^{(J)})$를 뽑습니다. 시각 $t-1$의 particle 전체 $x_{t-1}^{(1)},\dots,x_{t-1}^{(N)}$을 $x_{t-1}^{(1:N)}$으로 줄여 쓰고, 이 값들을 고정했을 때 나온 $x_t$의 density $p\big(x_t\mid x_{t-1}^{(1:N)}\big)$를 계산합니다. 이것은 조건 없는 $p(x_t)$와 다른 양입니다.

§5의 코드는 ancestor를 random하게 고르지 않고 모든 $i$를 한 번씩 씁니다. 이 경우에도 ancestor $x_{t-1}^{(1:N)}$을 고정해 두면, cloud에서 계산한 평균의 expectation은 mixture에 대한 expectation과 같습니다.

$t=1$에서는 더 강하게 말할 수 있습니다. $x_0^{(i)}$가 $p(x_0)$에서 i.i.d.로 뽑혔고 $x_1^{(i)}$가 각각 독립적으로 뽑히므로, $x_1^{(i)}$는 $\overline{\mathrm{bel}}_1=p(x_1)$에서 뽑은 i.i.d. sample입니다.

오차는 두 곳에서 들어옵니다. 첫째, $t-1$의 particle이 $\mathrm{bel}_{t-1}$의 유한한 근사이므로 mixture가 정확한 $\overline{\mathrm{bel}}_t$와 다릅니다. 둘째, 새 particle은 그 mixture에서 random하게 뽑힌 값입니다. 앞의 전제가 성립하는 한 두 오차 모두 $N$이 커지면 줄어듭니다.

위: §5의 세 particle이 각자의 transition distribution $\mathcal N(x_{t-1}^{(i)}+1,\,0.2^2)$에서 값 하나씩을 받습니다. 아래: $\mathrm{bel}_{t-1}=0.7\,\mathcal N(2,0.25^2)+0.3\,\mathcal N(6,0.25^2)$에서 뽑은 40개를 같은 모델로 보낸 결과로, 실선은 정확한 $\overline{\mathrm{bel}}_t$ (component standard deviation $\sqrt{0.25^2+0.2^2}\approx0.32$로 퍼짐), 점선은 mixture $\frac1N\sum_i p(x_t\mid x_{t-1}^{(i)})$입니다.

아래 패널에서 두 mode가 $+1$만큼 이동하고 각 mode 주변이 조금 넓어진 것은 L4 §3에서 본 shift와 convolution이 particle에서도 그대로 나타난 것입니다.

---

7. 아직 빠진 것

지금까지 한 것은 초기 sampling과 propagation입니다. Measurement $y_t$는 한 번도 쓰지 않았습니다.

§6의 전제가 성립하면 propagate된 cloud는 $\overline{\mathrm{bel}}_t=p(x_t\mid y_{1:t-1})$를 나타냅니다. 우리가 원하는 것은 L4 §4의 $\mathrm{bel}_t=p(x_t\mid y_{1:t})\propto p(y_t\mid x_t)\,\overline{\mathrm{bel}}_t$입니다. Particle의 위치는 $y_t$와 무관하게 정해졌으므로, $p(y_t\mid x_t)$가 $x_t$에 따라 달라지는 한 이 cloud만으로는 posterior를 나타낼 수 없습니다.

현재까지의 알고리즘은 다음과 같고, 비어 있는 두 줄이 다음 두 강의의 내용입니다.

for i = 1..N:
    # initial particles (this lecture)
    x[0][i] ~ p(x_0)
for t = 1, 2, ...:
    for i = 1..N:
        # propagate (this lecture)
        x[t][i] ~ p(x_t | x[t-1][i])
    # weight each x[t][i] using y_t  -> L6
    # resample                       -> L7

남은 질문은 두 가지입니다. 첫째, 이미 놓인 particle에 $y_t$를 어떻게 반영하는가입니다. 이것은 importance sampling으로 답하고, particle이 predicted belief에 따라 이미 놓여 있으므로 weight가 likelihood만으로 정해진다는 결론은 L6 §6에서 유도합니다.

둘째, weight가 시간에 따라 쌓이면 무슨 일이 생기는가입니다. 이것은 L7 §1에서 시작합니다.

---

이해 확인

1. $x_t^{(7)}\sim p(x_t\mid x_{t-1}^{(7)})$를 말로 어떻게 읽는지 쓰시오. 조건에는 $x_{t-1}^{(7)}$ 한 값만 들어가는데, 이렇게 만든 particle cloud 전체가 $\overline{\mathrm{bel}}_t$를 나타낼 수 있는 이유를 설명하시오.

2. Monte Carlo estimator $\frac1N\sum_i f(x^{(i)})$에는 $p(x^{(i)})$가 곱해지지 않는다. 그런데도 $\int f(x)\,p(x)\,dx$를 근사하는 이유를 설명하고, 이때 필요한 조건을 쓰시오.

3. 이전 시각에 particle 1,000개 중 400개가 $A$, 600개가 $B$에 있고 $P(C\mid A)=0.25$, $P(C\mid B)=0.5$이다. 다음 시각에 $C$에 있는 particle 수의 expectation을 구하고, 이 계산이 prediction 식의 어느 부분에 해당하는지 쓰시오. 또 실제 개수가 정확히 그 값이라고 말할 수 없는 이유를 설명하시오.

4. 초기 particle에서 시작해 propagation만 반복한 cloud가 posterior $p(x_t\mid y_{1:t})$를 나타내지 못하는 이유를 설명하시오.

---

답

1. "7번 particle의 시각 $t$ 값은, 같은 particle의 시각 $t-1$ 값을 조건으로 한 transition distribution에서 뽑는다"라고 읽습니다. Particle 하나는 자기 ancestor 값에만 조건을 겁니다. Ancestor index를 균등하게 고른 뒤 transition에서 뽑은 값은 law of total probability에 의해 mixture $\frac1N\sum_i p(x_t\mid x_{t-1}^{(i)})$를 따르고, 모든 $i$를 한 번씩 쓰는 코드에서도 ancestor를 고정하면 cloud 평균의 expectation이 이 mixture에 대한 expectation과 같습니다. Ancestor들이 $\mathrm{bel}_{t-1}$의 sample이므로 이 mixture가 prediction 적분의 Monte Carlo 근사입니다. → §6

2. $p$의 정보는 곱셈이 아니라 sample이 떨어지는 위치로 들어갑니다. 같은 값끼리 묶으면 $\sum_x f(x)\,N_x/N$이 되고 빈도 $N_x/N$이 $p(x)$에 가까워집니다. Sample이 i.i.d.이고 $\mathbb E_p\lvert f(X)\rvert<\infty$이면 law of large numbers로 수렴하며, variance가 유한하면 오차가 $1/\sqrt N$으로 줄어듭니다. → §4

3. $400\times0.25+600\times0.5=100+300=400$개입니다. 이것은 $\sum_{x_{t-1}}P(C\mid x_{t-1})\,\mathrm{bel}_{t-1}(x_{t-1})$에서 $\mathrm{bel}_{t-1}$ 자리에 빈도 0.4, 0.6을 넣은 계산입니다. 각 particle의 이동이 random이므로 개수도 random이고, 400은 expectation입니다 (standard deviation은 $\sqrt{400(0.25)(0.75)+600(0.5)(0.5)}=15$). → §6

4. Propagation은 particle 위치를 $y_t$와 무관하게 정합니다. 직전 시각에 update를 거친 particle에서 출발했더라도 propagation 결과는 $p(x_t\mid y_{1:t-1})$까지만 나타내고, update를 한 번도 하지 않았다면 데이터가 들어가지 않은 $p(x_t)$를 나타냅니다. $p(y_t\mid x_t)$가 $x_t$에 따라 달라지면 posterior는 이것과 모양이 다르므로 $p(y_t\mid x_t)$를 weight로 반영해야 하며, 이것이 L6의 내용입니다. → §7