3月机器学习在线班第六课笔记--信息熵与最大熵模型

机器学习

---

信息熵

信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。（百度百科）

香农定义的信息熵的计算公式如下：

$$H(X) = - \sum {p({x_i})} \log (p({x_i}))~~~~(i = 1,2, \ldots ,n)$$
其中$X$ 表示的是随机变量，随机变量的取值为$({x_1},{x_2}, \ldots ,{x_n})$ ，p({x_i}) 表示事件$x_i$发生的概率，且有$\sum {p({x_i})} = 1$ 。信息熵的单位为bit。
说实在的，在听课的时候对这个概念一直是懵懵懂懂的，一直跨不过去。现在查找一些资料，希望能够通过笔记让自己清楚该概念。首先的疑问就是：为什么这样表达？
首先定义事件$x_i$的信息量为其发生概率对数的负数，记为I(x_i)，有：
$$I({x_i}) = - \log p({x_i})$$
有了该定义，可以发现信息熵$H(X)$即为随机变量$X$的平均信息量（期望）。那么疑问就变成：为什么$- \log p({x_i})$可以表示为事件$x_i$的信息量？

其实这挺好理解：事件$x_i$的信息量大小和它发生的概率（不确定性）有直接的关系。比如说，要搞清楚一件非常不确定的事，或是一无所知的事情，就需要了解大量的信息。相反，如果对某件事已经有较多了解，我们不需要太多的信息就能把它搞清楚。即信息量函数应该与事件概率成单调递减关系。同时，两个独立事件$x_i,x_j$（满足$p(x_i,x_j) = p(x_i) * p(x_j)$）的信息量大小应等于各自信息量之和。那么同时符合以上要求的是$I(x_i) = - \log p(x_i)$。
在香农1948年的论文《A Mathematical Theory of Communication》中，他通过论证信息熵函数需要满足的多条性质，推导出信息熵公式的唯一性。有兴趣的可以看看。

为了更好的理解，我们举例说明：

随机变量为均匀分布

在《数学之美》中的例子：假如我错过了看世界杯，赛后我问一个知道决赛结果的观众“哪支球队是冠军？”他不愿意直接告诉我，而是让我猜，每猜一次需要1bit，他的回答是以下2个中的一个：是，否。假设我对这32支球队一无所知，即我认为每支球队获得冠军的概率是相等的，那么我至少需要付多少bit给他才能知道谁是冠军？
我把球队编号为1到32，然后使用折半查找法的原理（如：”冠军队在1-16吗？”）每一次就可以减少一半的队伍，这样只需要5次，就能够知道冠军球队。也就是说，谁是世界杯冠军这条信息的信息量只值5bit。代入计算公式，在这种情况下（等概率假设）得到的信息熵即为5bit。

课堂上，邹博老师给出的一个例子：

有五个硬币，四个等重，另外一个是假币所以质量相比其他4个要轻。我事先不知道关于任何硬币的信息（即认为每一个硬币是假币的概率都是1/5）。这个例子和之前的猜球队冠军有一些相似，我也是需要经过询问才能得到答案，且每问一次需要付1bit。但不同之处在于，现在我可以询问的对象变成了天平，天平每一次能够比较两堆硬币，且能够给出3个结果中的一个：左边比右边重，右边比左边重，两边同样重。问我至少需要付多少bit就能够确保知道哪个是假币？

我们通过自己的计算可知道，如果幸运的话我只需要1bit就能够把假币测出来（天平左右各两个硬币，结果等重，那么假币即为天平外的一个），但是通常情况下需要2bit才能知道假币。这个时候，会发现不能够按照之前的预测世界杯冠军的方式来计算信息熵了(按照之前的方法直接计算得到$log_25>2$)，毕竟之前问观众只能给出2种结果，现在问天平能够给出3种结果啊，需要的bit应该更少。
实际上不仅仅需要关心随机变量的信息熵，还应该关心被询问对象(例子中观众、天平)的表达能力（即被询问对象的信息熵）。正确的表达式应该是：

