最大熵原理

原理简介

最大熵原理：学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。

直观地说，最大熵原理认为要选择的模型需要满足：

1. 已有的事实（约束条件）：必须满足
2. 不确定的部分：等可能

如何表示“等可能”呢？我们知道，均匀分布的熵最大，反过来讲，熵最大时，数据趋向于均匀分布，即等可能。因此，可以使用熵--可优化的数值目标，来实现“等可能”的要求。

最大熵原理是统计学习的一般原理，将它应用到分类得到最大熵模型(Maximum Entropy Model)。

例题

问题：假设随机变量$X$$X$有5个取值$A,B,C,D,E$${A,B,C,D,E}$，估计取各个值的概率$P(A),P(B),P(C),P(D),P(E)$$P(A),P(B),P(C),P(D),P(E)$。

$\text{解}$$解$ 概率值需要满足如下约束条件：

$P(A)+P(B)+P(C)+P(D)+P(E)=1$$P(A) + P(B) + P(C) + P(D) + P(E) = 1$

满足这个约束条件的概率分布有无穷多个。按照最大熵原理，在没有其它信息的情况下，需要假定等可能分布，即：

$P(A)=P(B)=P(C)=P(D)=P(E)=\frac{1}{5}$$P(A) = P(B) = P(C) = P(D) = P(E) = \frac{1}{5}$

有时，能从一些先验知识中得到一些对概率值的约束条件，如：

$\begin{array}{c}P(A)+P(B)+P(C)+P(D)+P(E)=1\\ P(A)+P(B)=\frac{3}{10}\end{array}$$P(A) + P(B) + P(C) + P(D) + P(E) = 1 \\ P(A) + P(B) = \frac{3}{10}$

满足这两个约束条件的概率分布依然有无穷多个。在缺少其它信息的情况下，可以认为$A、B$$A、B$是等概率的，$C、D、E$$C、D、E$是等概率的，于是：

$\begin{array}{c}P(A)=P(B)=\frac{3}{20}\\ P(C)=P(D)=P(E)=\frac{7}{20}\end{array}$$P(A) = P(B) = \frac{3}{20} \\ P(C) = P(D) = P(E) = \frac{7}{20}$

最大熵模型

模型定义

假设分类模型是一个条件概率分布$P(Y|X),X\in R^n,Y\in R$$P(Y|X), X \in R^n,Y \in R$，$X$$X$表示输入，$Y$$Y$表示输出。该模型表示的是对于给定的输入$X$$X$，以条件概率$P(Y|X)$$P(Y|X)$输出$Y$$Y$。

给定训练数据集：$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$$T=\{(x_1,y_1),(x_2,y_2), \cdots, (x_N,y_N) \}$

学习目标：使用最大熵原理选择最好的分类模型。

构造模型条件

对于给定的训练数据集，可以确定联合分布$P(X,Y)$$P(X,Y)$的经验分布和边缘分布$P(X)$$P(X)$的经验分布，分别记作$\tilde{P}(X,Y)$$\tilde{P}(X,Y)$和$\tilde{P}(X)$$\tilde{P}(X)$。

用特征函数$f(x,y)$$f(x,y)$描述输入$x$$x$和输出$y$$y$之间的某一事实，其定义为：

特征函数为二值函数，当$x$$x$和$y$$y$满足这个事实时取值为1，否则取值为0。

特征函数$f(x,y)$$f(x,y)$关于经验分布$\tilde{P}(X,Y)$$\tilde{P}(X,Y)$的期望值，用$E_{\tilde{P}}(f)$$E_{\tilde{P}}(f)$表示：

特征函数$f(x,y)$$f(x,y)$关于模型$P(Y|X)$$P(Y|X)$与经验分布$\tilde{P}(X)$$\tilde{P}(X)$的期望值，用$E_p(f)$$E_p(f)$表示：

如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即：

我们将$(7)$$(7)$式作为模型学习的约束条件。假设有$m$$m$个特征函数$f_i(x,y),i=1,2,\cdots ,m$$f_i(x,y), \quad i=1,2,\cdots,m$，那么就有$m$$m$个约束条件。

最大熵模型

假设满足所有约束条件的模型集合为：

定义在模型$P(Y\mid X)$$P(Y \mid X)$上的条件熵为：

