Intro.

히든 마르코프 모델(Hidden Markov Model, HMM)은 마르코프 체인의 확장된 모델로, 관측 가능한 데이터(Observable Data)와 숨겨진 상태(Hidden States) 간의 확률적 관계를 모델링 한다. HMM은 감춰진 상태를 통해 관측된 데이터를 설명하는 확률 모델로, 각 상태가 은닉 되어 직접 관찰할 수 없다는 특징을 가진다.

HMM 구성.

• 상태 공간(State Space) HMM은 유한한 개수의 상태들로 구성되며, 이 상태들은 Markov chain의 상태들이다. 상태는 보통 $S=\{s_1,s_2,s_3,\dots,s_n\}$으로 표현된다.
  
• 관찰 공간(Observation Space) 관찰값은 $V=\{v_1,v_2,v_3,\dots,v_m\}$의 값들로 이루어져 있다. 관찰값은 각 상태에 의해 생성된다.
  
• 초기 상태 분포(Initial State Distribution) 초기 상태의 확률 분포는 $\pi$로 나타내며, 이는 각 상태가 처음에 발생할 확률이다. 즉, $\pi i=P(Q_1=S_i)$이다.
  
• 전이 확률(Transition Probabilities) 전이 확률은 한 상태에서 다른 상태로 이동할 확률이다. $A=[a_{ij}]$로 나타내며,$a_{ij}=P(Q_{t+1}=S_j|Q_t=S_i)$이다. 이는 시간 $t$에 상태 $S_i$에 있을 때 시간 $t+1$에 상태 $S_j$로 전이할 확률을 의미한다.
  
• 관찰 확률(Emission Probabilities) 각 상태에서 관찰값이 발생할 확률이다. $B=[b_j(k)]$로 나타며, $b_j(k)=P(Q_t=v_k|Q_t=S_j)$이다. 이는 시간 $t$에 상태 $S_j$에 있을 때 관찰값 $v_k$가 발생할 확률을 의미한다.
  

HMM 문제.

• 평가 문제(Evaluation Problem): 관찰된 시퀀스가 주어졌을 때, 특정 HMM이 그 시퀀스를 생성할 확률을 계산하는 문제이다. 주로 Forward 알고리즘을 사용하여 해결한다.
• 디코딩 문제(Decoding Problem): 가장 가능성이 높은 숨겨진 상태의 시퀀스를 찾는 문제이다. Viterbi 알고리즘을 사용하여 해결한다.
• 학습 문제(Learning Problem): 모델의 파라미터를 학습하는 문제이다. 관찰된 데이터가 주어졌을 때, HMM의 파라미터 A, B, $\pi$를 최적화하는 것이다. Baum-Welch 알고리즘을 사용하여 해결한다.

Example.

날씨 예측을 HMM으로 설명할 수 있다. 여기서는 숨겨진 상태로 '맑음(Sunny)', '흐림(Cloudy)', '비(Rainy)'가 있다고 가정하자. 관찰값은 '산책(Walk)', '쇼핑(Shop)', '청소(Clean)'이다.

• 상태 전이 확률 행렬 $A$ 한 상태에서 다른 상태로 전이할 확률을 나타내며, 이 행렬은 모델의 숨겨진 상태 간의 전이 확률을 정의한다. 여기서는 행과 열 모두 숨겨진 상태인 날씨를 뜻한다. 예로, $a_{11}=0.7$로 ‘Sunny’ 상태에서 ‘Sunny’ 상태로의 전이 확률을 의미하며, $a_{23}=0.3$으로 ‘Cloudy’ 상태에서 ‘Rainy’ 상태로의 전이 확률을 의미한다.
  $A=\left[ \begin{matrix} 0.7&0.2&0.1\\ 0.3&0.4&0.3\\ 0.2&0.3&0.5\\ \end{matrix} \right]$
