단어와 같은 이산적인 심볼로 구성된 시퀀스 데이터의 패턴을 통계적으로 모델링할 때 Hidden Markov 모델(HMM; 은닉 마르코프 모델)을 사용할 수 있습니다. 품사(Part Of Speech; POS)를 태깅하는 문제와 함께 HMM 모델이 어떻게 설계되었는지 파악해봅시다. 베이지안(bayesian), 마르코프(markov)와 독립(independence) 등의 수학적 특징이 어떻게 HMM 모델에 내포되어있는지를 단계별로 알아봅니다.


1. HMM이란?

먼저, HMM 모델의 정의와 용어, 그리고 이를 나타내는 그림을 보면서 가볍게 훑어보자.

정의(definition)

  • X_n Y_n 는 discrete time의 stochastic 프로세스이다. (단, N \ge 1 )
  • (X_n, Y_n ) 쌍은 다음 조건으로 hidden markov 모델이 된다.
    • X_n 는 markov 프로세스이며 (hidden이라) 곧바로 관측되지 않는다.
    • 모든 n\geq 1 와, x_1,\ldots, x_n , (measurable 공간에 있는) A 에 대해서
      • \mathbf{P}\bigl(Y_n \in A\ \bigl|\ X_1=x_1, \ldots,X_n=x_n\bigr) \\     = \mathbf{P}\bigl(Y_n \in A\ \bigl|\ X_n=x_n\bigr)

용어(terminology)

  • X_n : hidden state 또는 state
  • Y_n : observation
  • \mathbf{P}\bigl( X_n=x_n\bigr|\ X_n=x_n\bigr) : transition 확률1
  • \mathbf{P}\bigl(Y_n \in A\ \bigl|\ X_n=x_n\bigr) : emission 또는 output 확률

다이어그램(diagram)

Markov 모델은 markov 가정이 내포된 모델로, 바로 이전에만 영향을 받는 시퀀스 데이터의 확률을 계산해준다. Hidden Markov 모델은 관측 여부에 따른 두 가지 시퀀스를 모델링해주며, 기존의 Markov 프로세스가 hidden 프로세스에 자리잡게 되고, observe 프로세스는 단순히 각 step의 hidden state에 의존하는 형태를 가진다.

간단히 보면 시퀀스-to-시퀀스 매핑을 하기 위한 모델이다2. 현실적인 통계로 확률 추정을 위해 많은 부분들을 근사화(approximate)를 했다고 볼 수 있다. True 확률을 모델링하려면 위의 화살표가 모두 fully-connected 되어야 한다.

이 글에선 HMM 모델이 어떻게 위와 같이 정의되었는지를 단계별로 품사태깅 문제와 함께 알아보고자 한다. 품사태깅 문제에서 x_n은 태그를, y_n은 단어를 뜻한다.

여기서 다룰 HMM 버전

HMM의 variation은 다양하다. 우리는 품사태깅을 위해 다음 버전의 HMM을 사용한다고 이해하면 된다. 우리는 hidden state와 observation state가 모두 discrete한 경우를 다룬다. 이는 심볼릭 기반의 품사태깅 문제와 직결된다. 음성인식의 경우는 hidden은 discrete하고, observation은 continuous하다. 두 state 모두 continuous한 문제도 있다.

Rabiner (1989)의 HMM 튜토리얼에 따르면 모든 HMM을 다음과 같이 세 가지 문제로 구분될 수 있다고 한다.

  • (1) Likelihood
  • (2) Decoding (or Inference)
  • (3) Learning

우리가 푸는 품사태깅 문제는 세종 코퍼스로부터 transition과 omission 확률들을 count 기반으로 추정할 수 있기에 (2) 문제만 풀면된다. (2)번 decoding 문제를 viterbi 알고리즘으로 푸는 내용은 Viterbi 알고리즘 (feat. 품사태깅) 을 참고하길 바란다. 이 글은 HMM 모델이 어떻게 시퀀스 확률을 표현할지를 나타내는 (1) Likelihood 과정이라 볼 수 있다.


2. 품사태깅 문제

품사태깅은 단어 시퀀스를 일대일 대응으로 태그 시퀀스에 매핑하는 문제와 같다. 단순히 규칙 기반의 매핑 모델을 만들기에는 문제가 복잡하다. 똑같은 형태라도 문맥에 따라 달라지는데 문맥의 경우의 수 매우 많아지기 때문이다. 데이터의 힘을 가지는 확률 모델이 필요하다.

문제를 단순히 생각하면, 태그(t_n )와 단어(w_n ) 사이의 모든 관계를 이해할 수 있는 결합 확률(joint probability) 함수가 필요하다. 이는 확률 모델의 가장 기본적인 형태이다.

\mathbf{P(t_1...t_n, w_1...w_n)}

여기서 단어 시퀀스 입력에 맞게 가장 적합한 태그 시퀀스를 출력하기 위해 argmax 를 씌워서 매핑 문제를 풀고 있음을 밝힌다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{P(t_1... t_n, w_1...w_n)}

