第6章 逻辑斯蒂回归和最大熵模型

逻辑斯谛回归(LR)是经典的分类方法

1．逻辑斯谛回归模型是由以下条件概率分布表示的分类模型。逻辑斯谛回归模型可以用于二类或多类分类。

$$P(Y=k|x)=\frac{\exp \left(w_k\cdot x\right)}{1+{\sum }_{k=1}^{K-1}\exp \left(w_k\cdot x\right)},k=1,2,\cdots ,K-1$$

$$P(Y=K|x)=\frac{1}{1+{\sum }_{k=1}^{K-1}\exp \left(w_k\cdot x\right)}$$

这里，$x$为输入特征，$w$为特征的权值。

逻辑斯谛回归模型源自逻辑斯谛分布，其分布函数$F(x)$是$S$形函数。逻辑斯谛回归模型是由输入的线性函数表示的输出的对数几率模型。

2．最大熵模型是由以下条件概率分布表示的分类模型。最大熵模型也可以用于二类或多类分类。
$$P_w(y|x)=\frac{1}{Z_w(x)}\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)$$

$$Z_w(x)=\sum _y\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)$$

其中，$Z_w(x)$是规范化因子，$f_i$为特征函数，$w_i$为特征的权值。

3．最大熵模型可以由最大熵原理推导得出。最大熵原理是概率模型学习或估计的一个准则。最大熵原理认为在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。

最大熵原理应用到分类模型的学习中，有以下约束最优化问题：

$$\min -H(P)=\sum _{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$$

$$s.t.P\left(f_i\right)-\tilde{P}\left(f_i\right)=0,i=1,2,\cdots ,n$$

$$\sum _{y}P(y|x)=1$$

求解此最优化问题的对偶问题得到最大熵模型。

4．逻辑斯谛回归模型与最大熵模型都属于对数线性模型。

5．逻辑斯谛回归模型及最大熵模型学习一般采用极大似然估计，或正则化的极大似然估计。逻辑斯谛回归模型及最大熵模型学习可以形式化为无约束最优化问题。求解该最优化问题的算法有改进的迭代尺度法、梯度下降法、拟牛顿法。

这里也感谢DataWhale的无私奉献，我结合了原先的学习资料，整合了一下，得到现有的笔记，这里也欢迎大家参与DataWhale的组队学习中，https://datawhalechina.github.io/statistical-learning-method-solutions-manual/#/

---

最大熵模型

• 最大熵模型（maximun entropy model）由最大熵原理推导实现，而最大熵原理损失概率模型学习的一个准则。最大熵原理认为，学习概率模型是，所有可能的概率模型（分布）中，熵最大的模型是最好的模型。

• 最大熵原理也可以表述为在满足约束条件的模型集合中取熵最大的模型

• 假设满足所有约束条件的模型的集合为
  KaTeX parse error: Got function '\tilde' with no arguments as subscript at position 29: …n P|E_P(f_i)=E_\̲t̲i̲l̲d̲e̲{P}({f_i})\}

• 定义在条件概率分布$P(X|Y)$上的条件熵为
  $$H(P)=-\sum _{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$$
  则模型集合C中条件熵$H(P)$最大的模型称为最大熵模型。式中的对数为自然对数。

最大熵模型的学习

• 最大熵模型的学习过程就是求解最大熵模型的过程。最大熵模型的学习可以形式化为约束最优的问题。最大熵模型的学习就等价与约束最优化问题
• 将约束最优化的原始问题转换为无约束最优化的对偶问题。通过求解对偶问题求解原始问题。
• 简单来说，约束最优化问题包含$\le 0$，和$=0$两种约束条件，这是约束优化问题的一般形式

$$\begin{array}{rl}\underset{x\in R^n}{\min }& f(x)\\ s.t.& c_i(x)\le 0,i=1,2,\dots ,k\\ & h_j(x)=0,j=1,2,\dots ,l\end{array}$$

• 引入广义拉格朗日函数

$$L(x,\alpha ,\beta )=f(x)+\sum _{i=0}^k{\alpha }_i{c}_i(x)+\sum _{j=1}^l{\beta }_j{h}_j(x)$$

$\alpha$和$\beta$是拉格朗日乘子

• 在KKT的条件下，原始问题和对偶问题的最优值相等

$$\begin{gathered} {\nabla }_{x}L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0 \\ {\nabla }_{\alpha }L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0 \\ {\nabla }_{\beta }L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0 \\ {\alpha }_i^{\ast }{c}_i(x^{\ast })=0,i=1,2,\dots ,k \\ {c}_i(x^{\ast })\le 0,i=1,2,\dots ,k \\ {\alpha }_i^{\ast }\ge 0,i=1,2,\dots ,k \\ {h}_j(x^{\ast })=0,j=1,2,\dots ,l \end{gathered}$$

• 前面三个条件是由解析函数的知识，对于各个变量的偏导数为0，后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束,第四个条件是KKT的对偶互补条件

• 在$L(P,w)$对$P$求偏导并令其为零解得

$$P(y|x)=\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)+w_0-1\right)=\frac{\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)}{\exp \left(1-w_0\right)}$$

