L3 · Hidden State Models

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

이 강의는 시간에 따라 변하는 hidden state와 매 시각 들어오는 measurement를 확률 모델로 적는 방법을 다룹니다. Bayes filter 식을 유도하기 직전까지, 어떤 가정이 필요하고 그 가정이 정확히 무엇을 말하는지 정리합니다.

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

1. 시간이 들어오면

L1과 L2에서는 random variable 두 개, $X$ 와 $Y$ 만 봤습니다. 로봇 위치 $X$ 하나와 센서 값 $Y$ 하나를 놓고 Bayes theorem으로 $p(x \mid y)$ 를 계산했습니다.

실제 로봇은 움직입니다. 위치가 시간에 따라 바뀌므로 random variable 하나로는 부족하고, 시각마다 하나씩 필요합니다.

X_0,\ X_1,\ X_2,\ \dots

$X_t$ 는 시각 $t$ 에서의 위치입니다. 센서도 시각마다 새 값을 줍니다.

Y_1,\ Y_2,\ Y_3,\ \dots

Hidden state와 measurement

앞으로 random variable은 두 종류로 나뉩니다.

Hidden state $X_t$ 는 시각 $t$ 에서 우리가 알고 싶지만 직접 관측하지 못하는 양입니다. latent state라고도 합니다. 예를 들어 로봇의 위치와 velocity, 지면 상태, 추적하는 물체의 위치가 여기에 해당합니다.
Measurement $Y_t$ 는 시각 $t$ 에 센서가 실제로 내놓는 값입니다. observation이라고도 합니다. camera image, lidar distance, IMU reading, encoder count, GPS fix가 예입니다.

Measurement는 state 자체가 아닙니다. 센서는 state에 noise가 섞인 값이나 state의 일부만을 보여 주므로, state는 measurement들로부터 추론해야 합니다. 이 추론을 확률 계산으로 하는 것이 이 시리즈의 Bayes filter입니다.

대문자 $X_t$ 는 random variable이고 소문자 $x_t$ 는 그것이 취하는 값입니다(L1 §2). 논문에서는 이 구분을 느슨하게 쓰는 경우가 많습니다.

시간 index 규칙

이 시리즈는 다음 규칙을 씁니다.

State는 $t=0$ 부터 있습니다. $x_0$ 에 대해서는 measurement가 없고, 초기 belief $p(x_0)$ 만 있습니다.
Measurement는 $t=1$ 부터 들어옵니다. $y_1$ 은 $x_1$ 에 대한 첫 measurement입니다.

$p(x_0)$ 를 어떻게 정하는지는 L2 §6에서 봤습니다. 이 강의는 $t$ 가 커질 때 $p(x_t \mid y_1, \dots, y_t)$ 를 계산하는 데 필요한 모델과 가정을 정리합니다.

2. 시퀀스 notation 읽기

Bayes filter 식에는 colon이 들어간 아래첨자가 계속 나옵니다.

x_{0:t} = (x_0, x_1, \dots, x_t), \qquad y_{1:t} = (y_1, y_2, \dots, y_t)

$x_{0:t}$ 는 " $x_0$ 부터 $x_t$ 까지"라고 읽습니다. 예를 들어 $y_{1:3} = (y_1, y_2, y_3)$ 입니다. colon은 "처음부터 여기까지의 sequence 전체"를 뜻합니다. $p(x_{0:t})$ 는 이 sequence 전체의 joint distribution입니다.

$t=1$ 이면 $y_{1:0}$ 은 빈 sequence입니다. 그래서 $p(x_1 \mid y_{1:0})$ 은 조건이 없는 $p(x_1)$ 과 같습니다. 이 규칙 덕분에 첫 step을 따로 적지 않아도 됩니다.

두 belief 읽기

이제 filter의 중심에 있는 두 식을 읽습니다.

p(x_t \mid y_{1:t-1})

이 식은 " $y_1$ 부터 $y_{t-1}$ 까지 주어졌을 때 $x_t$ 의 distribution"이라고 읽습니다. 시각 $t$ 의 measurement $y_t$ 는 아직 보지 않았습니다. 지금까지의 센서 정보로 현재 state를 예측한 belief이므로 predicted belief라고 부르고 $\overline{\mathrm{bel}}_t(x_t)$ 로 씁니다.

p(x_t \mid y_{1:t})

이 식은 " $y_1$ 부터 $y_t$ 까지 주어졌을 때 $x_t$ 의 distribution"입니다. 이번에는 $y_t$ 까지 반영했습니다. 이것을 filtering belief라고 부르고 $\mathrm{bel}_t(x_t)$ 로 씁니다.

두 식의 차이는 bar 뒤에 $y_t$ 가 있느냐 하나뿐이고, 그 차이를 메우는 계산이 Bayes theorem을 쓰는 update입니다. 그 update에서 $\overline{\mathrm{bel}}_t$ 가 prior 자리에, $\mathrm{bel}_t$ 가 posterior 자리에 들어갑니다. 유도는 L4 §4에서 합니다.

읽기 연습

$p(x_4 \mid y_{1:3})$ 을 읽어 봅니다.

Bar 앞의 $x_4$ 는 distribution을 묻는 대상, 곧 시각 4의 state입니다.
Bar 뒤의 $y_{1:3} = (y_1, y_2, y_3)$ 은 이미 본 measurement입니다.
$y_4$ 는 bar 뒤에 없으므로 아직 보지 않았습니다.

그래서 이 식은 시각 4의 predicted belief $\overline{\mathrm{bel}}_4(x_4)$ 입니다.

식	읽는 법	$y_t$ 반영	이름
$p(x_t \mid y_{1:t-1})$	$y_{t-1}$ 까지 보고, $y_t$ 를 보기 전의 $x_t$	아니오	predicted belief $\overline{\mathrm{bel}}_t$
$p(x_t \mid y_{1:t})$	$y_t$ 까지 본 뒤의 $x_t$	예	filtering belief $\mathrm{bel}_t$
$p(x_{0:t} \mid y_{1:t})$	$y_t$ 까지 본 뒤의 state sequence 전체	예	path posterior (L7에서 사용)

3. Transition model과 measurement model

Hidden state model은 initial belief $p(x_0)$ 와 함께 두 개의 conditional distribution으로 만들어집니다. 하나는 state가 시간에 따라 어떻게 변하는지를, 다른 하나는 state에서 measurement가 어떻게 나오는지를 말합니다.

