[NLP] 6. Hidden Markov Model

Intro

이전까지 특정 word를 기반으로 하여 modeling을 수행하는 방법을 알아보았다. 하지만, 우리가 특정 word의 sequence를 통해서 각 word에 대한 classification을 한 번에 하고 싶은 경우는 어떻게 할까?(예를 들어, 각 단어의 품사를 지정하는 일) 일반적으로 각 단어가 특정 해당 class일 확률로 구하는 방법이 일반적일 것이다. 하지만, 문맥을 고려하여 확률을 구할 방법은 없을까? 그 방법은 바로 bigram을 이용하면 될 것이다. 그렇다면, 사실 우리가 사용하는 문맥이 단어 자체보다는 이전 class가 더 영향이 크다면, 이는 어떻게 해야할까? 이를 위한 해결책이 HMM이다. NLP 뿐만 아니라 여러 분야에서 넓게 사용되고 있지만, 여기서는 NLP 분야에서 어떻게 이를 사용하는지를 알아볼 것이다.

Markov Model

HMM을 알아보기전에 Markov Model을 알아야 한다. 이는 특정 sequence의 확률을 추정하는 방법이다. 즉 우리에게 state sequence ( $S= {s_{0}, s_{1}, ..., s_{N}}$ )가 주어질 때, 각 state에서 다음 state로 전이(이동)할 확률을 이용해서 state sequence의 확률을 구하는 방법이다.

nlp-markov-model-1

위의 그림이 state 각 각에서 다음 state로 전이할 확률을 나타낸 것이라면, 우리는 아래 그림과 같은 그림으로 sequence의 확률을 추론할 수 있는 것이다.

nlp-markov-model-2

따라서, 위의 그림에서 우리가 만약 $(s_{0}, s_{1}, s_{0}, s_{2})$ 으로 이루어진 sequence의 확률을 얻기를 바란다면, 그 확률은 아래와 같아진다.

\begin{align*} p(s_{0}, s_{1}, s_{0}, s_{2}) &= p(s_{0}| \text{start}) \times p(s_{1}|s_{0}) \times p(s_{0}|s_{1}) \times p(s_{2}|s_{1}) \times p(end|s_{2}) \\ &= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1 \end{align*}

이를 잘 살펴보니 bigram에서의 Likelihood를 구하는 공식과 똑같다. 즉, state 각 각을 word라고 본다면, Markov Model을 통해서 구할 수 있는 확률은 bigram의 Likelihood인 것이다.

그리고 이를 일반화하면 다음과 같다.

p(seq) = \prod_{i=1}^{N}p(seq_{i}|seq_{i-1})

그런데, 여기서 n이 3 이상인 ngram을 적용하고 싶다면, 각 state를 n-1 gram으로 설정하면 된다.

\begin{align*} X_{i} &= (Q_{i-1}, Q_{i}) \text{라면, }\\ P(X_{i} | X_{i-1}) &= P(Q_{i-1}, Q_{i} | Q_{i-2}, Q_{i-1}) \\ &= P(Q_{i} | Q_{i-2}, Q_{i-1}) \end{align*}

따라서, trigram을 적용해보면 아래와 같다.

\begin{align*} p((start, w_{0}), (w_{0}, w_{1}), (w_{1}, w_{0}), (w_{0}, w_{2})) &= p(w_{0}| \text{start}, \text{start}) \times p(w_{1}|\text{start}, w_{0}) \times p(w_{0}|w_{0}, w_{1}) \times p(w_{2}|w_{1}, w_{0}) \times p(end|w_{0}, w_{2}) \\ &= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1 \end{align*}

Hidden Markov Model

Hidden Markov Model은 state를 하나 더 만든다는 것이 핵심이다. 그래서, 우리가 직접 관측하는 state(observed state)와 직접적으로 관측하지 않지만, 관측한 state들에 의존하는 state(hidden state) 총 두 개의 state를 사용한다. 일반적인 예시가 text가 입력되었을 때 우리는 각 단어를 observed state라고 한다면, 각 단어의 품사를 hidden state라고 정의할 수 있다.