则模型集合$\mathcal{C}$$\mathcal{C}$中条件熵最大$H(P)$$H(P)$的模型称为最大熵模型。

模型学习

最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$$T=\{(x_1,y_1),(x_2,y_2), \cdots, (x_N,y_N) \}$以及特征函数$f_i(x,y),i=1,2,\cdots ,m$$f_i(x,y), \quad i=1,2,\cdots,m$，最大熵模型的学习等价于约束最优化问题：

按照最优化问题的习惯，将求max问题改为等价的求min问题：

对于上述原始的最优化问题，可以转为无约束最优化的对偶问题，通过求解对偶问题进而求解原始问题。

1. 构建拉格朗日函数

   引入拉格朗日乘子$w_0,w_1,w_2,\cdots ,w_m$$w_0,w_1,w_2, \cdots, w_m$，定义拉格朗日函数$L(P,w)$$L(P, w)$：

   $$\begin{array}{}\text{(10)}& \begin{array}{rl}L(P,w)\equiv & -H(P)+w_0(1-\sum _{y}P(y\mid x))+\sum _{i=1}^m{w}_i(E_{\overline{p}}\left(f_i\right)-E_P\left(f_i\right))\\ =& \sum _{x,y}\tilde{P}(x)P(y\mid x)\log P(y\mid x)\\ & +w_0(1-\sum _{y}P(y\mid x))\\ & +\sum _{i=1}^m{w}_i(\sum _{x,y}\tilde{P}(x,y)f_i(x,y)-\sum _{x,y}\tilde{P}(x)P(y\mid x)f_i(x,y))\end{array}\end{array}$$

2. 定义对偶问题

   最优化的原始问题为：

   $$\begin{array}{}\text{(11)}& \underset{P\in \mathcal{C}}{min}\underset{w}{max}L(P,w)\end{array}$$

   对偶问题是：

   $$\begin{array}{}\text{(12)}& \underset{w}{max}\underset{P\in \mathcal{C}}{min}L(P,w)\end{array}$$

3. 求对偶问题中的极小化问题

   首先需要求解对偶问题内部的最小化问题$\underset{P\in \mathcal{C}}{min}L(P,w)$$\underset{P \in \mathcal{C}}{min} \; L(P, w)$，$\underset{P\in \mathcal{C}}{min}L(P,w)$$\underset{P \in \mathcal{C}}{min} \; L(P, w)$是$w$$w$的函数，将其记作：

   $$\begin{array}{}\text{(13)}& \mathrm{\Psi }(w)=\underset{P\in \mathbf{C}}{min}L(P,w)=L(P_w,w)\end{array}$$

   $\mathrm{\Psi }(w)$$\Psi(w)$称为对偶函数，同时，将其解记作：

   $$\begin{array}{}\text{(14)}& P_w=\arg \underset{P\in \mathbf{C}}{min}L(P,w)=P_w(y\mid x)\end{array}$$

   具体地，为了求$\mathrm{\Psi }(w)$$\Psi(w)$的最小值， 求$L(p,w)$$L(p, w)$对$P(y\mid x)$$P(y \mid x)$的偏导数：

   $$\begin{array}{}\text{(15)}& \begin{array}{rl}\frac{\partial L(P,w)}{\partial P(y\mid x)}& =\sum _{x,y}\tilde{P}(x)(\log P(y\mid x)+1)-\sum _y{w}_0-\sum _{x,y}(\tilde{P}(x)\sum _{i=1}^m{w}_i{f}_i(x,y))\\ & =\sum _{x,y}\tilde{P}(x)(\log P(y\mid x)+1-w_0-\sum _{i=1}^m{w}_i{f}_i(x,y))\end{array}\end{array}$$

   令偏导数等于0，在$\tilde{P}(x)>0$$\tilde{P}(x) > 0$ 的情况下，解得：

   $$\begin{array}{}\text{(16)}& P(y\mid x)=\exp (\sum _{i=1}^m{w}_i{f}_i(x,y)+w_0-1)=\frac{\exp (\sum _{i=1}^m{w}_i{f}_i(x,y))}{\exp (1-w_0)}\end{array}$$

   由于$\sum _{y}P(y\mid x)=1$$\sum_y P(y \mid x) = 1$,两边求和得：

   $$\begin{array}{}\text{(17)}& \begin{array}{c}{P}_w(y\mid x)=\frac{1}{Z_w(x)}\exp (\sum _{i=1}^m{w}_i{f}_i(x,y))\\ \text{其}\text{中}，Z_w(x)=\sum _y\exp (\sum _{i=1}^m{w}_i{f}_i(x,y))\\ Z_w(x)\text{称}\text{为}\text{规}\text{范}\text{化}\text{因}\text{子}，f_i(x,y)\text{是}\text{特}\text{征}\text{函}\text{数}，w_i\text{是}\text{特}\text{征}\text{的}\text{权}\text{值}\end{array}\end{array}$$

   $P_w=P_w(y\mid x)$$P_w = P_w(y \mid x)$就是最大熵模型，$w$$w$是最大熵模型中的参数向量。