Transition model

p(x_t \mid x_{t-1})

"이전 state가 $x_{t-1}$ 일 때 현재 state $x_t$ 의 distribution"이라고 읽습니다. 이것을 transition model이라고 합니다. dynamics model 또는 motion model이라고도 부릅니다. Bar 뒤의 $x_{t-1}$ 은 정확히 안다고 놓은 값이고, 불확실한 것은 bar 앞의 $x_t$ 뿐입니다.

Discrete: transition matrix

세 칸 $\{1,2,3\}$ 위의 로봇이 보통 오른쪽으로 한 칸 가지만, 제자리에 머물거나 뒤로 밀리기도 한다고 합시다. 모든 경우를 matrix 하나로 적을 수 있습니다.

T = \begin{bmatrix} 0.2 & 0.8 & 0 \\ 0.1 & 0.2 & 0.7 \\ 0 & 0.2 & 0.8 \end{bmatrix}, \qquad T_{ij} = P(X_t = j \mid X_{t-1} = i)

행은 이전 state, 열은 현재 state입니다. 첫 행은 " $X_{t-1}=1$ 이면 0.2의 확률로 1에 머물고 0.8의 확률로 2로 간다"는 뜻입니다. 오른쪽 끝인 3에서는 더 갈 곳이 없어서 0.8의 확률로 머뭅니다.

각 행의 합은 1이지만, 각 열의 합은 1일 필요가 없습니다. 행 $i$ 는 조건 $X_{t-1}=i$ 를 고정한 뒤 $X_t$ 에 대한 distribution이므로 합이 1입니다(L1 §5). 열 $j$ 는 서로 다른 조건에서 같은 칸 $j$ 로 갈 확률을 모은 것이라 distribution이 아닙니다. 이 matrix의 열 합은 $0.3,\ 1.2,\ 1.5$ 입니다.

이 강의에서는 매 step 같은 $T$ 를 쓴다고 둡니다. 모델에 따라 transition이 시각이나 제어 입력에 따라 달라질 수도 있습니다.

Continuous: noise가 들어간 운동 방정식

위치가 실수이고, 명령한 이동량 $u_t$ 만큼 움직이되 noise가 섞인다고 합시다.

x_t = x_{t-1} + u_t + \epsilon_t, \qquad \epsilon_t \sim \mathcal{N}(0, \sigma^2)

여기서 $\epsilon_t$ 는 $X_{t-1}$ 을 포함한 과거의 모든 variable과 independent라고 가정합니다. 그러면 $X_{t-1} = x_{t-1}$ 로 고정했을 때 $\epsilon_t$ 의 distribution은 그대로이고, $X_t$ 는 상수 $x_{t-1} + u_t$ 에 그 noise를 더한 값입니다. mean만 옮겨진 Gaussian이 됩니다.

p(x_t \mid x_{t-1}) = \mathcal{N}(x_t;\ x_{t-1} + u_t,\ \sigma^2) = \frac{1}{\sqrt{2\pi}\,\sigma} \exp\!\left(-\frac{(x_t - x_{t-1} - u_t)^2}{2\sigma^2}\right)

$\mathcal{N}(x_t;\ \mu,\ \sigma^2)$ 는 "mean $\mu$ , variance $\sigma^2$ 인 Gaussian density를 $x_t$ 에서 계산한 값"이라고 읽습니다. 예를 들어 $x_{t-1}=3$ , $u_t=1$ , $\sigma=0.2$ 이면 $x_t$ 는 4를 중심으로 퍼지고, $[3.6,\ 4.4]$ 안에 들어갈 확률은 약 $0.954$ 입니다.

$u_t$ 는 filter가 계산하는 시점에 이미 값을 알고 있으므로 bar 뒤에 조건으로 둡니다. 엄밀하게는 $p(x_t \mid x_{t-1}, u_t)$ 로 써야 하지만, 이 시리즈에서는 보통 $u_t$ 를 생략하고 $p(x_t \mid x_{t-1})$ 로 씁니다.

이렇게 생략하려면 $u_t$ 가 $y_{1:t-1}$ 과 $u_{1:t-1}$ 이 주는 것 이상의 정보를 $x_{t-1}$ 에 대해 담지 않아야 합니다. 기호로는 $p(x_{t-1} \mid y_{1:t-1}, u_{1:t}) = p(x_{t-1} \mid y_{1:t-1}, u_{1:t-1})$ 입니다. $u_t$ 를 미리 정해 두었거나 과거 measurement와 belief만으로 계산하면 이 조건이 성립합니다. 반대로 state에도 영향을 주는 hidden variable이 $u_t$ 를 정하면 깨집니다.

Measurement model

p(y_t \mid x_t)

"현재 state가 $x_t$ 일 때 measurement $y_t$ 의 distribution"이라고 읽습니다. 이것을 measurement model이라고 합니다. observation model 또는 sensor model이라고도 부릅니다.

Discrete: near/far 센서

벽까지의 거리를 "near"와 "far" 두 값으로만 알려 주는 센서를 생각합니다. 벽은 칸 1 쪽에 있습니다.

$x_t$	$P(Y_t = \text{near} \mid x_t)$	$P(Y_t = \text{far} \mid x_t)$	행 합
1	0.9	0.1	1
2	0.5	0.5	1
3	0.1	0.9	1

센서가 완벽하지 않으므로 칸 1에서도 가끔 "far"가 나옵니다. 각 행은 $x_t$ 를 고정한 뒤 $Y_t$ 에 대한 distribution이므로 합이 1입니다.

측정값이 들어와 $y_t = \text{near}$ 로 고정되면, near 열을 $x_t$ 의 함수로 읽습니다. 이것이 likelihood이고, 합은 $0.9 + 0.5 + 0.1 = 1.5$ 로 1이 아닙니다(L2 §2). 같은 table을 행 방향으로 읽으면 measurement model이고, 관측된 값의 열 하나를 세로로 읽으면 likelihood입니다.

Continuous: 위치를 noise와 함께 재는 센서

y_t = x_t + \nu_t, \qquad \nu_t \sim \mathcal{N}(0, \sigma_y^2)

$\nu_t$ 가 $x_t$ 와 independent이면 transition model과 같은 이유로 다음이 됩니다.