nlp-markov-model-3

위의 예시는 우리가 관측하는 데이터( $O$ )가 3개의 state를 가지고, 이 사건에 의존적인 또 다른 사건( $H$ )이 3개의 state를 가지는 경우이다. 이를 이용해서 기존 Markov Model보다 복잡한 작업을 수행하는 것이 가능하다.

Estimation

우리가 할 수 있는 작업은 크게 두 가지이다. 일반적인 Markov Model에서 할 수 있던 방식이 Trellis 방식이고, 또 다른 방식이 Viterbi 방식이다.

$(o_{0}, o_{1}, o_{0}, o_{2})$ 의 확률이 궁금할 때(Trellis)
$(o_{0}, o_{1}, o_{0}, o_{2})$ 가 주어질 때, 이것의 hidden state의 sequence 중 가장 유력한 sequence를 찾고자할 때(Viterbi)

위의 경우를 각각 풀어보도록 하자.

1. Trellis

우리가 직접 관측한 데이터의 sequence 자체의 확률이 궁금할 때이다. 따라서, 이에 대한 분석은 $(o_{0}, o_{1}, o_{0}, o_{2})$ 의 확률을 분석해보면서 설명하겠다.

\begin{align*} p(o_{0}, o_{1}, o_{0}, o_{2}) &= p(o_{0}, o_{1}, o_{0}) \times p(o_{2} | o_{0}, o_{1}, o_{0}) \\ &= p(o_{0}, o_{1}, o_{0}) \times \{p(o_{2} | h_{0})p(h_{0} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{1})p(h_{1} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{2})p(h_{2} | o_{0}, o_{1}, o_{0})\} \\ &= p(o_{0}, o_{1}, o_{0}) \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ &= p(o_{0}, o_{1}) \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ &= p(o_{0}) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ &= \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \end{align*}

이를 그림으로 표현하면 다음과 같다.

nlp-hidden-markov-model-1

또한, 이 식을 다음과 같이 축소가 가능하다.

\begin{align*} &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ =& \sum_{i=0}^{2}\alpha_{0 i} \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ =& \sum_{i=0}^{2}{\alpha_{1 i} } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ =& \sum_{i=0}^{2}{\alpha_{2 i} } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ =& \sum_{i=0}^{2}{\alpha_{3 i} } \end{align*}

우리는 이를 통해서, Markov Model의 특징을 하나 배울 수 있다. 그것은 바로 복잡한 sequence 전체의 확률에서 벗어나서 바로 직전의 확률값만 으로 다음 확률을 추론할 수 있다는 것이다. 이것이 Markov Chain이라는 이론이고, 이를 이용했기 때문에 Markov Model라고 부르는 것이기도 하다.

따라서, $\alpha$ 는 다음과 같이 정의할 수 있다.

\alpha(t, i) = \sum_{k=1}^{N}{\alpha(t-1, k)p(h_{i}|h_{k})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})

또, 이를 반대로 할 경우에는 다음과 같은 식을 얻을 수 있다.

nlp-hidden-markov-model-2

\begin{align*} &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\ =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{\beta_{3i}} \\ =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{\beta_{2i}} \\ =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{\beta_{1i}} \\ =& \sum_{i=0}^{2}{\beta_{0i}} \\ \end{align*}

\beta(t, i) = \sum_{k=1}^{N}{\beta(t+1, k)p(h_{k}|h_{i})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})

위의 처럼 앞에서부터 풀이를 해나가면서, $\alpha$ 의 합으로 끝이 나도록 푸는 방법을 forwarding 방식이라하고, 반대로 뒤에서부터 풀이하면서 $\beta$ 의 합으로 푸는 방법을 backwarding 방식이라고 한다. 사실 이 경우는 HMM이 굳이 아니더라도, MM으로 구할 수 있으니 굳이 필요는 없다. 하지만, 이것은 후에 modeling 단계에서 사용하기 때문에 알아두어야 한다.

