统计机器学习-逻辑斯谛回归与最大熵模型

2020-07-02 本文已影响0人又双叒叕苟了一天

逻辑斯谛回归（逻辑回归）模型，是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，推广到分类问题得到最大熵模型。逻辑斯谛回归和最大熵模型都属于对数线性模型。

逻辑斯谛回归模型

逻辑斯谛分布的定义

设 $X$ 是连续随机变量， $X$ 服从逻辑斯谛分布是指 $X$ 具有下列分布函数和概率密度函数：
$F(x)=P(X\leq x)=\frac1{1+e^{-(x-\mu)/\gamma}}\tag1$

$f(x)=F'(x)=\frac1{\gamma(1+e^{-(x-\mu)/\gamma})^2}\tag2$

式中， $\mu$ 是位置参数， $\gamma\gt0$ 为形状参数。

分布函数和密度函数如下图所示

F(x)

f(x)

分布函数是一条S形的曲线，以点 $(\mu,\frac12)$ 中心对称。密度函数根据 $x=\mu$ 左右对称，形状参数的值越小，在中心附近增长越快。另外，根据sigmoid函数定义
$\mathrm{sigmod}(x)=\frac1{1+e^{-x}}$
概率密度函数也可以写成
$f(x)=\mathrm{sigmoid}\bigg((x-\mu)/\mu\bigg)$

二项逻辑斯谛回归模型

二项逻辑斯谛回归模型是一种分类模型，由条件概率分布 $P(Y|X)$ 表示， $Y$ 通常取实值0或1。二项逻辑斯谛回归模型是如下的条件概率分布：
$P(Y=1|x)=\frac{\exp(w\cdot x+b)}{1+\exp(w\cdot x+b)}\tag3$

$P(Y=0|x)=\frac1{1+\exp(w\cdot x+b)}\tag4$

这里， $x\in\textbf R^n$ 是输入， $Y= \{0,1\}$ 是输出， $w\in\textbf R^n$ 和 $b\in\textbf R$ 是参数， $w$ 称为权值向量， $b$ 称为偏置， $w\cdot x$ 为 $w$ 和 $x$ 的内积。

有时为了方便，将权值向量和输入向量进行扩充，仍记做 $w$ 和 $x$ ， $w=(w^{(1)},w^{(2)},\cdots,w^{(n)},b)^T$ ， $x=(x^{(1)},x^{(2)},\cdots,x^{(n)},1)^T$ ，这时，逻辑斯谛回归模型概率分布如下：
$P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\tag5$

$P(Y=0|x)=\frac1{1+\exp(w\cdot x)}\tag6$

如果根据 $\mathrm{softmax}$ 函数的定义
$\mathrm{softmax}(x_1,x_2)=(\frac{e^{x_1}}{\sum_{i=1}^2e^{x_i}},\frac{e^{x_2}}{\sum_{i=1}^2e^{x_i}})$
该条件概率分布还可以写成
$P(Y=0|x),P(Y=1|x)=\mathrm{softmax}(0,w\cdot x)$
一个事件发生的几率，定义为发生的概率 $p$ 和不发生概率 $1-p$ 的比值 $\frac p{1-p}$ 。则该事件的对数几率或logit函数为：
$\mathrm{logit}(p)=\log\frac p{1-p}$
在逻辑斯谛回归模型中
$\mathrm{logit}(p)=\log\frac p{1-p}=\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=\log\frac{\exp(w\cdot x)}{1}=w\cdot x$
即逻辑斯谛回归模型中，输出 $Y=1$ 的对数几率是线性函数。反之，也就可以用一个线性函数转化成逻辑斯谛回归 $Y=1$ 发生的概率，即：
$P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\tag5$

二项逻辑斯谛回归模型的参数估计

逻辑斯谛回归模型学习时，对于给定的训练数据集 $T= \{(x_1,y_1),(x_2,y_x),\cdots,(x_n,y_n)\}$ ，其中， $x_i\in\textbf R^n$ ， $y_i\in \{0,1\}$ ，可以用极大似然估计法估计模型参数，从而得到逻辑斯谛回归模型。

