29장 State Space Models

State Space Model (SSM) 한 마디 요약 : 전체 시스템을 관측하는 것이 불가능하기에 시간에 따라서 Markov Process 를 가지며 변하는 Hidden State 을 모델링 해주며 각각의 Hidden State 에 해당되는 Output 까지 고려해줍니다.

29.1 Introduction

Notations :

$\boldsymbol{z}_t \in \mathbb{R}^{N_z} :$ Hidden States

$\boldsymbol{u}_t \in \mathbb{R}^{N_u} :$ Optional Observed Inputs

$\boldsymbol{y}_t \in \mathbb{R}^{N_y} :$ Observed Outputs

$\boldsymbol f :$ Transition Function

$\boldsymbol q_t :$ Process Noise

$\boldsymbol h :$ Observation Function

$\boldsymbol r_t :$ Observation Noise

SSM : Probabilistic Model for Sequences with a Latent Markov State.

\begin{aligned} \boldsymbol{z}_t & =\boldsymbol{f}\left(\boldsymbol{z}_{t-1}, \boldsymbol{u}_t, \boldsymbol{q}_t\right) \\ \boldsymbol{y}_t & =\boldsymbol{h}\left(\boldsymbol{z}_t, \boldsymbol{u}_t, \boldsymbol{y}_{1: t-1}, \boldsymbol{r}_t\right) \end{aligned}

위를 만족한다면 SSM 이라고 부를 수가 있습니다.

그러면 우리가 관심있는 두 변수는 사실 $\boldsymbol z_t, \boldsymbol y_t$ 이며 이들을 확률변수로 바라본다면, 다음과 같은 Probabilistic Model 으로 표현해줄 수도 있습니다.

$p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}, \boldsymbol{u}_t\right) =p\left(\boldsymbol{z}_t \mid \boldsymbol{f}\left(\boldsymbol{z}_{t-1}, \boldsymbol{u}_t\right)\right) :$ Transition Model

$p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t, \boldsymbol{u}_t, \boldsymbol{y}_{1: t-1}\right) =p\left(\boldsymbol{y}_t \mid \boldsymbol{h}\left(\boldsymbol{z}_t, \boldsymbol{u}_t, \boldsymbol{y}_{1: t-1}\right)\right) :$ Observation Model

가장 General 한 케이스로 Joint Probability 를 그려준다면 다음과 같습니다.

p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T} \mid \boldsymbol{u}_{1: T}\right)=\left[p\left(\boldsymbol{z}_1 \mid \boldsymbol{u}_1\right) \prod_{t=2}^T p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}, \boldsymbol{u}_t\right)\right]\left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t, \boldsymbol{u}_t, \boldsymbol{y}_{1: t-1}\right)\right]

이것을 활용시켜서 저희가 더 흔히 알고 있는 모델들로 적용시키는 것이 가능합니다.

예시로 $y_t$ 가 $y_{t-1}, z_t$ 에만 의존한다면 Autoregressive Model 이 되며, 이는 다음과 같이 모델해줄 수 있습니다.

p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T} \mid \boldsymbol{u}_{1: T}\right)=\left[p\left(\boldsymbol{z}_1 \mid \boldsymbol{u}_1\right) \prod_{t=2}^T p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}, \boldsymbol{u}_t\right)\right]\left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid \boldsymbol{y}_{t-1}, \boldsymbol{z}_t, \boldsymbol{u}_t\right)\right]

반면에 Input $u_t$ 가 없다고 가정한다면 다음과 같이 나옵니다.

p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T}\right)=\left[p\left(\boldsymbol{z}_1\right) \prod_{t=2}^T p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}\right)\right]\left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t\right)\right]

29.2 Hidden Markov Models (HMMs)

HMM 도 SSM 으로 바라볼 수 있으며, 이것은 Hidden State 들이 Discrete 한 경우를 의미합니다.

$z_t \in \{1,\cdots, K\} :$ Latents

$p(z_1 = j) =\pi_j :$ Initial State Distribution

$p\left(z_t=j \mid z_{t-1}=i\right)=A_{i j} :$ Transition Model

$p\left(y_t=k \mid z_t=j\right)=y_{j k} :$ Observation Model
예시로 $D$ Discrete Observation 중 하나면 $p\left(\boldsymbol{y}_t \mid z_t=j\right)=\prod_{d=1}^D \operatorname{Cat}\left(y_{t d} \mid \boldsymbol{y}_{d, j,:}\right)$

