HMM & CRF

형태소 분석 및 품사 태깅을 위해 HMM(Hidden Markov Model) 및 CRF(Conditional Random Field)을 공부하고 있다. LOVIT님의 블로그를 통해 기본 개념을 간단히 이해한 후 실제 CRF를 다룬 논문 및 코드를 읽어보려고 한다.

Hidden Markov Model

다음 포스팅을 참고하였다.

• Hidden Markov Model (HMM) 기반 품사 판별기의 원리와 문제점

Hidden Markov Model(HMM)은 길이가 \(n\)인 sequence \(x_{1:n} = [x_1, \ldots, x_n]\)에 대하여 \(P(y_{1:n}~\vert~x_{1:n})\)가 가장 큰 \(y_{1:n}\)(state)을 찾는 문제를 해결하기 위해 등장한 모델이다. 품사 태깅 문제에서는 \(x_{1:n}\)은 토크나이징된 단어들, \(y_{1:n}\)는 각 단어별 품사라고 이해할 수 있다.

HMM은 이 문제를 해결하기 위해 \(P(y_{1:n}~\vert~x_{1:n})\)를 다음과 같이 Markov Property를 만족하는 식으로 정의한다.

\[P(y_{1:n}~\vert~x_{1:n}) = P(x_1~\vert~y_1) \times P(y_1~\vert~START) \times P(y_2~\vert~y_1) \times P(x_2~\vert~y_2) \times \cdots\]

이처럼 한 단계 전의 state 정보를 이용하는 모델을 first-order Markov Model 이라고 한다. state간의 변화 확률 \(P(y_{i+1}~\vert~y_i)\)을 transition probability, 각 state에서 우리가 관측 가능한 값이 발생할 확률 \(P(x_i~\vert~y_i)\)을 emission probability라고 한다.

이 모델을 실제 데이터를 통해 구현할 때는, 각 품사/단어별 등장 빈도를 세어 확률을 계산한 후, 주어진 문장의 다양한 품사 태깅 후보군들에 대하여 로그 확률을 계산하여 가장 유력한 후보를 선정한다.

다만 HMM은 \(y_i\)와 \(y_{i+1}\), 그리고 \(x_i\)와 \(y_i\) 사이의 관계를 토대로 모델링하므로, \(x_i\)와 \(x_{i+1}\) 간의 관계를 담아내지 못하는 단점이 있다.

이, 가, 빠졌어 -> [Noun, Josa, Verb]
남, 이, 빼줬어 -> [Noun, Josa, Verb]

여기서 이는 각각 다른 품사로 사용되었으나 이는 맥락 및 의미를 고려해야만 분석이 가능하다. 그러나 HMM은 앞뒤 맥락을 고려하지 못하므로 이를 담아낼 수 없으며, 이를 Unguaranteed Independency Problem 이라고 한다. 이 문제를 해결하기 위해 Maximum Entropy Markov Model(MEMM)이나 Conditional Random Field(CRF) 등의 모델이 등장한다.

• 추가 자료
  • Hidden Markov Model 기반 품사 판별기의 decode 함수

Conditional Random Field

다음 포스팅들을 참고하였다.

• From Softmax Regression to Conditional Random Field for Sequential Labeling
• Conditional Random Field (CRF) 기반 품사 판별기의 원리와 HMM 기반 품사 판별기와의 차이점

TBA

• 추가 자료
  • Conditional Random Field based Korean Space Correction
  • Conditional Random Field based Named Entity Recognition