[ML] 은닉 마르코프 모델 : Hidden Markov Models(HMM)

ratgos님의 blog 게시글을 참고하여 작성되었습니다

Hidden Markov Models

은닉 마르코프 모델, 혹은 은닉 마코프 모델이라고 불리는 HMM은 순차적인 데이터를 다루는데 강점을 지닌 모델로 개체명 인식(NER), 품사 태깅(POS tagging)등 단어의 연쇄로 나타나는 언어구조 처리에 과거 많은 주목을 받았던 기법이다

---

마코프 체인(Markov chain) : HMM이 전제로 한 모델

Markov chain은 Markov Property을 지닌 이산확률과정을 가리키며, 러시아어 문헌에 나오는 글자들의 순서에 관한 모델을 구축하기위해 처음 제안된 개념이다

 

한 상태의 확률은 단지 그 이전 상태에만 의존한다는 것이 Markov chain의 핵심이다

즉, 한 상태에서 다른 상태로의 전이는 그동안의 상태 전이에 대한 history를 필요로 하지 않고 바로 직전 상태로 추정할 수 있다는 개념이다

 

Markov Chain의 도식화 : 𝑃(𝑞𝑖|𝑞1,...,𝑞𝑖−1)=𝑃(𝑞𝑖|𝑞𝑖−1)

 

날씨를 Markov chain으로 모델링한 예시

• 각 node는 상태를, edge는 전이를 나타냄
  •     node : 일반적인 날씨의 상태(HOT/COLD/WARM) , 시작과 끝 상태도 포함
• 엣지위의 𝑎𝑖𝑗는 𝑖번째 상태에서 𝑗번째 상태로 전이할 확률(각 노드별로 전이확률의 합은 1)

---

HMM

HMM은 각 상태가 Markov Chain을 따르되 hidden되어 있다고 가정함. 즉, 관측치 뒤에 은닉되어 있는 상태를 추정하고자 함

 

날씨를 예시로 HMM을 도식화한 그림

• 관측치(관측할 수 있는 것) : 당시 소비한 아이스크림의 개수
• 은닉되어 있는 상태(알고자 하는 것) : 당시 날씨
• 𝐵는 방출확률(Emission Probability)  : 날씨라는 은닉된 상태로부터 아이스크림 개수라는 관측치가 튀어나올 확률

---

Likelihood 

likelihood란 어떤 확률 분포에서 왔을지에 대한 확률로, 

모델 λ가 주어졌을 때 관측치 𝑂가 나타날 확률 𝑝(𝑂|λ)로, 즉, 모델 λ이 관측치 하나를 뽑았는데 그 관측치가 𝑂일 확률을 나타냄

 

관측된  𝑂 가 아이스크림 [3개, 1개, 3개]인 경우

 

Markov Chain, 직전 상태만 고려하여 계산

𝑃(313,ℎ𝑜𝑡ℎ𝑜𝑡𝑐𝑜𝑙𝑑)=𝑃(ℎ𝑜𝑡|𝑠𝑡𝑎𝑟𝑡)×𝑃(ℎ𝑜𝑡|ℎ𝑜𝑡)×𝑃(𝑐𝑜𝑙𝑑|ℎ𝑜𝑡)×𝑃(3|ℎ𝑜𝑡)×𝑃(1|ℎ𝑜𝑡)×𝑃(3|𝑐𝑜𝑙𝑑)=0.8×0.6×0.3×0.4×0.2×0.1

 

관측치 [3,1,3]에 대한 최종적인 우도 계산

𝑃(313)=𝑃(313,𝑐𝑜𝑙𝑑𝑐𝑜𝑙𝑑𝑐𝑜𝑙𝑑)+𝑃(313,𝑐𝑜𝑙𝑑𝑐𝑜𝑙𝑑ℎ𝑜𝑡)+...𝑃(313,ℎ𝑜𝑡ℎ𝑜𝑡ℎ𝑜𝑡)

 

---

Compute Likelihood : Forward Algorithm

N개의 은닉상태가 있고 관측치의 길이가 T라면 우도 계산 시 고려해야 할 가짓수는 N^T으로 시간복잡도가 매우 증가,

따라서 중복되는 계산은 저장해두는 Dynamic Programming(DP) 기법 사용

 

𝛼1(1)=𝑃(𝑐𝑜𝑙𝑑|𝑠𝑡𝑎𝑟𝑡)×𝑃(3|𝑐𝑜𝑙𝑑)

𝛼1(2)=𝑃(ℎ𝑜𝑡|𝑠𝑡𝑎𝑟𝑡)×𝑃(3|ℎ𝑜𝑡)

𝛼2(1)= 𝛼1(1)×𝑃(𝑐𝑜𝑙𝑑|𝑐𝑜𝑙𝑑)×𝑃(1|𝑐𝑜𝑙𝑑)+𝛼1(2)×𝑃(𝑐𝑜𝑙𝑑|ℎ𝑜𝑡)×𝑃(1|𝑐𝑜𝑙𝑑)

 

j번째 상태에서 𝑜1,…,𝑜𝑡가 나타날 전방확률 α는 아래와 같이 정의

전방확률을 관측치 시퀀스 끝까지 계산하게 되면 앞서 계산한 우도와 동치

---

Decoding : Viterbi Algorithm

 

디코딩(decoding) : 모델λ과 관측치 시퀀스 O가 주어졌을 때 가장 확률이 높은 은닉상태의 시퀀스 Q를 찾는 것.

비터비 알고리즘(Viterbi Algorithm) : HMM의 디코딩 과정에서 사용되는 알고리즘 

• 비터비 확률(Viterbi Probability) 

Forward Algoritm에서 구하는 전방확률 α와 비터비 확률을 계산하는 과정이 유사하나, 전자는 각 상태의 전방확률을 구하기 위해 가능한 모든 경우의 수를 고려해 그 확률들을 더하고(sum), 후자는 그 확률들 가운데 최대값(max)을 구하는 것

 

디코딩 과정