GMM-HMM

반면에 Observation 은 사실 Continuous 가 될 수도 있기에 Continuous 이면 정규분포로 세팅하는 경우도 있습니다.

p\left(\boldsymbol{y}_t \mid z_t=j\right)=\sum_{k=1}^M w_{j k} \mathcal{N}\left(\boldsymbol{y}_t \mid \boldsymbol{\mu}_{j k}, \boldsymbol{\Sigma}_{j k}\right)

The Parameters of Gaussian are time-invariant, and are trained.
Above is also called GMM-HMM.

HMM with 5 Hidden States, and 2D-Gaussian Observation Model.

Left : HMM with 5 Hidden States, Right : 똑같은 HMM, 근데 Hidden State 이 이제는 색깔로 표현. y 축의 경우 y_1 과 y_2 값들을 의미하는 듯하며 두 개의 변수를 하나의 축으로 둔 것 같음.

GPT 5’s Annotation (많이 틀리긴 함)

Autoregressive HMM

Autoregressive-HMM 의 경우에는 기본적인 HMM 의 경우 $z_t$ 가 주어졌다면 $y_t, y_{t-1}, \cdots$ 끼리는 Conditionally Independent 하다는 가정이 있으며, Autoregressive 한 케이스에서는 그와는 반대로 $y_t$ 가 $y_{t-1}, z_t$ 에 대해서 의존합니다.

예시로 Continuous 한 데이터에 대해서는 Observation Model 을 정규분포로 가정할 수 있습니다.

p\left(\boldsymbol{y}_t \mid \boldsymbol{y}_{t-1}, z_t=j, \boldsymbol{\theta}\right)=\mathcal{N}\left(\boldsymbol{y}_t \mid \mathbf{E}_j \boldsymbol{y}_{t-1}+\boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j\right)

$\mathbf E_j$ 가 여기에서 유일한 차이점인데 이게 해주는 것은 $\boldsymbol y_{t-1}$ 의 점을 $t$ 시점의 분포로 바꿔줄 수 있다는 점입니다. 이게 없다면 그저 GMM-HMM 과 똑같아버려집니다.

각 Point $(y_1, y_2)$ 마다 Arrow 가 있으며, 각각의 화살표는 다음 Step 의 Mean 을 가르키고 있습니다. 구체적으로 각각의 화살표는 $\left(E_j y+\mu_j\right)-y$ 를 의미합니다.

결론적으로는 Standard HMM 에서는 $y_t$ 끼리 Correlation 이 없지만, AR-HMM 에서는 이를 모델링 해주고 있다 정도로 마무리 지을 수가 있습니다.

29.3 HMM Applications

Example 1

데이터가 Fig 29.6(a) 에 보이시는 바와 같이 구성이 되어 있으며, 이것을 Fig 29.7 에 보이시는 바와 같이 State 들을 여러개로 쪼개서 SSM Model 을 Fit 시킬 수 있습니다. 특이하게도 $4$ 이후로는 다 똑같은 값들을 예측합니다.

Specific Details :
$\begin{aligned}z_1 & \sim \text { Categorical }\left(\left\{\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}\right\}\right) \\z_t \mid z_{t-1} & \sim \operatorname{Categorical}\left(\left\{\begin{array}{cc}p & \text { if } z_t=z_{t-1} \\\frac{1-p}{4-1} & \text { otherwise }\end{array}\right\}\right)\end{aligned}$

Example 2

Protein Alignment 에도 사용이 가능합니다.

29.4 Parameter Learning

29.4.1 EM-Algorithm

\begin{aligned}p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T} \mid \boldsymbol{\theta}\right) & =\left[p\left(z_1 \mid \boldsymbol{\pi}\right)\right]\left[\prod_{t=2}^T p\left(z_t \mid z_{t-1}, \mathbf{A}\right)\right]\left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid z_t, \mathbf{B}\right)\right] \\& =\left[\prod_{k=1}^K \pi_k^{\mathbb{I}\left(z_1=k\right)}\right]\left[\prod_{t=2}^T \prod_{j=1}^K \prod_{k=1}^K A_{j k}^{\mathbb{I}\left(z_{t-1}=j, z_t=k\right)}\right]\left[\prod_{t=1}^T \prod_{k=1}^K p\left(\boldsymbol{y}_t \mid \mathbf{B}_k\right)^{\mathbb{I}\left(z_t=k\right)}\right] \\ &= \pi_{z_1}\left(\prod_{t=2}^T A_{z_{t-1} z_t}\right)\left(\prod_{t=1}^T p\left(y_t \mid z_t ; B\right)\right) \end{aligned}

