L4 · The Bayes Filter

시리즈: Bayes and Particle Filters · 이전: L3 · 다음: L5 · concept: Bayes Filter

이 강의는 L3의 두 가정만 가지고 belief를 한 step씩 갱신하는 식 두 개를 유도합니다. Prediction은 law of total probability이고 update는 Bayes theorem이라는 것을 한 줄씩 확인합니다.

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

목차

• 1. 무엇을 재귀적으로 들고 가는가
• 2. Prediction step 유도
• 3. Prediction을 숫자와 그림으로
• 4. Update step 유도
• 5. Normalization constant
• 6. 전체 알고리즘
• 7. 왜 그대로는 계산하기 어려운가
• 이해 확인
• 답

---

1. 무엇을 재귀적으로 들고 가는가

Filtering의 목표는 매 시각 $t$마다 $p(x_t \mid y_{1:t})$를 얻는 것입니다. 정의는 L3 §8에서 conditioning set으로 구분했습니다. 매번 $y_1$부터 $y_t$까지 전부 다시 처리하면 measurement가 쌓일수록 계산이 커집니다. Bayes filter는 직전 시각의 결과 하나만 들고 가서 새 measurement 하나로 갱신합니다.

이 강의에서는 두 distribution에 이름을 붙입니다.

$\mathrm{bel}_t(x_t)$는 "$y_1$부터 $y_t$까지 본 뒤 현재 state $x_t$에 대한 belief"라고 읽습니다. Bar가 붙은 $\overline{\mathrm{bel}}_t(x_t)$는 "$y_t$는 아직 보지 않고 $y_{t-1}$까지만 본 상태에서 $x_t$에 대한 predicted belief"라고 읽습니다. 둘은 같은 variable $x_t$의 distribution이고, 차이는 conditioning set에 $y_t$가 들어 있는지 하나뿐입니다.

한 step은 두 단계로 나뉩니다.

Prediction은 transition model $p(x_t \mid x_{t-1})$을 쓰고, update는 measurement model $p(y_t \mid x_t)$를 씁니다. 두 가정 아래에서는 과거 measurement $y_{1:t-1}$이 다음 belief 계산에 $\mathrm{bel}_{t-1}$을 통해서만 들어갑니다. 그래서 $y_{1:t-1}$ 자체를 보관할 필요가 없습니다. 이것은 §2와 §4의 유도에서 직접 확인됩니다.

시작점

시리즈 기호표에서 정한 대로 state는 $t=0$부터, measurement는 $t=1$부터 있습니다. 따라서 $t=0$에서 가진 것은 initial belief $\mathrm{bel}_0(x_0) = p(x_0)$ 하나입니다. 이 값을 사전 정보나 가정으로 정하는 방법은 L2 §6에서 보았고, 이 강의의 3칸 복도 예는 거기서 든 $p(x_0) = [0.1,\ 0.8,\ 0.1]$에서 시작합니다.

첫 measurement가 $t=1$에 오므로 첫 동작은 prediction입니다. $y_{1:0}$은 빈 sequence이므로 $\overline{\mathrm{bel}}_1(x_1) = p(x_1)$입니다.

Filter의 출력은 숫자 하나가 아니라 distribution입니다. "로봇이 몇 번 칸에 있다"는 point estimate는 이 distribution의 값이 가장 큰 state(mode)나 mean을 골라 나중에 읽어냅니다.

---

2. Prediction step 유도

$\mathrm{bel}_{t-1}(x_{t-1}) = p(x_{t-1} \mid y_{1:t-1})$은 이미 가지고 있습니다. 시간이 한 step 지나 state가 $x_{t-1}$에서 $x_t$로 바뀌었고, $y_t$는 아직 오지 않았습니다. 구하려는 것은 $\overline{\mathrm{bel}}_t(x_t) = p(x_t \mid y_{1:t-1})$입니다.

두 state로 먼저 계산하기

State가 $A$, $B$ 두 개라고 하겠습니다. 이전 belief와 transition model은 다음과 같습니다.

