基本知识
熵和条件熵
熵(entropy)原是一个热力学中的概念，后由香农引入到信息论中。在信息论和概率统计中，熵用来表示随机变量的不确定性的度量。其定义如下：
设$X \in {x_1,x_2,…,x_n}$为一个离散随机变量，其概率分布为$p(X=x_i)=p_i,i=1,2…,n$，则X的熵为：
$$
H(X)=-\sum_{i=1}^n p_ilogp_i
$$
其中，当$p_i=0$时，定义$0log0=0$。
上式中的对数log以2为底或者以e为底，分别对应bit或nat，熵的两种单位。由熵的公式可知H(X)仅依赖于X的分布，而与X的具体取值无关，因此，常将H(X)记为H(p)。
熵的意义：可以认为熵是描述事物无序性的参数，熵越大则无序性不确定性越大。一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发的产生新的有序结构。当熵处于最小值，即能量集中程度最高、有效能量处于最大值时，那么整个系统也处于最有序的状态，相反为最无序状态。熵增原理预示着自然界越变越无序。s
由熵的计算公式可知熵的取值范围为：
$$
0 \leq H(X) \leq log n
$$
- 左边的等号在X为确定值的时候成立，即X没有变化的可能；
- 右边的等号在X为均匀分布的时候成立；
条件熵的定义：
设$X \in {x_1,x_2,…,x_n},Y \in {y_1,y_2,…,y_n)}$为离散的随机变量。在已知X的条件下，Y的条件熵（conditional entropy）可以定义为：
$$
H(Y|X)=\sum_i^n p(x_i)H(Y|X=x_i)=-\sum_{i=1}^n p(x_i) \sum_{j=1}^m p(y_j|x_i)log p(y_j|x_i)
$$
它表示已知X的情况下，Y的条件概率分布的熵对X的数学期望。
最大熵原理
最大熵的理论基础是熵增理论，即在无外力作用下，事物总是朝着最混乱的方向发展。同时，事物是约束和自由的统一体。事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则。在已知条件下，熵最大的事物，最可能接近它的真实状态。
最大熵原理是在1957年由E.T.Jaynes提出的，其主要思想是，在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。因为在这种情况下符合已知知识的概率分布可能不止一个。常在[3]中写道：“我们知道熵定义的实际上是一个随机变量的不确定性，熵最大的时候，说明随机变量最不确定，换句话说，也就是随机变量最随机，对其行为做准确的预测最困难。从这个意义上讲，那么最大熵原理的实质就是，在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，这是我们可以作出的唯一不偏不倚的选择，任何其他的选择都意味着我们增加了其他的约束和假设，这些约束和假设根据我们掌握的信息无法做出。”
吴军老师的《数学之美》第20章中提到了一个掷骰子的例子可以很好的解释最大熵原理。对于一个骰子，每面向上的概率是多少，可能我们会不加思索会说是$\frac {1}{6}$，但是，如果说骰子的其中四点被做过特殊处理，四点向上的概率为$\frac {1}{3}$，那么其他点向上的概率则变为$\frac {2}{15}$。虽然，这是一个很简单的问题，却隐含着最大熵的原理。首先，在骰子没做任何处理之前，我们认为骰子的各个面出现的概率是相同的，即符合均匀分布，此时熵最大。然后，当增加四点被做过特殊处理后，其他面的向上的概率变为$\frac {2}{15}$，在这里四点被做过特殊处理，即所谓的约束条件，满足约束条件之后，而对其它则不做任何假设其他面向上的概率是相同的，即为$\frac {2}{15}$，也是熵最大的。在这个例子中，不作任何假设就是使用“等概率”，这个时候概率分布最均匀，从而使得概率分布的熵最大，即最大熵原理。
最大熵模型的定义
最大熵原理是统计学学习的一般原理，将它应用到分类得到最大熵模型。
假设分类模型是一个条件概率分布$P(Y|X)$，$X \in \cal X \subseteq R^*$表示输入，$Y \in \cal Y $表示输出，$\cal X和\cal Y$表示输入和输出的集合。这个模型表示的是对于给定的输入X，以条件概率$P(Y|X)$输出Y。
给定义一个训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，学习的目标是用最大熵原理选择最好的分类模型。首先，考虑模型应该满足的条件。给定训练数据集，可以确定联合概率分布P(X,)的经验分布和边缘分布P(X)经验分布，分别以$\hat P(X,Y)$和$\hat P(X)$表示，这里：
$$
\begin{align}
&\hat P(X=x,Y=y)=\frac {v(X=x,Y=y)}{N} \\
&\hat P(X=x)=\frac {v(X=x)}{N}
\end{align}
$$
其中，$v(X=x,Y=y)$表示训练数据中样本(x,y)出现的频数，$v(X=x)$表示训练数据中输入x出现的频数，N表示训练样本的容量。
用特征函数(feature function)$f(x,y)$描述输入x和输出y之间的某一事实，其定义为：
$$
f(x,y)=\begin{cases}
1, & x与y满足某一事实 \\
0, & 否则
\end{cases}\\
$$
它是一个二值函数，当x和y满足这个事实时取值为1，否则取值为0。
特征函数$f(x,y)$在训练数据集上关于经验分布$\hat P(X,Y)$的期望值，用$E_{\hat p}(f)$表示：
$$E_{\hat p}(f) = \sum_{x,y} \hat P(x, y)f(x,y)$$
特征函数$f(x,y)$关于模型上关于$p(x,y)$的数学期望为：
$$E_{p}(f) = \sum_{x,y}p(x,y)f(x,y)$$
$p(y|x)$与经验分布$\hat p(x)$的期望值用$E_p(f)$表示。需要注意的是$p(x,y)$是未知的，而且建模的目标是$p(y|x)$。因此，我们希望将排$p(x,y)$表示成$p(y|x)$的函数。利用贝叶斯定理有，$p(x,y)=p(x)p(y|x)$，但$p(x)$依然是未知的，此时，只好利用$\hat p(x)$来近似了。这样$E_p(f)$可以重新定义为：
$$E_p(f) = \sum_{x,y}\hat P(x)P(y|x)f(x,y)$$
对于概率分布$p(y|x)$，我们希望特征$f$的期望值应该和从训练数据中得到的特征期望值是一致的，因此，提出约束：
$$E_p(f) = E_{\hat p}(f)$$
即：
$$
\sum_{x,y}\hat P(x)P(y|x)f(x,y)=\sum_{x,y}p(x,y)f(x,y)
$$
假设从训练数据集中抽取了n个特征，相应地，便有n个特征函数$f_i(i=1,2,…,n)$以及n个约束条件：
$$
C_i:E_p(f_i)=E_{\hat p}(f_i),i=1,2,…,n.
$$
最大熵模型定义：
利用最大熵原理选择一个最好的分类模型，即对于任意一个给定的输入$x \in \cal X$，可以以概率$p(y|x)$输出$y \in \cal Y$。前面已经讨论了特征函数和约束条件，要利用最大熵原理，还差一个熵的定义，注意，我们的目标是获取一个条件分布，因此，这里也采用相应的条件熵，如下：
$$H(p(y|x))= \sum_{x,y} \hat p(x)p(y|x)log p(y|x)$$
下文将$H(p(y|x))$简记为$H(p)$，为了后面计算方便，上式中的对数为自然对数，即以e为底。至此，可以给出最大熵模型的完整描述了。对于给定的训练数据T，特征函数$f_i(x,y),i=1,2,…,n$，最大熵模型就是求解：
$$
\begin{align}
&max_{p\in C} H(p)=(-\sum_{x,y} \hat p(x)p(y|x)log p(y|x)),\\
&s.t. \\
&\sum_y p(y|x)=1
\end{align}
$$
或者:
$$
\begin{align}
&min_{p\in C} -H(p)=(-\sum_{x,y} \hat p(x)p(y|x)log p(y|x)),\\
&s.t. \sum_y p(y|x)=1
\end{align}
$$
则模型集合C中条件熵$H(p)$最大的模型称为最大熵模型。
最大熵模型的学习
最大熵模型的学习过程就是最大熵模型的求解过程。最大熵模型的学习可以形式化为约束最优化问题，主要思路和步骤如下：
- 利用拉格朗日乘子法将最大熵模型由一个带约束的最优化问题转化为一个与之等价的无约束的最优化问题，它是一个极小极大问题（min max)；
- 利用对偶问题等价性，转化为求解上一步得到的极小极大问题的对偶问题，它是一个极大极小问题（max min）
在求解内层的极小问题时，可以导出最大熵模型的解具有指数形式，而在求解最外层的极大问题时，还将意外地发现其与最大似然估计的等价性。
对于给定的训练数据$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$以及特征函数$f_i(x,y),i=1,2,…n$，最大熵模型的学习等价于约束最优化问题：
$$
\begin{align}
&max_{p\in C} H(p)=-\sum_{x,y}\hat p(x)p(y|x)logp(y|x)\\
&s.t. E_p(f_i)=E_{\hat p}(f_i),i=1,2,…,n\\
& \sum_yp(y|x)=1
\end{align}
$$
按照最优化问题的习惯，将求最大值问题转换为求最小值的问题：
$$
\begin{align}
&min_{p\in C} -H(p)=\sum_{x,y}\hat p(x)p(y|x)logp(y|x)\\
&s.t. E_p(f_i)-E_{\hat p}(f_i)=0,i=1,2,…,n\\
& \sum_yp(y|x)=1
\end{align}
$$
求解约束最优化问题，所得出的解，就是最大熵模型学习的解，下面给出具体的推导。这里先将约束最优化的原始问题转换为无约束最优化的对偶问题，通过求解对偶问题求解原始问题。
首先，引入拉格朗日乘子$\lambda_{0},\lambda_{1},…,\lambda_n$，记为$\lambda=(\lambda_{0},\lambda_{1},…,\lambda_n)^T$，定义拉格朗日函数为$L(p,\lambda)$，则：
$$\begin{align}
L(p,\lambda)&=-H(p)+\lambda_0(1-\sum_yp(y|x))+\sum_{i=1}^n \lambda_{i}(E_{\hat p}(f_i)-E_p(f_i))\\
&=\sum_{x,y}\hat p(x)p(y|x)log p(y|x)+\lambda_0(1-\sum_y p(y|x))+\sum_{i=1}^n(E_{\hat p}(f_i)-E_p(f_i))
\end{align}
$$
利用拉格朗日对偶性，可知最大熵模型等价于求解：
$$
min_{p\in C} max_{\lambda} L(p,\lambda)
$$
我们把上式称为原始问题（primary problem)极小极大问题；通过交换极大和极小的位置，可以得到原始问题的对偶问题（dual problem）为
$$max_{\lambda}min_{p\in C}L(p,\lambda)$$
由于$H(p)$是关于p的凸函数，因此，原始问题和对偶问题是等价的。这样可以通过求解对偶问题来求解原始问题。首先，对于对偶问题内层的极小问题$min_{p\in C}L(p,\lambda)$是关于参数$\lambda$的函数，将其记为$\psi(\lambda)$，即：
$$
\psi(\lambda)=min_{p\in C}L(p,\lambda)=L(p_{\lambda},\lambda)
$$
其中，
$$
p_{\lambda} = arg min_{p\in C}L(p,\lambda)
$$
首先，计算拉格朗日函数$L(p,\lambda)$对$p(y|x)$的偏导数。
$$\begin{align}
\frac {\partial L(p,\lambda)}{\partial p(y|x)}
&=\sum_{x,y}\hat p(x)(logp(y|x)+1)-\sum_y \lambda_0 - \sum_{i=1}^n \lambda_i(\sum_{x,y}\hat p(x)f_i(x,y))\\
&=\sum_{x,y}\hat p(x)(logp(y|x)+1)-\sum_x \hat p(x)\sum_y \lambda_0 - \sum_{x,y}\hat p(x)\sum_{i=1}^n \lambda_i f_i(x,y)\\
&=\sum_{x,y} \hat p(x)(log p(y|x)+1) - \sum_{x,y}\hat p(x)\lambda_0 - \sum_{x,y}\hat p(x)\sum_{i=1}^n \lambda_i f_i(x,y)\\
&=\sum_{x,y}\hat p(x)(log p(y|x)+1 - \lambda_0 - \sum_{i=1}^n \lambda_if_i(x,y))
\end{align}
$$
另偏导数等于0，在$\hat p(x)>0$的情况下，进一步，令$\frac {\partial L(p, \lambda)}{\partial p(y|x)}=0$可得：
$$
log p(y|x)+1 - \lambda_0 - \sum_{i=1}^n \lambda_if_i(x,y)=0
$$
从而得到：
$$p(y|x)=e^{\lambda_0 - 1} \cdot e^{\sum_{i=1}^n \lambda_i f_i(x,y)}$$
将上式代入约束条件$\sum_y p(y|x)=1$，即：
$$
\sum_y p(y|x)=e^{\lambda_0 - 1} \cdot \sum_y e^{\sum_{i=1}^n \lambda_i f_i(x,y)=1}
$$
可得：
$$
e^{\lambda_0-1} = \frac {1}{\sum_y e^{\sum_{i=1}^n \lambda_i f_i(x,y)}}
$$
将上式代入到$p(y|x)=e^{\lambda_0 - 1} \cdot e^{\sum_{i=1}^n \lambda_i f_i(x,y)}$得到：
$$
p_{\lambda} = \frac {1}{Z_{\lambda}(x)}e^{\sum_{i=1}^n \lambda_if_i(x,y)}
$$
其中，
$$Z_{\lambda}(x)=\sum_{y} e^{\sum_{i=1}^n \lambda_if_i(x,y)}$$
称为规范化因子，注意，此时的$\lambda=(\lambda_1,\lambda_2,…,\lambda_n)^T$，不再包含$\lambda_0$了。
$p_{\lambda}$就是最大熵模型的解，它具有指数形式，其中$\lambda_1,\lambda_2,…,\lambda_n$为参数，分别对应$f_1,f_2,…,f_n$的权重，$\lambda_i$越大，表示特征$f_i$越重要。
之后求解对偶问题外部的极大化问题：
$$max_{\lambda} \psi (\lambda)$$
设其解为：
$$
\lambda^{*} = argmax_{\lambda} \psi (\lambda)
$$
则，最大熵模型的解为$p^* = p_{\lambda^*}$
为此，首先要给出$\psi(\lambda)$的表达式：
$$\begin{align}
\psi(\lambda)
&=L(p_{\lambda},\lambda)\\
&=\sum_{x,y}\hat p(x)p_{\lambda}(y|x)logp_{\lambda}(y|x)+\sum_{i=1}^n \lambda_{i}(E_{\hat p}(f_i) - E_{p}(f_i))\\
&=\sum_{x,y}\hat p(x)p_{\lambda}(y|x)logp_{\lambda}(y|x)+\sum_{i=1}^n \lambda_{i}(\sum_{x,y}\hat p(x,y)f_i(x,y) - \sum_{x,y}\hat p(x)p_{\lambda}(y|x)f_i(x,y))\\
&=\sum_{i=1}^n \lambda_i \sum_{x,y}\hat p(x,y)f_i(x,y) + \sum_{x,y} \hat p(x)p_{\lambda}(y|x)(log p_{\lambda}(y|x) - \sum_{i=1}^n \lambda_if_i(x,y))
\end{align}
$$
由于，
$$
log p_{\lambda}(y|x) = \sum_{i=1}^n \lambda_if_i(x,y) - log Z_{\lambda}(x)
$$
带入前面的$\psi (\lambda)$可得：
$$
\begin{align}
\psi(\lambda)&=\sum_{i=1}^n\lambda_i \sum_{x,y}\hat p(x,y)f_i(x,y) - \sum_{x,y}\hat p(x)p_{\lambda}(y|x)log Z_{\lambda}(x)\\
&=\sum_{i=1}^n\lambda_i \sum_{x,y}\hat p(x,y)f_i(x,y) - \sum_x \hat p(x)log Z_{\lambda}(x)\sum_y p_{\lambda}(y|x)\\
&=\sum_{i=1}^n\lambda_i \sum_{x,y}\hat p(x,y)f_i(x,y) - \sum_x \hat p(x)log Z_{\lambda}(x)
\end{align}
$$
有了$\psi(\lambda)$的具体表达式，就可以求解其最大值点$\lambda^*$了。
对$\psi (\lambda)$的最大化等价于最大熵模型的极大似然估计。已知训练数据的经验分布为$\hat p(x,y)$，条件概率分布$p(y|x)$的对数似然函数表示为：
$$
L_{\hat p}(p) = log \prod_{x,y}p(y|x)^{\hat p(x,y)}=\sum_{x,y} \hat p(x,y)logp(y|x)
$$
将$p_{\lambda}$带入似然函数，可得：
$$
\begin{align}
L_{\hat p}(p_{\lambda})&=\sum_{x,y}\hat p(x,y)log p_{\lambda}(y|x)\\
&=\sum_{x,y}\hat p(x,y)(\sum_{i=1}^n \lambda_if_i(x,y) - logZ_{\lambda}(x))\\
&=\sum_{x,y}\hat p(x,y)\sum_{i=1}^n \lambda_if_i(x,y) - \sum_{x,y}logZ_{\lambda}(x)\\
&=\sum_{i=1}^n \lambda_i(\sum_{x,y} \hat p(x,y)f_i(x,y)) - \sum_{x,y} \hat p(x,y)log Z_{\lambda}(x)\\
&=\sum_{i=1}^n \lambda_i \sum_{x,y} \hat p(x,y)f_i(x,y) - \sum_x \hat p(x)log Z_{\lambda}(x)
\end{align}
$$
可以看到公式25和公式30是相等的，这说明最大化$\psi(\lambda)$和最大化似然估计是等价的。
最大熵模型最优化方法有多种，比如GIS算法、IIS算法以及梯度下降法等方法，这里就不具体介绍了，具体可参考《统计学习》方法。
最大熵模型的优缺点
最大熵模型的优点如下：
- 建模时，实验者只需要集中精力选择特征，而不需要花费精力考虑如何使用这些特征；
- 特征选择灵活，且不需要额外的独立假定或者内在约束；
- 模型应用在不同领域时的可移植性强；
- 可结合更丰富的信息；
缺点：
- 时空开销大；
- 数据稀疏问题严重；
- 对语料的依赖性较强；
特征引入算法
在使用最大熵模型的时候，往往会构建很多特征，但并不是所有的特征都是有用的，所以需要作特征选择。尤其对于自然语言处理问题，这些特征的选取往往具有很大的主观性。同时，因为特征数量往往很多，必须引入一个客观标准自动计算以引入特征到模型中，同时针对特征进行参数估计。Della Pietra et al[6]对自然语言处理中随机域的特征选择进行了描述，在进行特征选取时，是由特征的信息增益作为衡量标准的。一个特征对所处理问题带来的信息越多，该特征越适合引入到模型中。一般我们首先形式化一个特征空间，所有可能的特征都为后补特征，然后从这个后补特征集内选取对模型最为有用的特征集合。特征引入的算法如下：
算法： 特征引入算法
输入：候选特征集合F，经验分布$\hat p(x,y)$
输出：模型选用的特征集合S，集合这些特征的模型$P_s$
- 初始化：特征集合S为空，它所对应的模型$P_s$均匀分布，n=0;
- 对于候选特征集合F中的每一个特征$f\in F$，计算加入该特征后为模型带来的增益值$G_f$；
- 选择具有最大增益值$G(S,f)$的特征$f_n$;
- 把特征$f_n$加入到集合S中，$S=(f_1,f_2,…,f_n)$;
- 重新调整参数值，使用GIS算法计算模型$P_s$;
- n=n+1，返回到第2步；
在算法的第2步中，要计算每个特征的增益值，这里是根据Kullback-Leibler（简称KL）距离来计算的。衡量两个概率分布p和q的KL距离，公式如下：
$$
D(p||q) = \sum_x p(x)ln \frac {p(x)}{q(x)}
$$
距离的大小与两种分布的相似程度成反比，距离越小表示两种分布越逼近。因此，在加入第n个特征前后，求的模型分布与样本分布之间的KL距离为：
$$
D(\hat p||p^{(n-1)}) = \sum_x \hat p(x) ln \frac {\hat p(x)}{p^{(n-1)}(x)}\\
D(\hat p||p^{(n)}) = \sum_x \hat p(x) ln \frac {\hat p(x)}{p^{(n)}(x)}
$$
这样，我们定义引入第n个特征$f^{(n)}$后的增益值为：
$$
f^{(n)} = D(\hat p||p^{(n-1)}) - D(\hat p||p^{(n)})
$$
因此，选择第n个特征为：
$$
f^{(n)} = arg max_{f \in F}G(p, f^{(n)})
$$
参考文献
- https://www.cnblogs.com/pinard/p/6093948.html；
- https://blog.csdn.net/itplus/article/details/26550597；
- 自然语言处理的最大熵模型-常宝宝；
- 统计学习方法第6章；
- 自然语言处理技术中的最大熵模型方法-李素建、刘群等；
- Stephen Della Pietra, Vincent Della Pietra, and John Lafferty, Inducing features of random fields, IEEE Transactions on Pattern Analysis and Machine Intelligence 19:4, pp.380–393, April, 1997