$$\frac{{H(X)}}{{H(Y)}}$$
其中$X$为随机变量，$Y$为被询问对象。该问题最终得到的结果是$\frac{{H(X)}}{{H(Y)}}{\rm{ = }}\frac{{{{\log }_2}5}}{{{{\log }_2}3}} = 1.46$。世界杯冠军问题中之所以只计算随机变量的信息熵是因为被询问对象的信息熵刚好是1（$H(Y)=log_22$），所以忽略了。在计算机领域和通信领域，被询问对象一般都只能给出{0,1}两种结果，其信息熵为1，由此直接忽略。特殊情况下的忽略不代表不存在。

随机变量不再是均匀分布

有五个硬币，四个等重，另外一个是假币所以质量相比其他4个要轻。已知第一个硬币和第二个硬币是假硬币的概率为1/3，其他硬币为假硬币的概率为1/9。天平每一次能够比较两堆硬币，且能够给出3个结果中的一个：左边比右边重，右边比左边重，两边同样重。问我至少需要付多少bit就能够确保知道哪个是假币？
由于之前已经分析过，直接带入上面的计算公式即可得：

$$\frac{{H(X)}}{{H(Y)}}{\rm{ = }}\frac{{ - (\frac{1}{3}{{\log }_2}\frac{1}{3})*2 - (\frac{1}{9}{{\log }_2}\frac{1}{9})*3}}{{{{\log }_2}3}} = 1.333$$
也就是说，实际编码过程中需要2个bit来存储每一次。

在经典熵的定义式中，对数的底是2，单位为bit。在我们之后的例子中，为了方便分析使用底数e。如果底数为e，那么单位是nat(奈特)。重新写一遍信息熵的公式：

$$H(X) = - \sum {p(x_i)} ln(p(x_i))~~(i = 1,2, \ldots ,n)$$
为此，我们来研究研究函数$f(x) = x\ln (x)$，看看图像长啥样。由信息熵的公式及定义，可以发现此时的$x$ 表示的是事件发生的概率，有$x \in [0,1]$。求导分析：$f'(x) = \ln x + 1,f''(x) = \frac{1}{x} > 0$；由此发现$f(x)$是凸函数。令$f'(x)=0$可得$x=\frac{1}{e}$。由于$\mathop {\lim }_{x \to 0} f(x) = 0$，我们定义$f(0) = 0$ 。最后经过采样可得图像如下：

信息熵的总体理解

从之前的分析可以看出，熵其实定义了一个函数（概率分布函数$p(x)$）到一个值（信息熵H(X)）的映射。而且从表达式中可以知道：随机变量不确定性越大，$p(x)$越小，熵值越大。由此，熵是随机变量不确定性的度量。一种极限情况是：当随机变量退化为定值时（概率为1），那么此时的熵值为0。另一个极限就是：当随机变量服从均匀分布的时候，此时的熵值最大。

让我们以较为熟悉的随机变量分布来举例说明信息熵：

两点分布的熵

假设两点分布中$p(X=1)=q$，直接将概率分布函数代入信息熵公式可得：

$${\rm{H(X) = }} - \sum_{x \in X} {p(x)} \ln (p(x)) = - q\ln q - (1 - q)\ln (1 - q)$$
通过随机采样可以得到图像：

通过对图像的分析可以印证我们之前的结论：当$p(X=1)=0.5$，二点分布即为均匀分布，此时对应于图像中熵的最大值；当$p(X=1)=1$或$p(X=1)=0$时，二点分布退化为确定性分布，那么此时的熵为0.

联合熵、条件熵和相对熵

之前定义了单个随机变量的熵，现在将定义推广到两个随机变量的情形。对于服从联合分布为$p(x,y)$的一对离散随机变量$(X,Y)$ ,其联合熵定义为：

