최대엔트로피마코프모델(Maximum Entropy Markov Models)
04 Nov 2017 | MEMMs
이번 글에선 최대엔트로피마코프모델(Maximum Entropy Markov Models, MEMM)을 다루어 보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의와 Speech and Language Processing(2nd edition) 등을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
MEMM은 이름 그대로 최대엔트로피모델과 은닉마코프모델(Hidden Markov Models)을 결합한 모델입니다.
은닉마코프모델
은닉마코프모델은 각 상태(state)가 이전 상태에만 의존하는 마코프체인(Markov Chain)을 따르되 은닉(hidden)되어 있다고 가정합니다. 은닉마코프모델에서는 관측치를 토대로, 관측치 뒤에 은닉되어 있는 상태를 추정합니다. 아래 그림은 단어가 관측치이고, 품사 정보가 은닉 상태인 은닉마코프모델을 도식화한 것입니다.
은닉마코프모델은 본질적으로 시퀀스 분류기입니다. 직전 상태에서 현재 상태로의 전이확률(transition probability)과 현재 상태에서 관측치를 관측할 확률인 방출확률(emission probability)를 토대로, 관측된 단어 시퀀스 $W$가 주어졌을 때 가장 확률이 높은 은닉 상태(품사)의 시퀀스 $T$를 찾기 때문입니다.
이를 식으로 나타내면 다음과 같습니다. $P(T)$는 전이확률, $P(W$|$T)$는 방출확률을 가리킵니다.
\[\begin{align*}
\hat { T } =&arg\max _{ T }{ P\left( T|W \right) } \\ =&arg\max _{ T }{ P\left( W|T \right) \cdot P(T) } \\ =&arg\max _{ T }{ \prod _{ i }^{ }{ P\left( { W }_{ i }|{ T }_{ i } \right) } \prod _{ i }^{ }{ P({ T }_{ i }|{ T }_{ i-1 }) } }
\end{align*}\]
그러나 은닉마코프모델은 시퀀스 추정에 전이확률과 방출확률 정보만을 활용하므로, 문맥의 다양한 자질(feature)들을 활용할 수 없다는 단점이 있습니다.
최대엔트로피모델
이번엔 최대엔트로피모델을 살펴보겠습니다. 자연언어처리 분야에서는 다항로지스틱 회귀(multinominal logistic regression)를 최대엔트로피모델이라 부릅니다. 단어 $w$가 주어졌을 때 범주(예 : 품사) $t$가 나타날 확률은 다음과 같습니다.
\[P(t|w)=\frac { exp\left\{ { \overrightarrow { { w }_{ t } } }^{ T }\overrightarrow { f } \left( w \right) \right\} }{ \sum _{ t'\in T }^{ }{ exp\left\{ { \overrightarrow { { w }_{ t' } } }^{ T }\overrightarrow { f } \left( w \right) \right\} } }\]
위 식에서 벡터 $f$는 단어 $w$에 해당하는 자질(feature)들의 모음입니다. 예컨대 자질 벡터의 첫번째 요소는 ‘직전 단어가 명사이면 1, 그렇지 않으면 0’, 두번째 요소는 ‘현재 단어가 동사이면 1, 아니면 0’… 이런 식으로 $f$의 요소값들을 구성합니다. 범주 $t$에 대응하는 가중치 벡터 $w_t$는 다항로지스틱 모델의 회귀계수를 가리킵니다.
최대엔트로피모델은 자질벡터 $f$를 매우 유연하게 설정할 수 있어 연구자의 언어학적 배경 지식을 모델링에 적극 활용할 수 있다는 장점이 있습니다. 그러나 최대엔트로피모델은 은닉마코프모델처럼 시퀀스 분류기(sequence classifier)가 아니라는 단점이 있습니다. 시퀀스가 아닌 단일 관측치(single observation)에 대해서만 예측이 가능하다는 것이지요.
최대엔트로피마코프모델
MEMM은 최대엔트로피모델의 유연한 자질 활용 능력을 바탕으로 시퀀스 분류를 가능하게 하는 모델입니다. MEMM을 도식화한 그림은 아래와 같습니다. 그림에 나와 있는 것처럼 은닉 상태는 마코프체인을 따른다고 가정하되, 시퀀스 예측에 첫글자, 분사형 등 다양한 자질을 활용하는 방식입니다.
MEMM이 최적 상태 시퀀스를 예측하는 걸 수식으로 나타내면 다음과 같습니다. $i$번째 단어의 자질(feature)과 직전 은닉상태(품사)를 바탕으로 가장 확률이 높은 현재 은닉상태(품사)를 반환하는 것입니다.
\[\begin{align*}
\hat { T } =&arg\max _{ T }{ P\left( T|W \right) } \\ =&arg\max _{ T }{ \prod _{ i }^{ }{ P\left( { T }_{ i }|{ W }_{ i },{ T }_{ i-1 } \right) } }
\end{align*}\]
이 때 $P(T_i$|$W_i,T_{i-1})$는 최대엔트로피 모델을 가리킵니다. 이를 식으로 적으면 다음과 같습니다. 아래 식에서 $f$는 $i$번째 단어 $w_i$와 $i-1$번째 은닉상태(품사)에 해당하는 자질벡터입니다.
\[P({ T }_{ i }|{ W }_{ i },{ T }_{ i-1 })=\frac { exp\left\{ { \overrightarrow { { w }_{ t } } }^{ T }\overrightarrow { f } \left( { W }_{ i },{ T }_{ i-1 } \right) \right\} }{ \sum _{ t'\in T }^{ }{ exp\left\{ { \overrightarrow { { w }_{ t' } } }^{ T }\overrightarrow { f } \left( { W }_{ i },{ T }_{ i-1 } \right) \right\} } }\]
비터비 알고리즘
MEMM에서 최적 상태열 추정은 은닉마코프모델과 마찬가지로 비터비 알고리즘(Viterbi Algorithm)을 활용합니다. 이를 도식화한 그림은 다음과 같습니다.
MEMM의 파라메터 추정
MEMM의 학습은 최대엔트로피모델의 가중치 벡터를 추정하는 과정입니다. 다양한 방식이 있지만 iterative scaling algorithm를 많이 쓴다고 합니다. 이와 관련해서는 이곳을 참고하시면 좋을 것 같습니다.
이번 글에선 최대엔트로피마코프모델(Maximum Entropy Markov Models, MEMM)을 다루어 보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의와 Speech and Language Processing(2nd edition) 등을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
MEMM은 이름 그대로 최대엔트로피모델과 은닉마코프모델(Hidden Markov Models)을 결합한 모델입니다.
은닉마코프모델
은닉마코프모델은 각 상태(state)가 이전 상태에만 의존하는 마코프체인(Markov Chain)을 따르되 은닉(hidden)되어 있다고 가정합니다. 은닉마코프모델에서는 관측치를 토대로, 관측치 뒤에 은닉되어 있는 상태를 추정합니다. 아래 그림은 단어가 관측치이고, 품사 정보가 은닉 상태인 은닉마코프모델을 도식화한 것입니다.
은닉마코프모델은 본질적으로 시퀀스 분류기입니다. 직전 상태에서 현재 상태로의 전이확률(transition probability)과 현재 상태에서 관측치를 관측할 확률인 방출확률(emission probability)를 토대로, 관측된 단어 시퀀스 $W$가 주어졌을 때 가장 확률이 높은 은닉 상태(품사)의 시퀀스 $T$를 찾기 때문입니다.
이를 식으로 나타내면 다음과 같습니다. $P(T)$는 전이확률, $P(W$|$T)$는 방출확률을 가리킵니다.
\[\begin{align*} \hat { T } =&arg\max _{ T }{ P\left( T|W \right) } \\ =&arg\max _{ T }{ P\left( W|T \right) \cdot P(T) } \\ =&arg\max _{ T }{ \prod _{ i }^{ }{ P\left( { W }_{ i }|{ T }_{ i } \right) } \prod _{ i }^{ }{ P({ T }_{ i }|{ T }_{ i-1 }) } } \end{align*}\]그러나 은닉마코프모델은 시퀀스 추정에 전이확률과 방출확률 정보만을 활용하므로, 문맥의 다양한 자질(feature)들을 활용할 수 없다는 단점이 있습니다.
최대엔트로피모델
이번엔 최대엔트로피모델을 살펴보겠습니다. 자연언어처리 분야에서는 다항로지스틱 회귀(multinominal logistic regression)를 최대엔트로피모델이라 부릅니다. 단어 $w$가 주어졌을 때 범주(예 : 품사) $t$가 나타날 확률은 다음과 같습니다.
\[P(t|w)=\frac { exp\left\{ { \overrightarrow { { w }_{ t } } }^{ T }\overrightarrow { f } \left( w \right) \right\} }{ \sum _{ t'\in T }^{ }{ exp\left\{ { \overrightarrow { { w }_{ t' } } }^{ T }\overrightarrow { f } \left( w \right) \right\} } }\]위 식에서 벡터 $f$는 단어 $w$에 해당하는 자질(feature)들의 모음입니다. 예컨대 자질 벡터의 첫번째 요소는 ‘직전 단어가 명사이면 1, 그렇지 않으면 0’, 두번째 요소는 ‘현재 단어가 동사이면 1, 아니면 0’… 이런 식으로 $f$의 요소값들을 구성합니다. 범주 $t$에 대응하는 가중치 벡터 $w_t$는 다항로지스틱 모델의 회귀계수를 가리킵니다.
최대엔트로피모델은 자질벡터 $f$를 매우 유연하게 설정할 수 있어 연구자의 언어학적 배경 지식을 모델링에 적극 활용할 수 있다는 장점이 있습니다. 그러나 최대엔트로피모델은 은닉마코프모델처럼 시퀀스 분류기(sequence classifier)가 아니라는 단점이 있습니다. 시퀀스가 아닌 단일 관측치(single observation)에 대해서만 예측이 가능하다는 것이지요.
최대엔트로피마코프모델
MEMM은 최대엔트로피모델의 유연한 자질 활용 능력을 바탕으로 시퀀스 분류를 가능하게 하는 모델입니다. MEMM을 도식화한 그림은 아래와 같습니다. 그림에 나와 있는 것처럼 은닉 상태는 마코프체인을 따른다고 가정하되, 시퀀스 예측에 첫글자, 분사형 등 다양한 자질을 활용하는 방식입니다.
MEMM이 최적 상태 시퀀스를 예측하는 걸 수식으로 나타내면 다음과 같습니다. $i$번째 단어의 자질(feature)과 직전 은닉상태(품사)를 바탕으로 가장 확률이 높은 현재 은닉상태(품사)를 반환하는 것입니다.
\[\begin{align*} \hat { T } =&arg\max _{ T }{ P\left( T|W \right) } \\ =&arg\max _{ T }{ \prod _{ i }^{ }{ P\left( { T }_{ i }|{ W }_{ i },{ T }_{ i-1 } \right) } } \end{align*}\]이 때 $P(T_i$|$W_i,T_{i-1})$는 최대엔트로피 모델을 가리킵니다. 이를 식으로 적으면 다음과 같습니다. 아래 식에서 $f$는 $i$번째 단어 $w_i$와 $i-1$번째 은닉상태(품사)에 해당하는 자질벡터입니다.
\[P({ T }_{ i }|{ W }_{ i },{ T }_{ i-1 })=\frac { exp\left\{ { \overrightarrow { { w }_{ t } } }^{ T }\overrightarrow { f } \left( { W }_{ i },{ T }_{ i-1 } \right) \right\} }{ \sum _{ t'\in T }^{ }{ exp\left\{ { \overrightarrow { { w }_{ t' } } }^{ T }\overrightarrow { f } \left( { W }_{ i },{ T }_{ i-1 } \right) \right\} } }\]비터비 알고리즘
MEMM에서 최적 상태열 추정은 은닉마코프모델과 마찬가지로 비터비 알고리즘(Viterbi Algorithm)을 활용합니다. 이를 도식화한 그림은 다음과 같습니다.
MEMM의 파라메터 추정
MEMM의 학습은 최대엔트로피모델의 가중치 벡터를 추정하는 과정입니다. 다양한 방식이 있지만 iterative scaling algorithm를 많이 쓴다고 합니다. 이와 관련해서는 이곳을 참고하시면 좋을 것 같습니다.
Comments