4. 求对偶问题中的极大化问题

   求解对偶问题外部的极大化问题：

   $$\begin{array}{}\text{(18)}& \underset{w}{max}\mathrm{\Psi }(w)\end{array}$$

   将其解记为$w^{\ast }$$w^*$，即：

   $$\begin{array}{}\text{(19)}& w^{\ast }=\underset{w}{\arg max}\mathrm{\Psi }(w)\end{array}$$

   因此， 可以使用最优化问题求解对偶函数$\mathrm{\Psi }(w)$$\Psi(w)$的极大化，得到$w^{\ast }$$w^*$，从而可以得到最优化模型$P^{\ast }$$P^*$，这里，$P^{\ast }=P_{w^{\ast }}=P_{w^{\ast }}(y\mid x)$$P^* = P_{w^*} = P_{w^*}(y \mid x)$是学习到的最优化模型（最大熵模型）。

对上述总结，最大熵模型的一般形式为：

极大似然估计

已知训练数据的经验概率分布$\tilde{P}(X,Y)$$\tilde{P}(X,Y)$，条件概率分布$P(Y\mid X)$$P(Y \mid X)$的对数似然函数表示为：

当条件概率分布$P(y\mid x)$$P(y \mid x)$是最大熵模型的解（$\text{公}\text{式}17$$公式17$）时，对数似然函数$L_{\tilde{P}}\left(P_w\right)$$L_{\tilde{P}}\left(P_{w}\right)$为：

根据$\text{公}\text{式}17$$公式17$，对偶函数$\mathrm{\Psi }(w)$$\Psi(w)$可化简为：

比较$\text{式}(21)$$式(21)$和$\text{式}(22)$$式(22)$，可得：

因此，对偶函数$\mathrm{\Psi }(w)$$\Psi(w)$等价于对数似然函数$L_{\tilde{P}}\left(P_w\right)$$L_{\tilde{P}}\left(P_{w}\right)$。因此，最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

模型学习的最优化算法

已知最大熵模型为：

最大熵模型的对数似然函数为：

目标：通过极大似然法估计模型参数，即求使得对数函数达到极大的$w^{\ast }$$w^*$。

改进的迭代尺度法

改进的迭代尺度法 (improved iterative scaling, IIS) 是一种最大熵模型学习的最优化算法。

IIS的思想：

1. 初始化最大熵模型的参数向量：$w=(w_1,w_2,\cdots ,w_n{)}^T$$w = (w_1,w_2,\cdots,w_n)^T$。
2. 找到新的参数向量：$w+\delta =(w_1+{\delta }_1,w_2+{\delta }_2,\cdots ,w_n+{\delta }_n)$$w+\delta = (w_1+\delta_1,w_2+\delta_2,\cdots,w_n+\delta_n)$，使得模型的对数似然函数值增大。
3. 重复$\text{步}\text{骤}2$$步骤2$，迭代更新参数 $w=w+\delta$$w = w + \delta$，直到满足退出条件。

推导过程：