$$H(X,Y) = - \sum_{x \in X,y \in Y} {p(x,y)} \ln (p(x,y))$$
上式也可以表示为：
$$H(X,Y) = - E(\log p(x,y)).$$
我们也可以定义一个随机变量在给定另一个随机变量下的条件熵，它是条件分布上关于起条件作用的那个随机变量取平均之后的期望值。

定义：若 $(X,Y)\sim p(x,y)$，条件熵定义为：

$$\begin{array}{l} H(Y|X) &= \sum_{x \in X} {p(x)H(Y|X = x)} \\ &= - \sum_{x \in X} {p(x)} \sum_{y \in Y} {p(y|x)\log p(y|x)} \\ &= - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(y|x)} } \end{array}$$
联合熵和条件熵的定义的这个自然性可由一个事实得到体现：一对随机变量的熵等于其中一个随机变量的熵加上另一个随机变量的条件熵，即： $H(X,Y) = H(X) + H(Y|X)$（链式法则）。其证明见如下：
$$\begin{array}{l} H(X,Y) &= - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x,y)} } \\ &= - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x)p(y|x)} } \\ &= - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x)} } - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(y|x)} } \\ &= - \sum_{x \in X} {p(x)\log p(x)} - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(y|x)} } \\ &= H(X) + H(Y|X) \end{array}$$
相对熵是两个随机分布之间距离的度量。假设$p(x),q(x)$ 是随机变量$X$中取不同值时的两个概率分布，那么 $p$对$q$的相对熵是：
$$D\left( {p||q} \right) = \sum_x {p\left( x \right)\log \frac{{p\left( x \right)}}{{q\left( x \right)}}} = {E_{p\left( x \right)}}\log \frac{{p\left( x \right)}}{{q\left( x \right)}}$$
在上述定义中，我们约定：$0\log \frac{0}{0} = 0{,_{}}0\log \frac{0}{q} = 0{,^{}}0\log \frac{p}{0} = \infty$（基于连续性）。因此，如果存在$x\in X$使得$p(x) > 0,q(x) = 0$，则有$D\left( {p||q} \right) = \infty$。
可以通过证明知道相对熵总是非负的，而且，当且仅当 $p=q$时为零。但是由于相对熵并不对称（一般$D\left( {p||q} \right) \ne D\left( {q||p} \right)$ ），而且也不满足三角不等式，因此它实际上并不是两个分布之间的真正距离。然而，将相对熵视作分布之间的“距离”往往会很有用。

互信息

互信息是一个随机变量包含另一个随机变量信息量的度量。互信息也是在给定另一个随机变量知识的条件下，原随机变量不确定度的缩减量。（为什么这么说，接下来会有解释。）
定义：考虑两个随机变量$X$和$Y$，它们的联合概率密度函数为$p(x,y)$，其边缘概率密度函数分别为$p(x),p(y)$。互信息$I(x,y)$为联合分布$p(x,y)$和乘积分布 $p(x)p(y)$之间的相对熵，即：

$$\begin{array}{l} I(X;Y) &= \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log \frac{{p(x,y)}}{{p(x)p(y)}}} } \\ &= D(p(x,y)||(p(x)p(y)))\\ &= {E_{p(x,y)}}\log \frac{{p(X,Y)}}{{p(X)p(Y)}} \end{array}$$
通过查看表达式，即可知道互信息具有对称性，即 。同样可以简单证明得互信息的非负性，这里省略。

熵与互信息的关系

可将互信息$I(x,y)$重新写为：

$$\begin{array}{l} I(X;Y) &= \sum_{x \in X,y \in Y} {p(x,y)\log \frac{{p(x,y)}}{{p(x)p(y)}}} \\ &= \sum_{x \in X,y \in Y} {p(x,y)\log \frac{{p(x|y)}}{{p(x)}}} \\ &= - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x)} } + \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x|y)} } \\ & = - \sum_{x \in X} {p(x)\log p(x)} - ( - \sum_{x \in X} {\sum_{y \in Y} {p(x,y)\log p(x|y)} } )\\ &= H(X) - H(X|Y) \end{array}$$
由此可见，互信息息$I(x,y)$是在给定另一个随机变量$Y$知识的条件下，$X$ 不确定度的缩减量。

