W9.L2. Hidden Markov Model - Joint, Marginal Probability

| Main Questions on HMM

Given the topology of the M

 

Evaluation question

- Given $\pi,\ a,\ b,\ X$

- Find $P(X\mid M, \pi, a, b)$

- How much is $X$ likely to be observed in the trained model?

 

Decoding question

- Given $\pi,\ a,\ b,\ X$

- Find $argmax_{z}\ P(Z\mid X, M, \pi, a, b)$

- What would be the most probable sequences of latent states?

- 보이는 데이터들을 가장 잘 설명할 수 있는 Latent 들의 sequence 를 알아내봐라!

 

Learning question

- Given $X$

- Find $argmax_{\pi, a, b}\ P(X\mid M, \pi, a, b)$

- What would be the underlying parameters of the HMM given the observations?

- Parameters 모르는 상태에서 주어진 데이터 X 만으로 각 Parameters 를 알아내봐라!

 

 

Decoding questions and learning questions are very similar to supervised and unsupervised learning

We often need to find $\pi, a, b$ prior to the supervised learning with $X$

 

 

| Obataining $\pi, a, b$ given $X$ and $M$

주사위 게임에서 Loaded dice (불공정한 주사위), Fair dice (공정한 주사위)

안보이는 Latent (Loaded/Fair) 까지 다 알고있다고 가정하고 ...

$P(L \to L) = P(z_{t+1}=L \mid z_{t}=L) $ 

$P(x_{t}=1 \mid z_{t}=L) $ 

...

위 확률들은 데이터들을 직접 Counting 한 다음, MLE, MAP 로 $\pi, a, b$ 를 알아낼 수 있다!

 

 

| Joint Probability

Let's assume that we have a training dataset with $X$ and $Z$

$X$ 와 $Z$ 를 모두 안다고 가정해보자!

그렇다면 MLE 혹은 MAP 로 $\pi, a, b$ 를 미리 다 알아낼 수 있다는 것.

 

Full Joint $P(X, Z)$ 를 알면 되겠다!

 

Topology 를 보고 Factorize!  ... (W7.L5. Bayesian Network)

$$
\begin{align*}
P(X, Z)&=P(x_1, ..., x_t, z_1, ..., z_t) \\
&=P(z_1)P(x_1 \mid z_1)P(z_2 \mid z_1)P(x_2 \mid z_2)P(z_3 \mid z_2)P(x_3 \mid z_3)\\
&=\pi_{z_{1}=1} \cdot b_{x_{1}=1, z_{1}=1} \cdot a_{z_{1}=1, z_{2}=1} \cdot ...
\end{align*}
$$

 

166 이라는 관측이 있었다!

Loaded dice 일까? Fair dice 일까?

 

Z=LLL, Z=FFF 두 가지 경우라 가정하고 계산을 해보면 ...

$P(166, LLL)=\frac{1}{2} \cdot \frac{1}{10} \cdot \frac{7}{10} \cdot \frac{1}{2} \cdot \frac{7}{10} \cdot \frac{1}{2}=0.0061 $

$P(166, FFF)=\frac{1}{2} \cdot \frac{1}{6} \cdot \frac{1}{2} \cdot \frac{1}{6} \cdot \frac{1}{2} \cdot \frac{1}{6}=0.00005 $ 

 

LLL 이 FFF 보다 더 Likely 한 대답!

즉 166 이 관측되었다면 아마 LLL 일거야!

(Evaluation Question)

 

사실 LLL, LLF, LFL, LFF, ... 총 8가지 경우가 있는데 기하급수적으로 늘어난다 ... 

즉 Decoding 하기에는 너무 어렵고 Decoding 은 다른 방법을 써야 할 것이다 ...

 

 

| Marginal Probability

Decoding Question:  X 라는 것이 주어졌을 때, Z 는 무엇일까?

X 가 166 으로 관측되었을 경우,  LLL, LLF, ...   Z 는 무엇일까?

 

사실 우리는 X 만 알고 Z 는 알지 못함 → Marginalize Z

GMM : $P(X \mid \theta) = \sum_{Z} P(X, Z \mid \theta)$

HMM : $P(X \mid \pi, a, b) = \sum_{Z} P(X, Z \mid \pi, a, b) $

 

 

Marginal Probability

 

$P(X) = \sum_{Z} P(X, Z) = \sum_{z_1} ... \sum_{z_t} P(x_1, ..., x_t, z_1, ..., z_t) $

 

Factorize using topology

 

$P(X) = \sum_{z_1} ... \sum_{z_t} \prod_{t=2}^{T} a_{z_{t-1}, z_{t}} \prod_{t=1}^{T} b_{z_{t}, x_{t}} $

 

 

계산하려고 보니깐 Loop 가 너무 많네...

한 번 Recursive 한 Form 으로 만들어보기 위해 아래 수식을 전개해보자!

- Hint 1: $P(A, B, C) = P(A) P(B \mid A) P(C \mid A, B)$

- Hint 2: Topology graph

$$
\begin{align*}
P(x_1, ..., x_t, z_{t}^{k}=1) &= \sum_{z_{t-1}}P(x_1, ..., x_{t-1}, x_t, z_{t-1}, z_{t}^{k}=1) \\
&= \sum_{z_{t-1}}P(x_1, ..., x_{t-1}, z_{t-1}) \cdot P(z_{t}^{k}=1 \mid x_1, ..., x_{t-1}, z_{t-1}) \cdot P(x_t \mid z_{t}^{k}=1, x_1, ..., x_{t-1}, z_{t-1}) \\
&= \sum_{z_{t-1}}P(x_1, ..., x_{t-1}, z_{t-1}) \cdot P(z_{t}^{k}=1 \mid z_{t-1}) \cdot P(x_t \mid z_{t}^{k}=1) \\
&= P(x_t \mid z_{t}^{k}=1) \cdot \sum_{z_{t-1}}P(x_1, ..., x_{t-1},z_{t-1})\cdot P(z_{t}^{k}=1 \mid z_{t-1}) \\
&= b_{z_{t}^{k}, x_{t}} \cdot \sum_{z_{t-1}}P(x_1, ..., x_{t-1}, z_{t-1}) \cdot a_{z_{t-1}, z_{t}^{k}} \\
\end{align*}
$$

 

Recursive representation

 

$$ P(x_1, ..., x_t, z_{t}^{k}=1) = \alpha_{t}^{k} = b_{k, x_{t}} \sum_{i} \alpha_{t-1}^{i} \cdot a_{i, k} $$

 

 

 

 

Reference
문일철 교수님 강의 
https://www.youtube.com/watch?v=mnUcZbT5E28&list=PLbhbGI_ppZISMV4tAWHlytBqNq1-lb8bz&index=59