p(y_t \mid x_t) = \mathcal{N}(y_t;\ x_t,\ \sigma_y^2)

$\sigma_y = 0.5$ 이고 $x_t = 5$ 라고 합시다. $y_t = 5.1$ 에서 이 density의 값은 약 $0.78$ 이고, $y_t = 20$ 에서는 약 $3 \times 10^{-196}$ 입니다. 이 값들은 probability가 아니라 density 값입니다. 측정값이 20으로 들어오면 " $x_t = 5$ "라는 가설의 likelihood는 이만큼 작아집니다.

두 모델은 누가 정하는가

	transition model	measurement model
식	$p(x_t \mid x_{t-1})$	$p(y_t \mid x_t)$
무엇에 대한 distribution인가	현재 state $x_t$	현재 measurement $y_t$
조건으로 고정한 것	이전 state $x_{t-1}$ (와 알고 있는 $u_t$ )	현재 state $x_t$
보통 어디서 오는가	운동 방정식과 process noise 모델	센서 방정식과 calibration으로 정한 noise 모델

두 모델 모두 엔지니어가 정하는 모델입니다. 실제 시스템과 어긋날 수 있고, 어긋나면 filter가 내는 belief도 틀어질 수 있습니다.

4. Conditional independence

§5의 두 가정은 모두 conditional independence로 적힙니다. 먼저 정의를 보고, 숫자 예로 확인합니다.

정의

$C$ 가 주어졌을 때 $A$ 와 $B$ 가 conditionally independent라는 것은, $p(c) > 0$ 인 모든 $c$ 와 모든 $a, b$ 에 대해 다음이 성립한다는 뜻입니다.

p(a, b \mid c) = p(a \mid c)\, p(b \mid c)

이것을 $A \perp B \mid C$ 라고 쓰고, " $C$ 가 주어지면 $A$ 와 $B$ 는 independent하다"라고 읽습니다. 성립하지 않으면 $A \not\perp B \mid C$ 로 씁니다. 조건이 없는 $A \perp B$ 는 보통의 independence입니다.

같은 조건을 다른 형태로 쓸 수도 있습니다. $p(b, c) > 0$ 인 곳에서 다음과 같습니다.

p(a \mid b, c) = p(a \mid c)

두 형태가 같다는 것은 product rule을 $c$ 를 조건으로 둔 형태에서 바로 보입니다. 먼저 그 형태를 확인합니다.

\begin{aligned} p(a, b \mid c) &= \frac{p(a, b, c)}{p(c)} && \text{(definition of conditional)} \\ &= \frac{p(a \mid b, c)\, p(b, c)}{p(c)} && \text{(product rule)} \\ &= p(a \mid b, c)\, p(b \mid c) && \text{(definition of conditional)} \end{aligned}

이 식에서 $p(a \mid b, c)$ 를 $p(a \mid c)$ 로 바꾸면 첫 번째 형태가 나옵니다. 반대로 첫 번째 형태가 성립하면 $p(a \mid c)\,p(b \mid c) = p(a \mid b, c)\,p(b \mid c)$ 이고, 양변을 $p(b \mid c) > 0$ 으로 나누면 두 번째 형태가 나옵니다.

두 번째 형태가 뜻을 더 잘 보여 줍니다. $C$ 를 이미 알고 있으면, $B$ 를 추가로 알아도 $A$ 에 대한 belief가 바뀌지 않습니다.

예: 비, 우산, 젖은 땅

$R$ 은 비가 오는지( $1$ 또는 $0$ ), $U$ 는 우산 든 사람이 보이는지, $W$ 는 땅이 젖었는지입니다. 모델을 다음과 같이 정합니다.

$P(R=1) = 0.3$
$P(U=1 \mid R=1) = 0.8$ , $P(U=1 \mid R=0) = 0.1$
$P(W=1 \mid R=1) = 0.9$ , $P(W=1 \mid R=0) = 0.2$
비가 오는지가 정해지면 우산과 땅은 서로 영향을 주지 않습니다. 곧 $U \perp W \mid R$ 입니다.

$R$ 을 모르는 상태에서 먼저 $P(W=1)$ 과 $P(U=1)$ 을 law of total probability로 구합니다.

P(W=1) = 0.9 \times 0.3 + 0.2 \times 0.7 = 0.41, \qquad P(U=1) = 0.8 \times 0.3 + 0.1 \times 0.7 = 0.31

다음으로 둘이 함께 일어날 확률을 구합니다. 여기서 $R$ 에 대해 합하는 것은 모르는 $R$ 을 없애는 marginalization입니다.

\begin{aligned} P(W=1, U=1) &= \sum_{r \in \{0,1\}} P(W=1, U=1, R=r) && \text{(marginalization)} \\ &= \sum_{r} P(W=1, U=1 \mid R=r)\, P(R=r) && \text{(product rule)} \\ &= \sum_{r} P(W=1 \mid R=r)\, P(U=1 \mid R=r)\, P(R=r) && \text{(conditional independence)} \\ &= 0.9 \times 0.8 \times 0.3 + 0.2 \times 0.1 \times 0.7 = 0.230 \end{aligned}

그러면 우산을 본 뒤 땅이 젖었을 확률은 다음과 같습니다.

P(W=1 \mid U=1) = \frac{P(W=1, U=1)}{P(U=1)} = \frac{0.230}{0.31} \approx 0.742

우산을 봤다는 사실이 땅이 젖었을 확률을 $0.41$ 에서 약 $0.742$ 로 올렸습니다. 따라서 $U$ 와 $W$ 는 independent가 아닙니다. 우산이 땅을 적시는 것이 아니라, 우산이 비에 대한 정보를 주고 비가 땅을 적시기 때문입니다.

비가 온다는 것을 알고 나면 달라집니다. conditional independence에 의해 $P(W=1 \mid U=1, R=1) = P(W=1 \mid R=1) = 0.9$ 이고, 우산은 더 이상 정보를 주지 않습니다.

$A \perp B \mid C$ 는 $A \perp B$ 를 뜻하지 않습니다. 이 예에서 $U \perp W \mid R$ 이지만 $U \not\perp W$ 입니다. §6에서 filter의 state와 과거 measurement 사이에 같은 구조가 나옵니다.

