HMM / MEMMs / CRF

Log-Linear Models

: 지수를 이용해 조건부 확률 구하기

: depends on the conditional distribution using the exponential function

 

some input domain X

a finite label set y

Aim is to provide a conditional probability P(y|x)

 

Feacutrs in Log-lnear Models

Theoritically, we can use any features in X and S

- The current word

- The surrounding words

- The current POS tag

- The surrounding tags

 

 

• Structured Prediction 특징 -      Y consists of multiple components Y = {y1, y2,…, yn} -      (Strong) correlations between output components = -      Exponential output space • HMM’s Transition and emission -      Transition probabilities : the probability of the current value only depends on previous states 시간j에서의 은닉 상태가 주어졌을 때, 시간 j-1에서의 은닉상태가 선택되는데 영향을 줌 -      Emission probabilities: the current token only depends on own sates 주어진 상태S에서 특정한 결과값 x가 관찰될 확률분포 -      A generative model with strong assumptions • Generative VS Discriminative -      Generative Model: Modeling the joint distribution: P(X,S) -      Discriminative Model: Modeling P(S|X) directly • Log-Linear Models: depends on the conditional distribution using the exponential function 지수를 이용해 조건부 확률 구하기 • Features in Log-linear Models: 이론적으로 모든 feature사용 가능 -      The current word 현재 단어 -      The surrounding words 주변 단어들 -      The current POS tag 현재 태그 -      The surrounding tags 주변 태그들 -      We can use any features in ->but feature complex 해짐 • 여러 feature 사용시 생기는 문제점 1.     Feature Sparsity 2.     Feature Selection이 매우 어려워짐. 무엇이 useful한지 알수 없어. It is hard to select which feature is useful. 3.     독립적인 가정 필요. We need independence assumptions to compute the nominator. This is because Strong assumptions lead to less flexible features. • Using Log-Linear Model – only depends on previous & currents because of Markov assumption -> 그래서 Trackable • Maximum Entropy Markov Models (MEMMs): 시퀀스를 분류. -      Goal: modeling the distribution. -      i번째 단어의 feature와 직전 POS를 바탕으로 가장 확률이 높은 POS 반환 -      we do not need to make any independent assumptions on input. 독립 가정들 만들 필요 없다. -      Discriminative 모델의 특징 -> 독립적인 가정 필요 X (input x가 주어진다고 항상 가정됨 그래서 독립적인 가정 필요 X) • Features in MEMMs -      Markov assumption in HMM과 비슷하지만, features는 more richer하고 더 다양함 -      The current word / The current tag -      The surrounding words -      The previous POS tag -      Prefix or suffix features • Decoding with MEMMs: Viterbi Algorithm -      HMM이나 MEMM 모두 Markov 가정을 사용하므로 Viterbi algorithm을 사용 -      Markov가정이 있어서 Current state가 previous state에 의존 • HMMs VS MEMMs -      Model Performance: MEMM > HMM – slight better -      In MEMMs, feature vectors f allows much richer representations 장점 1. Sensitivity to any word 어떤 단어든지 사용 가능 장점 2. Sensitivity to spelling features (prefixes, suffixes) of current or surrounding words -      Parameter estimation in MEMMs is more expensive than in HMM but is still not prohibitive for most tasks -> 단점) HMM은 simple한데, MEMM은 복잡해서 expensive • Can we relax the Markov assumption in MEMMs but keep the same features? -> Yes. As the features and the assumptions are correlated with each other. 우리가 have stronger assumption & weaker feature을 가지면 keep the same features가능하다. 하지만, weaker assumption을 갖고있다면 모델을 바꿔줘야 해 CRFs로. • Conditional Random Filed (CRFs) -      MEMMs와 동일하게 Whole features들 사용(몽땅가능) -      And features들은 only depends on current and previous states • HMM(generative & direction) VS MEMM(Discriminative and direction)  VS CRF (Discriminative and undirective) -       HMM과 달리 CRF는 특정위치에서 특정값 확신 가능. 비방향이라 label biase문제에 더 자유로움. -       Generative model(HMM)은 관측값을 모델링하는데 걸리는 시간 고정과 독립성에 대해 매우 엄격한 가정을 요구 -       CRF는 관측 시퀀스의 임의의 독립적이지 않은 기질들에 의존하는 것이 가능 -      CRF < MEMMs : CRF is weaker than MEMMs (노방향이라서) • Decoding with CRF – Viterbi algorithm (MEMM과 완전동일) • 최신연구에 따르면, CRF is really better than MEMM