由于互信息的对称性，可得：

$$I(X;Y) = I(Y;X){\rm{ = }}H(Y) - H(Y|X)$$
由于之前已经得到表达式$H(X,Y) = H(X) + H(Y|X)$，代入上式可得：
$$I(X;Y) = H(X) + H(Y) - H(X,Y)$$
我们把之前的一些重要表达式都放在一块：
$$\begin{array}{l} I(X;Y) = H(X) - H(X|Y)\\ I(X;Y) = H(Y) - H(Y|X)\\ I(X;Y) = H(X) + H(Y) - H(X,Y)\\ I(X;Y) = I(Y;X) \end{array}$$
实际上，韦恩图可以很好地表示以上各变量之间的关系，对着上面的公式，应该可以很好理解下面的图表达的含义。

---

最大熵模型

当我们需要对一个随机事件的概率分布做出预测的时候，我们的预测应当满足全部一致的条件，而对未知的情况不要做任何主观的假设。在这种情况下，概率分布最均匀，预测的风险最小。因为这个时候分布的信息熵是最大的，所以人们称满足上述条件要求的模型就是“最大熵模型”。“最大熵模型”的核心两点：1.承认已知事物（或知识）；2.对未知事物不做任何假设，没有任何偏见。 It agrees with everything that is known, but carefully avoids assuming anything that is not known.

我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素说法，因为当我们遇到不确定性时，就要保留各种可能性。说白了，就是保留全部的不确定性，将风险降到最小。--摘自《Google黑板报》作者：吴军。

如何引入最大熵模型呢？我们使用NLP（自然语言处理）中的例子来说明：
“学习”这个词可能是动词，也可能是名词。另一方面，“学习”这个词可以被标为主语、谓语、宾语、定语。
令$x_1$表示“学习”被标成名词，$x_2$表示“学习”被标成动词。令$y_1$表示“学习”被标为主语，$y_2$ 表示被标为谓语，$y_3$表示宾语，$y_4$表示定语。得到下面的表示：

$$p({x_1}) + p({x_2}) = 1\\ \sum_{i = 1}^4 {p({y_i})} = 1$$
如果没有其他的知识，根据信息熵的理论，概率趋向于均匀。所以有：
$$p(x_1)=p(x_2)=0.5\\ p(y_1)=p(y_2)=p(y_3)=p(y_4)=0.25$$
但是在实际情况中，“学习”被标为定语的可能性很小，只有0.05。我们引入这个新的知识： ，在满足了这个约束的情况下，其他的事件我们尽可能的让他们符合自然，符合均匀分布（无偏原则）：
$$p(x_1)=p(x_2)=0.5\\ p(y_1)=p(y_2)=p(y_3)=\frac{0.95}{3}$$
再加入一个知识：当“学习”被标作动词的时候，它被标作谓语的概率为0.95。这个其实是很自然的事情。都已经是动词了，那么是谓语的可能性就很大了：
$$p({y_2}|{x_1}) = 0.95$$
已经有了两个知识了，第二个还是条件概率相关的知识。就像最大熵模型的核心两点所述，已知的知识点我需要承认，未知的部分不做任何假设，保持无偏（让概率尽量分布平均）。我们现在需要做的就是：在满足这两个已知知识点的前提下，让剩余的概率符合尽可能的均匀分布。可以想象，随着已知的知识点越来越多，其实也就是约束越来越多，求解的过程会变得越来越复杂。那么该怎么做呢？其实就是使得熵尽可能的大就行了。写成表达式即为：

我们要一个$x$和$y$ 的分布，满足：

