Hidden Markov Model for Part-Of-Speech Tagging

 

1. Hidden Markov Model의 개요

• 히든 마르코프 모델은 관찰 가능한 데이터와 숨겨진 상태 간의 관계를 모델링하는 확률적 모델이다.
• 주로 시계열 데이터나 단어 시퀀스 데이터에 사용되며, 각각의 상태가 '현재 상태는 오직 이전 상태에만 의존하는 특성(마르코프 성질)'을 가지고 있다.

$P(q_{i}|q_{1}, ..., q_{i-1})=P(q_{i}|q_{i-1})$ (마르코프 성질)

 

 

2. Notation

 

1) $Q=q_0, q_1, q_2, ..., q_n, q_F$ (State set)

$q_0$는 시작 상태, $q_F$는 종료 상태, n은 상태의 개수

 

2) $A$ (Transition Probability Matrix)

$n \times n$. $a_{ij}$는 $i$번째 상태에서 $j$번째로 전이할 확률 ($\sum_{j=1}^{n}a_{ij}=1$)

 

3) $B=b_i(o_t)$ (Emission Probability Matrix)

$i$번째 상태에서 $t$번째 관측 데이터 $o_t$가 나타날 확률

 

4) $O = [o_1, o_2, ..., o_T] $ (Observation Sequence)

길이가 T인 관측 데이터 시퀀스

 

5) $\alpha_t(j)=P(o_1, o_2, ..., o_t, q_t = j|\lambda)$ (Forward Probability)

모델 $\lambda$가 주어졌을 때, $j$번째 상태와 $o_1, ..., o_t$가 나타날 확률

 

6) $\beta_t(j)=P(o_{t+1}, o_{t+2}, ..., o_T, q_t=j|\lambda)$ (Backword Probability)

모델 $\lambda$가 주어졌을 때, $j$번째 상태와 $o_{t+1}, ..., o_T$가 나타날 확률

 

7) $\pi$ (Initial Probability)

초기 상태가 $q_i$일 확률

 

 

3. 히든 마르코프 모델 (HMM, Hidden Markov Model)

 

히든 마르코프 모델은 $\lambda=(A, B)$ 2개의 파라미터($A$ : 전이 확률, $B$ : 방출 확률)로 구성되어 있다.

 

 

마르코프 성질에 의해 전체 상태 시퀀스 $Q = (q_1, q_2, ..., q_n)$의 확률 $P(Q)$은 초기 상태과 각 상태 전이 확률의 곱으로 전개될 수 있다.

 

$P(q_1, q_2, ..., q_n) = P(q_1)P(q_2|q_1)P(q_3|q_2)...P(q_n|q_{n-1})$

 

 

히든 마르코프 모델에 적용하면 아래의 두 가정에 의해 전체 상태 시퀀스 $P(Q | O)$는 다음과 같이 전개될 수 있다.

• '현재 상태는 오직 직전 상태만 의존한다',
• '관찰된 시퀀스는 각 시점의 히든 상태에만 의존한다'

 

$P(q_1, ..., q_n|o_i, ..., o_n)=P(o_i, ..., o_n|q_1, ..., q_n)P(q_1, ..., q_n)$

$=(\prod_{t=1}^{n}P(o_t|q_t))(P(q_1)\prod_{t=2}^{n}P(q_t|q_{t-1}))$

 

 

 

모델 파라미터 $\lambda$가 주어졌을 때, 은닉 상태 시퀀스 $Q$에 대해 관찰 시퀀스 $O$가 발생할 확률은 아래와 같다.

 

$P(O,Q|\lambda)=P(Q|\lambda)P(O|Q,\lambda)=P(q_1)(\prod_{n=2}^{n}P(q_t|q_{t-1}))(\prod_{t=1}^{n}P(o_t|q_t))$

($P(Q|\lambda)=P(q_1)\prod_{n=2}^{n}P(q_t|q_{t-1})$,  $P(O|Q,\lambda)=\prod_{t=1}^{n}P(o_t|q_t)$)

 

 

우도 함수는 관찰된 데이터 $O$에 대해 모델 파라미터 $\lambda$의 함수이므로, 모든 가능한 히든 상태 시퀀스 $Q$에 대한 결합 확률의 합으로 계산된다.

 

$L(\lambda)=P(O|\lambda)=\sum_{Q}P(O, Q|\lambda)$

 

 

베이즈 정리에 따라 구하고자하는 $P(Q|O, \lambda)$를 전개하면 아래와 같다.

 

$P(Q|O, \lambda)=\frac{P(Q,O,\lambda )}{P(O,\lambda )}=\frac{P(Q,O)|P(\lambda )}{P(O,\lambda )|P(\lambda )}=\frac{P(O,Q|\lambda)}{P(O|\lambda)}=\frac{P(O,Q|\lambda)}{\sum_{Q}P(O,Q|\lambda)}$

 

