은닉마르코프모델

HMM 은 어떤 문제에 적용할까?

1. Evaluation : 민예가 공부 공부 놈 의 확률은 얼마나 될까?

2. Decoding : 민예가 지난 3일 동안 공부 공부 놀았는데, 그때 날씨는 어땟을까?

3. Learning : 민예를 보니깐 대부분 공부 공부 놈인데, 이 민예의 특성을 잘 반영하는 민예모델을 만들어보자.

자세한 구현은 여기있다. 논문은 여기있다.

Evaluation

• 문제 : HMM 파라미터와 관측치가 주어졋을 때, 관측치가 나타날 확률을 계산한다.

• 해결방법 : Forward algorithm

• 예시 : 정박사가 오늘 산책, 내일 산책, 모레 연구, 글피 쇼핑을 할 확률은?

• 활용분 : 시퀀스가 주어졌을 때, 정박사 HMM의 확률이 높은지, 조박사의 HMM의 확률이 높은지 판단할 수 있으므로 Sequence Classification 문제에 활용할 수 있다.

전방 확률

시점 및 상태별 Forward Probability

• $\alpha_1(1) = \pi_1 * b_1(\text{산책})= 0.6 * 0.1 = 0.06$

• $\alpha_1(2) = \pi_2 * b_2(\text{산책})= 0.4 * 0.6 = 0.24$

• $\alpha_2(1) = (\alpha_1(1) * a_{11} + \alpha_1(2) * a_{21} ) *b_1(산책)= (0.06*0.7 + 0.24*0.4)*0.1 = 0.0138$

• $\alpha_2(2) = (\alpha_1(1) * a_{12} + \alpha_1(2) * a_{22} ) *b_2(산책)= (0.06*0.3 + 0.24*0.6)*0.6 = 0.0972$

• $\alpha_3(1) = (\alpha_2(1) * a_{11} + \alpha_2(2) * a_{21} ) *b_1(연구)= (0.0138*0.7 + 0.0972*0.4)*0.5 = 0.02427$

• $\alpha_3(2) = (\alpha_2(1) * a_{12} + \alpha_2(2) * a_{22} ) *b_2(연구)= (0.0138*0.3 + 0.0972*0.6)*0.1 = 0.00625$

• $\alpha_4(1) = (\alpha_3(1) * a_{11} + \alpha_3(2) * a_{21} ) *b_1(쇼핑)= (0.02427*0.7 + 0.00625*0.4)*0.4 = 0.00780$

• $\alpha_4(2) = (\alpha_3(1) * a_{12} + \alpha_3(2) * a_{22} ) *b_2(쇼핑)= (0.02427*0.3 + 0.00625*0.6)*0.3 = 0.00331$

정박사가 오늘 산책, 내일 산책, 모레 연구, 글피 쇼핑을 할 확률은 $0.00780+0.00331 = 0.01111$

Forward Probability

$$P(o|\lambda) = {\sum_{j=1}^{n}}\alpha_T(j)$$

$\text{ for } i = 1,$

$$\alpha_t(1) = \pi_i * b_i(o_1)$$

$\text{ for } 2<=i <=T,$

$$\alpha_t(i) = [{\sum_{j=1}^{n} (\alpha_{t-1}(j) * a_{ji}) } ]* b_i(o_t)$$

후방 확률

시점 및 상태별 Backward Probability

• $\beta_4(1) = 1$

• $\beta_4(2) = 1$

• $\beta_3(1) = ( \beta_4(1) * a_{11} + \beta_4(2) * a_{12} ) * b_1(쇼핑) = (1*0.7 +1*0.3)*0.4 = 0.4$

• $\beta_3(2) = ( \beta_4(1) * a_{21} + \beta_4(2) * a_{22} ) * b_2(쇼핑) = (1*0.4 +1*0.6)*0.3 = 0.3$

• $\beta_2(1) = ( \beta_3(1) * a_{11} + \beta_3(2) * a_{12} ) * b_1(연구) = (0.4*0.7 +0.3*0.3)*0.5 = 0.185$

• $\beta_2(2) = ( \beta_3(1) * a_{21} + \beta_3(2) * a_{22} ) * b_2(연구) = (0.4*0.4 +0.3*0.6)*0.1 = 0.034$

• $\beta_1(1) = ( \beta_2(1) * a_{11} + \beta_2(2) * a_{12} ) * b_1(산책) = (0.185*0.7 +0.034*0.3)*0.1 = 0.01397$

