中文分词词性和序列标注之MEMM-2-最大熵模型

二、最大熵模型

1. 条件最大熵的意义

条件熵函数是条件概率分布函数的度量，其概率分布越均匀，熵值越大。

$$ H(Y|X) = - \sum_{x, y} p(x, y) log \, p(y|x) $$

给定$ x $的情况下$ Y $的熵对于$ x $的期望越大，表示$ X $并未给$ Y $带来多少信息增益，也就是说$ X $对$ Y $决策帮助信息越少。这看似矛盾，因为我们需要的是根据$ X $对$ Y $分类。如果$ X $对$ Y $无帮助，那么分类毫无意义(此时$Y$均匀分布)。但在实际操作中$ X,Y $被特征函数强制约束(出现$ x $同时出现$ y $)。因此，最大熵其实只能把特征函数未约束的信息对$ Y $的影响均匀分布。

承认在已知信息（特征函数约束）以外可能有未知信息会对判断$y$造成影响。但无法确定未知信息会对识别每个$ y $的具体值造成何种影响，为了风险最小化，不对未知信息对$ Y $的决策影响做任何主观倾向假设,而是认为未知信息对所有$ y $的影响程度都是趋于相同的，于是风险被平摊。

例如，事件集合$ Y = \{y_1,y_2,y_3,y_4 \}; \sum^4_{i=1} p(y_i) = 1$, 已知$ P(Y=y_1) = 0.4 $, 那么在没有其他更多信息帮助下, 最大熵理论认为 $ P(Y=y_2) = P(Y=y_3) = P(Y=y_4) = ( 1.0 - P(Y=y_1) ) / 3 = 0.2 $。

2 特征函数

特征函数 $ f(x, y) $ 指示某事实是否成立，例如：

$$ f(x, y) = \begin{cases} 1, & \text{if y='rn' and next(x) = 'is'} \\ 0, & \text{else} \end{cases} $$

如果 s是人名并且下一个词是"is". 则返回1指示存在此事实。$ \text{对数线性模型}^{\text{[4]}} $并未限制特征函数的取值范围，但通常输出为 $ \{0,1\} $ 的特征函数更容易分析和直观理解。例如返回1就是存在此特征。

3. 最大熵模型

最大熵模型是一种对数线性模型，其目的是对样本做$ P(Y|X) $建模, 其需要在满足观测事实约束时才有意义，现描述使用特征函数约束的最大熵模型。

设经验分布：

$$ \begin{align} \tilde{P}(X=x) &= \frac{Count(X=x)}{N} \\ \tilde{P}(X=x, Y=y) &= \frac{Count(X=x, Y=y)}{N} \end{align} $$

$ Count $是计数函数，$ N $是样本总数。

使用前面介绍的特征函数对$ x,y $对约束（指示存在的事实）。那么，统计样本可得到特征函数指示事实的经验分布期望:

$$ E_{\tilde{P}}(f) = \sum_{x,y} \tilde{p}(x, y) f(x, y) $$

假设我们的最大熵模型对条件概率估计正确，那么很显然应可得到符合观测事实的$ P(Y|X) $分布，也就是说。使用模型估计的特征函数期望应该和在样本中统计到的特征函数期望相同。

$$ \begin{align} E_{P}(f) & = E_{\tilde{P}}(f) \\ \sum_{x,y} \tilde{p}(x) p(y|x) f(x, y) & = \sum_{x,y} \tilde{p}(x,y) f(x,y) \end{align} $$

同时，模型得到的条件概率分布应该合法，于是最大熵模型的完整描述如下：

$$ \begin{align} \max_{P} H(P) & = – \sum_{x, y} \tilde{p}(x) p(y|x) \log \, p(y|x) \Leftrightarrow \min_{P} -H(P) \\ \text{subject to:} \\ E_{P}(f_i) & = E_{\tilde{P}}(f_i) \qquad i=1,2,\cdots,n \\ \sum_y p(y|x) & = 1 \end{align} $$

$ P $是分布函数, $ p $是质量函数，因没有$ p(x, y) $, 因此使用 $ \tilde{p}(x) p(y|x) $近似。按照惯例，转换为最小化负熵。其实就是求解满足约束的最小负条件熵的条件概率分布函数。

五、参考资料
[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model
[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)
[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models
[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques
[5] 李航; 统计学习方法
[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369