$P(Q|O, \lambda)$
- 주어진 관찰 시퀀스 $O$와 모델 파라미터 $\lambda$ 하에서 히든 상태 시퀀스 $Q$의 조건부 확률.
- 관찰 데이터가 주어졌을 때, 히든 상태 시퀀스 $Q$가 발생할 확률로 관찰 데이터에 히든 상태를 추정하는데 사용

$P(Q,O|\lambda)$
- 모델 파라미터 $\lambda$ 하에서 히든 상태 시퀀스 $Q$와 관찰 시퀀스 $O$가 함께 발생할 확률(결합 확률).
- 특정 상태 시퀀스와 관찰 시퀀스가 동시에 발생할 확률로, 모델 파라미터를 추정하는데 사용

 

 

예시를 들어보자

그림 1

 

그림 1은 날씨에 따른 아이스크림 소비량과 그 확률에 대한 예시를 도식화한 그림이다.

여기서 날씨는 은닉 상태(HOT, COLD), 아이스크림 소비량은 관측 데이터, $B_1$, $B_2$는 은닉 상태에 따른 관측 데이터의 조건부 확률이다.

 

 

위에서 전개한 식에 따르면,

관측 데이터 시퀀스 [3, 1, 3]이 주어졌을 때(아이스크림 소비량이 3개 -> 1개 -> 3개일 때), 은닉 상태 시퀀스가 [hot, hot cold]일 확률은 아래와 같이 계산할 수 있다.

 

P(3 1 3, hot hot cold) = P(hot|start) X P(hot|hot) X P(cold|hot) X P(3|hot) X P(1|hot) X P(3|cold)

= 0.8 X 0.6 X 0.3 X 0.4 X 0.2 X 0.1

 

 

 

그럼 주어진 관측 데이터 시퀀스에서 모든 가능한 은닉 상태 시퀀스의 결합 확률로 우도를 구할 수 있다.

 

P(3 1 3) = P(3 1 3, cold cold cold) + P(3 1 3, cold cold hot) + ... + P(3 1 3, hot hot hot)

 

여기서 관측 데이터 시퀀스의 길이는 3이므로, $n^T=2^3=8$가지의 경우에 수가 존재한다.

 

 

위 전개식과 예제를 통해서 우도를 도출하는 과정을 보았는데, 히든 마르코프 모델에서 최적의 $\lambda$를 구하는데에 해결해야하는 문제점이 3가지 존재한다.

각 문제점을 해결할 수 있는 알고리즘을 알아보자

 

4. Compute Likelihood -> Forward Algorithm

 

모델 파라미터 $\lambda$와 길이가 T인 관측 데이터 시퀀스가 주어졌을 때, 모든 가능한 은닉 상태 시퀀스의 결합 확률 $P(O|\lambda)$를 계산해야 한다.

 

 

 

$P(o_1, hot|\lambda) = P(hot|start) \times P(3|hot)$

$P(o_1, cold|\lambda) = P(cold|start) \times P(3|cold)$

 

$P(o_2, hot|\lambda) = P(hot|start) \times P(3|hot) \times P(hot|hot) \times P(1|hot)$

$ + P(cold|start) \times P(3|cold) \times P(hot|cold) \times P(1|hot)$

 

...

 

 

 

 

위와 같이 모든 관측 포인트마다 계산을 하게 되면 중복 연산은 물론 은닉 상태와 관측 데이터 시퀀스의 길이가 길어질수록 연산량이 매우 증가한다는 문제점이 있다.($n^T$) 

 

 

 

Forward Algorithm의 핵심은 중복되는 연산을 메모라이징(Dynamic Programming)시켜 연산량을 줄이는 것이다.

Forward Algorithm을 위의 각 관측 포인트에서 다시 표현하면 아래와 같다.

 

 

 

$\alpha_1(hot) = P(hot|start) \times P(3|hot)$

$\alpha_2(cold) = P(cold|start) \times P(3|cold)$

 

$\alpha_2(hot) = \alpha_1(hot) \times P(hot|hot) \times P(1|hot) + \alpha_1(cold) \times P(hot|cold) \times P(1|hot)$

...

 

 

$j$번째 상태에서 $o_1, o_2, ..., o_t$가 나타날 forward probability $\alpha$는 다음과 같이 정의된다.

 

$\alpha_t(j)=\sum_{i=1}^{n}\alpha_{t-1}(i) \times a_{ij} \times b_{j}(o_t)$

 

 

 