$$\begin{array}{l} p(x_1) + p(x_2) = 1~~~ \sum_{i = 1}^4 p({y_i}) = 1\\ p({y_2}|{x_1}) = 0.95~~~ p({y_4}) = 0.05 \end{array}$$
而且使得$H(Y|X)$达到最大值。

以上表达中，一般我们用$H(Y|X)$，其实这跟用$H(X,Y)$ 是一个效果。因为根据之前推导可得$H(X,Y) = H(Y|X) + H(X)$,而$X$是训练集合，分布已经知道的（记住，我们认为训练集合是有代表性的），所以$H(X)$ 是一个定值。由此，令$H(Y|X)$最大相当于令$H(X,Y)$ 最大。
最后的数学表达式为：

$$\begin{array}{l} \max H(Y|X) = - \sum_{x,y} {p(x,y)\log p(y|x)} \\ ~~~~~~~~~~~~~~~~p({x_1}) + p({x_2}) = 1\\ p({y_1}) + p({y_2}) + p({y_3}) + p({y_4}) = 1\\ ~~~~~~~~~~~~~~~~~~~~~~~~p({y_4}) = 0.05\\ ~~~~~~~~~~~~~~~~~~~~p({y_2}|{x_1}) = 0.95\\ \end{array}$$

上面的表达式仅仅针对某一个NLP的特例。最大熵模型Maxent(Maximum Entropy)的一般式为：

$$\mathop {\max }_{p \in P} H(Y|X) = - \sum_{\left( {x,y} \right)} {p(x,y)\log p(y|x)}$$
其中,$P=\{p|p是X上满足条件的概率分布\}$ 。注意区分这里的$P$和$p$。

---

为了进一步说明最大熵模型在NLP中的应用，我们给出一些在NLP中的常用的定义，以此推出最大熵模型的一个约束条件的具体表达式：

• 特征：$(x,y)$
  $x$:这个特征中的上下文信息（已知部分）
  $y$:这个特征中需要确定的信息（未知部分）
• 样本：关于某个特征$(x,y)$的样本，特征所描述的语法现象在标准集合里的分布；
  也就是$(x_i,y_i)$对，形如：$(x_1,y_1),(x_2,y_2),(x_3,y_3)...$ 其中$y_i$是$y$的一个实例，$x_i$是$y_i$的上下文信息。