• 因为$\sum _{y}P(y|x)=1$，然后得到模型

$$P_w(y|x)=\frac{1}{Z_w(x)}\exp \sum _{i=1}^n{w}_i{f}_i(x,y)$$

$$其中，Z_w(x)=\sum _y\exp (\sum _{i=1}^n{w}_i{f}_i(x,y))$$

• 这里$Z_w(x)$先用来代替$\exp (1-w_0)$,$Z_w$是归一化因子
• 并不是因为概率为1推导出了$Z_w$的表达式，这样一个表达式是凑出来的，意思就是遍历$y$的所有取值，求分子表达式的占比

极大似然估计

• 对偶函数的极大化等价于最大熵模型的极大似然估计
• 已知训练数据的经验分布$\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)$$

• 当条件分布概率$P(y|x)$是最大熵模型时

$$\begin{array}{rl}{L}_{\tilde{P}}(P_w)& =\sum _{x,y}\tilde{P}(x,y)\log P(y|x)\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _{x,y}\tilde{P}(x,y)\log (Z_w(x))\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _{x,y}\tilde{P}(x)P(y|x)\log (Z_w(x))\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _x\tilde{P}(x)\log (Z_w(x))\sum _{y}P(y|x)\\ & =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _x\tilde{P}(x)\log (Z_w(x))\end{array}$$

• 推导过程用到了$\sum _{y}P(y|x)=1$

模型学习的最优化算法

• 逻辑斯蒂回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解
• 用最优化的观点来看，常用找最优解的方法有改建的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。牛顿法和拟牛顿法一般收敛速度更快。
• 简单算法在这里不做描述了，因为之前也做了笔记，这里着重描述一下改进的迭代尺度算法

改进的迭代尺度算法（IIS）

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

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

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

（2）对每一 i ∈ { 1 , 2 , … , n } i \in \{ 1,2,\dots,n\} i∈{1,2,…,n}

（a） 令 ${\delta }_i$ 是方程
$$\sum _{x,y}\tilde{P}(x)P(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}^n{f}_i(x,y)$$
（b）更新 $w_i$ 值: $w_i\leftarrow w_i+{\delta }_i$ 。
（3）如果不是所有 $w_i$ 都收玫，重复步 (2)。