设
$P(Y=1|x)=\pi(x)$

$P(Y=1|x)=1-\pi(x)$

则似然函数为
$\prod_{i=1}^N\bigg[[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}\bigg]$
对数似然函数为
$L(w)=\sum_{i=1}^N\bigg[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))\bigg]$
对 $L(w)$ 求极大值，得到 $w$ 的估计值。

求极值可以求 $\frac{\partial L(w)}{\partial w}=0$ 的解析解，但有时解析解不太容易求解，所以也可以使用梯度下降或牛顿法这些迭代方法得到近似解。

多项逻辑斯谛回归

多分类的多项逻辑斯谛回归模型，假设随机变量 $Y$ 的取值集合是 $\{1,2,\cdots,K\}$ ，其概率分布为：
$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1$

$P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}$

这里， $x\in\textbf R^{n+1}$ ， $w_k\in\textbf R^{n+1}$ 。即 $K$ 分类的多项逻辑斯谛回归，需要估计 $K-1$ 个参数向量 $w_k$ 。此外，概率分布也可以看做
$P(Y=1|x),P(Y=2|x),\cdots,P(Y=K|x)=\mathrm{softmax}(w_1\cdot x,w_2\cdot x,\cdots,0)$

最大熵模型

最大熵原理是概率模型学习的一个准则。最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。首先定义熵。

最大熵原理

假设离散随机变量 $X$ 的概率分布是 $P(X)$ ，则其熵是
$H(P)=-\sum_xP(x)\log P(x)$
熵满足下列不等式：
$0\leq H(P)\leq\log|X|$
式中， $|X|$ 是 $X$ 的取值个数，当且仅当 $X$ 的分布是均匀分布时右边的等号成立。也就是说，当 $X$ 服从均匀分布时，熵最大。在决策树时，熵也作为特征选择的一个依据，熵代表了 $X$ 的不确定性，在0-1分布中有下图：

可以看出随机变量 $X$ 在均匀分布时，熵最大。最大熵原理的思想就是给予随机变量 $X$ 的每个取值相同的概率，前提是满足已知的约束。例如：

假设随机变量 $X$ 有5个取值 $\{A,B,C,D,E\}$ ，并且已知 $P(A)+P(B)=\frac3{10}$ ，要求各个取值的概率。根据最大熵原理， $P(A)=P(B)=\frac3{20}$ ， $P(C)=P(D)=P(E)=\frac7{30}$ 。

最大熵模型的定义

最大熵原理是选择模型的思想，将其应用到分类模型就叫做最大熵模型。

假设分类模型是一个条件概率分布 $P(Y|X)$ ， $X\in\mathcal X\subseteq\textbf R^n$ 表示输入， $Y\in\mathcal Y$ 表示输出， $\mathcal X$ 和 $\mathcal Y$ 分别是输入和输出的集合。这个模型表示的是对于给定的输入 $X$ ，以条件概率 $P(Y|X)$ 输出 $Y$ 。

给定一个训练数据集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
学习的目标是用最大熵原理选择最好的分类模型。

首先定义联合分布 $P(X,Y)$ 的经验分布 $\tilde P(X,Y)$ ，边缘概率 $P(X)$ 的经验分布 $\tilde P(X)$ 和特征函数 $f(x,y)$
$\tilde P(X=x,Y=y)=\frac{v(X=x,Y=y)}N$

$\tilde P(X=x)=\frac{v(X=x)}N$

其中， $v(X=x,Y=y)$ 表示训练数据中样本 $(x,y)$ 出现的频数， $v(X=x)$ 表示训练数据中输入 $x$ 出现的频数， $N$ 表示训练样本容量。