• 特征函数：对于一个特征$(x_i,y_i)$，定义特征函数：
  $$f\left( {x,y} \right) = \left\{ {\begin{array}{*{20}{c}} 1&{x = {x_i}~and~y = {y_i}}\\ 0&{else} \end{array}} \right.$$
  这个特征函数很简单，只有当$x = {x_i}~and~y = {y_i}$ 时候为1，其他均为0。该函数为接下来的样本特征期望值做铺垫。
• 样本特征函数期望值：对于一个特征$(x_i,y_i)$，在样本中的特征函数期望值是：
  $$\bar p(f) = \sum_{({x_i},{y_i})} {\bar p(x,y)f(x,y)}$$
  其中$\bar p(x,y)$是$(x,y)$在样本中出现的概率。由特征函数的定义，可以很好理解上式，求解的即为特征$(x_i,y_i)$在样本中出现的概率,也可以看成是特征函数的期望值。

条件Constraints:
对每个特征$(x,y)$，模型所建立的特征函数的期望值必须与训练样本特征函数期望值相等，即$p(f){\rm{ = }}\bar p(f)$。

特征$f$在模型中的特征函数期望值为：

$$p(f) = \sum_{({x_i},{y_i})} {\bar p(x)p(y|x)f(x,y)}$$
其中，$\bar p(x)$表示样本中$x$出现的概率，而$p(y|x)$则是模型中需要求解的条件概率。
由条件Constraints中的要求，可得：$p(f){\rm{ = }}\bar p(f)$。即：
$$\sum_{({x_i},{y_i})} {\bar p(x)p(y|x)f(x,y)} = \sum_{({x_i},{y_i})} {\bar p(x,y)f(x,y)}$$
上面这个等式就是最大熵模型中的限制条件，那么最大熵模型的完整提法是：
$${p^*} = \arg \mathop {\max }_{p \in P} H(Y|X) = - \sum_{(x,y)} {p(x,y)\log p(y|x)} = - \sum_{(x,y)} {p(y|x)\bar p(x)\log p(y|x)} \\ 其中P = \{ p(y|x)|\forall {f_i}:\sum_{(x,y)} {\bar p(x)p(y|x){f_i}(x,y)} = \sum_{(x,y)} {\bar p(x,y){f_i}(x,y)} ,\forall x:\sum_y {p(y|x) = 1} \} \\ f_i表示特征函数。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$

求解最大熵模型

我们使用Lagrange乘子法来求解，该条件约束优化问题的Lagrange函数为：

$$\Lambda (p,\vec \lambda ) = H(Y|X) + \sum_{i = 1}^m {{\lambda _i}(E({f_i}) - \bar E({f_i}))} + {\lambda _0}{\rm{(}}\sum_y {p(y|x){\rm{ - }}1} )\\ $$
其中参数$p$表示$p(y|x)$,$\vec \lambda$表示$\lambda$的向量形式，即：
$$L = \sum_{(x,y)} {p(y|x)\bar p(x)\log \frac{1}{{p(y|x)}}} + \sum_{i = 1}^m {{\lambda _i}\sum_{(x,y)} {{f_i}(x,y)\left[ {\bar p(x)p(y|x) - \bar p(x,y)} \right]} + } {\lambda _0}\left[ {\sum_y {p(y|x){\rm{ - }}1} } \right]$$
按照Lagrange乘子法的思路，对参数$p$ 求偏导，可得：
$$\begin{array}{c} \frac{{\partial L}}{{\partial p(y|x)}} = \bar p(x)( - \log p(y|x) - 1) + \sum_{i = 1}^m {{\lambda _i}} \bar p(x){f_i}(x,y) + {\lambda _0}\mathop = ^\Delta 0\\ \Rightarrow {p^*}(y|x) = \exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y) + \frac{{{\lambda _0}}}{{\bar p(x)}} - 1} \right) = \exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y)} \right)\exp (\frac{{{\lambda _0}}}{{\bar p(x)}} - 1) \end{array}$$

可以看出$p^*(y|x)$表达式的第二个因子对应的是约束$\sum_y p^*(y|x) =1$。将$p^*(y|x)$表达式带入到$\sum_y p^*(y|x) = 1$，可求得：

$$\begin{array}{l} \sum_y {\exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y)} \right)\exp (\frac{{{\lambda _0}}}{{\bar p(x)}} - 1)} = 1\\ \exp (\frac{{{\lambda _0}}}{{\bar p(x)}} - 1) = \frac{1}{{\sum_y {\exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y)} \right)} }} \end{array}$$
令${Z_\lambda }(x) = \sum_y {\exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y)} \right)}$可得：
$$p^*(y|x) = \frac{1}{{{Z_\lambda }\left( x \right)}}\exp \left( {\sum_i {{\lambda _i}{f_i}(x,y)} } \right)$$

经过这个步骤，我们似乎已经求得了最优的最大熵模型中$p^*(y|x)$ 的表达式，但是，请注意的是参数$\vec \lambda$并没有求解得到，$p^*(y|x)$的表达式依赖于参数$\vec \lambda$ 。下一步，如果我们能够求解出$\vec \lambda$ ，那么问题才算真正解决。
关于参数$\vec \lambda$ 的求解，我们使用对偶函数来帮助我们解决。将已经求得的$p^*(y|x)$ 的表达式代入到Lagrange函数中，可得到以上问题的对偶函数$L(\lambda)$为