따라서 $P(X_t = A \mid X_{t-1} = A) = 0.8$, $P(X_t = A \mid X_{t-1} = B) = 0.1$입니다. L3 §6과 같은 숫자입니다. L3에서는 과거 measurement가 왜 여전히 필요한지를 보였고, 여기서는 같은 계산을 prediction step으로 읽습니다.

$X_t = B$에 도달하는 경로는 이전 state에 따라 두 개입니다.

두 경로는 $X_{t-1}$의 값이 서로 다르므로 동시에 일어날 수 없습니다. 그래서 더합니다. 같은 방법으로 $P(X_t = A \mid y_{1:t-1}) = 0.3 \times 0.8 + 0.7 \times 0.1 = 0.24 + 0.07 = 0.31$입니다. 결과 $\overline{\mathrm{bel}}_t = [0.31,\ 0.69]$의 합은 1입니다.

일반식을 한 줄에 법칙 하나씩

이제 같은 계산을 기호로 씁니다. 먼저 조건이 붙은 product rule이 필요합니다.

이것은 L1 §6의 product rule을 "$c$가 이미 주어진 세계" 안에서 쓴 것입니다. 모든 확률에 같은 조건 $c$가 붙어 있을 뿐 규칙은 같습니다.

첫 줄은 모르는 이전 state $x_{t-1}$을 joint에 넣고 모든 값에 대해 더합니다. 이 sum이 없애는 variable은 $x_{t-1}$입니다. 둘째 줄은 product rule에서 $a = x_t$, $b = x_{t-1}$, $c = y_{1:t-1}$로 대응시킨 것입니다. 셋째 줄은 조건에서 $y_{1:t-1}$을 지웠습니다.

셋째 줄이 L3의 가정에서 나오는 과정

L3 §5의 Markov assumption은 다음 형태였습니다.

이 조건에는 $x_{0:t-2}$까지 들어 있습니다. 유도에 필요한 것은 $x_{0:t-2}$가 없는 형태이므로 한 번 더 marginalization을 합니다.

둘째 줄에서는 $a = x_t$, $b = x_{0:t-2}$, $c = (x_{t-1}, y_{1:t-1})$로 대응시켰고, $(x_{0:t-2}, x_{t-1}) = x_{0:t-1}$을 썼습니다. $t = 1$이면 $x_{0:t-2}$와 $y_{1:t-1}$이 모두 비어 있어서 이 과정이 필요 없습니다. Continuous state라면 sum을 integral로 바꾸면 같은 줄이 성립합니다.

이 줄에는 과거 measurement $y_{1:t-1}$이 conditioning set에 들어 있는 형태의 Markov assumption이 필요합니다. State만 있는 $p(x_t \mid x_{0:t-1}) = p(x_t \mid x_{t-1})$로는 부족합니다. 반례는 L3 §5에서 보았습니다.

셋째 줄에서 $y_{1:t-1}$이 transition factor에서는 사라졌지만 결과식에서 사라진 것은 아닙니다. 과거 measurement는 $p(x_{t-1} \mid y_{1:t-1})$ 쪽에 그대로 남아 있습니다. $x_{t-1}$을 알면 dynamics에는 과거 measurement가 필요 없지만, 우리는 $x_{t-1}$을 모르기 때문입니다.

숫자를 넣어 확인합니다.

위 표와 같습니다.

Continuous state

State가 continuous이면 모든 $p$가 density이고, sum은 integral이 됩니다. $x_{t-1}$을 폭이 작은 구간으로 나누어 더한 Riemann sum의 극한이라는 점은 L1 §8과 같습니다.

Integrand에는 $x_t$와 $x_{t-1}$이 둘 다 있습니다. $dx_{t-1}$로 적분하면 모든 가능한 $x_{t-1}$에 대해 더해지므로 $x_{t-1}$이 없어지고 $x_t$만 남습니다. 이 식은 이렇게 읽습니다. "각 $x_t$ 값마다, 가능한 모든 이전 state $x_{t-1}$에 대해 그곳에 있었을 belief와 그곳에서 $x_t$로 갈 transition density를 곱해서 모두 더한다."