1. 寻找下界函数1

   对于给定的经验分布$\tilde{P}(x,y)$$\tilde{P}(x, y)$，模型参数从$w$$w$增加到$w+\delta$$w+\delta$，对数似然函数的改变量是：

   $$\begin{array}{}\text{(27)}& \begin{array}{rl}L(w+\delta )-L(w)& =\sum _{x,y}\tilde{P}(x,y)\log P_{w+\delta }(y\mid x)-\sum _{x,y}\tilde{P}(x,y)\log P_w(y\mid x)\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)-\sum _x\tilde{P}(x)\log \frac{Z_{w+\delta }(x)}{Z_w(x)}\end{array}\end{array}$$

   利用不等式：$-\log \alpha \ge 1-\alpha ,\alpha >0$$-\log \alpha \geq 1 - \alpha,\quad \alpha > 0$

   建立对数似然函数改变量的下界：

   $$\begin{array}{}\text{(28)}& \begin{array}{rl}L(w+\delta )-L(w)& ⩾\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\sum _x\tilde{P}(x)\frac{Z_{w+\delta }(x)}{Z_w(x)}\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)\exp \sum _{i=1}^m{\delta }_i{f}_i(x,y)\end{array}\end{array}$$

   将右端记为：

   $$\begin{array}{}\text{(29)}& A(\delta \mid w)=\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)\exp \sum _{i=1}^m{\delta }_i{f}_i(x,y)\end{array}$$

   于是有：

   $$\begin{array}{}\text{(30)}& L(w+\delta )-L(w)\ge A(\delta \mid w)\end{array}$$

   即$A(\delta \mid w)$$A(\delta \mid w)$是对数似然函数改变量的一个下界。

   然而，若对$A(\delta \mid w)$$A(\delta \mid w)$求${\delta }_i$$\delta_i$的导数，由于$g=\exp \sum _{i=1}^m{\delta }_i{f}_i(x,y)=\prod _{i=1}^m\exp ({\delta }_i{f}_i(x,y))$$g = \exp \sum_{i=1}^{m} \delta_{i} f_{i}(x, y) = \prod_{i=1}^{m} \exp \left ( \delta_{i} f_{i}(x, y) \right )$，那么$\frac{\partial g}{\partial {\delta }_i}=\prod _{i=1}^m\exp ({\delta }_i{f}_i(x,y))$$\large \frac{\partial g}{\partial \delta_i} = \prod_{i=1}^{m} \exp \left ( \delta_{i} f_{i}(x, y) \right )$ 的结果耦合了多个${\delta }_i$$\delta_i$，导致不易优化。为了能够继续优化，IIS试图一次只优化其中一个变量${\delta }_i$$\delta_i$，而固定其它变量${\delta }_j,i\ne j$$\delta_j, \; i \neq j$。