2. Viterbi

이는 observed state의 sequence에 의해서 파생되는 가장 적절한 hidden sequence를 구하는 것이 목표이다. 이를 통해서 할 수 있는 대표적인 것이 sequence classification이다.

그렇다면 가장 유력한 hidden state의 sequence를 $\hat{s}^{(H)}$ 라고 하자. 이는 다음과 같다.

\begin{align*} \hat{s}^{(H)} &= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(H)}|s^{(O)}) \\ &= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(O)}|s^{(H)})P(s^{(H)}) \\ &= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\underbrace{P(o_{1}, o_{2}, ... , o_{N}|h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}}\underbrace{P(h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}} \\ &= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\prod_{i=1}^{N}p(o_{i}|h_{i})p(h_{i}|h_{i-1}) \end{align*}

nlp-hidden-markov-model-3

즉, 각 layer에서 단 하나의 가장 큰 output만 살아남을 수 있게 되는 것이다. 이 과정이 사실상 HMM의 본질적인 목표이다. sequence를 입력해서 sequence 형태의 classification 결과를 얻는 것이다.

Modeling

여태까지 HMM을 활용하여 sequential class를 어떻게 estimation 하는지 알아보았다. 그렇다면, 이제는 이를 위해서 사용되는 확률값을 구해야한다. 필요한 확률값은 다음과 같다.

$p(h_{i}|h_{i-1})$ : Hidden State에서 Hidden State로 넘어가기 위한 확률이다.
$p(o_{i}|h_{i})$ : 방출 확률로 특정 Hidden State에서 다음 State의 Observed State로 넘어가는 방법이다.
$\pi_{i}$

Trelli 방식에서 만들었던, $\alpha$ 와 $\beta$ 의 의미를 이해해야 한다. 각 각은 해당 과정까지 오면서 누적해온 확률이라고 할 수 있다. 그리고, 우리가 원하는 것은 입력으로 주어진 데이터를 잘 반영할 수 있는 확률 값을 찾는 것이다. 그렇다면, 우리가 생각할 수 있는 방법은 평균을 활용하는 것이다. 이를 구하는 과정을 먼저 살펴보자.

\begin{align*} c(i, j, k) &= h_{i}\text{에서 } h_{j}\text{로 넘어가고, } o_{k}\text{가 관측될 확률의 합} \\ &= \sum_{t=2}^{T} \alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j) \\ \\ c(i,j) &= h_{i}\text{에서 } h_{j}\text{로 넘어갈 확률의 합} \\ &= \sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\ \\ c(i) &= h_{i}\text{에서 상태를 변경하는 확률의 합} \\ &= \sum_{j=1}^{N}\sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\ \end{align*}

위의 값을 통해서 우리는 우리가 가지고 있던 확률을 업데이트할 수 있다.

\begin{align*} p(h_{j}|h_{i}) &= {c(i,j)\over c(i)} \\ p(o_{k}|h_{i}) &= {c(i,j,k)\over c(i,j)} \end{align*}

즉, 우리는 다음 과정을 수행하여 Modeling을 수행할 수 있는 것이다.

초기값 ( $p(h_{i}|h_{i-1})$ , $p(o_{i}|h_{i})$ , $\pi_{i}$ )을 초기화 한다.
Trelli를 통해서 $\alpha$ , $\beta$ 를 계산한다.
$p(h_{i}|h_{i-1})$ , $p(o_{i}|h_{i})$ 를 업데이트 한다.
( $pi_{i}$ 같은 경우는 발생 빈도로 업데이트 한다.)
임계치에 도달할 때까지 2,3번을 반복한다.

이 과정을 대게 10번 정도만 하면 수렴하게 되고, 이를 확률로 사용하는 것이다.

Reference

Tumbnail : Photo by David Ballew on Unsplash