特征函数 $f(x,y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实
$f(x,y)= \begin{cases} 1,&x与y满足某一事实\\ 0,&否则 \end{cases}$
如果模型能够获取训练数据中的信息，那么就可以假设下面两个期望相等
$E_{P(X,Y)}(f(x,y))=E_{\tilde P(X,Y)}(f(x,y))$
即
$\sum_{x,y}[P(x,y)f(x,y)]=\sum_{x,y}[\tilde P(x,y)f(x,y)]$
上式中用 $P(x,y)$ 用 $\tilde P(x)P(y|x)$ 表示，就变成了
$\sum_{x,y}[\tilde P(x)P(y|x)f(x,y)]=\sum_{x,y}[\tilde P(x,y)f(x,y)]\tag6$
对于 $n$ 个特征就应该有 $n$ 个上述公式(6)的约束成立，也就是最大熵模型应满足的 $n$ 个事实，在此约束下，选择熵最大的分类模型。下面定义最大熵模型：

假设满足所有约束条件的模型集合为
$\mathcal C= \{P\in\mathcal P|E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\}\tag7$
定义在条件概率分布 $P(Y|X)$ 上的条件熵为
$H(P(Y|X))=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag8$
则模型集合 $\mathcal C$ 中条件熵 $H(P(Y|X))$ 最大的模型称为最大熵模型。式中对数为自然对数。条件熵 $H(P(Y|X))$ 表示在已知 $X$ 的情况下 $Y$ 的不确定性。

最大熵模型的学习

最大熵模型可以描述为下列约束最优化问题：
$\max_{P\in\mathcal C}\ \ H(P)=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag9$

$\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\tag{10}$

$\sum_yP(y|x)=1\tag{11}$

对目标函数取相反数，转化成极小化问题
$\min_{P\in\mathcal C}\ \ -H(P)=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag{12}$

$\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\tag{13}$

$\sum_yP(y|x)=1\tag{14}$

定义拉格朗日函数
$\begin{align} L(P,w)&=-H(P)+w_0\bigg(1-\sum_yP(y|x)\bigg)+\sum_{i=1}^n[w_i(E_{\tilde P}(f_i)-E_{\tilde P}(f_i))]\\ &=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]+w_0\bigg(1-\sum_yP(y|x)\bigg)+\sum_{i=1}^nw_i\bigg(\sum_{x,y}[\tilde P(x,y)f_i(x,y)]-\sum_{x,y}[\tilde P(x)P(y|x)f_i(x,y)]\bigg) \end{align}$
最优化的原始就变成了
$\min_{P\in\mathcal C}\max_wL(P,w)$
根据拉格朗日对偶性，对偶问题是
$\max_w\min_{P\in\mathcal C}L(P,w)$
可以通过求解对偶问题来求解原始问题，首先求解内部极小化问题
$\Psi(w)=\min_{P\in\mathcal C}L(P,w)=L(P_w,w)$
此时可以先把 $w$ 看做常量，其解写作
$P_w=\arg\min_{P\in\mathcal C}L(P,w)=P_w(y|x)$
要求极小化，就要求 $L(P,w)$ 对 $P(y|x)$ 的偏导数，并使其等于0
$\frac{\partial L(P,w)}{\partial P(y|x)}=\sum_{x,y}\tilde P(x)\bigg(\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)\bigg)=0$
由于 $\tilde P(x)\gt0$ ，所以
$\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)=0$
解得
$P(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\exp(1-w_0)}$
由于 $\sum_yP(y|x)=1$ ，解得
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)\tag{15}$
其中
$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)\tag{16}$
$Z_w(x)$ 称为规范化因子； $f_i(x,y)$ 是特征函数； $w_i$ 是特征的权值，由式(15)-(16)表示的模型是 $P_w=P_w(y|x)$ 就是最大熵模型。这里 $w$ 是最大熵模型中的参数向量。之后把 $P_w(y|x)$ 代入 $L(P,w)$ 求解对偶问题外部的极大化问题，得到模型参数
$\max_w\Psi(w)=\max_wL(P_w,w)$
其解记为 $w^*$ ，即
$w^*=\arg\max_w\Psi(w)=\arg\max_wP(P_w,w)$
这里可以用最优化算法求解 $w^*$ ，例如梯度下降，牛顿法，拟牛顿法。就得到了最大熵模型 $P_{w^*}(y|x)$ 。