따라서, Forward Probability를 관측 데이터 시퀀스의 끝까지 계산하면 우도와 동치가 된다.

 

$P(O|\lambda) = P(o_1, o_2, ..., o_T|\lambda) = P(o_1, o_2, ..., o_T,q_t=q_F|\lambda) = \alpha_T(q_F)$

 

 

 

5. Decoding -> Viterbi Algorithm

두번째는 문제점은 모델 파라미터 $\lambda$와 관측 데이터 시퀀스 $O$가 주어졌을 때, 어떻게 가장 확률이 높은 은닉 상태 시퀀스 Q를 찾는 것(Decoding)이다. 히든 마르코프 모델에서 디코딩 과정은 Viterbi Algorithm이 사용된다.

 

Viterbi Algorithm은 가장 가능성 있는 은닉 상태 시퀀스를 찾기 위한 Dynamic Programming 기반의 알고리즘으로 작동 방식을 아래와 같다.

a. 초기화 (initialization)
$v_0(s) = P(s)P(o_0|s)$

b. 재귀 (recursive)
 $v_t(s) = max_{s'}[v_{t-1}(s')P(s|s')]P(o_t|s)$

c. 역추적 (backtracking)
$s_{T}^{*}=argmax_s[v_T(s)]$

 

 

위에서 정의한 notation에 따라  $v_t$ Viterbi Probability를 정리하면 

 

$v_t(j) = max_{i}^{n}[v_{t-1}(i) \times a_{ij} \times b_{j}(o_t)]$

 

$v_t(j)$는 $t$번째 관측 시점에서 $j$번째 히든 상태의 Viterbi Probablity이다.

 

 

 

$v_1(hot) = max[P(hot|start) \times P(3|hot)] = P(hot|start) \times P(3|hot)$

$v_1(cold) = max[P(cold|start) \times P(3|cold)] = P(cold|start) \times P(3|cold)$

 

$v_2(hot) = max[v_1(hot) \times P(hot|hot) \times P(1|hot), v_1(cold) \times P(hot|cold) \times P(1|hot)]$

 

Viterbi Probabilty은 최적의 경로 추적(backtracking)에 사용되고, t번째 시점의 j번째 상태의 backtrace는 다음과 같이 정리할 수 있다.

 

$b_t(j) = arg max_{i=1}^{n}[v_{t-1}(i) \times a_{ij} \times b_{j}(o_t)]$

 

6. Training -> EM Algorithm

 

세번째 문제점은 히든 마르코프 모델은 은닉 상태를 가지기 때문에 관측 데이터로만 모델의 전체 상태를 추정하고, 파라미터를 최적화하기 어렵다. 이는 Buam-Welch Algorithm(EM Algorithm)으로 해결할 수 있다.

 

 

1) Forward Probability와 Backword Probability

앞에서 likelyhood를 계산하기위해 Forward Probability를 계산했다.

그림 2. Forward Probability

 

$\alpha_t(j) = \sum_{i=1}^{n} \alpha_{t-1}(i) \times a_{ij} \times b_j(o_t)$

 

 

 

전방 확률(Forward Probability)과 마찬가지로 후방 확률(Backward Probability)도 계산할 수 있다.

그림 3. Backward Probability

 

 

$\beta_t(i) = \sum_{j=1}^{n} a_{ij} \times b_j(o_{t+1}) \times \beta_{t+1}(j)$

 

 

특정 시점 t에서 j번째 상태를 지나는 경로의 확률 합은 전방 확률과 후방 확률의 곱 $P(q_t = j, O|\lambda) = \alpha_t(j) \times \beta_t(j)$ 와 같고, 이를 도식화하면 위 그림과 같다.

 

 

 

특정 시점 t에서 Forward Probability와 Backward Probability를 곱한 값을 모든 상태에 대해 더해준 값은 우도와 동치과 되며, 관측 데이터 시퀀스의 맨끝에서 처음으로의 Backward Probability 또한 동치이다.

 

 

 

$ P(O|\lambda) = P(o_1, o_2, \ldots, o_T | \lambda) = P(o_1, o_2, \ldots, o_T, q_t = q_{0} | \lambda) = \beta_0(q_0) = \sum_{s=1}^{n} \alpha_t(s) \times \beta_t(s)$

 

 

 

2) 방출 확률 업데이트와 $\gamma$

$t$시점에 $j$번째 상태일 확률 $\gamma_{t}(j)$는 베이즈 정리와 Forward Probability, Backward Probaility로 다음과 같이 정의할 수 있다.

 

$\gamma_t(j) = P(q_t = j | O, \lambda) = \frac{P(q_t = j, O | \lambda)}{P(O | \lambda)} = \frac{\alpha_t(j) \beta_t(j)}{\sum_{s=1}^{N} \alpha_t(s) \beta_t(s)}$

 

 