• 관찰 확률 행렬 $B$ 숨겨진 상태에서 특정 관찰값이 발생할 확률을 나타내며, 이 행렬은 상태와 관찰값 간의 관계를 정의한다. 여기서는 행은 숨겨진 상태인 날씨를 뜻하고 열은 관찰값을 뜻한다. 예로, $b_{sunny}(Walk)$는 0.6으로 $b_{11}$을 뜻하며 $b_{cloudy}(Clean)$은 0.3으로 $b_{23}$을 뜻한다.
  $B=\left[ \begin{matrix} 0.6&0.3&0.1\\ 0.3&0.4&0.3\\ 0.2&0.3&0.5\\ \end{matrix} \right]$
• 초기 상태 확률 분포 $\pi$ 시스템이 시작할 때 각 상태에 있을 확률을 나타낸다.
  $\pi=\left[ \begin{matrix} 0.5&0.3&0.2\\ \end{matrix} \right]$
  • $\pi_1$=0.5: 처음에 'Sunny' 상태에 있을 확률이 0.5
  • $\pi_2$=0.3: 처음에 'Cloudy' 상태에 있을 확률이 0.3
  • $\pi_3$=0.2: 처음에 'Rainy' 상태에 있을 확률이 0.2

예제로 사용할 관찰 시퀀스를 $O=[Walk, Shop, Clean]$라고 가정하자.

Step 1. Forward 알고리즘

1. 초기화

   각 상태에서 첫 번째 관찰값에 대한 초기 확률을 계산한다.

   $\alpha_1(i)=\pi_i\cdot b_i(O_i)$

   여기서 $\pi$는 초기 상태 확률, $b_i(O_i)$는 상태 $S_i$에서 첫 번째 관찰 값 $O_1(Walk)$가 발생할 확률을 뜻한다.

   • $\alpha_1(Sunny)=\pi(Sunny)\cdot b_{Sunny}(Walk)=0.5\cdot 0.6=0.3$
   • $\alpha_1(Cloudy)=\pi(Cloudy)\cdot b_{Cloudy}(Walk)=0.3\cdot 0.3=0.09$
   • $\alpha_1(Rainy)=\pi(Rainy)\cdot b_{Rainy}(Walk)=0.2\cdot 0.2=0.04$

2. 재귀

   다음으로, 각 시간 $t$에서 모든 상태 $j$에 대해 $\alpha_t(j)$를 계산한다.

   $\alpha_{t+1}(j)=(\sum^N_{i=1}\alpha_t(i)\cdot a_{ij})\cdot b_j(O_{t+1})$
   • $\alpha_2(Sunny)=(\alpha_1(Sunny)\cdot a_{Sunny, Sunny}+\alpha_1(Cloudy)\cdot a_{cloudy,Sunny}+\alpha_1(Rainy)\cdot a_{Rainy,Sunny})\cdot b_{sunny,2(shop)}=(0.3\cdot0.7+0.09\cdot0.3+0.04\cdot0.2)\cdot0.3=0.0822$
   • $\alpha_2(Cloudy)=(0.3\cdot0.2+0.09\cdot0.4+0.04\cdot0.3)\cdot0.4=0.0384$
   • $\alpha_2(Rainy)=(0.3\cdot0.1+0.09\cdot0.3+0.04\cdot0.5)\cdot0.3=0.0189$
   • $\alpha_2(Sunny)=(0.0822\cdot0.7+0.0384\cdot0.3+0.0189\cdot0.2)\cdot0.1=0.00619$
   • $\alpha_3(Cloudy)=(0.0822\cdot0.2+0.0384\cdot0.4+0.0189\cdot0.3)\cdot0.3=0.01193$
   • $\alpha_3(Rainy)=(0.0822\cdot0.1+0.0384\cdot0.3+0.0189\cdot0.5)\cdot0.5=0.0733$