最大熵模型和多项逻辑斯谛回归

观察最大熵模型中公式(15)-(16)
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

和多项逻辑斯谛回归的公式
$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1$

$P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}$

可以看出两者是非常近似的。在多项逻辑斯谛回归中，对输入 $x$ 通过权值 $w_k$ 进行了加权求和，得到第 $k$ 个分类的未规范化的概率，随后通过 $\mathrm{softmax}$ 函数进行了归一化，使其符合概率分布。而在最大熵模型中，多了一个通过约束的特征函数 $f_i(x,y)$ 对输入 $x$ 进行特征提取的过程，然后对特征向量进行加权求和，得到未规范化的概率，随后通过 $\mathrm{softmax}$ 函数进行了归一化，使其符合概率分布，模型的参数 $w_i$ 通过最大熵原理习得。此外，最大熵模型和多项逻辑斯谛回归都是对数线性模型。

极大似然估计

下面证明求解对偶问题极大化等价于对最大熵模型进行极大似然估计，即求解 $w^*=\arg\max_w\Psi(w)$ 等价于求解条件概率 $P(Y|X)$ 的对数似然函数的极大化。

已知训练数据的经验概率分布 $\tilde P(X,Y)$ ，条件概率分布 $P(Y|X)$ 的对数似然函数表示为
$L_{\tilde P}(P_w)=\log\prod_{x,y}P(y|x)^{\tilde P(x,y)}=\sum_{x,y}[\tilde P(x,y)\log P(y|x)]$
将公式(15)-(16)代入
$\begin{align} L_{\tilde P}(P_w)&=\sum_{x,y}[\tilde P(x,y)\log P(y|x)]\\ &=\sum_{x,y}[\tilde P(x,y)\log\frac1{Z_w(x)}\exp(\sum_{i=1}^nw_if_i(x,y)]\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\log Z_w(x)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log Z_w(x)\tag{17} \end{align}$
在看对偶函数
$\Psi(w)=L(P_w,w)=\sum_{x,y}[\tilde P(x)P_w(y|x)\log P_w(y|x)]+w_0\bigg(1-\sum_yP_w(y|x)\bigg)+\\\sum_{i=1}^nw_i\bigg[\sum_{x,y}[\tilde P(x,y)f_i(x,y)]-\sum_{x,y}[\tilde P(x)P_w(y|x)f_i(x,y)]\bigg]$
由于 $\sum_yP_w(y|x)=1$ ，所以
$\begin{align} \Psi(w)&=\sum_{x,y}[\tilde P(x)P_w(y|x)\log P_w(y|x)]+\sum_{i=1}^n\bigg(\sum_{x,y}[\tilde P(x,y)f_i(x,y)]-\sum_{x,y}[\tilde P(x)P_w(y|x)f_i(x,y)]\bigg)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)+\sum_{x,y}\tilde P(x)P_w(y|x)\bigg(\log P_w(y|x)-\sum_{i=1}^nw_if_i(x,y)\bigg)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\tilde P(x)P_w(y|x)\log Z_w(x)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log Z_w(x) \end{align}$
所以
$\Psi(w)=L_{\tilde P}(P_w)$
即求解对偶问题极大化等价于对最大熵模型进行极大似然估计。

所以得到最大熵模型的等价的形式
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$
其中
$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$
这里， $x\in\textbf R^n$ 为输入， $y\in \{1,2,\cdots,K\}$ 为输出， $w\in\textbf R^n$ 为权值向量， $f_i(x,y),\ \ i=1,2,\cdots,n$ 为任意实值特征函数。

最大熵模型学习的最优化算法

求解最大熵模型，需要求解对偶问题的解 $w^*=\arg\max_w\Psi(w)$ 。直接求解析解一般是比较困难的，但是可以通过迭代算法，例如改进的迭代尺度法（IIS），梯度下降法，牛顿法或拟牛顿法得到近似解。下面介绍IIS法和拟牛顿法。