그럼 $\gamma$로 j번째 상태에서 관측 데이터 $v_k$가 나타날 확률 $\hat{b}_j(v_k)$은 아래와 같다.

 

$\hat{b}_j(v_k) = \frac{ \sum_{t=1, s.t.o_t=v_k}^{T}\gamma (j)}{\sum_{t=1}^{T} \gamma_t(j)}$

 

$\sum_{t=1}^{T} \gamma_t(j)$는 $j$번째 상태가 나타날 확률이고,

$ \sum_{t=1, s.t.o_t=v_k}^{T}\gamma (j)$는 $j$번째 상태이면서, $o_t$가 $v_k$일 확률이다.

 

($\sum$이 적용된 이유는 방출 확률은 특정 시점 $t$와 무관한 값이기 때문. 어떤 시점이든 $\gamma$가 존재하기 때문에 T개의 관측 데이터 시퀀스 전체에 걸쳐 모든 시점에 대해 $\gamma$를 더해준다.)

 

 

 

3) 전이 확률 업데이트와 $\xi$

$t$ 시점에 i번째 상태이고, $t+1$시점에 $j$번째 상태일 확률 $xi$는 베이즈 정리에 의해 다음과 같이 정의된다.

 

$\xi_t(i,j) = P(q_t = i, q_{t+1} = j | O, \lambda) = \frac{P(q_t = i, q_{t+1} = j, O | \lambda)}{P(O|\lambda)}$

 

$\xi$를 전방확률과 후방확률로 전개하기 위해선 한가지 처리가 더 필요하다.

 

아래의 그림을 보자

 

 

$\alpha_t(i)$는 i번째 상태 좌측의 모든 path에 해당하는 확률, $\beta_{t+1}(j)$는 j번째 상태 우측의 모든 path에 해당하는 확률의 합이다. 근데 $\alpha_t(i)$, \beta_{t+1}(j)$의 곱으로는 i 상태에서 j 상태로의 path를 이어줄 수 없다.

 

 

따라서 $t$ 시점에 상태 $i$에서 $t+1$시점에 상태 $j$로 이어주기 위해

$i$번째 상태에서 $j$번째 상태로 전이할 확률 $\alpha_{ij}$와 $o_{t+1}$를 관측할 방출 확률 $b_j(o_{t+1})$를 곱해주어야한다.

 

 

$i$번째 상태에서 $j$번째 상태로 path와 전방 확률, 후방 확률을 이용해 다시 $\xi$를 전개해보자

 

$\xi_{t}(i, j) = \frac{P(q_t = i, q_{t+1} = j, O | \lambda)}{P(O|\lambda)}=\frac{\alpha_t \times a_{ij} \times b_j(o_{t+1}) \times \beta_{t+1}(j)}{\sum_{s=1}^{n}\alpha_{t}(s) \times \beta_t(s)}$

 

 

$\xi$로 $i$번째 상태에서 $j$번째 상태로 전이할 확률 \hat{a}_{ij}를 정의하면 아래와 같다.

 

$\hat{a}_{ij}=\frac{\sum_{t=1}^{T-1}\xi_{t}(i,j)}{\sum_{t=1}^{T-1}\sum_{k=1}^{N}\xi_{t}(i, k)}$

 

$\sum_{t=1}^{T-1}\sum_{k=1}^{N}\xi_{t}(i, k)$는 $i$번째 상태에서 모든 path들의 확률을 더한 값(아래 그림의 붉은 점선)이고,

$\sum_{t=1}^{T-1}\xi_{t}(i,j)$는 $i$번째 상태에서 $j$번째 상태로 전이할 확률(아래 그림의 검은 점선)이다.

 

($\sum_{t=1}^{T-1}$이 적용된 이유는 전이확률을 시점 $t$와는 무관하기 때문. 어떤 시점이든 $i$번째 상태에서 다른 상태로 전이할 확률 $\xi_{t}$가 존재하기 때문이다. 단, 시퀀스 마지막 $T$번째 시점에서 종료 상태로 전이할 확률은 1이므로 $T-1$까지만 더해준다)

 

 

 

4) Training

 

a. 초기화

• 모델 파라미터 $\lambda(A, B)$를 초기화한다.

 

b. E-step (Expectation Step)

• Forward-Backworad 알고리즘으로 Probability $\alpha$와 Backward Probability $\beta$를 계산한다.
• $\alpha$, $\beta$로 $\gamma$와 $\xi$를 업데이트 한다.

 

c. M-step (Maximization step)

• $\gamma$, $\xi$로 모델 파라미터$\lambda(A, B)$를 업데이트 한다