2. 寻找下界函数2

   引入变量$f^{\mathrm{\#}}(x,y)=\sum _{i=1}^m{f}_i(x,y)$$f^{\#}(x,y) = \sum_{i=1}^{m} f_i(x,y)$。因为$f_i$$f_i$是二值函数，故$f^{\mathrm{\#}}(x,y)$$f^{\#}(x,y)$表示所有特征在$(x,y)$$(x,y)$出现的次数。

   将$A(\delta \mid w)$$A(\delta \mid w)$进行改写：

   $$\begin{array}{}\text{(31)}& \begin{array}{rl}A(\delta \mid w)=& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)\exp (f^{\mathrm{\#}}(x,y)\sum _{i=1}^m\frac{{\delta }_i{f}_i(x,y)}{f^{\mathrm{\#}}(x,y)})\end{array}\end{array}$$

   利用指数函数的凸性以及对任意$i$$i$，有$\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}\ge 0\text{且}\sum _{i=1}^m\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}=1$$\large \frac{f_i(x,y)}{f^{\#}(x,y)} \geq 0 且 \sum_{i=1}^{m} \frac{f_i(x,y)}{f^{\#}(x,y)} = 1$，根据Jensen不等式，得到：

   $$\begin{array}{}\text{(32)}& \exp (\sum _{i=1}^m\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}{\delta }_i{f}^{\mathrm{\#}}(x,y))⩽\sum _{i=1}^m\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))\end{array}$$

   于是：

   $$\begin{array}{}\text{(33)}& \begin{array}{rl}A(\delta \mid w)⩾& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\\ & \sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)\sum _{i=1}^m\left(\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}\right)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))\end{array}\end{array}$$

   记不等式右侧为：

   $$\begin{array}{}\text{(34)}& \begin{array}{rl}B(\delta \mid w)=& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^m{\delta }_i{f}_i(x,y)+1-\\ & \sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)\sum _{i=1}^m\left(\frac{f_i(x,y)}{f^{\mathrm{\#}}(x,y)}\right)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))\end{array}\end{array}$$

   于是得到：

   $$\begin{array}{}\text{(35)}& L(w+\delta )-L(w)\ge B(\delta \mid w)\end{array}$$

   这里，$B(\delta \mid w)$$B(\delta \mid w)$为对数似然函数改变量的一个新的下界。

    

   求$B(\delta \mid w)$$B(\delta \mid w)$对${\delta }_i$$\delta_i$的偏导数：

   $$\begin{array}{}\text{(36)}& \frac{\partial B(\delta \mid w)}{\partial {\delta }_i}=\sum _{x,y}\tilde{P}(x,y)f_i(x,y)-\sum _x\tilde{P}(x)\sum _y{P}_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))\end{array}$$

   在上式中，除${\delta }_i$$\delta_i$外不含任何其它变量。令偏导数为0得到：

   $$\begin{array}{}\text{(37)}& \sum _{x,y}\tilde{P}(x)P_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))=E_{\tilde{P}}\left(f_i\right)\end{array}$$

   于是，根据上式可依次求解${\delta }_i$$\delta_i$，求得$\delta$$\delta$后，可进一步得到$w$$w$，从而可以重复迭代过程。

    

   基于上述推导，给出改进的迭代尺度法IIS。

   $\text{算}\text{法}1.1(\text{改}\text{进}\text{的}\text{迭}\text{代}\text{尺}\text{度}\text{法}\mathbf{IIS})$$算法1.1 (改进的迭代尺度法 \mathbf{IIS})$

   $\text{输}\text{入}：\text{特}\text{征}\text{函}\text{数}{f}_1,f_2,\cdots ,f_m;\text{经}\text{验}\text{分}\text{布}\tilde{P}(X,Y);\text{模}\text{型}{P}_w(y\mid x)$$输入：特征函数f_1,f_2,\cdots,f_m;经验分布 \tilde{P}(X,Y);模型 P_w(y \mid x)$

   $\text{输}\text{出}：\text{最}\text{优}\text{参}\text{数}\text{值}{w}_i^{\ast };\text{最}\text{优}\text{模}\text{型}{P}_{w^{\ast }}$$输出：最优参数值w_i^*; 最优模型 P_{w^*}$

   $\text{算}\text{法}\text{步}\text{骤}：$$算法步骤：$

   1. $\text{对}\text{所}\text{有}\text{的}i\in \{1,2,\cdots ,n\}，\text{取}\text{初}\text{值}{w}_i=0$$对所有的 i \in \{1,2,\cdots,n \}，取初值 w_i = 0$

   2. $\text{对}\text{每}\text{一}\text{个}i\in \{1,2,\cdots ,n\}$$对每一个 i \in \{1,2,\cdots,n \}$

      1. $\begin{array}{c}\text{令}{\delta }_i\text{是}\text{方}\text{程}\sum _{x,y}\tilde{P}(x)P_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))=E_{\tilde{P}}\left(f_i\right)\text{的}\text{解}。\\ \text{其}\text{中}，f^{\mathrm{\#}}(x,y)=\sum _{i=1}^m{f}_i(x,y)\end{array}$$令 \delta_i 是方程 \sum_{x, y} \tilde{P}(x) P_{w}(y \mid x) f_{i}(x, y) \exp \left(\delta_{i} f^{\#}(x, y)\right)=E_{\tilde{P}}\left(f_{i}\right) 的解。 \\ 其中，f^{\#}(x,y) = \sum_{i=1}^{m} f_i(x,y)$
      2. $\text{更}\text{新}{w}_i\text{的}\text{值}：w_i\leftarrow w_i+{\delta }_i$$更新 w_i 的值：w_i \leftarrow w_i + \delta_i$

   3. $\text{如}\text{果}\text{不}\text{是}\text{所}\text{有}\text{的}{w}_i\text{都}\text{收}\text{敛}，\text{重}\text{复}\text{步}\text{骤}(2)$$如果不是所有的 w_i 都收敛，重复步骤(2)$

    

   算法的核心是求解${\delta }_i$$\delta_i$。分以下情况进行讨论：

   1. $f^{\mathrm{\#}}(x,y)\text{是}\text{常}\text{数}$$f^{\#}(x,y)是常数$

      即对任何$x,y$$x,y$，有$f^{\mathrm{\#}}(x,y)=M$$f^{\#}(x,y) = M$，那么${\delta }_i$$\delta_i$可以显式地表示为：

      $$\begin{array}{}\text{(38)}& {\delta }_i=\frac{1}{M}\log \frac{E_{\tilde{P}}\left(f_i\right)}{E_P\left(f_i\right)}\end{array}$$

   2. $f^{\mathrm{\#}}(x,y)\text{不}\text{是}\text{常}\text{数}$$f^{\#}(x,y) 不是常数$

      必须通过数值法求解${\delta }_i$$\delta_i$，简单有效的方法是牛顿法。令$g({\delta }_i)=\sum _{x,y}\tilde{P}(x)P_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))=E_{\tilde{P}}\left(f_i\right)$$g(\delta_i) = \sum_{x, y} \tilde{P}(x) P_{w}(y \mid x) f_{i}(x, y) \exp \left(\delta_{i} f^{\#}(x, y)\right)=E_{\tilde{P}}\left(f_{i}\right)$，牛顿法通过迭代求得${\delta }_i^{\ast }$$\delta_i^*$，使得$g({\delta }_i^{\ast })=0$$g(\delta_i^*) = 0$，迭代公式是：

      $$\begin{array}{}\text{(39)}& {\delta }_i^{(k+1)}={\delta }_i^{(k)}-\frac{g\left({\delta }_i^{(k)}\right)}{g^{\prime }\left({\delta }_i^{(k)}\right)}\end{array}$$

      只要适当选取初始值${\delta }_i^{(0)}$$\delta_i^{(0)}$，由于$g({\delta }_i)$$g(\delta_i)$有单根，因此牛顿法恒收敛，而且收敛速度很快。

    

拟牛顿法

最大熵模型：

目标函数：

梯度：

其中，梯度具体为：

相应的拟牛顿法BFGS算法如下。

$\text{算}\text{法}1.2(\text{最}\text{大}\text{熵}\text{模}\text{型}\text{学}\text{习}\text{的}\mathbf{BFGS}\text{算}\text{法})$$算法1.2 (最大熵模型学习的 \mathbf{BFGS} 算法)$

$\text{输}\text{入}：\text{特}\text{征}\text{函}\text{数}{f}_1,f_2,\cdots ,f_m;\text{经}\text{验}\text{分}\text{布}\tilde{P}(X,Y);\text{目}\text{标}\text{函}\text{数}f(w);\text{梯}\text{度}g(w)=\mathrm{\nabla }f(w),\text{ 精度要求 }\epsilon$$输入：特征函数f_1,f_2,\cdots,f_m;经验分布 \tilde{P}(X,Y);目标函数 f(w);梯度 g(w) = \nabla f(w), \text { 精度要求 } \varepsilon$

$\text{输}\text{出}：\text{最}\text{优}\text{参}\text{数}\text{值}{w}^{\ast };\text{最}\text{优}\text{模}\text{型}{P}_{w^{\ast }}(y\mid x)$$输出：最优参数值w^*; 最优模型 P_{w^*}(y \mid x)$

$\text{算}\text{法}\text{步}\text{骤}：$$算法步骤：$

1. $\text{选}\text{定}\text{初}\text{始}\text{点}{w}^{(0)}，\text{取}{B}_0\text{为}\text{正}\text{定}\text{对}\text{称}\text{矩}\text{阵}，\text{置}k=0$$选定初始点 w^{(0)}， 取 B_0 为正定对称矩阵，置 k=0$
2. $\text{计}\text{算}{g}_k=g(w^{(k)})。\text{ 若 }\Vert g_k\Vert <\epsilon \text{, 则停止计算, 得 }{w}^{\ast }=w^{(k)}\text{; 否则转 }(3)\text{; }$$计算 g_k = g(w^{(k)})。\text { 若 }\left\|g_{k}\right\|<\varepsilon \text {, 则停止计算, 得 } w^{*}=w^{(k)} \text {; 否则转 }(3) \text {; }$
3. $\text{ 由 }{B}_k{p}_k=-g_k\text{ 求出 }{p}_k\text{; }$$\text { 由 } B_{k} p_{k}=-g_{k} \text { 求出 } p_{k} \text {; }$
4. $\begin{array}{c}\text{一}\text{维}\text{搜}\text{索}：\text{求}{\lambda }_k\text{使}\text{得}：\\ f(w^{(k)}+{\lambda }_k{p}_k)=\underset{\lambda ⩾0}{min}f(w^{(k)}+\lambda p_k)\end{array}$$一维搜索：求 \lambda_k 使得： \\ f\left(w^{(k)}+\lambda_{k} p_{k}\right)=\min _{\lambda \geqslant 0} f\left(w^{(k)}+\lambda p_{k}\right)$
5. $\text{ 置 }{w}^{(k+1)}=w^{(k)}+{\lambda }_k{p}_k\text{; }$$\text { 置 } w^{(k+1)}=w^{(k)}+\lambda_{k} p_{k} \text {; }$
6. $\begin{array}{c}\text{计}\text{算}{g}_{k+1}=g\left(w^{(k+1)}\right)，\text{若}\Vert g_{k+1}\Vert <\epsilon ，\text{则}\text{停}\text{止}\text{计}\text{算}，\text{得}{w}^{\ast }=w^{(k+1)}；\text{否}\text{则}，\text{按}\text{下}\text{式}\text{求}\text{出}{B}_{k+1}：\\ B_{k+1}=B_k+\frac{y_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}{\delta }_k}-\frac{B_k{\delta }_k{\delta }_k^{\mathrm{T}}{B}_k}{{\delta }_k^{\mathrm{T}}{B}_k{\delta }_k}，\\ \text{其}\text{中}，\\ y_k=g_{k+1}-g_k,{\delta }_k=w^{(k+1)}-w^{(k)}\end{array}$$计算 g_{k+1} = g \left(w^{(k+1)} \right)，若 \left\|g_{k+1}\right\|<\varepsilon ，则停止计算，得 w^{*}=w^{(k+1)}；否则，按下式求出 B_{k+1}： \\ \large B_{k+1}=B_{k}+\frac{y_{k} y_{k}^{\mathrm{T}}}{y_{k}^{\mathrm{T}} \delta_{k}}-\frac{B_{k} \delta_{k} \delta_{k}^{\mathrm{T}} B_{k}}{\delta_{k}^{\mathrm{T}} B_{k} \delta_{k}}， \\ 其中， \\ y_{k}=g_{k+1}-g_{k}, \quad \delta_{k}=w^{(k+1)}-w^{(k)}$
7. $\text{置}k=k+1，\text{转}(3)。$$置 k=k+1，转(3)。$

例题：最大熵模型学习

问题：假设随机变量$X$$X$有5个取值$A,B,C,D,E$${A,B,C,D,E}$，已知$P(A)+P(B)=\frac{3}{10}$$P(A) + P(B) = \frac{3}{10}$，估计取各个值的概率$P(A),P(B),P(C),P(D),P(E)$$P(A),P(B),P(C),P(D),P(E)$。

$\text{解}$$解$ 为了方便，分别以$y_1,y_2,y_3,y_4,y_5$$y_1,y_2,y_3,y_4,y_5$表示$A,B,C,D,E$${A,B,C,D,E}$。于是，最大熵模型学习的最优化问题是：

引入拉格朗日乘子$w_0、w_1$$w_0、w_1$，定义拉格朗日函数：

根据拉格朗日对偶性，可以通过求解对偶最优化问题得到原始最优化问题的解，因此，接下来求解：

首先求解$L(P,w)$$L(P,w)$关于$P$$P$的极小化问题。为此，固定$w_0、w_1$$w_0、w_1$，求偏导数：

令各偏导数等于0，解得：

于是：

再求解$L(P_w,w)$$L(P_w,w)$关于$w$$w$的极大化问题：

分别求$L(P_w,w)$$L(P_w,w)$对$w_0、w_1$$w_0、w_1$的偏导数并令其为0，得到：

于是，得到所要求的概率分布为：

参考文档

1. (52条消息) 最大熵模型中的对数似然函数的解释_wkebj的博客-CSDN博客
2. 为什么最大熵模型的极大似然估计中带有指数？ - 知乎 (zhihu.com)
3. 最大熵模型中的对数似然函数表示法解释 - 知乎 (zhihu.com)
4. (52条消息) 最大熵模型中的数学推导_结构之法 算法之道-CSDN博客