결합 확률은 연쇄 규칙(chain rule)으로 다음과 같이 분해할 수 있다. 문제의 정의(단어를 보고 태그를 예측하는 일)를 기준으로 단어가 조건부로 내려오게 된다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{P(t_1...t_n | w_1...w_n)P(w_1...w_n)}

우리의 문제는 주어진 단어 시퀀스에서 가장 적합한 태그 시퀀스를 구하는 일이므로 확률의 오른쪽 항은 상수가 되어 신경쓰지 않아도 된다. 이를 삭제해서 문제를 더 심플하게 생각할 수 있다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{P(t_1...t_n | w_1...w_n)}

이제 위와 같은 조건부 확률을 구하면 된다. 직관적으로 봤을 때 매핑하는 문제의 형태 자체가 조건부 확률과 어울리는 것을 알 수 있다.

이를 추정하는 방법은 다양하다. 신경망, SVM 등 다른 확률 모델은 위의 조건부 확률을 모델 파라미터를 학습해서 구한다. 반면, HMM은 따로 모델 파라미터가 존재하지 않고 카운트 기반으로 단순하게 조건부 확률을 추정할 수 있다.

큰 문제는 경우의 수가 매우 많다는 것이다. 위의 조건부 확률의 샘플 스페이스는 단어 시퀀스인데 단어의 종류가 많을 뿐더러 이들의 시퀀스의 경우의 수는 무수히 많다. 예를 들어, 고유한 단어가 3만개가 있고 입력 시퀀스의 길이를 30개라 하자. 이들로 구성된 시퀀스의 모든 경우의 수는 다음과 같다.

(30000)^{30} = ...

제한된 학습 데이터((태그, 단어) 쌍의 집합)로는 모든 경우의 수를 확보할 수 없고, 각각의 경우도 충분히 유의미한 통계량을 가지기 힘들다. 스무딩으로 처리한다고 해도 그 케이스가 매우 많아 불안정한 확률을 추정할 수 밖에 없다. 만약, 학습 데이터가 무한하다면 가능할지도 모른다.


3. Naive 조건부 확률에서 HMM으로

여기서 공학적인 접근이 필요하다. 정확히 구하기 어렵다는 것을 인지하고 근사적으로 풀 수 있는 방법으로 우회해야 한다. 제한적인 데이터에서 조건부 확률을 최대한 유의미하게 추정할 수 있는 방법이 있을까?

첫 번째, 베이스 정리을 적용한다.

베이스 정리를 참고하면 위의 조건부 확률(사후 확률)을 아래와 같이 여러 개의 항으로 분해할 수 있다. 이는 마치 하나의 복잡한 문제를 독립된 여러 개의 부분 문제들로 나눠서 생각하는 것과 같다. 분해된 항 중에는 사전(Prior) 확률도 포함되는데 이를 통해 시퀀스 모델링(부분 문제)을 독립적으로 처리할 수 있다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{ \displaystyle \frac{P(w_1...w_n | t_1...t_n)P(t_1...t_n)}{P(w_1...w_n)} }

위는 태그 시퀀스 확률의 최대값을 구하는 문제이므로 단어에 대한 사전 확률은 삭제할 수 있다. 문제를 분해한 보람이 있다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{ P(w_1...w_n | t_1...t_n)P(t_1...t_n) }

베이스 정리의 큰 장점으로 조건부 확률의 샘플 스페이스가 바뀌는 것이다. 샘플 스페이스 크기에 따라 확률 분포 개수가 달라진다. 단어 시퀀스보다 태그 시퀀스의 경우의 수가 훨씬 적다. 또한, 다른 태그 시퀀스에 포함된 데이터를 모두 배제한 채 특정 하나의 태그 시퀀스에 속하는 데이터만 가지고 확률 분포를 추정한다.

참고로 베이스 정리를 적용한 이 형태를 Maximum a Posteriori (MAP) 추정이고, 적용 전의 형태는 Maximum Likelihood (ML) 추정이다. HMM에 hidden이라는 말이 붙은 이유도 베이스 정리를 적용했기 때문이다. 데이터는 단어밖에 관측되지 않지만 확률은 관측되지 않는 태그를 중심으로 측정된다. 첫 번째 그림의 화살표 방향에 주목하자.

두 번째, 마르코프(markov) 특징을 적용한다.

사전 확률을 근사화하기 위해서 마르코프 특징을 적용한다. (조건부 확률은 나중에 훨씬 더 강력한 근사화를 할 것이다. 우선 사전 확률을 먼저 보자.) 마르코프 특징을 적용 전과 후를 식으로 알아보자.

연쇄 규칙으로 사전 확률(P(t_1...t_n))을 다음과 같이 조건부 확률들로 분해할 수 있다. 각각의 조건부 확률은 랜덤 프로세스의 state에 직결된다.

\mathbf{ P(t_1, t_2, t_3, ... , t_n) }   \\   \mathbf{ = P(t_1|t_2, t_3, ... , t_n) }   \\   \mathbf{ \times P(t_2|t_3, ... , t_n) }     \\    \mathbf{ \times P(t_3| ... , t_n) }     \\ \mathbf{ \times ... }    \\ \mathbf{   \times P(t_n)  }

