[Chapter 6] Markov Chains

Markov Chain

Hidden Markov Model를 정의하기 위해 Markov chain( observed Markov Model )에 대해 알아야 한다. Markov Chain은  Sequence 값이 입력될 경우 유일한 하나의 State를 결정하는 Weighted Finite-State Automaton의 특수한 경우이다. 모호성 문제가 없기 때문이다.(?)

Markov Chain As Graphical Model

Markov Chain의 그래프 모델의 구성 요소는 Set of States, Transition Probability Matrix, Start State & End Satate로 구성된다. Transition Probability Matrix의 합 $a_{01} + a_{02} + \cdot\cdot\cdot + a_{nn}$은 1이다.

 



- Set of States                                $Q = q_1q_2\cdot\cdot\cdot q_N$

- Transition Probability Matrix     $A = q_{01}q_{02}\cdot\cdot\cdot q_{n1}\cdot\cdot\cdot q_{nn}$

- Start State & End State               $q_0,q_F$

 

특정 State의 확률을 구할 때 이전 State에만 의존하는 Markov Assumption로 인해 $a_{ij}$는 $P(q_i|q_{i-1})$로 표현된다.

 

Markov Assumption: $P(q_i|q_1 \cdot\cdot\cdot q_{i-1}) = P(q_i|q_{i-1})$

Markov Chain As Graphical Model - Not Rely On Start & End State

Markov Chain Graphical Model에 Start & End State에 의존하지 않기 위해 각 State에 시작 확률을 부여하는 방식을 사용할 수 있다. Inital Probability Distribution과 Accepting States로 구성된다. Initial Probability Distribution의 모두 원소의 합은 1이다.

 

- Initial Probability Distribution      $\pi_1,\pi_2,\cdot\cdot\cdot ,\pi_N$

- Accepting State                              $QA = \left\{q_x,q_y \cdot\cdot \cdot \right\}  , QA \subset Q$

궁금 & 공부

1. 통계 Markov Chain에 대해 찾아보고 이해하기

2. Markov Chain이 모호성 문제가 없는 이유

3. Markov Model의 예시를 찾아보고 실제 확률 구해보는 프로그램 짜보기