EM 의 목적 : Maximize $\log p_\theta(y_{1:T})$ where $\theta = (\pi, A, B)$ when $z_{1:T}$ are Hidden.

E-Step :

Compute Expected Statistics Under $\boldsymbol \theta^{\text{old}}$

State Marginal : $\gamma_{n, t}(j) \triangleq p\left(z_t=j \mid \boldsymbol{y}_{n, 1: T_n}, \boldsymbol{\theta}^{\text {old }}\right)$

Transition Marginal : $\xi_{n, t}(j, k) \triangleq p\left(z_{t-1}=j, z_t=k \mid \boldsymbol{y}_{n, 1: T_n}, \boldsymbol{\theta}^{\text {old }}\right)$

그런 다음에 이것을 활용해서 Complete-Data Log Likelihood 를 구축하면 됩니다.

Q\left(\theta \mid \theta^{\text {old }}\right)=\mathbb{E}_{p\left(z_{1: T} \mid y_{1: T}, \theta^{\text {old }}\right)}\left[\log p\left(y_{1: T}, z_{1: T} \mid \theta\right)\right]

여기에서 $\gamma$ 그리고 $\xi$ 들을 이용한다면 다음과 같이 Decompose 시킬 수 있습니다.

\begin{aligned}Q\left(\theta \mid \theta^{\text {old }}\right)= & \sum_j \gamma_1(j) \log \pi_j \\& +\sum_{t=2}^T \sum_{i, j} \xi_t(i, j) \log A_{i j} \\& +\sum_{t=1}^T \sum_j \gamma_t(j) \log p\left(y_t \mid z_t=j ; B\right) .\end{aligned}

M-Step :

Maximize Each parameter $(\pi, A, B)$ based off of the likelihood we got in the E-Step, but with the constraints $\sum_j \pi_j = 1, \sum_j A_{ij} = 1$ .

우선은 $\pi :$

\pi_j^{\text {new }}=\frac{\sum_n \gamma_{n, 1}(j)}{\sum_n 1}

다음으로는 $A:$

N_{i j}=\sum_n \sum_{t=2}^{T_n} \xi_{n, t}(i, j), \quad N_i=\sum_j N_{i j}=\sum_n \sum_{t=2}^{T_n} \gamma_{n, t-1}(i) .

A_{i j}^{n e w}=\frac{N_{i j}}{N_i .}

마지막으로 $B :$

C_{j v}=\sum_n \sum_t \gamma_{n, t}(j) \mathbf{1}\left[y_{n, t}=v\right], \quad N_j=\sum_n \sum_t \gamma_{n, t}(j)

B_{j v}^{\text {new }}=\frac{C_{j v}}{N_j}

E-Step 과 M-Step 을 반복시키면 EM-Algorithm 이 됩니다.

요즘 안 사용하는 이유? Scaling Issue…

SGD 으로도 똑같은 것을 할 수가 있다 $\rightarrow$ 29.4.2 내용.

29.4.4 Bayesian HMM’s

정말로 별거가 아니라 이제는 $\theta = (\pi, A, B)$ 들도 확률변수로 바라본다는 것이 끝인 내용.

\log p(\boldsymbol{\theta}, \mathcal{D})=\log p(\boldsymbol{\theta})+\sum_{n=1}^N \log p\left(\boldsymbol{y}_{1: T, n} \mid \boldsymbol{\theta}\right)

보통은 다음과 같은 Prior 들을 사용한다고 합니다 (Conjugate Priors, when Posterior and Prior follow the same Distribution).

Dirichlet 분포를 Prior 으로 자주 사용하는 이유?

확률벡터 $\pi = (\pi_1, \cdots, \pi_K)$ 위의 분포가 Dirichlet 분포이며, 왜 특별하냐면 우리의 데이터 개수를 $\alpha$ 에 반영시킬 수 있기 때문이다. 일종의 Pseudo-Histogram 으로 생각.