这一算法关键的一步是 $(\mathrm{a})$, 即求解方程中的 ${\delta }_i$ 。如果 $f^{\#}(x,y)$ 是常数, 即 对任何 $x,y$, 有 $f^{\#}(x,y)=M$, 那么 ${\delta }_i$ 可以显式地表示成
$${\delta }_i=\frac{1}{M}\log \frac{E_{\tilde{P}}\left(f_i\right)}{E_P\left(f_i\right)}$$
如果 $f^{\#}(x,y)$ 不是常数，那么必须通过数值计算求 ${\delta }_i$ 。简单有效的方法是牛顿法。

以 $g\left({\delta }_i\right)=0$ 表示方程, 牛顿法通过迭代求得 ${\delta }_i^{\ast }$, 使得 $g\left({\delta }_i^{\ast }\right)=0$ 。迭代公式是
$${\delta }_i^{(k+1)}={\delta }_i^{(k)}-\frac{g\left({\delta }_i^{(k)}\right)}{g^{\prime }\left({\delta }_i^{(k)}\right)}$$
只要适当选取初始值 ${\delta }_i^{(0)}$, 由于 ${\delta }_i$ 的方程有单根, 因此牛顿法恒收敛, 而且收敛速度很快。

练习

class MaxEntropy:
def init(self, EPS=0.005):
self._samples = []
self._Y = set() # 标签集合，相当去去重后的y
self._numXY = {} # key为(x,y)，value为出现次数
self._N = 0 # 样本数
self.Ep = [] # 样本分布的特征期望值
self._xyID = {} # key记录(x,y),value记录id号
self._n = 0 # 特征键值(x,y)的个数
self._C = 0 # 最大特征数
self._IDxy = {} # key为(x,y)，value为对应的id号
self._w = []
self._EPS = EPS # 收敛条件
self._lastw = [] # 上一次w参数值

def loadData(self, dataset):
    self._samples = deepcopy(dataset)
    for items in self._samples:
        y = items[0]
        X = items[1:]
        self._Y.add(y)  # 集合中y若已存在则会自动忽略
        for x in X:
            if (x, y) in self._numXY:
                self._numXY[(x, y)] += 1
            else:
                self._numXY[(x, y)] = 1

    self._N = len(self._samples)
    self._n = len(self._numXY)
    self._C = max([len(sample) - 1 for sample in self._samples])
    self._w = [0] * self._n
    self._lastw = self._w[:]

    self._Ep_ = [0] * self._n
    for i, xy in enumerate(self._numXY):  # 计算特征函数fi关于经验分布的期望
        self._Ep_[i] = self._numXY[xy] / self._N
        self._xyID[xy] = i
        self._IDxy[i] = xy

def _Zx(self, X):  # 计算每个Z(x)值
    zx = 0
    for y in self._Y:
        ss = 0
        for x in X:
            if (x, y) in self._numXY:
                ss += self._w[self._xyID[(x, y)]]
        zx += math.exp(ss)
    return zx

def _model_pyx(self, y, X):  # 计算每个P(y|x)
    zx = self._Zx(X)
    ss = 0
    for x in X:
        if (x, y) in self._numXY:
            ss += self._w[self._xyID[(x, y)]]
    pyx = math.exp(ss) / zx
    return pyx

def _model_ep(self, index):  # 计算特征函数fi关于模型的期望
    x, y = self._IDxy[index]
    ep = 0
    for sample in self._samples:
        if x not in sample:
            continue
        pyx = self._model_pyx(y, sample)
        ep += pyx / self._N
    return ep

def _convergence(self):  # 判断是否全部收敛
    for last, now in zip(self._lastw, self._w):
        if abs(last - now) >= self._EPS:
            return False
    return True

def predict(self, X):  # 计算预测概率
    Z = self._Zx(X)
    result = {}
    for y in self._Y:
        ss = 0
        for x in X:
            if (x, y) in self._numXY:
                ss += self._w[self._xyID[(x, y)]]
        pyx = math.exp(ss) / Z
        result[y] = pyx
    return result

def train(self, maxiter=1000):  # 训练数据
    for loop in range(maxiter):  # 最大训练次数
        print("iter:%d" % loop)
        self._lastw = self._w[:]
        for i in range(self._n):
            ep = self._model_ep(i)  # 计算第i个特征的模型期望
            self._w[i] += math.log(self._Ep_[i] / ep) / self._C  # 更新参数
        print("w:", self._w)
        if self._convergence():  # 判断是否收敛
            break

dataset = [['no', 'sunny', 'hot', 'high', 'FALSE'],
           ['no', 'sunny', 'hot', 'high', 'TRUE'],
           ['yes', 'overcast', 'hot', 'high', 'FALSE'],
           ['yes', 'rainy', 'mild', 'high', 'FALSE'],
           ['yes', 'rainy', 'cool', 'normal', 'FALSE'],
           ['no', 'rainy', 'cool', 'normal', 'TRUE'],
           ['yes', 'overcast', 'cool', 'normal', 'TRUE'],
           ['no', 'sunny', 'mild', 'high', 'FALSE'],
           ['yes', 'sunny', 'cool', 'normal', 'FALSE'],
           ['yes', 'rainy', 'mild', 'normal', 'FALSE'],
           ['yes', 'sunny', 'mild', 'normal', 'TRUE'],
           ['yes', 'overcast', 'mild', 'high', 'TRUE'],
           ['yes', 'overcast', 'hot', 'normal', 'FALSE'],
           ['no', 'rainy', 'mild', 'high', 'TRUE']]
maxent = MaxEntropy()
x = ['overcast', 'mild', 'high', 'FALSE']
maxent.loadData(dataset)
maxent.train()
print('predict:', maxent.predict(x))

predict: {'yes': 0.9999971802186581, 'no': 2.819781341881656e-06}

第6章Logistic回归与最大熵模型-习题

习题6.1

​ 确认Logistic分布属于指数分布族。

解答：
第1步：
首先给出指数分布族的定义：
对于随机变量$x$，在给定参数$\eta$下，其概率分别满足如下形式：$$p(x|\eta )=h(x)g(\eta )\exp ({\eta }^{T}u(x))$$我们称之为指数分布族。
其中：
$x$：可以是标量或者向量，可以是离散值也可以是连续值
$\eta$：自然参数
$g(\eta )$：归一化系数
$h(x),u(x)$：$x$的某个函数

---

**第2步：**证明伯努利分布属于指数分布族
伯努利分布：$\phi$是$y=1$的概率，即$P(Y=1)=\phi$
$\begin{array}{rl}P(y|\phi )& ={\phi }^y(1-\phi {)}^{(1-y)}\\ & =(1-\phi ){\phi }^y(1-\phi {)}^{(-y)}\\ & =(1-\phi )(\frac{\phi }{1-\phi }{)}^y\\ & =(1-\phi )\exp \left(y\ln \frac{\phi }{1-\phi }\right)\\ & =\frac{1}{1+e^{\eta }}\exp (\eta y)\end{array}$
其中，$\eta =\ln \frac{\phi }{1-\phi }\iff \phi =\frac{1}{1+e^{-\eta }}$
将$y$替换成$x$，可得$P(x|\eta )=\frac{1}{1+e^{\eta }}\exp (\eta x)$
对比可知，伯努利分布属于指数分布族，其中$h(x)=1,g(\eta )=\frac{1}{1+e^{\eta }},u(x)=x$

---

第3步：
广义线性模型（GLM）必须满足三个假设：

1. $y|x;\theta \sim ExponentialFamily(\eta )$，即假设预测变量$y$在给定$x$，以$\theta$为参数的条件概率下，属于以$\eta$作为自然参数的指数分布族；
2. 给定$x$，求解出以$x$为条件的$T(y)$的期望$E[T(y)|x]$，即算法输出为$h(x)=E[T(y)|x]$
3. 满足$\eta ={\theta }^{T}x$，即自然参数和输入特征向量$x$之间线性相关，关系由$\theta$决定，仅当$\eta$是实数时才有意义，若$\eta$是一个向量，则${\eta }_i={\theta }_i^{T}x$

---

**第4步：**推导伯努利分布的GLM
已知伯努利分布属于指数分布族，对给定的$x,\eta$，求解期望：$$\begin{array}{rl}{h}_{\theta }(x)& =E[y|x;\theta ]\\ & =1\cdot p(y=1)+0\cdot p(y=0)\\ & =\phi \\ & =\frac{1}{1+e^{-\eta }}\\ & =\frac{1}{1+e^{-{\theta }^{T}x}}\end{array}$$可得到Logistic回归算法，故Logistic分布属于指数分布族，得证。

习题6.2

  写出Logistic回归模型学习的梯度下降算法。

解答：
对于Logistic模型：$$\begin{gathered} P(Y=1|x)=\frac{\exp (w\cdot x+b)}{1+\exp (w\cdot x+b)} \\ P(Y=0|x)=\frac{1}{1+\exp (w\cdot x+b)} \end{gathered}$$对数似然函数为：$L(w)=\sum _{i=1}^N\left[y_i(w\cdot x_i)-\log \left(1+\exp (w\cdot x_i)\right)\right]$
似然函数求偏导，可得$\frac{\partial L(w)}{\partial w^{(j)}}=\sum _{i=1}^N\left[x_i^{(j)}\cdot y_i-\frac{\exp (w\cdot x_i)\cdot x_i^{(j)}}{1+\exp (w\cdot x_i)}\right]$
梯度函数为：$\nabla L(w)=\left[\frac{\partial L(w)}{\partial w^{(0)}},\cdots ,\frac{\partial L(w)}{\partial w^{(m)}}\right]$
Logistic回归模型学习的梯度下降算法：
(1) 取初始值$x^{(0)}\in R$，置$k=0$
(2) 计算$f(x^{(k)})$
(3) 计算梯度$g_k=g(x^{(k)})$，当$\Vert g_k\Vert <\epsilon$时，停止迭代，令$x^{\ast }=x^{(k)}$；否则，求${\lambda }_k$，使得$f(x^{(k)}+{\lambda }_k{g}_k)=\underset{\lambda ⩾0}{\max }f(x^{(k)}+\lambda g_k)$
(4) 置$x^{(k+1)}=x^{(k)}+{\lambda }_k{g}_k$，计算$f(x^{(k+1)})$，当$\Vert f(x^{(k+1)})-f(x^{(k)})\Vert <\epsilon$或 $\Vert x^{(k+1)}-x^{(k)}\Vert <\epsilon$时，停止迭代，令$x^{\ast }=x^{(k+1)}$
(5) 否则，置$k=k+1$，转(3)

%matplotlib inline
import numpy as np
import time
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from pylab import mpl

# 图像显示中文
mpl.rcParams['font.sans-serif'] = ['Microsoft YaHei']


class LogisticRegression:
    def __init__(self, learn_rate=0.1, max_iter=10000, tol=1e-2):
        self.learn_rate = learn_rate  # 学习率
        self.max_iter = max_iter  # 迭代次数
        self.tol = tol  # 迭代停止阈值
        self.w = None  # 权重

    def preprocessing(self, X):
        """将原始X末尾加上一列，该列数值全部为1"""
        row = X.shape[0]
        y = np.ones(row).reshape(row, 1)
        X_prepro = np.hstack((X, y))
        return X_prepro

    def sigmod(self, x):
        return 1 / (1 + np.exp(-x))

    def fit(self, X_train, y_train):
        X = self.preprocessing(X_train)
        y = y_train.T
        # 初始化权重w
        self.w = np.array([[0] * X.shape[1]], dtype=np.float)
        k = 0
        for loop in range(self.max_iter):
            # 计算梯度
            z = np.dot(X, self.w.T)
            grad = X * (y - self.sigmod(z))
            grad = grad.sum(axis=0)
            # 利用梯度的绝对值作为迭代中止的条件
            if (np.abs(grad) <= self.tol).all():
                break
            else:
                # 更新权重w 梯度上升——求极大值
                self.w += self.learn_rate * grad
                k += 1
        print("迭代次数：{}次".format(k))
        print("最终梯度：{}".format(grad))
        print("最终权重：{}".format(self.w[0]))

    def predict(self, x):
        p = self.sigmod(np.dot(self.preprocessing(x), self.w.T))
        print("Y=1的概率被估计为：{:.2%}".format(p[0][0]))  # 调用score时，注释掉
        p[np.where(p > 0.5)] = 1
        p[np.where(p < 0.5)] = 0
        return p

    def score(self, X, y):
        y_c = self.predict(X)
        error_rate = np.sum(np.abs(y_c - y.T)) / y_c.shape[0]
        return 1 - error_rate

    def draw(self, X, y):
        # 分离正负实例点
        y = y[0]
        X_po = X[np.where(y == 1)]
        X_ne = X[np.where(y == 0)]
        # 绘制数据集散点图
        ax = plt.axes(projection='3d')
        x_1 = X_po[0, :]
        y_1 = X_po[1, :]
        z_1 = X_po[2, :]
        x_2 = X_ne[0, :]
        y_2 = X_ne[1, :]
        z_2 = X_ne[2, :]
        ax.scatter(x_1, y_1, z_1, c="r", label="正实例")
        ax.scatter(x_2, y_2, z_2, c="b", label="负实例")
        ax.legend(loc='best')
        # 绘制p=0.5的区分平面
        x = np.linspace(-3, 3, 3)
        y = np.linspace(-3, 3, 3)
        x_3, y_3 = np.meshgrid(x, y)
        a, b, c, d = self.w[0]
        z_3 = -(a * x_3 + b * y_3 + d) / c
        ax.plot_surface(x_3, y_3, z_3, alpha=0.5)  # 调节透明度
        plt.show()

# 训练数据集
X_train = np.array([[3, 3, 3], [4, 3, 2], [2, 1, 2], [1, 1, 1], [-1, 0, 1],
                    [2, -2, 1]])
y_train = np.array([[1, 1, 1, 0, 0, 0]])
# 构建实例，进行训练
clf = LogisticRegression()
clf.fit(X_train, y_train)
clf.draw(X_train, y_train)

迭代次数：3232次
最终梯度：[ 0.00144779  0.00046133  0.00490279 -0.00999848]
最终权重：[  2.96908597   1.60115396   5.04477438 -13.43744079]

习题6.3

  写出最大熵模型学习的DFP算法。（关于一般的DFP算法参见附录B）

解答：
第1步：
最大熵模型为：
$$\begin{array}{cl}\max & H(p)=-{\sum }_{x,y}P(x)P(y|x)\log P(y|x)\\ \text{st.}& E_p(f_i)-E_{\hat{p}}(f_i)=0,i=1,2,\cdots ,n\\ & {\sum }_{y}P(y|x)=1\end{array}$$
引入拉格朗日乘子，定义拉格朗日函数：
$$\begin{gathered} L(P,w)=\sum _{xy}P(x)P(y|x)\log P(y|x)+w_0\left(1-\sum _{y}P(y|x)\right) \\ +\sum _{i=1}{w}_i\left(\sum _{xy}P(x,y)f_i(x,y)-\sum _{xy}P(x,y)P(y|x)f_i(x,y)\right) \end{gathered}$$
$
最优化原始问题为：$
$$\underset{P\in C}{\min }\underset{w}{\max }L(P,w)$$
对偶问题为：
$$\underset{w}{\max }\underset{P\in C}{\min }L(P,w)$$
令
$$\Psi (w)=\underset{P\in C}{\min }L(P,w)=L(P_w,w)$$
$\Psi (w)$称为对偶函数，同时，其解记作
$$P_w={\mathrm{argmin}}_{P\in C}L(P,w)=P_w(y|x)$$
求$L(P,w)$对$P(y|x)$的偏导数，并令偏导数等于0，解得：
$$P_w(y|x)=\frac{1}{Z_w(x)}\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)$$
其中：
$$Z_w(x)=\sum _y\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)$$
则最大熵模型目标函数表示为​
$$\phi (w)=\underset{w\in R_n}{\min }\Psi (w)=\sum _{x}P(x)\log \sum _y\exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right)-\sum _{x,y}P(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y)$$
第2步：
DFP的$G_{k+1}$的迭代公式为：
$$G_{k+1}=G_k+\frac{{\delta }_k{\delta }_k^T}{{\delta }_k^T{y}_k}-\frac{G_k{y}_k{y}_k^T{G}_k}{y_k^T{G}_k{y}_k}$$

最大熵模型的DFP算法：
输入：目标函数$\phi (w)$，梯度$g(w)=\nabla g(w)$，精度要求$\epsilon$；
输出：$\phi (w)$的极小值点$w^{\ast }$
(1)选定初始点$w^{(0)}$，取$G_0$为正定对称矩阵，置$k=0$
(2)计算$g_k=g(w^{(k)})$，若$\Vert g_k\Vert <\epsilon$，则停止计算，得近似解$w^{\ast }=w^{(k)}$，否则转(3)
(3)置$p_k=-G_k{g}_k$
(4)一维搜索：求${\lambda }_k$使得$$\phi \left(w^{(k)}+{\lambda }_k{P}_k\right)=\underset{\lambda ⩾0}{\min }\phi \left(w^{(k)}+\lambda P_k\right)$$(5)置$w^{(k+1)}=w^{(k)}+{\lambda }_k{p}_k$
(6)计算$g_{k+1}=g(w^{(k+1)})$，若$\Vert g_{k+1}\Vert <\epsilon$，则停止计算，得近似解$w^{\ast }=w^{(k+1)}$；否则，按照迭代式算出$G_{k+1}$
(7)置$k=k+1$，转(3)