은닉 마르코프 모델

안드레이 마르코프(Andrey Andreyevich Markov; 1856-1922)는 1906년에 발표된 논문에서 마르코프 체인이라는 용어를 사용하면서 연쇄법칙을 이용한 확률기반 이론을 마련하였습니다. 

 

현재 가장 많이 사용되는 이론중에 하나이며 수학, 통계학, 정보통신, 생명정보학, 컴퓨터공학, 인공지능 분야에서는 마르코프 알고리즘을 적용하여 글자체 인식과 서열비교 분석등을 이용하고 있습니다. 

 

 

- 마르코프 체인 

 

마르코프 체인은 이산확률 과정입니다. 

 

날씨에 대한 예제를 들어 보면 어제, 오늘, 비가 올 확률이 서로 연관되어 있다면 각각의 확률이 연관되어 있다고 하여 체인이론으로 연관 규칙을 찾아 보는 방법입니다.

원래는 글자의 연관 규칙을 찾아내기 위해 만들어낸 방법으로 글자의 연관성에 대한 확률값을 표기하기 위한 방법입니다. 

 

날씨로 마르코프 체인을 설명하는 간단한 예제를 나타내 봅시다. 

 

 

                                                  x = {1=" 맑음" , 2="비"}

 

오늘 / 내일	맑음	비
맑음	0.6	0.4
비	0.3	0.7

 

오늘 맑은 날씨 이고, 내일도 맑을 확율은 0.6

오늘 맑은 날씨 이고, 내일 비가 올 확률은 0.4

오늘 비가 오고, 내일 맑을 확률은 0.3

오늘 비가 오고, 내일 비가 올 확률은 0.7 

 

 

전이확률로 표현하면 다음과 같습니다. 

 

오늘, 내일, 모레의 날씨(맑음, 비)를 표현하는 연관수식을 정의하면 다음과 같습니다. 

 

3년 간 특정일의 날씨중 80%가 맑았다면 모레 날씨가 맑을 확률은 얼마로 예측 할 수 있는가? 

 

 

- 마르코프 모델 

 

마르코프 체인을 기반으로 상태전이도를 나타내면 다음과 같습니다. 

 

 

마르코프 모델은 마르코프 체인을 모델링하여서 나타내는 이론입니다. 

연쇄법칙이라는 사건으로 확률적 상황을 나타내는 방법입니다.

 

 

 

- 은닉 마르코프 모델

 

은닉 마르코프 모델은 은닉(hidden)이라는 부분으로 규칙의 원리에 대해 생각해 볼 수 있는데 이것은 마르코프 체인이 n차 횟수까지 늘어나면 기하급수적으로 계산 데이터가 많아지기 때문에 확률적 내용은 은닉하여 반영하는 방법입니다. 

 

 

 

 

마르코프 모델에서 전이모델이 많아진다면 연쇄법칙에 대한 연산이 많아지게 됩니다. 그렇다면 기하급수적으로 늘어나는 수식을 표현하기 불가능해서 관측된 상태를 확률값으로 표현하여 은닉(hidden) 하게 됩니다. 

 

은닉 마르코프 모델은 상태를 은닉하여 연쇄법칙을 연산하는 마르코프 모델입니다. 

이 이론은 수학자 바움에 의해 정립(바움 웰치 알고리즘)이 되었습니다. 

 

https://ratsgo.github.io/speechbook/docs/am/baumwelch

Baum-Welch Algorithm

 

 

비터비 알고리즘(앤드류 비터비, 관련기사 링크)은 은닉마르코프 모델을 적용해서 만들어진 알고리즘인데 관측된 상황에서 가장 높은 상태들의 순서를 찾기 위한 동적 계획법 알고리즘입니다. CDMA에서 사용되는 것으로 알려져 있으며 주어진 음성신호에서 가장 높게 나타나는 신호를 찾는 알고리즘입니다. 

 

https://ratsgo.github.io/data%20structure&algorithm/2017/11/14/viterbi/

비터비 알고리즘 · ratsgo's blog

 

 

- 예제

 

여자친구의 삶 (https://cs.kangwon.ac.kr/~leeck/NLP/06-2_viterbi.pdf)

 

 

- 응용 

 

은닉 마르코프 모델을 적용한 서열 분석 

은닉 마르코프 모델을 이용한 필기체 인식 알고리즘 

 

 

- 유전자 서열분석 프로그램

 

Hmmer  (http://www.hmmer.org)

 

 

 

 

 

참고 사이트 - 1 , 2

은닉마코프모델(Hidden Markov Models) · ratsgo's blog

 

 

일설에 의하면 마르코프는 푸쉬킨의 시를 좋아했다고 합니다. 그래서 운율에 대한 분석을 하기 위한 수학적 의미로 마르코프 체인을 만들었다는 이야기도 있었고요. 

 

 

알렉산드로 푸쉬킨 

 

삶이 그대를 속일지라도 

 

삶이 그대를 속일지라도

슬퍼하거나 노여워하지 말라

슬픈 날을 참고 견디면

즐거운 날이 오리니

 

마음은 앞날에 살고

지금은 언제나 슬픈것이니 

모든 것은 덧없이 사라지고

지난간 것은 또 그리워지나니

 

 

알렉산드르 푸시킨 - 위키백과, 우리 모두의 백과사전