$$\begin{array}{l} \;\;\;\;\;L(\lambda )\\ = - \sum_{x,y} {p(y|x)\overline p (x)\log p(y|x)} + \sum_{i = 1}^k {{\lambda _i}\sum_{x,y} {{f_i}(x,y)\left[ {p(y|x)\overline p (x) - \overline p (x,y)} \right]} } + {\lambda _0}\left[ {\sum_y {p\left( {y|x} \right) - 1} } \right]\\ = - \sum_{x,y} {{p_\lambda }(y|x)\overline p (x)\log {p_\lambda }(y|x)} + \sum_{i = 1}^k {{\lambda _i}\sum_{x,y} {{f_i}(x,y)\left[ {{p_\lambda }(y|x)\overline p (x) - \overline p (x,y)} \right]} } \\ = - \sum_{x,y} {\overline p (x){p_\lambda }(y|x)\log {p_\lambda }(y|x)} + \sum_{i = 1}^k {\overline p (x){p_\lambda }(y|x){\lambda _i}\sum_{x,y} {{f_i}(x,y)} } - \sum_{i = 1}^k {\overline p (x,y){\lambda _i}\sum_{x,y} {{f_i}(x,y)} } \\ = - \sum_{x,y} {\overline p (x){p_\lambda }(y|x)\log {p_\lambda }(y|x)} + \sum_{x,y} {\overline p (x){p_\lambda }(y|x)} \sum_{i = 1}^k {{\lambda _i}} {f_i}(x,y) - \sum_{i = 1}^k {\overline p (x,y){\lambda _i}\sum_{x,y} {{f_i}(x,y)} } \\ = \sum_{x,y} {\overline p (x){p_\lambda }(y|x)} \log {Z_\lambda }\left( x \right) - \sum_{i = 1}^k {\overline p (x,y)\sum_{x,y} {{\lambda _i}{f_i}(x,y)} } \end{array}$$
上述表达式中，${Z_\lambda }(x) = \sum_y {\exp \left( {\sum_{i = 1}^m {{\lambda _i}} {f_i}(x,y)} \right)}$
因为没有显式的解析式，我们使用IIS (Improved Iterative Scaling) 改进的迭代尺度算法来计算最大熵模型的数值解。具体做法是：
假设最大熵模型当前的参数向量是$\vec \lambda$ ，希望能够找到新的参数向量$\vec \lambda+\delta$ ，使得对偶函数$L$增加。重复这个过程，直到找到对偶函数的最大值。
$$\begin{array}{l} L\left( {\lambda + \delta } \right) - L\left( \lambda \right)\\ = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) - \sum_x {\overline p \left( x \right)\log \frac{{{Z_{\lambda + \delta }}\left( x \right)}}{{{Z_\lambda }\left( x \right)}}} } } \\ \ge \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\frac{{{Z_{\lambda + \delta }}\left( x \right)}}{{{Z_\lambda }\left( x \right)}}} } } \\ = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\frac{{{Z_{\lambda + \delta }}\left( x \right)}}{{{Z_\lambda }\left( x \right)}}} } } \\ = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\exp \left( {\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right)} } \right)} } } \\ = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} \exp \left( {\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right)} } \right)} } } \end{array}$$
为进一步推导，我们打算针对凸函数$f(x) = {e^x}$使用Jensen不等式，令$f^\#(x,y)= \sum_{i = 1}^m f_i(x,y)$，可得：
$$\begin{array}{l} A(\delta |\lambda ) = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} \exp \left( {\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right)} } \right)} } } \\ = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} \exp \left( {{f^\# }\left( {x,y} \right)\sum_{i = 1}^n {\frac{{{\delta _i}{f_i}\left( {x,y} \right)}}{{{f^\# }\left( {x,y} \right)}}} } \right)} } } \\ \ge \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} \sum_{i = 1}^n {\frac{{{f_i}\left( {x,y} \right)}}{{{f^\# }\left( {x,y} \right)}}} \exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} } } \end{array}$$

接下来，对该下界求偏导，令偏导为0，求出相应的$\delta$。这么做的原因是：每一次迭代的$\delta$ 都能够令相邻两次迭代的函数值之间的差值$L(\lambda + \delta ) - L(\lambda )$尽可能大，也就是通过每一次迭代的$\delta$尽快达到$L$最大。令

$$B\left( {\delta |\lambda } \right) = \sum_{x,y} {\overline p \left( {x,y} \right)\sum_{i = 1}^n {{\delta _i}{f_i}\left( {x,y} \right) + 1 - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} \sum_{i = 1}^n {\frac{{{f_i}\left( {x,y} \right)}}{{{f^\# }\left( {x,y} \right)}}} \exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} } }$$
对$\delta$求偏导，得：
$$\begin{array}{l} \frac{{\partial B\left( {\delta |\lambda } \right)}}{{\partial {\delta _i}}} = \sum_{x,y} {\overline p \left( {x,y} \right){f_i}\left( {x,y} \right) - \sum_x {\overline p \left( x \right)\sum_y {{p_\lambda }\left( {y|x} \right)} {f_i}\left( {x,y} \right)\exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} } \\ = \sum_{x,y} {\overline p \left( {x,y} \right){f_i}\left( {x,y} \right) - \sum_{x,y} {\overline p \left( x \right){p_\lambda }\left( {y|x} \right){f_i}\left( {x,y} \right)\exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} } \\ = {E_{\bar p}}\left( {{f_i}} \right) - \sum_{x,y} {\overline p \left( x \right){p_\lambda }\left( {y|x} \right){f_i}\left( {x,y} \right)\exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} \end{array}$$
令偏导为0，得到：
$$\sum_{x,y} {\overline p \left( x \right){p_\lambda }\left( {y|x} \right){f_i}\left( {x,y} \right)\exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} {\rm{ - }}{E_{\bar p}}\left( {{f_i}} \right) = 0$$

分情况讨论：

• 若${f^\# }(x,y) = M$为常数，那么：
  $${\delta _i} = \frac{1}{M}\log \frac{{{E_{\bar p}}\left( {{f_i}} \right)}}{{{E_p}\left( {{f_i}} \right)}}$$
• 若${f^\# }(x,y)$不是常数，那么无法直接求得令偏导为0时候$\delta$的值，令偏导表示为
  $$g\left( {{\delta _i}} \right) = \sum_{x,y} {\overline p \left( x \right){p_\lambda }\left( {y|x} \right){f_i}\left( {x,y} \right)\exp \left( {{\delta _i}{f^\# }\left( {x,y} \right)} \right)} {\rm{ - }}{E_{\bar p}}\left( {{f_i}} \right)$$
  转化为求解$g({\delta _i}) = 0$ 的根。使用牛顿法：
  $${\delta _i}^{(k + 1)} = {\delta _i}^{(k)} - \frac{{g({\delta _i}^{(k)})}}{{g'({\delta _i}^{(k)})}}$$

因为需要计算$g({\delta _i}) = 0$的根而不是求$g({\delta _i})$ 的极小值，所以牛顿法中是函数值除以一阶导，而不是一阶导除以二阶导。实践中，可采用拟牛顿法BFGS解决。

将上述求解过程中得到的参数$\vec\lambda$，回代到下式中，即可得到最大熵模型的最优估计：

$$p*(y|x) = \frac{1}{{{Z_\lambda }\left( x \right)}}{e^{\sum_i {{\lambda _i}{f_i}(x,y)} }}\\ {Z_\lambda }\left( x \right) = \sum_y {{e^{\sum_i {{\lambda _i}{f_i}(x,y)} }}}$$

---

参考文献：

《统计学习方法》，李航著，清华大学出版社，2012年
A Mathematical Theory of Communication，shannon，1948