Prediction은 L1의 law of total probability $p(x) = \sum_z p(x \mid z)\, p(z)$에 $y_{1:t-1}$을 조건으로 붙이고, Markov assumption으로 한 factor의 조건을 줄인 식입니다. 새로 외울 법칙은 없습니다.

결과는 숫자 하나가 아니라 $x_t$의 함수입니다. 모든 $x_t$ 값에 대해 이 integral을 계산해야 한다는 점이 §7에서 문제가 됩니다.

---

3. Prediction을 숫자와 그림으로

Uncertainty의 두 출처

Prediction 식은 두 가지 uncertainty를 한 번에 처리합니다.

1. $x_{t-1}$을 정확히 모릅니다. 이것은 $\mathrm{bel}_{t-1}(x_{t-1})$에 들어 있습니다.
2. $x_{t-1}$을 알아도 transition 자체가 noisy합니다. 이것은 $p(x_t \mid x_{t-1})$에 들어 있습니다.

$x_{t-1} = a$라고 확신할 수 있으면 $\mathrm{bel}_{t-1}$의 mass가 전부 $a$에 있으므로 sum에 항이 하나만 남습니다. 그러면 $\overline{\mathrm{bel}}_t(x_t) = p(x_t \mid x_{t-1} = a)$이고, 1번은 없어지고 2번만 남습니다. 반대로 transition이 deterministic이면 2번이 없습니다. 예를 들어 $x_t = x_{t-1} + u_t$이면 belief는 모양 그대로 $u_t$만큼 옮겨집니다.

Prediction이 belief를 항상 퍼뜨리는 것은 아닙니다. 아래 convolution 절처럼 independent한 additive noise를 더하는 모델에서는 variance가 더해지므로 퍼집니다. 그러나 여러 state를 한 state로 모으는 transition은 predicted belief를 $\mathrm{bel}_{t-1}$보다 좁게 만들 수 있습니다. 예를 들어 3칸 복도에서 "오른쪽 벽까지 가라"는 명령이 칸 1, 2에서 0.9로 칸 3에 닿고 0.1로 제자리에 남는다면, 행을 이전 state로 둔 transition matrix는 아래와 같고 $[0.1,\ 0.8,\ 0.1]$이 $[0.01,\ 0.08,\ 0.91]$이 되어 가장 큰 값이 0.8에서 0.91로 커집니다.

제어에서 $x_t = Ax_{t-1} + Bu_t$를 계산할 때는 state 값 하나(vector 하나)를 다음 시각으로 보냅니다. Bayes filter는 같은 dynamics를 써서 distribution 전체를 다음 시각으로 보냅니다. State-space model이 어떤 조건에서 transition model이 되는지는 L3 §7에 있습니다.

Signals and Systems에서 본 prediction: shift와 convolution

모델을 $x_t = x_{t-1} + u_t + w_t$로 두겠습니다. $u_t$는 알고 있는 control input이고, $w_t$는 density $p_w$를 가진 process noise입니다. $w_t$가 $(x_{0:t-1}, y_{1:t-1})$ 전체와 independent하다고 가정합니다.

$x_{t-1}$이 주어지면 $x_t - x_{t-1} - u_t = w_t$입니다. Shift는 density의 높이를 바꾸지 않으므로 transition model은 noise density를 옮겨 놓은 것입니다.

