최대 엔트로피 마르코프 모델

통계에서 최대 엔트로피 마르코프 모델(MEMM), 즉 조건부 마르코프 모델(CMM)은 숨겨진 마르코프 모델(HM)과 최대 엔트로피(MaxEnt) 모델의 특징을 결합한 시퀀스 라벨링 그래픽 모델이다.MEMM은 학습할 미지의 값이 서로 조건적으로 독립되어 있지 않고 마르코프 체인에 연결되어 있다고 가정하여 표준 최대 엔트로피 분류자를 확장하는 차별적 모델이다.MEMM은 자연 언어 처리, 특히 음성 태그 지정^[1] 및 정보 추출에서 응용 프로그램을 찾는다.^[2]

모델

Suppose we have a sequence of observations ${\displaystyle O_{1},\dots ,O_{n}}$ that we seek to tag with the labels ${\displaystyle S_{1},\dots ,S_{n}}$that maximize the conditional probability ${\displaystyle P(S_{1},\dots ,S_{n}\mid O$$_{1},\dots,O_{n$ MEMM에서 이 확률은 마르코프 전환 확률로 인수되며, 여기서 특정 라벨로 전환될 확률은 해당 위치에서의 관측치와 이전 위치의 라벨에만^{[citation needed]} 의존한다.

${\displaystyle P(S_{1},\dots ,S_{n}\mid O_{1},\dots,O_{n}}=\prod _{t=1}^{n(S_{t}, mid S_{t-1},O_{t}).}$

이러한 각각의 전환 확률은 동일한 일반 분포 $o$)에서 나온다$.$ 이전 라벨 $s{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ s$'$의 가능한 각 라벨 값에 대해$,$ 특정 $라벨{\displaystyle }$ s ${\displaystyle s}$의 확률은 최대 엔트로피 분류기와 동일한 방식으로 모델링된다$$.^[3]

$P.O.=P_{s'}(s\mid o)={\frac {1}{Z(s')}}}}}\exp \left(\sum _{a}lambda _{a}f_{a}(o,s)\right).}$

여기서 $f{\displaystyle {}_{}}$ ${\displaystyle a_{}o}$ ,${\displaystyle s}$ ) ${\displaystyle f_{a}(o,s)}$은 실제 값 또는 범주형 특성 기능이며, $Z{\displaystyle (o}$, ${\displaystyle {}^{})}$ )$${\$displaystyle$ Z$(o,s')$는 분포가 1에 합치도록 하는 정규화 용어다$$.분포에 대한 이 형식은 형상에 대한 경험적 기대가 주어진 기대치와 같다는 제약조건을 만족하는 최대 엔트로피 확률 분포에 해당한다.

${\displaystyle \operatorname {E} _{e}\left[f_{a}(o,s)\right]=\operatorname {E} _{p}\left[f_{a}(o,s)\right]\quad {\text}$

${\displaystyle {매개변수}_{}}$ ${\$는 일반화된 반복 스케일링을 사용하여 추정할 수 있다$$.^[4]게다가 바움-바움-의 변종이다.HMM을 훈련하는 데 사용되는 Welch 알고리즘은 훈련 데이터가 불완전하거나 라벨이 누락되었을 때 매개변수를 추정하는 데 사용할 수 있다.^[2]

최적 상태 시퀀스 ${\displaystyle {S\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle }$S ${\displaystyle n_{}}$ ${\$은(는) HMM에 사용되는 것과 매우 유사한 Viterbi 알고리즘을 사용하여$$ 찾을 수 있다. 동적 프로그램은 전방 확률을 사용한다.

${\displaystyle \alpha _{t+1}=\sum _{s'\in S}\alpha _{t}s)P_{s'}(s\mid o_{t+1}).}$

장단점

시퀀스 태그 지정에 대한 HMM이 아닌 MEMM의 장점은 관찰을 나타내기 위해 형상을 선택할 때 더 많은 자유를 제공한다는 것이다.시퀀스 태그 지정 상황에서는 도메인 지식을 사용하여 특수 목적 기능을 설계하는 것이 유용하다.MEMMs를 소개하는 원문에서 저자들은 "기존에 보이지 않았던 회사명을 뉴스와이어 기사에서 추출하려고 할 때 단어의 정체성만으로는 그다지 예측이 안 된다. 그러나 단어의 대문자화, 즉 명사화, 즉 어포시스트에 사용되고, 기사 상단에 가까운 곳에 나타난다는 것을 아는 것은 그리 어려운 일이 아니다."라고 쓰고 있다.(국가-국가 구조에서 제공하는 문맥과 연계하여) 모든 것이 상당히 예측적이다."^[2]이와 같은 유용한 시퀀스 태그 지정 기능은 자주 독립적이지 않다.최대 엔트로피 모델은 형상들 사이의 독립성을 가정하지 않지만, HM에서 사용되는 생성 관찰 모델은 그렇다.^[2]따라서 MEMM은 사용자가 상관관계가 있지만 유용한 기능을 많이 지정할 수 있다.

MEMMs와 HMMs 및 조건부 무작위 필드(CRF) 대비 또 다른 장점은 훈련이 상당히 더 효율적일 수 있다는 것이다.HMM과 CRF에서는 훈련^{[citation needed]} 시 내부 루프로서 전방-후방 알고리즘의 일부 버전을 사용할 필요가 있다.그러나 MEMM에서 전환 확률에 사용되는 최대 엔트로피 분포의 모수를 추정하는 것은 각 전환 분포에 대해 별도로 수행할 수 있다.

MEMM의 단점은 그들이 잠재적으로 "적극적으로 그들의 관찰을 무시하는" 낮은 전환 분포를 가진 상태들로 인해 "레이블 바이어스 문제"를 겪을 수 있다는 것이다.조건부 무작위 장은 이미 1990년대 초 신경망 기반 마르코프 모델의 맥락에서 인식되었던 이러한 약점을 극복하기 위해 설계되었다.^[5][5][6]라벨 편향의 또 다른 원천은 알려진 이전 태그에 대해 훈련이 항상 이루어지기 때문에 이전 태그에 불확실성이 있을 때 모델이 시험 시간에 어려움을 겪는다는 것이다.

참조