f\left(x_1, \ldots, x_K ; \alpha_1, \ldots, \alpha_K\right)=\frac{1}{\mathrm{~B}(\boldsymbol{\alpha})} \prod_{i=1}^K x_i^{\alpha_i-1}

결론적으로는 Bayesian HMM 에서는 Dirichlet Prior 를 많이 사용하며, 이것을 사용하는 이유로는 데이터를 보고 난 다음에 Category 들에 대한 Histogram 으로 그려줄 수 있기 때문이다.

29.5 HMMs : Generalizations

Hidden Semi-Markov Model (HSMM)
- Standard HMM 에서는 State $i$ 에 $d$ Steps 만큼 남아있을 확률 $p(d_i = d)$ 이 Geometric, 즉 Memoryless 하게 구성이 됩니다.
- 이러한 Duration $d_t$ 까지 고려해주는 것이 HSMM 입니다.
- Why Semi-Markov? 이제는 Hidden 이 State 자체에서만 Markov 한게 아니기에.

Hierarchical HMMs (HHMM)
- State 자체를 Sub-HMM 으로 바라보는 개념.
- Phone : Basic unit of sound in a spoken language
  - Words $\rightarrow$ Sequence of Phones
  - Each Phone $\rightarrow$ Sequence of Sub-Phones

Factorial HMMs (FHMM)
- $p\left(\mathbf{z}_{1: T}^{1: M}, y_{1: T}\right)=\prod_{m=1}^M p\left(z_1^{(m)}\right) \prod_{t>2} p\left(z_t^{(m)} \mid z_{t-1}^{(m)}\right) \prod_{t=1}^T p\left(y_t \mid z_t^{(1)}, \ldots, z_t^{(M)}\right)$
- State 1 개를 Chain (Factor) 으로 바라보는 것.

Coupled HMMs
- FHMM 에서의 Chain 들이 서로에게 이제는 영향을 끼친다.

여기까지가

29.6 Linear Dynamical Systems (LDS)

이 장에서는 구체적으로 Linear-Gaussian State-Space Model (LG-SSM), a.k.a LDS 에 대해서 다룹니다.

LG-SSM 이기 위해서는,

Transition Function $\boldsymbol f$ + Observation Function $\boldsymbol h$ 들이 Linear 할 때.

Process Noise $\boldsymbol q_t$ + Observation Noise $\boldsymbol r_t$ 들이 Gaussian 일 때.

이며 그래프 모델 자체는 우측과 같습니다.

정의 자체는 그래서 다음과 같이 해줄 수가 있습니다.

\begin{aligned}p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}, \boldsymbol{u}_t\right) & =\mathcal{N}\left(\boldsymbol{z}_t \mid \mathbf{F}_t \boldsymbol{z}_{t-1}+\mathbf{B}_t \boldsymbol{u}_t+\boldsymbol{b}_t, \mathbf{Q}_t\right) \\p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t, \boldsymbol{u}_t\right) & =\mathcal{N}\left(\boldsymbol{y}_t \mid \mathbf{H}_t \boldsymbol{z}_t+\mathbf{D}_t \boldsymbol{u}_t+\boldsymbol{d}_t, \mathbf{R}_t\right)\end{aligned}

Bias 가 없고 Input 이 없다면 모델은 다음과 같이 Simplify 됩니다.

\begin{aligned}p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}\right) & =\mathcal{N}\left(\boldsymbol{z}_t \mid \mathbf{F}_t \boldsymbol{z}_{t-1}, \mathbf{Q}_t\right) \\p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t\right) & =\mathcal{N}\left(\boldsymbol{y}_t \mid \mathbf{H}_t \boldsymbol{z}_t, \mathbf{R}_t\right)\end{aligned}

그러면 이것을 방정식으로 다음과 같이 적어줄 수 있게 됩니다.

\begin{aligned}\boldsymbol{z}_t & =\mathbf{F}_t \boldsymbol{z}_{t-1}+\boldsymbol{q}_t \\\boldsymbol{y}_t & =\mathbf{H}_t \boldsymbol{z}_t+\boldsymbol{r}_t\end{aligned}

$\boldsymbol{q}_t \sim \mathcal{N}\left(\mathbf{0}, \mathbf{Q}_t\right) :$ Process Noise

$\boldsymbol{r}_t \sim \mathcal{N}\left(\mathbf{0}, \mathbf{R}_t\right) :$ Observation Noise