3. 종합

   마지막으로, 모든 $\alpha_t(i)$의 합을 계산하여 관찰 시퀀스 $O$가 주어진 모델에서 발생할 확률을 구한다.

   $P(O|\lambda)=\sum^N_{i=1}\alpha_T(i)$
   $P(O|\lambda)=0.00619+0.01193+0.00733=0.02545$

   따라서, 관찰 시퀀스 $O=[Walk, Shop, Clean]$가 주어진 HMM에 의해 발생할 확률은 0.02545이다.

Step 2: Viterbi 알고리즘 (디코딩 문제)

이제 Viterbi 알고리즘을 사용하여 가장 가능성이 높은 숨겨진 상태 시퀀스를 찾아볼 수 있다.

1. 초기화

   $\delta_1(i)=\pi_i\cdot b_i(O_1)$
   $\psi_1(i)=0$

• $\delta_1(Sunny)=0.5⋅0.6=0.3$
• $\delta_1(Cloudy)=0.3⋅0.3=0.09$
• $\delta_1(Rainy)=0.2⋅0.2=0.04$

💡 $\delta$와 $\psi$의 정의

• $\delta_t(i)$는 시간 $t$에서 상태 $S_i$에 도달할 수 있는 모든 경로 중에서 가장 높은 확률을 가지는 경로의 확률을 의미한다.
• $\psi_t(i)$는 시간 $t$에서 상태 $S_i$에 도달하는 가장 높은 확률의 경로가 시간 $t-1$에 어떤 상태에서 왔는지를 기록한다.

2. 재귀

   다음으로, 각 시간 $t$에서 모든 상태 $j$에 대해 $\delta_t(j)$와 $\psi_t(j)$를 계산한다.

   $\delta_{t+1}(j)=max_{1\leq i\leq N}[\delta_t(i)\cdot a_{ij}]\cdot b_j(O_{t+1})$
   $\psi_{t+1}(j)=argmax_{1\leq i\leq N}[\delta_t(i)\cdot a_{ij}]$
   • $δ2(Sunny)=max(0.3⋅0.7,0.09⋅0.3,0.04⋅0.2)⋅0.3=0.063,\quad \psi2(Sunny)=Sunny$
   • $\delta2(Cloudy)=max⁡(0.3⋅0.2,0.09⋅0.4,0.04⋅0.3)⋅0.4=0.036,\quad \psi2(Cloudy)=Sunny$
   • $\delta2(Rainy)=max⁡(0.3⋅0.1,0.09⋅0.3,0.04⋅0.5)⋅0.3=0.0108,\quad \psi2(Rainy)=Cloudy$
   • $\delta3(Sunny)=max⁡(0.063⋅0.7,0.036⋅0.3,0.0108⋅0.2)⋅0.1=0.00441, \quad \psi3(Sunny)=Sunny$
   • $\delta3(Cloudy)=max⁡(0.063⋅0.2,0.036⋅0.4,0.0108⋅0.3)⋅0.3=0.00648, \quad \psi3(Cloudy)=Cloudy$
   • $\delta3(Rainy)=max⁡(0.063⋅0.1,0.036⋅0.3,0.0108⋅0.5)⋅0.5=0.0054, \quad \psi3(Rainy)=Cloudy$

3. 종료

   마지막으로, 가장 높은 확률을 가지는 상태를 찾고, 그 경로를 추적한다.

   $P^*=max_{1\leq i\leq N}\delta_T(i)$
   $q^*_T=argmax_{1\leq i\leq N}\delta_T(i)$
   • $P^*=max(0.00441,0.00648,0.0054)=0.00648$
   • $q^*_3=Cloudy$

Step 3. Viterbi 알고리즘 경로 추적

Viterbi 알고리즘에서는 가장 가능성 있는 상태 경로를 추적하기 위해 백트래킹을 사용한다. 우리는 각 시간 단계에서 어떤 상태에서 왔는지를 기록한 $\delta$행렬과 $\psi$행렬을 사용한다. 이미 $q^*_3=Cloudy$ 라는 것을 알고 있으므로, 이전 시간 단계로 돌아가며, 경로를 추적할 수 있다.