반대 방향도 일반적으로 성립하지 않습니다. 동전 두 개를 independent하게 던진 결과를 $A, B \in \{0, 1\}$ 로, $C = A \oplus B$ (XOR)로 두면 $A \perp B$ 입니다. 그런데 $C$ 가 주어지면 $B$ 가 $A$ 를 정확히 정하므로, 예를 들어 $P(A=1 \mid C=0) = 0.5$ 이지만 $P(A=1 \mid B=1, C=0) = 1$ 이고 $A \not\perp B \mid C$ 입니다.

Conditional independence는 데이터에서 저절로 나오는 사실이 아니라, 모델을 만들 때 넣는 가정입니다. 이 예에서도 네 번째 줄에서 그렇게 정했습니다.

5. 두 가정과 joint의 분해

Bayes filter가 hidden state model에 두는 가정은 두 개이고, 둘 다 §4의 conditional independence입니다. 유도의 label에서는 가정 1을 Markov assumption, 가정 2를 measurement CI(conditional independence)로 줄여 쓰고, 뒤 강의의 유도도 같은 label을 씁니다.

가정 1: Markov assumption

p(x_t \mid x_{0:t-1},\ y_{1:t-1}) = p(x_t \mid x_{t-1})

"과거 state 전체와 과거 measurement 전체가 주어졌을 때 $x_t$ 의 distribution은, 바로 이전 state $x_{t-1}$ 만 주어졌을 때의 distribution과 같다"고 읽습니다. §4의 기호로는 $X_t \perp (X_{0:t-2},\ Y_{1:t-1}) \mid X_{t-1}$ 입니다.

이전 state $x_{t-1}$ 을 정확히 알면, 그보다 오래된 state와 지금까지의 measurement는 $x_t$ 에 대해 추가 정보를 주지 않는다는 가정입니다. Probabilistic Robotics는 가정 1과 가정 2를 모두 하나의 complete state assumption에서 끌어내고, 그 가정을 Markov assumption이라고도 부릅니다. 이 시리즈는 유도의 label을 붙이기 위해 둘을 나눠, 가정 1만 Markov assumption이라고 부릅니다. Bayesian Filtering and Smoothing은 bar 뒤에 과거 measurement를 넣은 형태로 Markov property를 적습니다. Bar 뒤에 $y_{1:t-1}$ 까지 들어간 이 형태가 L4의 prediction step 유도에 필요한 형태입니다.

묶음 전체에 대한 conditional independence는 그 일부에 대해서도 성립합니다. $p(a, b_1, b_2 \mid c) = p(a \mid c)\,p(b_1, b_2 \mid c)$ 의 양변에서 $b_2$ 를 marginalize하면 $p(a, b_1 \mid c) = p(a \mid c)\,p(b_1 \mid c)$ 가 되기 때문입니다. 그래서 가정 1에서 $p(x_t \mid x_{t-1},\ y_{1:t-1}) = p(x_t \mid x_{t-1})$ 도 성립합니다.

가정 2: measurement의 conditional independence

p(y_t \mid x_{0:t},\ y_{1:t-1}) = p(y_t \mid x_t)

" $x_0$ 부터 $x_t$ 까지의 모든 state와 과거 measurement가 주어졌을 때 $y_t$ 의 distribution은, 현재 state $x_t$ 만 주어졌을 때와 같다"고 읽습니다. 기호로는 $Y_t \perp (X_{0:t-1},\ Y_{1:t-1}) \mid X_t$ 입니다.

현재 measurement는 현재 state가 주어지면 과거 state와 과거 measurement에 대해 conditionally independent합니다. 그냥 "independent"라고 하면 틀립니다. $x_t$ 를 모르면 $y_t$ 와 $y_{t-1}$ 은 보통 dependent입니다. 두 measurement가 인접한 두 시각의 state에서 나왔고, 그 두 state가 transition model로 이어져 있기 때문입니다.

센서 noise가 서로 다른 시각끼리 independent하고 process noise와 $x_0$ 과도 independent하면 이 가정이 성립합니다(조건 전체는 §7). 센서에 천천히 변하는 bias가 있으면 noise가 시간에 따라 correlated이므로 가정 2가 깨집니다. 이런 경우에는 bias를 state에 포함시켜 모델을 다시 잡습니다.

Markov는 state를 어떻게 잡느냐의 성질

Markov assumption은 "과거가 중요하지 않다"는 뜻이 아닙니다. 과거가 미래에 주는 영향이 전부 $x_{t-1}$ 을 거쳐 전달되도록 state를 잡았다는 뜻입니다.

일정한 velocity로 움직이는 물체를 생각합니다. State를 위치 $s_t$ 하나로 잡으면, $s_{t-1}$ 만으로는 물체가 어느 방향으로 얼마나 빨리 가는지 알 수 없습니다. $s_{t-2}$ 를 함께 알면 $s_{t-1} - s_{t-2}$ 로 velocity를 추정할 수 있으므로 $s_{t-2}$ 가 추가 정보를 줍니다. 위치만으로는 Markov가 아닙니다.

State를 $x_t = [s_t,\ \dot s_t]^\top$ 로 잡고 두 성분에 들어가는 noise가 시각마다 independent하다면, 현재 위치와 velocity만으로 다음 state의 distribution이 정해집니다. 과거 위치들이 주던 정보는 $\dot s_t$ 에 들어 있습니다. 같은 물리 시스템이라도 state를 무엇으로 잡느냐에 따라 Markov assumption이 성립하기도 하고 깨지기도 합니다.

실제 로봇에서는 state가 결과에 영향을 주는 모든 것을 담는 경우가 드물어서, 두 가정은 보통 근사로만 성립합니다. 흔한 원인은 모델에 넣지 않은 환경의 dynamics, transition model과 measurement model 자체의 오차, belief를 grid나 particle로 근사할 때 생기는 오차, 그리고 여러 step의 control을 함께 정하는 hidden variable입니다. State를 늘리면 가정에 가까워지지만 계산량이 커지므로, 일부러 작은 state를 쓰기도 합니다. 모델에 넣지 않은 영향이 시각마다 independent한 noise에 가깝도록 state를 잡으면, filter는 이런 약한 위반에 크게 흔들리지 않는 경우가 많습니다.