여기서 마르코프 특징을 적용한 사전 확률은 다음과 같다. 랜덤 프로세스 측면으로 이해할 때 어느 시점의 state에서 다음 state로 이동할 때 현재 state만 고려하겠다는 뜻이다.

\mathbf{ P(t_1, t_2, t_3, ... , t_n) } \\ \mathbf{ = P(t_1|t_2) } \\ \mathbf{ \times P(t_2|t_3) } \\ \mathbf{ \times P(t_3|t_4) } \\ \mathbf{ \times ... } \\ \mathbf{ \times P(t_n) }

마르코프 특징이 적용된 식을 정리하면 다음과 같다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \, \mathbf{ P(w_1...w_n | t_1...t_n)    \prod_{i=1}^{n}\mathbf{P(t_i | t_{i-1})} }

아직까지, 조건부 확률이 시퀀스의 결합 확률이므로 여전히 카운트 기반으로 확률을 추정하기 어렵다.

세 번째, 독립(independence) 특징을 적용한다.

과감하게 조건부 확률에서 시간 정보를 아예 무시하는 시간-독립 성질을 부여한다. 어떤 단어가 앞뒤에 있는 단어들에 전혀 영향을 받지 않는다는 뜻이다. 마치 bag-of-word 모델과 같다.

\widehat{t_1...t_n} = \underset{t_1...t_n}{arg\,max} \,    \prod_{i=1}^{n}   \mathbf{ P(w_i | t_i) \mathbf{P(t_i | t_{i-1})} }

본래의 문제는 시퀀스 데이터를 모델링하는 일인데 확률 추정을 위해서 시간 정보를 모두 제외한 것처럼 보인다. 그러나, 사전 확률에서 최소한의 시간 정보를 포함할 수 있도록 bi-gram으로 모델링했다.

나이브하게 정의한 조건부 확률을 시작으로 카운트 기반으로 확률을 추정할 수 있도록 다양한 수학 트릭을 적용하였다. 결과적으로 최종 확률 함수가 HMM이 된다.

참고로 HMM에 베이스 규칙을 적용했기에 확률 함수를 사후(posterior) 확률로도 생각할 수 있다. 사후 확률은 우도(likelihood)과 사전(prior) 확률로 구성된다.

한 가지 생각해볼 점은, 다른 통계 모델, 머신러닝, 딥러닝 모델은 모두 공통적으로 제한된 학습 데이터로 학습을 잘해서 일반화를 잘시킬 수 있는 방향으로 발전했다. HMM도 그 발전 과정 중의 하나의 모델일 뿐이다.


4. HMM 확률 추정

이제 실제로 품사태깅 문제에서 HMM의 확률을 어떻게 추정하는지 살펴보자. 여기서는 count 기반으로 확률을 단순하게 추정한다. 따라서 미리 단어와 단어-태그 쌍의 count를 구해놓아야 한다.

첫 항의 조건부 확률은 단어 우도 확률로 정의되어 다음과 같이 구한다.

\mathbf{  P(w_i | t_i) =  \displaystyle \frac{C(t_i, w_i)}{C(t_i)}   }

\mathbf{ P(\text{father} | \text{NNG}) = \displaystyle \frac{C(\text{NNG}, \text{father})}{C(\text{NNG})} = \displaystyle \frac{534}{2583720} = 0.02 }

두 번째 항의 사전 확률은 태그 전이(Tag Transition) 확률로 다음과 같이 구한다.

\mathbf{ P(t_i | t_{i-1}) = \displaystyle \frac{C(t_{i-1}, t_i)}{C(t_i)} }

\mathbf{ P(\text{JKS} | \text{NNG}) = \displaystyle \frac{C(\text{NNG}, \text{JKS})}{C(\text{NNG})} = \displaystyle \frac{342134}{2583720} = 13.24 }

시퀀스 길이만큼 위의 계산을 구하고 모두 곱하기만 하면 된다. 문제를 최대한 단순화했기에 위와 같은 카운트 통계를 구하는 일은 그리 어렵지 않다. 소량의 학습 데이터에서도 가능하다.


5. 마무리

은닉 마르코프 모델(HMM)을 정의, 용어, 수식부터 접하면 이해하기 어렵습니다. 위와 같이 HMM 함수 식의 내부 특성과 왜 이렇게 생성됐는지에 대한 흐름을 알면 쉽게 이해할 수 있습니다.


6. 각주

  1. initial 확률은 start state를 더미 state로 둬서 transition 확률에 포함시킬 수 있다.
  2. 세상의 많은 문제들이 이러한 형태를 가진다. 예를 들어, 단어들의 시퀀스를 보고 품사 시퀀스를 찾는 문제, 음성 시퀀스에 대응하는 단어 시퀀스를 찾는 문제 등이 있다.

7. 참고

  1. (Wikipedia) Hidden Markov model
  2. Speech and Language Processing. (3rd ed. draft) Appendix A: Hidden Markov Models
  3. Speech and Language Processing. (3rd ed. draft) Chapter 8: Part-of-Speech Tagging
  4. (Github) 한국어 형태소 분석기와 품사 태거 (Korean Mophological Analysis and Part Of Speech (POS) Tagger)