이것을 prediction 식에 넣습니다. 적분 variable $x_{t-1}$은 $x'$로 쓰고, convolution의 정의는 $(f * g)(z) = \int f(x')\, g(z - x')\, dx'$입니다.

$h(z) = (\mathrm{bel}_{t-1} * p_w)(z)$라고 두면 $\overline{\mathrm{bel}}_t(x) = h(x - u_t)$이므로, $h$를 오른쪽으로 $u_t$만큼 옮긴 것입니다. Prediction은 belief를 noise density와 convolution해서 퍼뜨리고, control input만큼 shift하는 연산입니다. Convolution과 shift는 순서를 바꿔도 결과가 같습니다. $y_{1:t-1}$이 주어졌을 때 $x_t$는 $x_{t-1} + u_t$와 그것에 independent한 $w_t$의 합이므로, (variance가 유한하면) $\mathrm{Var}(x_t \mid y_{1:t-1}) = \mathrm{Var}(x_{t-1} \mid y_{1:t-1}) + \mathrm{Var}(w_t)$입니다.

위 두 panel이 이 절의 prediction입니다: $\mathrm{bel}_{t-1} = 0.6\,\mathcal N(1, 0.5^2) + 0.4\,\mathcal N(5, 0.5^2)$, $u_t = 2$, $w_t \sim \mathcal N(0, 0.6^2)$. 아래 두 panel은 §4의 update이며 $y_t = x_t + v_t$, $v_t \sim \mathcal N(0, 0.8^2)$, $y_t = 7.2$입니다.

그림의 둘째 panel에서 옅은 회색 점선은 shift 전의 belief, 회색 파선은 shift만 한 경우이고, 파란 선이 실제 predicted belief입니다. 각 component의 variance는 $0.5^2 = 0.25$에서 $0.25 + 0.6^2 = 0.61$로 커지고, 왼쪽 component의 최댓값은 약 0.48에서 약 0.31로 낮아집니다. 두 component의 weight 0.6과 0.4는 prediction으로 바뀌지 않습니다.

3칸 복도

같은 계산을 discrete state에서 해봅니다. 복도에 칸 1, 2, 3이 있고 $\mathrm{bel}_0 = p(x_0) = [0.1,\ 0.8,\ 0.1]$입니다. 로봇에게 "제자리에 있어라"라고 명령했지만 미끄러질 수 있어서, 제자리 0.8, 왼쪽 한 칸 0.1, 오른쪽 한 칸 0.1로 움직인다고 하겠습니다. 벽 쪽으로 움직이려 하면 벽에 막혀 제자리에 남습니다.

L3 §3처럼 행을 이전 state로 두면 transition matrix는 다음과 같습니다.

Prediction 식 $\overline{\mathrm{bel}}_1(i) = \sum_j (T_{\text{stay}})_{ji}\, \mathrm{bel}_0(j)$는 행 vector로 쓰면 $\overline{\mathrm{bel}}_1 = \mathrm{bel}_0\, T_{\text{stay}}$입니다.

$\overline{\mathrm{bel}}_1 = [0.17,\ 0.66,\ 0.17]$입니다. Measurement를 보기 전인데도 2번 칸의 belief가 0.8에서 0.66으로 낮아졌습니다. 로봇이 미끄러질 수 있다는 transition noise가 belief를 퍼뜨린 결과입니다.

벽이 없다면 이 계산은 discrete convolution입니다. 벽이 없는 긴 복도에서 $[0.1,\ 0.8,\ 0.1]$과 kernel $[0.1,\ 0.8,\ 0.1]$의 discrete convolution은 칸 0부터 4까지 $[0.01,\ 0.16,\ 0.66,\ 0.16,\ 0.01]$입니다. 벽은 칸 0과 칸 4로 나갈 mass 0.01을 칸 1과 칸 3으로 되돌려 놓습니다. 그래서 $0.16 + 0.01 = 0.17$이 됩니다.

---

4. Update step 유도

이제 sensor가 $y_t$를 내놓았습니다. 구하려는 것은 $\mathrm{bel}_t(x_t) = p(x_t \mid y_{1:t})$입니다. $y_{1:t} = (y_{1:t-1}, y_t)$이므로 $p(x_t \mid y_{1:t})$와 $p(x_t \mid y_t, y_{1:t-1})$은 같은 것을 다르게 쓴 것입니다.

과거 measurement가 주어진 세계에서의 Bayes theorem

$p(x_t, y_t \mid y_{1:t-1})$을 product rule로 두 방향으로 쪼갭니다.

두 우변이 같으므로, $p(y_t \mid y_{1:t-1}) > 0$일 때 양변을 나누면 다음을 얻습니다.

L2 §1의 유도에 $y_{1:t-1}$을 조건으로 붙인 것입니다. 여기까지는 모델 가정을 하나도 쓰지 않았습니다.

각 항을 읽어봅니다.

• 좌변 $p(x_t \mid y_{1:t})$: 이번 update의 posterior, 즉 $\mathrm{bel}_t(x_t)$입니다.
• 분자의 $p(x_t \mid y_{1:t-1})$: §2에서 계산한 $\overline{\mathrm{bel}}_t(x_t)$이고, 이번 update의 prior입니다.
• 분자의 $p(y_t \mid x_t, y_{1:t-1})$: likelihood인데 아직 조건에 $y_{1:t-1}$이 붙어 있습니다.
• 분모 $p(y_t \mid y_{1:t-1})$: 이번 update의 evidence입니다. §5에서 다룹니다.

Measurement의 conditional independence

L3 §5의 두 번째 가정은 $p(y_t \mid x_{0:t}, y_{1:t-1}) = p(y_t \mid x_t)$입니다. 필요한 것은 $x_{0:t-1}$이 조건에 없는 형태이므로, §2와 같은 방법으로 한 줄씩 줄입니다.

말로 하면, 현재 state $x_t$를 알면 $y_t$의 distribution을 계산하는 데 과거 measurement와 과거 state가 더 필요하지 않습니다. 이것은 $x_t$가 주어졌을 때의 conditional independence입니다. 조건 없이 보면 $y_t$와 $y_{1:t-1}$은 같은 state trajectory에 의존하므로 일반적으로 dependent합니다.

이제 Bayes theorem의 결과에 대입합니다.

분모는 $x_t$에 의존하지 않으므로 $\eta = 1 / p(y_t \mid y_{1:t-1})$로 묶어 씁니다.

숫자로 보는 update

§2와는 별개의 예입니다. Prediction을 마친 결과가 $\overline{\mathrm{bel}}_t = [0.7,\ 0.3]$ ($A$, $B$ 순서)이고, sensor가 $y_t = z$를 내놓았습니다. Sensor model은 $p(y_t = z \mid A) = 0.2$, $p(y_t = z \mid B) = 0.9$입니다. $z$는 $B$에서 훨씬 잘 나오는 reading입니다.

곱의 합 0.41로 나누면 $0.14 / 0.41 \approx 0.341$, $0.27 / 0.41 \approx 0.659$입니다. Measurement 전에는 $A$가 더 그럴듯했지만, 뒤에는 $B$가 더 그럴듯합니다. Likelihood 열의 합이 1.1인 것은 오류가 아닙니다. Likelihood는 $y_t$를 고정한 $x_t$의 함수라서 $x_t$에 대해 더해 1이 될 필요가 없습니다 (L2 §2).

Update는 predicted belief에 likelihood를 칸마다 곱해서 모양을 바꾸고, 합으로 나눠 다시 distribution으로 만드는 두 동작입니다. §3 그림의 아래 두 panel이 continuous 버전입니다. Predicted belief는 왼쪽 component에 mass가 더 많았지만($x_t > 5$에 약 0.40), $y_t = 7.2$가 오른쪽 component와 맞으므로 update 뒤에는 $x_t > 5$에 약 0.999가 실립니다.

여기서 prior × likelihood를 계산한 곳은 고정된 state 값(칸) 하나하나입니다. Particle을 predicted belief에서 뽑으면(transition model로 propagate하면) prior가 particle의 위치에 이미 들어 있어서 weight가 달라집니다. 그 이야기는 L6 §6에서 합니다.

---

5. Normalization constant

$p(y_t \mid y_{1:t-1})$은 "과거 measurement $y_{1:t-1}$을 알 때 이번 measurement가 실제로 받은 값 $y_t$로 나올 확률"라고 읽습니다. $y_t$가 continuous이면 확률 대신 density입니다. 이 값은 $x_t$에 의존하지 않습니다. 반면 받은 $y_t$와 과거 $y_{1:t-1}$에는 의존하므로, 다른 measurement가 오면 값이 달라질 수 있습니다.

"$x_t$에 대해 상수"와 "어떤 measurement에도 같은 값"은 다른 말입니다 (L2 §4).

$\eta^{-1}$을 두 가지 방법으로 구해봅니다.

첫째: evidence로 유도하기

$y_t$가 나올 확률을 구하는데 현재 state $x_t$를 모르므로, $x_t$를 joint에 넣고 없앱니다.

따라서 다음이 성립합니다. Discrete state이면 integral이 sum입니다.

§4의 숫자로는 $0.2 \times 0.7 + 0.9 \times 0.3 = 0.14 + 0.27 = 0.41$이고 $\eta = 1/0.41 \approx 2.439$입니다. 이 값은 표의 "곱" 열의 합과 같습니다.

둘째: normalization 조건으로 유도하기

$\mathrm{bel}_t$는 distribution이므로 $x_t$에 대해 적분하면 1이어야 합니다. Update 식의 양변을 $x_t$에 대해 적분합니다.

양변을 적분값으로 나누면 첫째와 같은 식이 나옵니다. 모델이 정해 주는 evidence와, posterior의 합을 1로 만드는 상수가 정확히 같은 값입니다. 그래서 discrete 계산에서는 evidence를 따로 구하지 않고 곱의 합으로 나누기만 하면 됩니다.

$\eta$는 사용자가 고르는 parameter가 아니라 predicted belief와 likelihood에서 계산되는 값입니다 (L2 §3). $y_t$가 continuous이면 $p(y_t \mid y_{1:t-1})$은 density 값이므로 1보다 클 수도 있습니다.

Prediction과 evidence의 적분 variable이 다른 이유

Prediction은 $dx_{t-1}$로, evidence는 $dx_t$로 적분합니다.

규칙은 하나입니다. 좌변에 남으면 안 되는 variable로 적분합니다. Prediction의 좌변은 $x_t$의 함수이므로 $x_{t-1}$을 없애고, evidence의 좌변에는 state가 없으므로 $x_t$를 없앱니다.

---

6. 전체 알고리즘

두 식을 나란히 놓으면 Bayes filter 전체입니다.

필요한 것은 initial belief $p(x_0)$, transition model $p(x_t \mid x_{t-1})$, measurement model $p(y_t \mid x_t)$, 그리고 들어오는 measurement뿐입니다. Control input이 있으면 transition model을 $p(x_t \mid x_{t-1}, u_t)$로 쓰고, belief의 조건에도 $u$를 넣습니다. 이 강의에서는 조건에 $u$를 적지 않습니다.

$u$를 적으면 §2 유도의 둘째 줄은 $p(x_t \mid x_{t-1}, y_{1:t-1}, u_{1:t})\, p(x_{t-1} \mid y_{1:t-1}, u_{1:t})$가 됩니다. 앞 factor를 $p(x_t \mid x_{t-1}, u_t)$로 줄이는 것은 $u_t$를 남긴 가정 1입니다. 뒤 factor를 $\mathrm{bel}_{t-1}(x_{t-1}) = p(x_{t-1} \mid y_{1:t-1}, u_{1:t-1})$로 바꾸려면 $u_t$를 조건에 더해도 이 belief가 바뀌지 않아야 합니다. $u_t$를 미리 정해 두었거나 $y_{1:t-1}$과 이전 belief만으로 계산했다면, $u_t$는 $x_{t-1}$에 대한 추가 정보를 담지 않으므로 이 조건이 성립합니다(L3 §3).

State가 $M$개인 discrete filter의 한 step은 다음과 같습니다.

input : bel[1..M]      # bel_{t-1}
        T[j][i]        # p(x_t = i | x_{t-1} = j)
        L[i]           # p(y_t | x_t = i), received y_t
output: bel_new[1..M]  # bel_t

# prediction
for i in 1..M:
    bel_bar[i] = sum over j of T[j][i] * bel[j]

# update
for i in 1..M:
    g[i] = L[i] * bel_bar[i]
# p(y_t | y_{1:t-1}) = 1 / eta
evidence = sum over i of g[i]
for i in 1..M:
    bel_new[i] = g[i] / evidence

바깥 loop는 bel ← p(x_0)로 시작해서 $t = 1, 2, \dots$마다 $y_t$를 받고 위 step을 실행합니다.

3칸 복도를 두 step 돌리기

§3의 복도를 이어서 씁니다. L2 §5처럼 칸 1, 2, 3에서 기대되는 거리 reading은 각각 2 m, 5 m, 8 m입니다. Sensor 출력을 이 세 값 중 가장 가까운 값으로 바꿔서 받는다고 하고, measurement model을 다음 표로 정합니다.

각 행은 state 하나에서 나올 reading의 distribution이라 합이 1입니다. 각 열은 reading 하나를 고정한 likelihood라 합이 1일 필요가 없습니다. $y = 5\,$m 열은 L2 §5의 likelihood $[0.05,\ 0.8,\ 0.1]$과 같습니다. 나머지 값도 L2 §5의 sensor처럼 거리가 멀수록 noise가 크다고 두고 정했습니다. 그래서 반대쪽 끝의 reading이 나올 확률도, 벽까지 8 m인 3번 칸에서 2 m로 읽힐 확률 0.05가 벽까지 2 m인 1번 칸에서 8 m로 읽힐 확률 0.02보다 큽니다.

Transition model은 명령에 따라 둘입니다. Step 1의 명령은 "제자리"이고 §3의 $T_{\text{stay}}$를 씁니다. Step 2의 명령은 "오른쪽으로 한 칸"이고, 0.8로 성공하고 0.2로 실패해 제자리에 남으며, 3번 칸에서는 벽 때문에 그대로 있습니다.

Measurement는 $y_1 = 5\,$m, $y_2 = 8\,$m가 들어왔습니다. 계산은 반올림하기 전 값으로 했습니다.

3칸 복도에서 Bayes filter를 두 step 실행한 결과입니다. 파랑은 prior 역할의 belief, 주황은 likelihood, 초록은 update 뒤의 belief이고, 둘째 줄 첫 panel은 첫째 줄의 결과를 그대로 가져온 것입니다.

Step 1에서 prediction은 belief를 퍼뜨렸고(0.8 → 0.66), measurement 5 m가 2번 칸과 잘 맞아서 update가 belief를 모았습니다(0.954). Step 2에서 prediction은 mass를 오른쪽으로 옮겼습니다. 2번 칸의 0.203은 2번 칸에서 이동에 실패한 $0.2 \times 0.954 \approx 0.191$과 1번 칸에서 오른쪽으로 온 $0.8 \times 0.015 \approx 0.012$의 합입니다. Measurement 8 m가 3번 칸과 맞아서 update 뒤 3번 칸이 0.971이 됩니다.

이 예에서는 update가 belief를 모았지만, 항상 그런 것은 아닙니다. Step 2에서 $y_2 = 2\,$m가 들어왔다면 likelihood $[0.93,\ 0.10,\ 0.05]$와 곱한 합이 약 0.0629이고, posterior는 약 $[0.045,\ 0.323,\ 0.631]$입니다. 가장 큰 값이 predicted belief의 0.794보다 낮아집니다. Predicted belief와 어긋나는 measurement는 belief를 더 퍼뜨릴 수 있습니다.

---

7. 왜 그대로는 계산하기 어려운가

위 알고리즘은 칸이 3개일 때는 손으로도 됩니다. 어려움은 state space가 커질 때 생깁니다.

첫째, belief는 state space 전체 위의 함수입니다. Prediction은 모든 $x_t$ 값마다 $x_{t-1}$ 전체에 대한 integral을 하나씩 계산해야 하고, update도 모든 $x_t$에서 곱한 뒤 $x_t$ 전체에 대해 적분해야 합니다.

둘째, grid로 근사하면 차원에 따라 크기가 지수적으로 늘어납니다. 각 축을 $M$칸으로 나누면 $n$차원 state의 칸 수는 $M^n$입니다. $M = 100$, $n = 10$이면 $100^{10} = 10^{20}$칸입니다. Transition이 모든 칸 쌍을 연결한다면 prediction 한 번에 $10^{20} \times 10^{20} = 10^{40}$번의 곱셈이 필요합니다.

Floating base 로봇은 base의 pose와 velocity만 해도 12차원이므로 $n = 10$은 큰 값이 아닙니다.

셋째, 일반적으로 closed form이 없습니다. Dynamics나 measurement model이 nonlinear이거나 noise가 Gaussian이 아니면, prediction과 update의 결과는 보통 유한한 개수의 parameter로 적히는 distribution family에 머물지 않습니다. State 수가 유한한 discrete model처럼 특수한 구조가 있으면 예외입니다. 똑같이 생긴 두 복도 중 어디인지 모르는 경우처럼 belief가 multimodal이면, mean과 variance 두 숫자로는 belief를 표현할 수 없습니다.

Continuous state에서 중요한 예외가 하나 있습니다. Dynamics와 measurement가 linear이고, noise가 Gaussian이며 시간에 걸쳐 independent하고 서로와 $x_0$에도 independent하고, $p(x_0)$도 Gaussian이면 belief가 계속 Gaussian으로 남고 이 recursion은 Kalman filter라는 closed form을 가집니다. Kalman filter는 따로 공부합니다.

그래서 belief 함수 전체를 저장하는 대신, belief가 큰 곳에 모이는 sample로 belief를 표현합니다. Prediction의 integral은 transition model에서 sample을 뽑는 것으로 바뀌고(L5 §6), update의 곱셈은 weight로 바뀝니다(L6 §6). 출발점은 L5 §1입니다.

---

이해 확인

1. Prediction 유도의 셋째 줄에서 transition factor의 조건 $y_{1:t-1}$을 지울 수 있는 이유를 설명하시오. 또한 그런데도 결과식이 여전히 $y_{1:t-1}$에 의존하는 이유를 설명하시오.

2. $\mathrm{bel}_{t-1} = [0.3,\ 0.7]$에서 가장 그럴듯한 $B$만 대입하면 $P(X_t = B) = 0.9$, 제대로 계산하면 0.69이다. 이 차이가 어떤 정보를 버려서 생기는지 설명하고, 대입이 정확한 답을 주는 경우를 쓰시오.

3. Prediction은 $dx_{t-1}$로, evidence는 $dx_t$로 적분한다. 각각 무엇을 없애려는 것이며 결과가 무엇의 함수인지 설명하시오.

4. Discrete Bayes filter에서 evidence를 따로 계산하지 않고 "곱의 합으로 나누기"만 해도 되는 이유를 설명하시오.

---

답

1. L3의 Markov assumption은 $x_{0:t-1}$과 $y_{1:t-1}$이 주어졌을 때 $x_t$의 distribution이 $x_{t-1}$에만 의존한다는 것입니다. $x_{0:t-2}$를 marginalize하고 product rule과 합이 1인 성질을 쓰면 $p(x_t \mid x_{t-1}, y_{1:t-1}) = p(x_t \mid x_{t-1})$을 얻습니다. 그러나 $x_{t-1}$을 모르기 때문에 $y_{1:t-1}$은 $\mathrm{bel}_{t-1}(x_{t-1}) = p(x_{t-1} \mid y_{1:t-1})$을 통해 결과에 남습니다. → §2

2. $A$였을 확률 0.3을 $B$로 취급해서 생깁니다. 차이는 $0.3 \times (0.9 - 0.2) = 0.21$입니다. $\mathrm{bel}_{t-1}$의 mass가 전부 한 state에 있으면 대입이 정확하고, 그때는 transition noise만 uncertainty로 남습니다. Mass가 있는 모든 이전 state에서 $X_t = B$로 갈 transition probability가 같을 때도 값이 같아지지만, 이 예의 0.2와 0.9처럼 다르면 point mass일 때뿐입니다. → §2, §3

3. Prediction은 좌변이 $x_t$의 함수여야 하므로 이전 state $x_{t-1}$을 없앱니다. Evidence는 좌변에 state가 없어야 하므로 현재 state $x_t$를 없애고, 받은 $y_t$에 대한 숫자 하나가 남습니다. → §5

4. Evidence를 marginalization, product rule, conditional independence로 유도한 식과, $\mathrm{bel}_t$의 합이 1이라는 조건에서 유도한 식이 같은 $\sum_{x_t} p(y_t \mid x_t)\, \overline{\mathrm{bel}}_t(x_t)$이기 때문입니다. 곱의 합이 곧 evidence입니다. → §5