RL에서도 같은 성질을 요구합니다. Markov Decision Process (MDP)의 state는 다음 state와 reward의 distribution이 현재 state와 action만으로 정해지도록 잡습니다. 차이는 MDP에서는 agent가 state를 직접 본다는 점이고, 이 시리즈에서는 state가 hidden이라 measurement로 추론해야 한다는 점입니다.

Joint distribution을 가정 하나씩 써서 분해하기

$t=2$ 까지의 모든 variable $x_0, x_1, y_1, x_2, y_2$ 의 joint를 봅니다. 도구는 chain rule이고, chain rule은 product rule(L1 §6)을 반복한 것입니다. Variable이 세 개이면 다음과 같습니다.

\begin{aligned} p(a, b, c) &= p(c \mid a, b)\, p(a, b) && \text{(product rule)} \\ &= p(c \mid a, b)\, p(b \mid a)\, p(a) && \text{(product rule)} \end{aligned}

이 전개는 variable의 순서를 어떻게 잡아도 등식으로 맞습니다. 순서를 시간 순서 $x_0, x_1, y_1, x_2, y_2$ 로 잡으면 각 factor의 bar 뒤에 그보다 앞선 variable만 옵니다. 그래서 바꿔야 하는 factor마다 두 가정 중 하나가 정확히 들어맞습니다.

p(x_0, x_1, y_1, x_2, y_2) = p(x_0)\; p(x_1 \mid x_0)\; p(y_1 \mid x_{0:1})\; p(x_2 \mid x_{0:1}, y_1)\; p(y_2 \mid x_{0:2}, y_1) \qquad \text{(chain rule)}

$p(x_1 \mid x_0)$ 는 이미 바로 이전 state만 조건으로 가지고 있어서 그대로 둡니다. 나머지 세 factor를 하나씩 바꿉니다.

\begin{aligned} p(y_1 \mid x_{0:1}) &= p(y_1 \mid x_1) && \text{(measurement CI, } t=1\text{)} \\ p(x_2 \mid x_{0:1}, y_1) &= p(x_2 \mid x_1) && \text{(Markov assumption, } t=2\text{)} \\ p(y_2 \mid x_{0:2}, y_1) &= p(y_2 \mid x_2) && \text{(measurement CI, } t=2\text{)} \end{aligned}

모두 대입하면 다음을 얻습니다.

p(x_0, x_1, y_1, x_2, y_2) = p(x_0)\; p(x_1 \mid x_0)\; p(y_1 \mid x_1)\; p(x_2 \mid x_1)\; p(y_2 \mid x_2)

순서를 $x_0, x_1, x_2, y_1, y_2$ 로 잡으면 $p(y_1 \mid x_0, x_1, x_2)$ 라는 factor가 생기는데, 미래 state $x_2$ 가 bar 뒤에 있어서 두 가정 어느 쪽도 그대로 적용되지 않습니다. 이 모델에서 $p(y_1 \mid x_{0:2}) = p(y_1 \mid x_1)$ 자체는 성립하지만, 그것은 위의 factorization을 얻은 뒤에 보일 수 있는 결과이지 가정에서 바로 나오지 않습니다.

일반 t

같은 일을 시각 $t$ 에서 한 번 합니다. $p(x_{0:t}, y_{1:t})$ 에서 가장 늦은 $y_t$ 와 $x_t$ 를 차례로 떼어 냅니다.

\begin{aligned} p(x_{0:t},\ y_{1:t}) &= p(y_t \mid x_{0:t},\ y_{1:t-1})\; p(x_{0:t},\ y_{1:t-1}) && \text{(product rule)} \\ &= p(y_t \mid x_{0:t},\ y_{1:t-1})\; p(x_t \mid x_{0:t-1},\ y_{1:t-1})\; p(x_{0:t-1},\ y_{1:t-1}) && \text{(product rule)} \\ &= p(y_t \mid x_t)\; p(x_t \mid x_{0:t-1},\ y_{1:t-1})\; p(x_{0:t-1},\ y_{1:t-1}) && \text{(measurement CI)} \\ &= p(y_t \mid x_t)\; p(x_t \mid x_{t-1})\; p(x_{0:t-1},\ y_{1:t-1}) && \text{(Markov assumption)} \end{aligned}

마지막 줄의 $p(x_{0:t-1}, y_{1:t-1})$ 에 같은 과정을 시각 $t-1, t-2, \dots, 1$ 에서 반복하면 $p(x_0)$ 만 남습니다. 결과는 다음과 같습니다. $\prod_{k=1}^{t}$ 는 $k=1$ 부터 $t$ 까지의 factor를 모두 곱한다는 뜻입니다.

\boxed{\,p(x_{0:t},\ y_{1:t}) = p(x_0) \prod_{k=1}^{t} p(x_k \mid x_{k-1})\; p(y_k \mid x_k)\,}

두 가정 아래에서 모든 variable의 joint는 initial belief $p(x_0)$ , transition model, measurement model 세 가지로 정해집니다. 그래서 hidden state model을 만든다는 것은 이 세 가지를 정하는 일입니다. 반대로 이 곱으로 joint를 정의하면 두 가정이 성립합니다.

bpf l3 dbn
위: 이 hidden state model의 dynamic Bayesian network(DBN)로, 각 node에는 그 node로 화살표를 보내는 node를 조건으로 둔 factor가 하나씩 대응하고 색칠된 measurement node만 관측됩니다. 아래: 같은 모델의 control block diagram이며( $z^{-1}$ 은 한 step delay), 두 그림의 화살표 뜻은 §7에서 비교합니다.

State만 쓴 Markov 형태로는 부족합니다

Markov assumption을 $p(x_t \mid x_{0:t-1}) = p(x_t \mid x_{t-1})$ 로 적는 경우가 많습니다. 이것은 가정 1에서 $y_{1:t-1}$ 을 marginalize해서 나오는 결과이고, 가정 1을 대신할 수는 없습니다.

반례를 봅니다. $x_0 \sim \mathcal{N}(0,1)$ , $x_1 = x_0 + w_1$ , $y_1 = x_1 + v_1$ , $x_2 = y_1$ , $y_2 = x_2 + v_2$ 이고, noise $w_1, v_1, v_2$ 는 $\mathcal{N}(0,1)$ 이며 서로와 $x_0$ 에 대해 independent라고 합시다. $x_2 = x_1 + v_1$ 이므로 $p(x_2 \mid x_{0:1}) = \mathcal{N}(x_2;\ x_1,\ 1) = p(x_2 \mid x_1)$ 이고, state만 쓴 형태와 가정 2는 모두 성립합니다.

