## HMM、MEMM、CRF几个模型间的比较

MEMM和CRF这两个模型，同是判别式模型，不关注如何建模观察变量$X$（在分词、POS等问题中，就是单词序列），而只关注条件概率$P(Y|X)$，带来的好处就是，（1）不用为了tractable地建模$X$，而对$X$做出很强的独立性假设（在朴素贝叶斯和HMM中，对$X$的独立性假设都非常强，要不也不会称之为“朴素”）（2）为了预测当前label，不仅可以使用当前词的特征、还可以使用前后词的特征，特征种类也可以是各种各样的，例如单词前缀、后缀等，虽然这些特征只是线性加和（线性加和其实背后也是有独立性假设的，这也是为什么HMM和CRF称为Generative-Discriminative Pair），但总归比HMM可以使用更多特征。

CRF拥有MEMM的所有优点，同时解决了label bias（标记偏置）问题。标记偏置问题的原因在于，MEMM建模$P(y_1,y_2,…,y_n|X)$时，使用的是局部归一化，即$P(y_1|X) P(y_2|X,y_1) ... P(y_n|X,y_{n-1})$，每个状态转移的概率都是单独model的。这样做的问题在于，假设在训练数据中，状态$a$只会转移到状态$b$。也就是训练得到的模型无论输入$X$是什么，$P(b|a,X)=1$。这会导致熵小的状态，有“不正当的优势”，因为无论输入是什么，你只要把状态想法转移到$a$，后面的概率是1，这样总的概率就会很高。CRF的归一，是全局归一化，这样的“不正当的优势”就不存在了。其实，把总的条件概率，分解为连乘的形式，是没问题的，CRF同样有一阶马尔科夫假设，同样可以做类似的分解，问题出在局部归一化上。

MEMMs and other non-generative finite-state models based on next-state classifiers, such as discriminative Markov models (Bottou, 1991), share a weakness we call here the label bias problem: the transitions leaving a given state compete only against each other, rather than against all other transitions in the model. In probabilistic terms, transition scores are the conditional probabilities of possible next states given the current state and the observation sequence. This per-state normalization of transition scores implies a “conservation of score mass” (Bottou, 1991) whereby all the mass that arrives at a state must be distributed among the possible successor states. An observation can affect which destination states get the mass, but not how much total mass to pass on. This causes a bias toward states with fewer outgoing transitions. In the extreme case, a state with a single outgoing transition effectively ignores the observation. In those cases, unlike in HMMs, Viterbi decoding cannot downgrade a branch based on observations after the branch point, and models with statetransition structures that have sparsely connected chains of states are not properly handled. The Markovian assumptions in MEMMs and similar state-conditional models insulate decisions at one state from future decisions in a way that does not match the actual dependencies between consecutive states.

## EM算法

### EM算法是一种优化算法

$\log{P(X,Y|\theta)} = \log{P(X|\theta)} + \log{P(Y|X,\theta)}$

$\log{P(X|\theta)} - \log{P(X|\theta^{(t)})} = \log{P(X,Y|\theta)} - \log{P(X,Y|\theta^{(t)})} + \log{\frac{P(Y|X,\theta^{(t)})}{P(Y|X,\theta)}}$

$\log{P(X|\theta)} - \log{P(X|\theta^{(t)})} = E_{P(Y|X,\theta^{(t)})}(\log{P(X,Y|\theta)} - \log{P(X,Y|\theta^{(t)})}) + E_{P(Y|X,\theta^{(t)})}\log{\frac{P(Y|X,\theta^{(t)})}{P(Y|X,\theta)}}$

$E_{P(Y|X,\theta^{(t)})}\log{P(X,Y|\theta)}$

### EM算法和K-means聚类

K-means（EM）：

1. 将每个样本分配到最近的一个类（计算每个样本属于每个类的概率）
2. 更新类中心（更新参数）