改进的迭代尺度法（IIS）的推导

由公式(17)可知需要最大化模型的对数似然函数
$L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\tilde P(x)\log Z_w(x)$
对于要求解的参数向量 $w=(w_1,w_2,\cdots,w_n)$ ，IIS的想法就是找到一个 $\delta=(\delta_1,\delta_2,\cdots,\delta_n)^T$ 使得更新后的参数向量 $w+\delta=(w_1+\delta_1,w_2+\delta_2,\cdots,w_n+\delta_n)$ 满足
$L(w+\delta)-L(w)\gt0$
那么就可以通过不断的迭代，使得似然函数逐渐增大，达到极大似然估计的效果，计算
$L(w+\delta)-L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)-\sum_x\tilde P(x)\log\frac{Z_{w+\delta}(x)}{Z_w(x)}$
利用不等式 $-\log\alpha\geq1-\alpha$ ，即
$-\log\frac{Z_{w+\delta}(x)}{Z_w(x)}\geq1-\frac{Z_{w+\delta}(x)}{Z_w(x)}$
得到似然函数增量的下界
$L(w+\delta)-L(w)\geq\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\sum_{i=1}^n\delta_if_i(x,y)\tag{18}$
将右端记为
$A(\delta|x)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\sum_{i=1}^n\delta_if_i(x,y)$
于是有
$L(w+\delta)-L(w)\geq A(\delta|x)$
如果能找到合适的 $\delta$ 使得 $A(\delta|x)$ 提高，那么对数似然函数也会提高，但是 $A(\delta|x)$ 中包含了 $n$ 个变量 $\delta_i$ ，同时对其进行优化是非常困难的，所以IIS试图每次只优化一个变量 $\delta_i$ ，固定其他变量 $\delta_j,j\neq i$ 。

为了达到这个目的，IIS引入了一个量 $f^\#(x,y)$
$f^\#(x,y)=\sum_i^nf_i(x,y)$
这个量表示所有特征在 $(x,y)$ 出现的次数。

所以，增量的下界可以改写为
$A(\delta|x)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\bigg(f^\#(x,y)\sum_{i=1}^n\frac{\delta_if_i(x,y)}{f^\#(x,y)}\bigg)\tag{19}$
利用指数函数的凸性以及对任意 $i$ ，有 $\frac{f_i(x,y)}{f^\#(x,y)}\geq0$ ，且 $\sum_i^n\frac{f_i(x,y)}{f^\#(x,y)}=1$ ，根据Jesen不等式得到
$\exp\bigg(f^\#(x,y)\sum_{i=1}^n\frac{\delta_if_i(x,y)}{f^\#(x,y)}\bigg)\leq\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))$
所以
$A(\delta|w)\geq\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))$
记右端
$B(\delta|w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))\tag{20}$
$B(\delta|w)$ 是对数似然函数增量的一个新的下界。求 $B(\delta|w)$ 对 $\delta_i$ 的偏导
$\frac{\partial B(\delta|w)}{\partial\delta_i}=\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0\tag{21}$
上面的方程中除了 $\delta_i$ 没有其他变量，所以可以对 $\delta_i$ 进行优化，然后以同样的方式依次对其他 $\delta_j$ 进行优化。

改进的迭代尺度法（IIS）的描述

输入：特征函数 $f_1,f_2,\cdots,f_n$ ；经验分布 $\tilde P(X,Y)$ ，模型 $P_w(y|x)$

输出：最优参数值 $w_i^*$ ；最优模型 $P_{w^*}$ 。

（1）对所有 $i\in \{1,2,\cdots,n\}$ ，取初值 $w_i=0$

（2）对每一 $i\in \{1,2,\cdots,n\}$ ：

求解方程(21)
$\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0$
其中
$f^\#(x,y)=\sum_i^nf_i(x,y)$

$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

更新 $w_i$ 的值： $w_i\leftarrow w_i+\delta_i$

（3）如果不是所有 $w_i$ 都收敛，重复步(2)。