그런데 $y_1$ 을 알면 $x_2 = y_1$ 로 정확히 정해지므로 $p(x_2 \mid x_1, y_1) \ne p(x_2 \mid x_1)$ 입니다. 가정 1이 깨졌고, 위의 factorization과 L4의 prediction step 유도도 성립하지 않습니다.

6. 과거 measurement는 왜 여전히 필요한가

가정 1을 보면 질문이 하나 생깁니다. 가정 1은 $x_{t-1}$ 이 주어지면 $y_{1:t-1}$ 이 $x_t$ 에 추가 정보를 주지 않는다고 말합니다. 그런데 filter는 $p(x_t \mid y_{1:t-1})$ 을 계산하면서 과거 measurement를 씁니다. 그렇다면 $x_t$ 는 과거 measurement에 대해서는 Markov가 아닌 것입니까?

두 식은 bar 뒤에 무엇이 있는지가 다릅니다. 가정 1의 $p(x_t \mid x_{t-1}, y_{1:t-1})$ 에는 $x_{t-1}$ 이 조건으로 들어 있고, filter가 계산하는 $p(x_t \mid y_{1:t-1})$ 에는 없습니다. 그리고 실제로 우리는 $x_{t-1}$ 을 모릅니다.

숫자로 보기

이전 state가 $A$ 또는 $B$ 이고, transition model이 다음과 같다고 합시다.

P(X_t = B \mid X_{t-1} = A) = 0.2, \qquad P(X_t = B \mid X_{t-1} = B) = 0.9

$x_{t-1} = B$ 를 정확히 안다면, 과거 measurement가 무엇이었든 가정 1에 의해 답이 정해집니다.

P(X_t = B \mid X_{t-1} = B,\ y_{1:t-1}) = P(X_t = B \mid X_{t-1} = B) = 0.9

과거 measurement는 쓸 곳이 없습니다.

$x_{t-1}$ 을 모른다면 과거 measurement로 만든 belief만 있습니다. $P(X_{t-1}=A \mid y_{1:t-1}) = 0.3$ , $P(X_{t-1}=B \mid y_{1:t-1}) = 0.7$ 이라고 합시다. 이제는 두 가능성을 모두 따져야 합니다. 합의 $a$ 는 모르는 이전 state의 값이고, 이 합이 $X_{t-1}$ 을 없앱니다.

\begin{aligned} P(X_t = B \mid y_{1:t-1}) &= \sum_{a \in \{A, B\}} P(X_t = B,\ X_{t-1} = a \mid y_{1:t-1}) && \text{(marginalization)} \\ &= \sum_{a} P(X_t = B \mid X_{t-1} = a,\ y_{1:t-1})\; P(X_{t-1} = a \mid y_{1:t-1}) && \text{(product rule)} \\ &= \sum_{a} P(X_t = B \mid X_{t-1} = a)\; P(X_{t-1} = a \mid y_{1:t-1}) && \text{(Markov assumption)} \\ &= 0.2 \times 0.3 + 0.9 \times 0.7 = 0.69 \end{aligned}

두 번째 줄의 product rule은 §4에서 확인한 형태에서 $c$ 자리에 $y_{1:t-1}$ 을 넣은 것입니다. 이 계산의 일반형이 L4의 prediction step입니다(L4 §2).