여기에서 저희의 파라미터들은 그러면 다음과 같습니다 (보통은 $t$ 에 의존하지 않는다는 가정이긴 함).

\boldsymbol{\theta}_t=\left(\mathbf{F}_t, \mathbf{H}_t, \mathbf{B}_t, \mathbf{D}_t, \mathbf{Q}_t, \mathbf{R}_t\right)

얘네들도 똑같이 학습시켜주면 됩니다.

29.7 LDS: Applications

29.7.1 Object Tracking

2차원에서 놀고 있는 Object 을 생각해보겠습니다. 이때 Position 이 $(u_t, v_t)$ 그리고 Velocity 를 $\left(\dot{u}_t,\dot{v}_t\right)$ 으로 두면 State at time $t$ 를 $\boldsymbol{z}_t=\left(\begin{array}{llll}u_t & v_t & \dot{u}_t & \dot{v}_t\end{array}\right)$ 으로 둘 수가 있습니다.

Discrete Time 만 고려하면 Discrete Time SSM 은 다음과 같습니다.

\underbrace{\left(\begin{array}{c}u_t \\v_t \\\dot{u}_t \\\dot{v}_t\end{array}\right)}_{\boldsymbol{z}_t}=\underbrace{\left(\begin{array}{cccc}1 & 0 & \Delta & 0 \\0 & 1 & 0 & \Delta \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 1\end{array}\right)}_{\mathbf{F}} \underbrace{\left(\begin{array}{c}u_{t-1} \\v_{t-1} \\\dot{u}_{t-1} \\\dot{v}_{t-1}\end{array}\right)}_{\boldsymbol{z}_{t-1}}+\boldsymbol{q}_t

$\Delta :$ Step Size between Consecutive Discrete Measurement Times

$\boldsymbol{q}_t \sim \mathcal{N}(\mathbf{0}, \mathbf{Q}) :$ Process Noise

Noise Covariance Matrix $\mathbf Q :$
$\mathbf{Q}=\left(\begin{array}{cccc}\frac{q_1 \Delta^3}{3} & 0 & \frac{q_1 \Delta^2}{2} & 0 \\0 & \frac{q_2 \Delta^3}{3} & 0 & \frac{q_2 \Delta^2}{2} \\\frac{q_1 \Delta^2}{2} & 0 & q_1 \Delta & 0 \\0 & \frac{q_2 \Delta^2}{2} & 0 & q_2 \Delta\end{array}\right)$

해석 :

Position 부분에만 $\Delta$ 가 Velocity 와 함께 직접적으로 더해지며 이는 Velocity 가 Position 에 관한 함수가 아니기에.

$\boldsymbol q_t$ 부분에 $\Delta$ 가 들어가며, 이는 Random Acceleration 이 Position + Velocity 에 어떤 영향을 끼치는지 관련이다.
- 우하단 : Velocity 는 Acceleration 한 번 적분한 것이기에 Velocity Variance 는 시간에 따라서 Linear 하다.
- 좌상단 : Position 은 Acceleration 두 번 적분한 것이기에 Position Variance 는 시간에 따라서 Cubic 하다.
- Off-Diagonals : Position 과 Velocity 의 Covariance 부분, 시간에 따라서 Quadratic 하다.

이러한 세팅에서 Location 을 관측한다고 해보자. 이때 Location 에 대한 Gaussian Noise 까지 있다고 하면, 다음과 같이 Observation Model 을 구축할 수가 있다.

\underbrace{\binom{y_{1, t}}{y_{2, t}}}_{\boldsymbol{y}_t}=\underbrace{\left(\begin{array}{llll}1 & 0 & 0 & 0 \\0 & 0 & 1 & 0\end{array}\right)}_{\mathbf{H}} \underbrace{\left(\begin{array}{l}u_t \\\dot{u}_t \\v_t \\\dot{v}_t\end{array}\right)}_{\boldsymbol{z}_t}+\boldsymbol{r}_t

$\boldsymbol{r}_t \sim \mathcal{N}(\mathbf{0}, \mathbf{R}) :$ Observation Noise

이것의 움직임을 (a), Kalman Filter 을 통해서 $p(\boldsymbol z_t \mid \boldsymbol y_{1:t}, \boldsymbol \theta)$ 을 구하면 (b) 와 같이, 그리고 Kalman Smoother 까지 활용해서 구하면 (c) 와 같이 나옵니다.