• $\beta_1(2) = ( \beta_2(1) * a_{21} + \beta_2(2) * a_{22} ) * b_2(산책) = (0.185*0.4 +0.034*0.6)*0.6 = 0.05664$

Backward Probability

$\text{ for } i =T,$

$$\beta_T(i) = 1$$

$\text{ for } 1<=i <=T-1,$

$$\beta_t(i) = \sum_{j=1}^n(\beta_{t+1}(j) * a_{ij}) * b_i(o_{t+1})$$

Decoding

• 문제 : HMM 모델과 관측치가 주어졋을 때, 가장 확률이 높은 은닉 상태를 알아낸다. 즉, 주어진 observation이 나타날 확률이 가장 큰 state 계산한다.

• 해결방법 : Viterbi algorithm

• 예시 : 정박사가 오늘 산책, 내일 산책, 모레 연구, 글피 쇼핑을 했다면 각 날들의 날씨는 ?

HMM 의 파라미터

• State transition probability, 상태전이 확률 (A) : $A = a_{ij}$

  • $a _{ij} = p(q_{t+1} = s_j | q_{t} = s_i) \text{ for 1 <= i, j <= n }$

  • $\sum_{j=1}^{n} a_{ij} = 1$

• Emission probability, 방출 확률 (B) : $B = b_j(v_k)$

  • $b _{j}(v_{k}) = p(o_{t} = v_k | q_{t} = s_j) \text{ for 1 <= j <= n, 1<=k<=m }$

  • $\sum_{k=1}^{m} b_{j}(v_k) = 1$

• Initial state probability, 초기 상태 확률 ($\pi$) : $\pi = \pi_{i}$

  • $\pi_i -> s_i$ 에서 시작할 확률

  • $\sum_{i=1}^{n} \pi_{i} = 1$

정박사 삶의 HMM

Viterbi Algorithm

Viterbi Algorithm

각 단계에서 큰 값을 뽑으면, 해, 해, 비, 비 이다.

Learning

• 문제 : HMM 파라미터 초깃값과 관측치가 주어졋을 때, 주어진 관측치가 가장 높은 확률이 나오도록 하는 HMM 의 파라미터를 알아낸다.

• 해결방법 : Baum-Welch algorithm

• 예시 :

Baum-Welch Algorithm (EM Algorithm)

• E-Step : $\alpha, \beta$ 를 이용해서 $\gamma(i), \xi(i, j)$ 를 구하는 것

• M-Step : $\gamma(i), \xi(i, j)$ 을 이용해서 HMM 의 파라미터(상태전이확률, 방출확률, 초기상태확률) 개선함.

$\alpha_t(i)*\beta_t(i)$ : t번째 시점에서 상태 i 를 지나는 모든 경로 해당하는 확률의 합

$\gamma(i)$ : 관측치와 HMM 의 파라미터가 주어졌을 때, t 시점의 은닉 상태가 $s_i$ 일 확률

$$\gamma(i) =\frac{\alpha_t(i)*\beta_t(i)} {\sum_{j=1}^{n}\alpha_{t}(j)*\beta_t(j)}$$

$\xi(i, j)$ : 관측치와 HMM의 파라미터가 주어졌을 때, t 시점의 은닉상태가 $s_i$ 이고, t+1시점의 은닉 상태가 $s_j$ 일 확률

$$\xi(i, j) = \frac{\alpha_t(i)*a_{ij}* b_j(o_{t+1})*\beta_{t+1}(j) }{\sum_{k=1}^n\sum_{l=1}^n \alpha_t(k)*a_{kl}* b_l(o_{t+1})*\beta_{t+1}(l)}$$

M-Step : 개선하는 방법

• 초기상태확률

$$\pi_i = \gamma_t(i)$$

• 상태전이확률

$$\alpha_{ij}^{new} = \frac{s_i에서 s_j로 전이할 확률}{s_i에서 전이할 기댓값}$$

$$\alpha_{ij}^{new} = \frac{\sum_{t=1}^T \xi(i,j)}{\sum_{t=1}^T\gamma(i)}$$

• 방출확률 : 모든 시점을 돌면서 $v_k$ 관측치가 나왔을 때, $b_i$ 의 감마를 더해준다.

$$b_i(v_k)^{new} = \frac{\sum_{o_t=v_t인t=1}^T{\gamma_t(i)}}{\sum_{t=1}^T\gamma(i)}$$