이제 과거 measurement 기록이 달랐다고 합시다. 다른 기록 $y'_{1:t-1}$ 이 $A$ 쪽을 가리켜서 belief가 $P(X_{t-1}=A \mid y'_{1:t-1}) = 0.9$ , $P(X_{t-1}=B \mid y'_{1:t-1}) = 0.1$ 이 되었다면, 같은 계산으로 다음을 얻습니다.

P(X_t = B \mid y'_{1:t-1}) = 0.2 \times 0.9 + 0.9 \times 0.1 = 0.27

Transition model은 그대로인데 과거 measurement만 달라져서 $X_t = B$ 일 확률이 $0.69$ 에서 $0.27$ 로 바뀌었습니다. 그러므로 $X_t$ 와 $Y_{1:t-1}$ 은 independent가 아닙니다.

두 관계를 함께 적기

\boxed{\,X_t \perp Y_{1:t-1} \mid X_{t-1}\,} \qquad \text{but in general} \qquad X_t \not\perp Y_{1:t-1}

§4의 비, 우산, 젖은 땅과 같은 구조입니다. 우산이 비를 거쳐서만 젖은 땅과 관련되었듯이, 과거 measurement는 이전 state에 대한 정보를 거쳐서만 $x_t$ 와 관련됩니다. 가정 1은 $x_{t-1}$ 을 조건으로 넣으면 과거 measurement가 $x_t$ 에 추가 정보를 주지 않는다는 것입니다. $x_{t-1}$ 을 모르면 과거 measurement는 $x_{t-1}$ 에 대한 belief를 바꾸고, 위 계산처럼 그 belief가 transition model을 거쳐 $x_t$ 의 distribution을 바꿉니다.

이 강의에서 가져갈 한 가지

과거 measurement가 필요한 이유는 dynamics에 memory가 있어서가 아니라 우리가 $x_{t-1}$ 을 모르기 때문입니다. 위 계산이 보여 주듯이 $p(x_t \mid y_{1:t-1})$ 을 구하는 데 필요한 것은 $y_{1:t-1}$ 자체가 아니라 그것으로 만든 belief $\mathrm{bel}_{t-1}(x_{t-1}) = p(x_{t-1} \mid y_{1:t-1})$ 와 transition model입니다. 그래서 filter는 measurement 기록 대신 belief 하나를 들고 갑니다.

7. 제어의 state-space model과의 관계

Control 수업에서 쓴 discrete-time state-space model은 다음과 같습니다.

x_{t+1} = A x_t + B u_t, \qquad y_t = C x_t + D u_t

Noise가 없으므로 $x_t$ 와 $u_t$ 가 정해지면 $x_{t+1}$ 과 $y_t$ 도 하나로 정해집니다. 현실의 불확실성을 넣으면 보통 다음처럼 씁니다. 여기서는 $D = 0$ 으로 둡니다.

x_{t+1} = A x_t + B u_t + w_t, \qquad y_t = C x_t + v_t

$w_t$ 는 process noise, $v_t$ 는 measurement noise입니다.

방정식이 두 모델을 정한다

$w_t$ 의 density를 $p_w$ , $v_t$ 의 density를 $p_v$ 라고 합시다. $x_t$ 와 $u_t$ 를 고정하면 $x_{t+1}$ 은 상수 $Ax_t + Bu_t$ 에 $w_t$ 를 더한 값이므로, 아래 조건이 성립할 때 다음과 같습니다.

p(x_{t+1} \mid x_t, u_t) = p_w(x_{t+1} - A x_t - B u_t), \qquad p(y_t \mid x_t) = p_v(y_t - C x_t)

예를 들어 $w_t \sim \mathcal{N}(0, Q)$ 이면 $p(x_{t+1} \mid x_t, u_t) = \mathcal{N}(x_{t+1};\ Ax_t + Bu_t,\ Q)$ 입니다. State equation과 $w_t$ 의 distribution이 transition model을, output equation과 $v_t$ 의 distribution이 measurement model을 정합니다. $x_{t+1} = f(x_t, u_t) + w_t$ 처럼 nonlinear이어도 같은 방식으로 $p(x_{t+1} \mid x_t, u_t) = p_w(x_{t+1} - f(x_t, u_t))$ 가 됩니다.

이 절은 control 관례대로 $x_t \to x_{t+1}$ 로 적었고, filter 식의 $p(x_t \mid x_{t-1})$ 은 index를 하나 당긴 같은 모델입니다. 시각 $t-1$ 에서 $t$ 로 가는 입력을 $u_t$ 로 부르는 책(Probabilistic Robotics)도 있고 $u_{t-1}$ 로 부르는 책도 있습니다.

Noise에 대한 조건

방정식의 모양만으로는 §5의 두 가정이 보장되지 않습니다. Noise가 다음 조건을 만족하면 두 가정이 성립합니다.

$w_t$ 는 서로 다른 시각끼리 independent합니다. $v_t$ 도 마찬가지입니다.
$w$ 와 $v$ 는 서로 independent합니다.
둘 다 초기 state $x_0$ 과 independent합니다.

정확히는 $x_0, w_0, w_1, \dots, v_1, v_2, \dots$ 전체가 mutually independent라고 둡니다. 두 개씩 짝지어 independent인 것만으로는 일반적으로 부족합니다. 또 output equation에 $Du_t$ 항이 있으면 measurement model은 $p(y_t \mid x_t, u_t)$ 로 써야 합니다.

조건이 깨지면 가정이 어떻게 깨지는지 두 경우를 봅니다.

$w_t$ 가 시간에 따라 correlated일 때. $x_t$ 와 $x_{t-1}$ 을 함께 알면 $w_{t-1} = x_t - Ax_{t-1} - Bu_{t-1}$ 이 정해지고, 이것이 $w_t$ 에 대한 정보, 곧 $x_{t+1}$ 에 대한 정보가 됩니다. 일반적으로는 $x_t$ 혼자서 $w_{t-1}$ 이 정해지지 않으므로(예: scalar에서 $A \ne 0$ ) $x_{t-1}$ 이 추가 정보를 주고, 가정 1이 깨집니다. 반대로 scalar에서 $A = 0$ 이고 $w_t = \rho\, w_{t-1} + e_t$ ( $e_t$ 는 시각마다 independent)이면 $x_t = Bu_{t-1} + w_{t-1}$ 만으로 $w_{t-1}$ 이 정해지므로 가정 1이 성립합니다. 가정 1이 깨지는 경우에는 §5의 velocity 예처럼 noise의 dynamics를 state에 포함시켜 state를 다시 잡으면 Markov 모델로 되돌릴 수 있습니다.
$v_t$ 와 $w_t$ 가 correlated일 때. $y_t$ 가 $w_t$ 에 대한 정보를 주고, $w_t$ 는 $x_{t+1}$ 을 움직입니다. 그러면 $p(x_{t+1} \mid x_t, y_t) \ne p(x_{t+1} \mid x_t)$ 가 되어 가정 1이 깨집니다.

이 조건들에 더해 모델이 linear이고 $w_t$ , $v_t$ , $x_0$ 이 모두 Gaussian이면 Bayes filter가 closed form으로 계산됩니다. 그것이 Kalman filter이고, 이 시리즈에서는 다루지 않습니다.

화살표의 뜻이 다르다

§5 그림의 두 panel은 같은 모델을 그리지만 화살표의 뜻이 다릅니다.

DBN의 화살표 $a \to b$ 는 모델에 $b$ 의 conditional distribution이 $a$ 를 조건으로 들어 있다는 뜻입니다. 화살표가 없는 것도 정보입니다. 예를 들어 $y_1$ 에서 $x_2$ 로 가는 화살표가 없다는 것이 가정 1의 일부를 나타냅니다.
Block diagram의 화살표는 signal이 한 block에서 다음 block으로 흐른다는 뜻입니다. Block은 입력 signal을 출력 signal로 바꾸는 연산이고, $z^{-1}$ block은 signal을 한 step 늦춥니다.

Block diagram은 signal이 어떻게 계산되는지를 그리고, DBN은 어떤 variable의 distribution이 어떤 variable을 조건으로 정해지는지를 그립니다. 그래서 block diagram에서는 noise $w_t, v_t$ 가 입력 signal로 들어오고, DBN에서는 noise가 따로 node로 그려지지 않고 $p(x_t \mid x_{t-1})$ 과 $p(y_t \mid x_t)$ 안에 들어 있습니다. 알고 있는 입력 $u_t$ 는 DBN에 화살표를 하나 더 그려 나타낼 수 있습니다. 이 절의 control index로는 $u_t$ 에서 $x_{t+1}$ 로, §3의 filter index로는 $u_t$ 에서 $x_t$ 로 가는 화살표입니다.

control state-space model	hidden state model
state $x_t$	hidden state $x_t$
state equation	transition model $p(x_{t+1} \mid x_t, u_t)$
output equation	measurement model $p(y_t \mid x_t)$
initial condition $x_0$	initial belief $p(x_0)$
output $y_t$	measurement $y_t$ (관측되는 것은 이것뿐)
화살표 = signal flow	화살표 = conditional dependence

Control에서 state는 "현재 state와 이후 입력을 알면 이후 출력이 정해지는 양"이었습니다. 확률 모델에서 state는 "현재 state를 알면 과거가 이후의 distribution에 추가 정보를 주지 않는 양"입니다. 같은 시스템에 state를 고르는 방법이 하나로 정해지지 않는다는 점은 State-Space Realizations & Canonical Forms에서 본 것과 같습니다.

8. Prediction, filtering, smoothing

세 용어는 어느 시각의 state를 어느 시각까지의 measurement로 추정하는지로 구분합니다. 대상 state를 $x_t$ , 조건으로 쓰는 measurement를 $y_{1:s}$ 라고 하면 $p(x_t \mid y_{1:s})$ 에서 $s$ 와 $t$ 의 크기 관계가 이름을 정합니다.

이름	식	조건	뜻
prediction	$p(x_t \mid y_{1:s})$	$s < t$	마지막 measurement보다 뒤의 state를 추정
filtering	$p(x_t \mid y_{1:t})$	$s = t$	시각 $t$ 까지(포함)의 measurement로 시각 $t$ 의 state를 추정
smoothing	$p(x_t \mid y_{1:s})$	$s > t$	$x_t$ 보다 뒤의 measurement까지 써서 시각 $t$ 의 state를 추정

Filtering은 시각 $t$ 의 state를 시각 $t$ 까지의 measurement로 추정하는 것입니다. 미래 measurement를 쓰지 않으므로 causal하고, 원칙적으로 매 시각 그 시각까지의 데이터로 계산할 수 있습니다(정확한 계산이 어려운 이유는 L4 §7). Control loop 안에서 지연 없이 매 시각 쓸 수 있는 것은 filtering과 prediction입니다.

§2의 predicted belief $p(x_t \mid y_{1:t-1})$ 은 $s = t-1$ 인 prediction, 곧 한 step 앞의 prediction입니다. Bayes filter는 매 step 이 prediction을 거쳐 filtering belief로 갑니다.

\mathrm{bel}_{t-1}(x_{t-1}) \;\longrightarrow\; \overline{\mathrm{bel}}_t(x_t) \;\longrightarrow\; \mathrm{bel}_t(x_t)

Smoothing의 예는 $y_{1:10}$ 까지 모두 받은 뒤 $x_5$ 를 다시 추정하는 $p(x_5 \mid y_{1:10})$ 입니다. Smoothing에는 $x_t$ 보다 뒤의 measurement가 필요하므로, 그 measurement가 들어올 때까지 기다리거나 기록이 끝난 뒤에만 계산할 수 있습니다. 이 시리즈는 smoothing을 다루지 않습니다(허브).

L4는 위 화살표 두 개, 곧 prediction step과 update step을 이 강의의 두 가정만으로 유도합니다.

이해 확인

1. $p(x_4 \mid y_{1:3})$ 과 $p(x_4 \mid y_{1:4})$ 중 $y_4$ 에 대한 Bayes update에서 prior 자리에 들어가는 것은 어느 쪽인지 고르고, 그 이유를 설명하시오.

2. Joint $p(x_0, x_1, y_1, x_2, y_2)$ 를 chain rule로 전개할 때 $x_0, x_1, y_1, x_2, y_2$ 순서를 쓰는 이유를 설명하시오. 또 $x_0, x_1, x_2, y_1, y_2$ 순서로 쓰면 무엇이 곤란한지 설명하시오.

3. 가정 1에 따르면 $X_t \perp Y_{1:t-1} \mid X_{t-1}$ 이다. 그런데도 filter가 $p(x_t \mid y_{1:t-1})$ 을 계산하면서 과거 measurement를 쓰는 이유를 설명하시오.

4. $x_{t+1} = Ax_t + Bu_t + w_t$ 에서 $w_t$ 가 시간에 따라 correlated이면 깨지는 가정은 무엇인가? 그 가정이 깨지는 이유와 되돌리는 방법을 설명하시오.

답

1. $p(x_4 \mid y_{1:3})$ 입니다. Bar 뒤에 $y_4$ 가 없으므로 $y_4$ 를 보기 직전의 belief이고, $y_4$ 를 반영하는 update의 prior 자리에 들어갑니다. 그 update의 결과가 $p(x_4 \mid y_{1:4})$ 입니다. → §2

2. 시간 순서로 전개하면 각 factor의 bar 뒤에 그 variable보다 앞선 variable만 와서 $p(y_k \mid x_{0:k}, y_{1:k-1})$ 과 $p(x_k \mid x_{0:k-1}, y_{1:k-1})$ 꼴이 되고, 가정 2와 가정 1이 각각 한 factor에 그대로 들어맞습니다. $x_0, x_1, x_2, y_1, y_2$ 순서에서는 $p(y_1 \mid x_0, x_1, x_2)$ 처럼 미래 state를 조건으로 가진 factor가 생기는데, 두 가정은 이 형태를 직접 말하지 않습니다. → §5

3. 가정 1은 $x_{t-1}$ 을 정확히 알 때의 이야기입니다. 실제로는 $x_{t-1}$ 을 모르고, 과거 measurement는 $x_{t-1}$ 에 대한 정보를 줍니다. 그래서 조건 없이는 일반적으로(transition이 $x_{t-1}$ 에 따라 달라지는 한) $X_t \not\perp Y_{1:t-1}$ 이고, 과거 measurement로 만든 belief를 transition model로 밀어야 합니다. 예에서 belief가 $[0.3, 0.7]$ 에서 $[0.9, 0.1]$ 로 바뀌자 $0.69$ 가 $0.27$ 로 바뀌었습니다. → §6

4. 보통 가정 1(Markov assumption)이 깨집니다. $x_t$ 와 $x_{t-1}$ 을 함께 알면 $w_{t-1}$ 이 정해지고, correlated noise에서는 이것이 $w_t$ , 따라서 $x_{t+1}$ 에 대한 정보가 됩니다. $x_t$ 혼자서 $w_{t-1}$ 을 정하지 못하는 경우(예: scalar에서 $A \ne 0$ )에는 $x_{t-1}$ 이 추가 정보를 주므로 가정 1이 깨집니다. Noise의 dynamics를 state에 포함시켜 state를 다시 잡으면 Markov 모델로 되돌릴 수 있습니다. → §7