확률 행렬과 Markov Chain

확률 행렬과 Markov Chain

1. Markov Model

확률 행렬은 행렬의 성분이 확률로 이루어진 행렬을 의미한다. 

Markov chain은 한 state에서 다른 state로 변할 확률이 과거 보다 '현재'의 상태에만 의존하는 모델을 의미한다. Markov chain은 확률행렬을 사용해서 state가 변하는 transition matrix를 만들 수 있다. 

, state n에서 state m으로 이동할 확률

Transition matrix의 각 row의 합은 1이다. 이는 확률의 합을 의미한다.

만약 초기 state를 S1이라고 정의하고 t시간 이후의 state를 St라고 정의하면, 다음과 같이 계산이 된다.

위와 같은 식은 '마르코프 가정'에 의한다. '마르코프 가정'이란 현재 state에서 다음 state로 변할 확률은 현재의 state만 의존한다고 가정한다. 만약 과거의 1 state만 고려하는 경우, 1차 마르코프 가정, 2 states를 고려하는 경우, 2차 마르코프 가정이 된다.

1차 마르코프 가정은 다음과 같은 조건을 만족한다.

어떤 state에 대한 확률은 이전 state들이 발생했을 때의 조건부 확률이다. 하지만, 과거의 state들이 매우 긴 경우에, 고려해야할 데이터의 수가 많아진다. 마르코프 가정은 시간 n에서 어떤 사건이 관측될 호가률은 시간 n-1 에서의 관측 결과인 q_{n-1}에만 의존한다는 것이다. 이러한 가정이 성립하는 system을 markov model이라고 정의한다. Markov chain은 이러한 가정이 성립하는 system의 출력 {q_i}로 정의된다.

Markov 가정을 사용해서 어떤 열이 관측될 확률은 과거와 현재의 관측 결과의 joint probability이다.

위의 식은 밑의 과정을 통해 구해진다.

Chain-rule

1차 Markov 가정

Markov Model은 다음과 같은 process에 의하여 설명될 수 있는 경우에 한정된다.

1. 주어진 시점에서 n개의 가능한 상태를 가진 system

2. 일정한 간격의 지속 시간을 갖고 새로운 state로 transition이 일어날 수 있는 system

3. state간의 transition이 확률로 표현될 수 있는 system

2. Hidden Markov Model

관측이 불가능한 process를 관측이 가능한 다른 process로 추정하는 이중 확률처리 모델이다. 우리이 상황은 process들을 관측할 수 없는 경우가 매우 많다. 오히려 이 process에서 파생되는 관측치를 통해 판단을 내린다. 그래서 hidden이라고 표현한다.

관측이 불가능한 열을 Q, 관측이 가능한 열을 O라고 정의할 때, 조건부 확률을 이용하여 관측이 불가능한 열에 관련된 확률을 계산할 수 있다.

베이즈 정리를 통해서,

Q 열의 확률과 O 열의 확률은 모든 i에 대해서 독립이므로, 식을 간략하게 나타낼 수 있다. 또한 확률에 비례하는 likelihood를 사용하면, 간략화가 된다.