在上述算法中，如果 $f^\#(x,y)$ 是常数，且 $f^\#(x,y)=M$ （即所有特征在任意 $(x,y)$ 出现的次数都是 $M$ 次， $f^\#(x,y)$ 与 $x,y$ 取值无关， $f^\#(x,y)$ 可以提到求和 $\sum_{x,y}$ 的外面），根据方程(21)则 $\delta_i$ 可以直接计算
$\begin{align} \exp(\delta_if^\#(x,y))&=\frac{\sum_{x,y}\tilde P(x,y)f_i(x,y)}{\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)}=\frac{\sum_{x,y}\tilde P(x,y)f_i(x,y)}{\sum_{x,y}\tilde P(x)P_w(y|x)f_i(x,y)}=\frac{\sum_{x,y}\tilde P(x,y)f_i(x,y)}{\sum_{x,y}P(x,y)f_i(x,y)}=\frac{E_{\tilde P(X,Y)}(f_i)}{E_{P(X,Y)}(f_i)}\\ &=\frac{E_{\tilde P}(f_i)}{E_P(f_i)} \end{align}$
所以
$\delta_i=\frac1{f^\#(x,y)}\log\frac{E_{\tilde P}(f_i)}{E_P(f_i)}=\frac1M\log\frac{E_{\tilde P}(f_i)}{E_P(f_i)}$

如果 $f^\#(x,y)$ 不是常数，根据方程(21)
$\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0$
即
$E_{\tilde P}(f_i)-\sum_{x,y}\bigg(\tilde P(x)P_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))\bigg)=0$
令左端等于 $g(\delta_i)$
$g(\delta_i)=E_{\tilde P}(f_i)-\sum_{x,y}\bigg(\tilde P(x)P_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))\bigg)$
这时候就需要求解方程 $g(\delta_i)=0$ 的解。这是个一元方程，可以直接求解，也可以通过牛顿法迭代公式
$\delta_i^{(k+1)}=\delta_i^{(k)}-\frac{g(\delta_i^{(k)})}{g'(\delta_i^{(k)})}\tag{22}$
解方程。

拟牛顿法

最大熵模型的学习还可以用拟牛顿法。

对于最大熵模型：
$P_w(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{Z(x)}=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}$
目标是最大化对数似然函数：
$L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log\tilde P(x)\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$
对其取相反数，得到拟牛顿法需要最小化的目标函数：
$\min_{w\in\textbf R^n}\ \ f(w)=\sum_{x}\log\tilde P(x)\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)-\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)\tag{23}$
梯度
$\frac{\partial f(w)}{\partial w_i}=\sum_{x,y}\tilde P(x)P_w(y|x)f_i(x,y)-E_{\tilde P}(f_i)=E_{P}(f_i)-E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n$

最大熵模型学习的BFGS算法

输入：特征函数 $f_1,f_2,\cdots,f_n$ ；经验分布 $\tilde P(x,y)$ ，目标函数 $f(w)$ ，梯度 $g(w)=\nabla f(w)$ ，精度要求 $\varepsilon$ ；

输出：最优参数值 $w^*$ ；最优模型 $P_{w^*}(y|x)$ 。

（1）选定初始点 $w^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$

（2）计算 $g_k=g(w^{(k)})$ 。若 $||g_k||\lt\varepsilon$ ，则停止计算，得 $w^*=w^{(k)}$ ；否则转(3)

（3）由 $B_kp_k=-g_k$ 求出 $p_k$

（4）一维搜索：求 $\lambda_k$ 使得
$f(w^{(k)}+\lambda_kp_k)=\min_{\lambda_k\geq0}f(w^{(k)}+\lambda p_k)$
（5）置 $w^{(k+1)}=w^{(k)}+\lambda_kp_k$

（6）计算 $g_{k+1}=g(w^{(k+1)})$ ，若 $||g_{k+1}||\leq\varepsilon$ ，则停止计算，得 $w^*=w^{(k+1)}$ ；否则，按下式求出 $B_{k+1}$ ：
$B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}$
其中，
$y_k=g_{k+1}-g_k$