[머신러닝] 마코프 체인 모델(Markov Chain Model)-MC,HMM - 컴도리돌이

---

Markov chain

Hidden Markov model

characteristics, Difference

Model parameters

Construction

Prediction(Forward, Backward, Viterbi alogrithm)

Learning

---

마코프 체인(Markov Chain)

• 상태(state)의 확률은 단지 그 이전 관측된 상태에만 의존한다.
• 한 상태에서 다른 상태로의 전이(transition)는 상태 전이에 대한 긴 이력(history)을 필요로 하지 않고 바로 직전 상태에서의 전이로 추정할 수 있다.
• 모델 변수(model parameter): 전이 변수(transition parameter)

일차 마르코프 연쇄(first-order markov chain)

 

(1) - P(X1, X2, X3, X4) = P(X1) P(X2| X1) P(X3| X1, X2) P(X4| X1, X2, X3)

(2) - P(X1, X2, X3, X4) = P(X1) P(X2| X1) P(X3| X2) P(X4| X3)

 

• X1, , X2, X3, X4, 에 대한 결합 확률 분포를 나타내면, (1)이라는 일반적인 식이 나온다.
• (1)의 식에서 각각의 조건부 분포가 가장 최근의 관측값을 제외한 모든 이전 관측값들로부터 독립적이라고 가정하면, (2) 일차 마코프 연쇄(First-order Markov chain)를 얻게 된다.

 

이차 마르코프 연쇄(second-order markov chain)

• (2)와 같은 방식을 이용해서 순차 관측 값들의 경우에 몇 번의 연속적인 관측값들의 상태가 다음 값을 예측하는 데 있어서 정보를 주는데, 더 높은 차수의 마코프 연쇄를 사용할 수 있다. 그림과 같이 두 단계 앞의 관측 값에 대한 종속적으로 만들면 이차 마르코프 연쇄(second-order markov chain)를 얻게 된다.
• 특징 1 : 초기 분포의 영향은 시간이 지남에 따라 점점 감소한다. (초기 분포와 독립된 분포)
• 특징 2 : 고정 분포(stationary distribution) : Xt의 분포가 더 이상 바뀌지 않을 정도로 오랜 시간(무한대)이 지나면 Xt의 분포가 고정된다(수렴된다).

---

날씨에 대한 마코프 체인 예(Markov chain of weather)

 

1) X(날씨)의 상태(state)는 맑음(sun)과 비(rain)가 있는데 첫째 날(X1)에 날씨가 맑았다면, X2에도 날씨가 맑거나 비가 올  확률은?

 

 

2) X2에 날씨가 맑거나 비가 올 확률은?

 

변수 t에 대한 날씨의 확률은 초기 값(P(X1))의 확률이 p일 때 P(Xt)는 다음과 같다.

 

t번째 날의 날씨

위에 문제를 마코프 행렬(Markov Matrix)로 해결하면 다음과 같다.

---

전이 확률 학습(Learning transition Probabilities)

• 전이 확률에 대한 MLE는 학습된 데이터(training data)에서 관찰된 전이 빈도(frequencies of transitions)이다.
• 예를 들면, 연속된 데이터 ACGTCGCA가 있을 경우, 우리는 P(G|C)에 대한 CG와 CX의 수를 셀 수 있다.

 

 

연속된 데이터가 있을 경우 P(CG)를 알고 싶을 때

원하는 값을 세서 확률을 구할 수 있다.

---

은닉 마코프 모델(Hidden Markov Model)

• 통계적 마코프 모델로, 시스템이 은닉된 상태와 관찰 가능한 결과의 두 가지 요소로 이루어진 모델이다.
• 모델 변수(model parameters) : 전이 확률, 방출 확률
• 관찰 가능한 결과를 야기하는 직접적인 원인은 관측될 수 없는 은닉(Hidden) 상태이고, 그 상태들이 마코프 과정을 통해 도출된 결과들만이 관찰될 수 있다.
• 전이 확률(Trainsition probability) : 시간 t-1에서의 은닉 상태가 주어졌을 때 시간 t에서의 은닉 상태가 선택될 확률 분포.
• 방출 확률(emission probability) : 주어진 상태 Xt에서 특정한 결괏값 Yt이 관측될 확률 분포. 은닉 상태로부터 관측치가 튀어나올 확률.
• 마코프와 차이점 : 은닉에서 X의 state 자체는 보이지 않기 때문에(마코프 모델에서는 X의 state가 확인된다.) 오직 X 상태에 대한 각각의 Y값만 볼 수 있다.

---

날씨에 대한 은닉 마코프 모델의 예시(Hidden markov model of temperature and size of flower)

HMM example

1) 연속된 4개의 상태(X of state)가 있고 (H, H, C, C) , 관측된 데이터가 (small, medium, small, large) 일 경우 P(x)는?

 

---

은닉 마코프 모델을 기반한 문제(Problems based on hidden Markov model)

• 평가 문제(evaluation problem)
• 디코딩 문제(decoding problem)
• 학습 문제(learning problem)

 

1) 평가 문제(evaluation problem) - 모델(model)에 의해 시퀀스(sequence)가 생성될 가능성 찾기

• N개의 은닉 상태가 있을 때 관측치 길이가 T라면 계산 시 고려해야 할 가짓수가 N^T가 생긴다. 이런 비효율성을 완화하기 위해 다이내믹 프로그래밍 기법을 사용한다. 한 노드에 가는 계산을 저장해 두었다면 계산 시간을 단축시킬 수 있다.
• 포워드 알고리즘(Forward Algorithm) , 백워드 알고리즘(Backward Algorithm)

 

Forward algorithm : a는 인덱스(index)에 사용하는 함수, 그 함수(a,t+1)가 전 단계(a,t)의 전이 확률과 방출 확률을 곱하면 다음 단계가 나온다.

• Forward algorithm은 중복되는 계산 결과를 저장해 두었다가 필요할 때마다 불러서 쓴다.

Backward algorithm

2) 디코딩 문제(decoding) - 시퀀스에서 가장 가능성이 높은 부분을 분석하여 찾기

• 모델 λ과 관측치 시퀀스 O이 주어졌을 때 가장 확률이 높은 은닉 상태(hidden state)의 시퀀스 Q를 찾는 것이다. 이를 디코딩(decoding)이라 한다.
• 비터비 알고리즘(Viterbi algrothm) - 직전 단계의 계산 결과의 최적 상태를 활용하는 다이내믹 프로그래밍(dynamic programming) 

Viterbi algorithm

• forward algorithm은 각 상태에서 a를 구하기 위해 가능 모든 경우의 수를 고려해 그 확률들을 더해줬다면, Viterbi algorithm에서는 그 확률들 가운데 최댓값에 저장을 한다.

3) 학습 문제(learning problem) - MLE

• 각 시퀀스(training sequence)에 대한 상태 경로(state path)를 알고 있을 때 모델 매개변수를 학습시키는 것은 간단하다.
• 감독 접근 방식(Supervised approach)
• MLE로 모수 추정(Estimate the parameters by MLE)
• 확률을 얻기 위해 정규화(Normalize to get probability)

---