概述

本文围绕李航《统计学习方法》第一版无监督学习中的部分章节撰写学习笔记，

并将学习过程中个人遇到的问题与思考以及相应的解答进行记录总结。

阅读《统计学习方法》的初衷是给之后深度学习作为铺垫，

因此本文也将重点关注一些较为相关的基础理论算法内容。

具体包括原书以下章节:

第1章，统计学习及监督学习概论

第2章，感知机

第4章，朴素贝叶斯法

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

未来可能会根据个人学习需求在陆续添加其他章节内容。

统计学习及监督学习概论

个人认为的本章重点:

1.统计学习三要素(1.3节)

2.模型评估与模型选择(1.4节)

3.正则化与交叉验证(1.5节)

4.生成模型与判别模型(1.7节)

5.分类问题，标注问题，回归问题(1.8节-1.10节)

感知机

感知机是经典的线性二分类模型，是神经网络的基础。

输入为实例的特征向量$x\in X$ 输出为$y\in Y={+1,-1}$

朴素贝叶斯法

朴素贝叶斯法是经典的生成模型算法，是基于贝叶斯定理与特征条件独立假设的分类方法。

对于某一问题设计朴素贝叶斯法模型关键是得到朴素贝叶斯法的参数估计。

逻辑斯谛回归

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

逻辑斯蒂回归虽然有回归二字但其实并非用于线性回归问题。

最典型的逻辑斯蒂回归应用于输出值离散的二分类或多分类问题上。

相关引用: 刘建平Pinard-逻辑回归原理小结

从线性回归到逻辑回归

线性回归的模型是求出输出值 $y$ 和输入向量$x$之间的线性关系 $y=wx+b$，或者将偏置$b$并入特征矩阵$w$，记作$\hat{w}=(w^{T},b)^{T}$，

同样也将输入向量加以扩充，加进常数 1，记作$\hat{x}=(x^{T},1)^{T}$，显然有$\hat{w}\hat{x}=wx+b$。

对于线性回归问题，输入输出被映射成一个线性函数的关系，因此对于输出值 $y$ 是连续的。

如果 $y$ 是离散值怎么办？一个想法是对 $y$ 在做一次函数转化，变为$g(y)$。

如果我们令 $g(y)$ 的值在某个实数区间的时候是类别A，在另一个实数区间的时候是类别B，

以此类推就得到了一个分类模型，这也是逻辑斯谛回归要做的。

逻辑斯谛分布到逻辑回归模型

在引入逻辑斯谛回归之前首先介绍逻辑斯谛分布。

设 $X$ 是连续随机变量，$X$ 服从逻辑斯谛分布是指 $X$ 具有下列分布函数$F(x)$和密度函数$f(x)$:
$$F(x)=P(X\leq x)= {1\over 1+e^{-(x-\mu)/\lambda} }\ f(x)=F’(X)= {e^{-(x-\mu)/\lambda}\over \lambda(1+e^{-(x-\mu)/\lambda})^2}$$
这里顺便回顾一下分布函数与概率密度函数的含义。粗略的说概率密度函数$f(x)$就是$P(X=x)$的概率。

对于离散事件$x$而言， $F(m) = P(X\leq m) = \sum_{x = -\infty}^m P(X=x)$。

对于连续变量$x$而言，$F(m) = P(X\leq m) = \int_{x = -\infty}^m P(X=x)$。

而逻辑斯谛分布的密度函数与分布函数形如下图所示。

密度函数图像(左图)反映了逻辑斯谛分布模型中随机事件 $x$ 符合以均值 $\mu$ 为对称轴的，类似正态分布的触发概率。

而分布函数图像(右图)就是经典的sigmoid函数的原型。

假如我们规定随机事件 $x$ 的概率分布以$F(x)>0.5$ 和$F(x)<0.5$分为两类来分别对应二分类中输出$y$ 的值，

那么就能够应对输出值是离散值的情况，并用于求解分类问题。

而这里分布函数$F$ 就是上文 从线性回归到逻辑回归 指代的函数 $g$ 的原型。
$$g(z) = {1 \over 1+e^z}\ z = wx+b = \hat{w}\hat{x}\ \hat{w} = (w^{(1)},w^{(2)},\cdots, w^{(n)}, d)\ \hat{x} = (x^{(1)},x^{(2)},\cdots, x^{(n)}, 1)\ $$
(关于函数 $g$ 此处刘建平老师的博客和李航老师书中所记略有不同但本质一样)

函数 $g$ 有个非常好的性质: $g’(z)=g(z)(g(z)-1)$

这让sigmoid函数在神经网络算法中反向传播更新计算更简便。

二项逻辑斯谛回归模型

具体的二项逻辑斯谛回归模型是如下的条件概率分布:
$$P(Y=1|x)={e^{wx+b} \over 1 + e^{wx+b} }\ P(Y=0|x)= 1 - P(Y=1|x) = {1 \over 1 + e^{wx+b} }\ $$
而逻辑回归模型所需要学习的就是权值向量 $w$ 以及偏置 $b$，

刘建平老师的博客中将权值向量和偏置合并记作线性关系系数 $\theta$ (等同于此处的 $\hat{w}$)。

计算二元逻辑回归模型中事件$x$发生的对数几率: $log{P(Y=1|x) \over P(Y=0|x)} = wx+b$

这就是说，在逻辑斯谛回归模型中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。

或者说，输出 $Y=1$ 的对数几率是由输入 $x$ 的线性函数表示的模型，即逻辑斯谛回归模型。

多项逻辑斯谛回归模型

二项逻辑回归可以推广到多项逻辑回归模型。假设输出离散值$Y = {1,2,\cdots,K }$，那么多项逻辑回归模型是:
$$P(Y=k|x)={e^{\hat{w_k}x} \over 1 + \sum_{k=1}^{K-1} e^{\hat{w_k}x} }, \quad k = 1,2,\cdots, K-1\ P(Y=0|x)= 1 - P(Y=1|x) = {1 \over 1 + \sum_{k=1}^{K-1} e^{\hat{w_k}x} }\ $$
需要注意到$\hat{w_k}$ 是不同分类 $y$ 对应的一个向量参数。

模型参数估计

相关参考:

一文搞懂极大似然估计

详解最大似然估计（MLE）最大后验概率估计（MAP）以及贝叶斯公式的理解

现在已经知道了逻辑回归模型，即上述条件概率分布。

然而要使用逻辑回归模型去判断输入 $x$ 所对应的 $y$ 还需要求得模型中的参数$\hat{w}$ 。

为了求得参数$\hat{w}$ 需要用到极大似然估计的思想。

极大似然估计

通俗理解来说，就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值，

即：“模型和样本已定，参数未知”。

极大似然估计中采样需满足一个重要的假设，就是所有的样本都是互相独立且服从同一概率分布规则的。

一个比较好的例子是硬币的质地是否均匀，即想知道抛这枚硬币，正面出现的概率 $\theta$ 是多少。

假设投掷硬币5次得到的训练数据集，即已知的样本结果信息 $T= {(x_1, 1),(x_2, 1),(x_3, 0),(x_4, 1),(x_5, 0)}$，其中$x_i$表示第i次投掷行为，输出为$y_i\in {0,1}$ ，0为反面，1为正面。

我们想求的正面概率 $\theta$ 是模型参数，而抛硬币模型我们可以假设是二项分布。

那么，出现实验结果 $T$ 的似然函数是 : $P(T|\theta) = \theta^3(1-\theta)^2$，

当 $P(T|\theta)$ 最大时，此时的 $\theta$ 才是最有可能导致出现样本结果 $T$ 的参数。

找到函数 $P(T|\theta) = \theta^3(1-\theta)^2$ 的最大值处的 $\theta$ :

$\theta_{best} = \underset{ {\theta} }{argmax}\ P(T|\theta)$ ，求得对应的 $\theta_{best} = 0.6$ 。

通常我们会对似然函数取对数从而将乘法改为 $log$ 项相加更方便讨论最大值。

如果从经验角度来说，根据这个样本结果$T$ 很容易计算出投掷正面的概率为$\theta = 0.6$，也符合极大似然估计结果。

使用极大似然估计求二项逻辑回归中的参数$\hat{w}$

在逻辑斯蒂回归中，我们已经知道了概率分布模型是:
$$P(Y=1|x)={e^{wx+b} \over 1 + e^{wx+b} }\ P(Y=0|x)= 1 - P(Y=1|x) = {1 \over 1 + e^{wx+b} }\ $$
我们需要求得的参数是$w$ 与 $b$ 或者说 $\hat{w}$，

假设训练数据集，即已知的样本结果信息 $T = {(x_1, y_1), (x_2, y_2),\cdots, (x_N, y_N)}$ 其中$x_i\in R^n, y_i \in {0,1}$

由于二项逻辑回归模型的输出$y\in{1,0}$ 符合二项分布。

那么对应的似然函数为:
$$\prod_{i=1}^N[P(Y=1|x_i)]^{y_i}[1-P(Y=1|x_i)]^{1-y_i}$$
当样本 $y_i$ 输出为0，那么第 $i$ 个连乘项为 $P(Y=0|x_i)$，

当样本 $y_i$ 输出为1，那么第 $i$ 个连乘项为 $P(Y=1|x_i)$，

对似然函数取对数，并将结果化简得到二项逻辑回归的关于参数 $\hat{w}$ 的损失函数 $L(\hat{w})$:
$$
L(\hat{w}) = \sum_{i=1}^N[y_i(\hat{w}x_i)-log(1+e^{\hat{w}x_i})]\
\hat{w}{best} = \underset{ {\hat{w} } }{argmax}\ L(\hat{w})
$$
可以使用梯度下降法或者拟牛顿法进行迭代更新计算得到$\hat{w}{best}$。

最大熵模型

最大熵是概率模型学习的一个准则，最大熵原理认为，学习概率模型时，

在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。

相关参考:

最大熵模型原理小结 - 刘建平Pinard

李航《统计学习方法》最大熵模型p(y|x)推导的正确过程

信息熵与条件熵

相关参考:

通俗理解信息熵

在学习最大熵模型之前，先要了解信息学中信息熵的概念。

熵：表示随机变量的不确定性。

假设 $P(X=x_i)$ 代表随机事件 $X$ 为 $x_i$ 的概率，则其熵为:
$$H(X) = -\sum_{i=1}^n P(X=x_i)logP(X=x_i)$$
在李航的书中此处的 $log$ 以 $e$ 为底数。

公式中的 $log\ P(X=x_i)$ 用来衡量随机事件 $X$ 为 $x_i$ 时的信息量。

那么信息熵公式就可以被理解成随机事件 $X$ 所含信息量的期望，即: 各项概率 × 对应信息量的总和。

根据熵的定义，我们可以推广到两个变量 $X,Y$ 的联合熵:
$$H(X,Y) = -\sum_{x_i\in X}\sum_{y_j \in Y} P(X=x_i,Y=y_j)logP(X=x_i,Y=y_j)$$
在本节中我们需要使用条件熵来帮助进行推导最大熵模型。

条件熵是指在一个条件下，随机变量的不确定性:
$$\begin{aligned} H(Y|X=x_j) &= \sum_{y_i \in Y} P(Y=y_i|X=x_j)logP(Y=y_i|X=x_i)\ H(Y|X) &= \sum_{x_j\in X}P(X=x_j)H(Y|X=x_j)\ &= -\sum_{x_i\in X}\sum_{y_j \in Y}P(Y=y_i,X=x_j)logP(Y=y_i|X=x_j) \end{aligned}$$

最大熵原理以及最大熵模型

最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。

在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。

用一个例子解释一下这段话。

假设随机变量$X$ 有4个取值 ${A,B,C,D}$ ，取各个值的概率为$P(A),\cdots,P(D)$。

这些概率值满足以下约束条件: $P(A)+\cdots+P(D) = 1$

满足这个约束条件的概率分布有无穷多个。如果没有任何其他信息，仍要对概率分布进行估计，

一个办法就是认为这个分布中取各个值的概率是相等的，因为此时$H(X)$最大，符合最大熵准则。

即: 熵最大的模型是最好的模型。

根据最大熵原理得到最大熵模型定义。

下面需要先定义一系列函数

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

定义联合分布$P(X=x,Y=y)$ 的经验分布为 $\tilde{P}(X=x,Y=y)$

定义边缘分布$P(X=x)$ 的经验分布为 $\tilde{P}(X=x)$
$$\tilde{P}(X=x,Y=y) = {v(X=x,Y=y)\over N}\ \tilde{P}(X=x) = {v(X=x)\over N}\ $$
其中 $v(X=x,Y=y)$ 表示样本中出现 $(x,y)$ 的频数，$v(X=x)$ 表示训练数据中输入 $x$ 出现的频数。

定义特征函数 $f(x,y)$ 描述输入 $x$ 和输出 $y$ 是否存在联系。

可以认为只要出现在训练集中出现 $(x_i,y_j)$， 其$f(x_i,y_j)=1$， 否则 $f(x_i,y_j)=0$

特征函数$f(x,y)$ 关于经验分布$\tilde{P}(X,Y)$ 的期望，用$E_{\tilde{P} }(f)$ 表示:
$$E_{\tilde{P} }(f) = \sum_{x_i\in X}\sum_{y_j\in Y}\tilde{P}(X=x_i,Y=y_j)f(x_i,y_j)$$
特征函数$f(x,y)$ 关于模型$P(Y|X)$ 与经验分布$\tilde{P}(X)$的期望，用$E_{P}(f)$ 表示:
$$E_{P}(f) = \sum_{x_i\in X}\sum_{y_j\in Y}\tilde{P}(X=x_i)P(Y=y_j|X=x_i)f(x_i,y_j)$$
如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即$E_{\tilde{P} }(f) = E_{P}(f)$。

这个等式将作为模型学习的约束条件，假设存在n个特征函数$f_i(x,y),i=1,\cdots,n$ 那么就有n个约束条件。

最后根据以上公式给出最大熵模型

假设我们需要获得的最优模型是$P(Y|X)$ 简记为 $P$ ，也就是最终通过学习得到的结果。

定义在条件概率分布$P(Y|X)$ 上的条件熵$H(P)$为
$$H(P) = -\sum_{x_i\in X}\sum_{y_j \in Y}\tilde{P}(X=x_i)P(Y=y_j|X=x_i)logP(Y=y_j|X=x_i)$$
假设最大熵模型符合约束条件集合 $C$ ，那么最大熵模型的定义为:
$$C={P| E_{\tilde{P} }(f_i) = E_{P}(f_i), i= 1,2,\cdots,n}\ P_{best} = \underset{P}{argmax} = H(P)$$

最大熵模型的学习

最大熵模型的学习过程就是求解符合最大熵模型的$P(Y|X)$的过程，

由于不容易直接根据最大熵模型的定义求解，需要将问题通过拉格朗日函数转化为约束最优问题。

因此在展开讲解最大熵模型的学习之前需要先介绍一下拉格朗日函数以及拉格朗日对偶性。

拉格朗日函数与拉格朗日对偶性

相关参考:

10幅图帮助理解拉格朗日乘数法的原理

从0到完全理解拉格朗日函数的对偶函数

“拉格朗日对偶问题”如何直观理解？“KKT条件” “Slater条件” “凸优化”打包理解

首先拉格朗日函数能做什么?

拉格朗日函数能够将约束最优化问题变为无约束优化问题并进行求解。

拉格朗日函数如何求解约束最优化问题?

假设$f(x),c_i(x),h_j(x)$ 是定义在$R^n$ 上的连续可微函数，考虑约束最优化问题:
$$\begin{aligned} \underset{x\in R^n}{min}\quad & f(x)\ s.t \quad & c_i(x) \leq 0, i=1,2,\cdots,k\ & h_j(x) = 0, j=1,2,\cdots,l \end{aligned}$$
存在 $k$ 个不等式约束条件 $c_i(x)$ ，以及 $l$ 个约束条件$h_j(x)$。

引入拉格朗日函数将上述问题等价表述为:
$$
L(x,\alpha,\beta) = f(x) + \sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x), \quad \alpha_i\geq 0 \
set\quad A(x)= \underset{\alpha,\beta;\alpha_i\geq 0}{max} L(x,\alpha,\beta)\
p^{} = \underset{x}{min} A(x)
$$
其中的乘子 $a$ 与 $\beta$ 是未定参数向量需要被求解。我们将上述两种表示称为原始问题的最优解 $p^{}$。

通常我们会将原始问题转化为对偶问题求解，对偶问题就是实质相同但从不同角度观察的一对问题。

设对偶问题为$d^{}$，对偶函数为$I(\alpha,\beta)$那么有:$$
set\quad I(\alpha,\beta) =\underset{x}{min} L(x,\alpha,\beta) \quad x\in R^n \
d^{} = \underset{\alpha,\beta}{max} I(\alpha,\beta),\ s.t. \ \alpha_i\geq 0
$$
其中$a_i\geq 0$ 是对偶问题的约束条件，对于对偶问题中在求 $\underset{x}{min} L(x,\alpha,\beta)$ 时，

$x$ 不受约束条件$c_i(x)$ 与 $h_j(x)$ 影响，因此$x \in R^n$。

我们可以证明 $d^{} \leq p^{}$，证明如下:$$
\begin{aligned}
&\underset{\alpha,\beta;\alpha_i\geq 0}{max} L(x,\alpha,\beta) \geq L(x,\alpha,\beta) \geq \underset{x}{min} L(x,\alpha,\beta)\
&set\quad A(x)= \underset{\alpha,\beta;\alpha_i\geq 0}{max} L(x,\alpha,\beta), \quad I(\alpha,\beta) =\underset{x}{min} L(x,\alpha,\beta)\
&\because \quad A(x) \geq I(\alpha,\beta)\
&\therefore \quad \underset{x}{min} A(x) \geq \underset{\alpha,\beta;\alpha_i\geq 0}{max}I(\alpha,\beta)\
&\therefore \quad p^{} \geq d^{}
\end{aligned}
$$
更形象的图解证明可以参考视频 28分钟左右。

满足 $d^{} \leq p^{}$关系的对偶性称为弱对偶性，通过弱对偶性，我们可以给出原始问题$p^{*}$ 的范围。

当原始问题 $p^{}$ 是凸优化问题且满足Slater条件时，有 $d^{} = p^{*}$ ，即原始问题的最优解。

(但是一般情况是凸优化问题就有$d^{}=p^{}$，上述凸优化问题且满足Slater条件是充分条件)

什么是凸优化问题?

当 $f(x),c_i(x)$ 是凸函数，$h_j(x)$ 是仿射函数时，原问题 $p^{*}$ 是一个凸优化问题。

凸函数定义: ${f(x_1)+f(x_2) \over2} \geq f({x_1+x_2 \over 2})$ 且 定义域为凸集。$f(x)=x^2$ 就是一个典型的凸函数。

凸集的定义如下，假设集合 $C$ 是一个定义在 $n$ 维的定义域。

那么右侧橙色所表示的集合 $C$ 是凸集，而左侧蓝色所表示的集合不是凸集。

关于求最大熵问题一般都是凸优化问题，下面给出一个简单的例子感受一下。
$$
p^{}=\underset{P}{max} \ H(P) = -\sum_x P(x)logP(x)\
p^{}=\underset{P}{min} \ -H(P) = \sum_x P(x)logP(x)\
s.t. \ E_p(f_i) = E_{\tilde{P} }(f_i), \ i=1,\cdots,n\
\sum_{x}P(x)=\sum_{x}\tilde{P}(x)=1
$$
假设随机变量$X={x_1,x_2}$ 那么有 $- H(P) = P(x_1)logP(x_1) + (1-P(x_1))log(1-P(x_1))$ 函数图像:

从函数图像可以看出关于熵的函数$-H(P)$ 是一个凸函数。

同时关于最大熵模型的约束条件(仅有等式约束)，符合仿射函数条件。

所以求最大熵问题一般情况下符合凸优化问题定义。

什么是仿射函数?

仿射函数指符合 $c = Wx+b$ 且 $x,w\in R^n$ 关系的函数， 当$x,w$是一维时，它就是典型的线性函数。

而它的解集 $C={x|c=Wx+b}$ 是仿射集。

什么是Slater条件?

Slater条件定义如下:

存在一个点$x \in relint \ D$ ($relint \ D$ 表示非边界定义域)，

使得 $c_i(x) < 0, \ i=1,2,\cdots,k$ 且 $Wx = b$ ，即 $x$ 属于$h_j(x)$的解集。

为何选择求解对偶问题 $b^{}$而不是直接求解$p^{}$ ?

原始问题求解比较困难，主要是因为原始问题中 $f(x)$ 或 $A(x)$ 凹凸性不明确。

而对偶问题中 $I(\alpha,\beta)$ ，一定是一个凹函数 (与凸函数相反)，即一定存在最大值。

关于$I(\alpha,\beta)$ 是凹函数的证明可以看此博客

原始问题与对偶问题的求解

前文简单介绍了使用对偶问题求解拉格朗日函数表示的约束最优化问题。

但是无论是原始问题 $p^{}$还是对偶问题$d^{}$ 它们要求极小极大值或极大极小值，这在理解时非常抽象。

视频 28分钟左右，证明了$p^{}\geq d^{}$ 的同时也展示了如何直接求解原始问题和对偶问题:

设有原始问题$p^{}$:$$\begin{aligned} \underset{x\in R^n}{min}\quad & f(x)\ s.t \quad & c_i(x) \leq 0, i=1,2,\cdots,k\ & h_j(x) = 0, j=1,2,\cdots,l\\ L(x,\alpha,\beta) &= f(x) + \sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x) \end{aligned}$$其对偶问题$d^{}$为:$$d^{*} = \underset{\alpha,\beta}{max} \ \underset{x}{min} L(x,\alpha,\beta)\ s.t. \alpha_i \geq 0$$由于$h_j(x)=0$它对$L(x,\alpha,\beta)$的大小没有贡献，在讨论拉格朗日函数$L$ 的具体值时可以省略。

但是我们仍然需要在拉格朗日函数中加入 $h_j(x)$ 因为它的导数对求解问题有意义。

同时我们可以令$f(x) = t$，$\sum_{i=1}^k\alpha_ic_i(x) = \lambda^T u$ 。

那么拉格朗日函数的形式被简化成:
$$L(x,\alpha,\beta) = L(t,u)= t + \lambda^T u$$
其中 $t$ 是标量，$u$是一个向量，其维度大小等于约束条件 $c_i(x)$ 的个数$i$。

为了简化问题我们可以将拉格朗日函数看成关于变量 $t$ 和 $u$ 的函数 $L$ 。

同时简化后的原始问题和对偶问题为:
$$
p^{} = \underset{x}{min}{t|(t,u)\in G_1, u\leq0 }\
d^{} = \underset{\lambda}{max} \ \underset{x}{min} {t + \lambda^T u|(t,u)\in G_2,\lambda \geq 0}\
$$
其中 $G_1$ 表示原始问题的可行域，$G_2$ 表示对偶问题的可行域，且 $G_1 \in G_2$，

因为对偶问题中 $x$ 不受约束条件影响因此 $G_1$ 是 $G_2$ 的子集。

那么对于原始问题就是在可行域 $G_1$ 处找到一个点$(t,u)$ 使得 $t$ 最小。

而对于对偶问题:

第一步

假定斜率 $\lambda$ 已知，在$G_2$ 内找到一个点 $(t,u)$ ，即调整 $x$ 使得函数 $L(t,u)$ 过该点，且它的截距最小。

这里可能不太好理解为什么找截距$c$ ，即 $c = \underset{x}{min} L(t,u)$ 。

假设找到的函数$L(t,u)$ 过点 $(t^{}, u^{})\in G_2$且斜率$\lambda$已知，那么截距$c = t^{}+\lambda^Tu^{}$ 。

因为一旦确定了 $(t^{}, u^{})$，那么二元函数$L(t,u)$就退化成了一元函数$c -\lambda^Tu= t$。

而对于一元函数带入直线上任意一点都等于同一个值 $c$ 。

第二步

调整 $\lambda$ ，重复第一步，每个斜率各自对应一条直线，找出这些直线中截距最大的那一条。

那么最终的截距$c$ 就是我们要求的对偶问题的解，即$d^{*} = \underset{\lambda}{max} \ \underset{x}{min} {t + \lambda^T u|(t,u)\in G_2,\lambda \geq 0}$。

KKT条件

由于直接求解对偶问题中的极大极小值问题比较抽象，

我们通常会使用 $KKT$ 条件中梯度为0的条件求解拉格朗日函数中的参数$\alpha,\beta$ 以及变量 $x$ ,

可以说只要满足强对偶关系，那么可以使用$KKT$条件求解最优值。

对于凸优化原始问题 $p^{*}$
$$\begin{aligned} \underset{x\in R^n}{min}\quad & f(x)\ s.t \quad & c_i(x) \leq 0, i=1,2,\cdots,k\ & h_j(x) = 0, j=1,2,\cdots,l\ L(x,\alpha,\beta) =& f(x) + \sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x) \end{aligned}$$
其对应的$KKT$ 条件表述如下 :
$$
c_i(x) \leq 0\
h_i(x) = 0\\

\nabla_xL(x,\alpha,\beta) = 0\
\nabla_{\alpha}L(x,\alpha,\beta) = 0\
\nabla_{\beta}L(x,\alpha,\beta) = 0\
a_i \geq 0\\
\alpha_ic_i(x) = 0
$$
$KKT$ 条件的前两条对应原问题中的约束条件。

中间梯度为0以及$a_i\geq 0$ 是对偶问题的约束条件。

统计学习方法附录中有$\nabla_{\alpha}L(x,\alpha,\beta) = 0$ ，$\nabla_{\beta}L(x,\alpha,\beta) = 0$，将这种KKT条件作为强对偶性的充分必要条件。

而其他资料中只有前一条$\nabla_xL(x,\alpha,\beta) = 0$，将这种KKT条件作为强对偶性的必要条件。

最后一个条件被称为互补松弛条件。

在最大熵模型的学习问题中只有等式约束条件，因此不用太关注互补松弛条件。

关于互补松弛条件的含义具体可以查看视频 40分左右的讲解。

可以参考统计学习方法书中的例6.2来感受一下如何使用对偶性以及$KKT$条件求解最大熵模型:

已知随机事件$X = {A,B,C,D,E}$ 各自发生的概率$P(y_i), \ i = 1,\cdots,5$。

要求解随机事件$X$ 的最大熵模型$P(y_i),\ i=1,\cdots, 5$

对于随机事件$X$ 有约束条件:

$P(y_1) + P(y_2) = \tilde{P}(y_1) + \tilde{P}(y_2)= 3/10$，且 $\sum_i P(y_i) = \sum_i \tilde{P}(y_i) = 1$。

则原始问题 $p^{}$表示为:$$\begin{aligned} &min \ -H(P)=\sum_{i=1}^5P(y_i)logP(y_i)\ &s.t \ P(y_1) + P(y_2) = \tilde{P}(y_1) + \tilde{P}(y_2)= 3/10\ &\quad \quad \sum_i P(y_i) = \sum_i \tilde{P}(y_i) = 1 \end{aligned}$$设拉格朗日函数$L(P,w)$, 其中$w$是前面介绍拉格朗日函数里等式约束中的参数向量$\alpha$。$$
L(P,w) = -H(P) + w_1(P_(y_1)+P(y_2)-3/10) + w_0(\sum_{i=1}^5P(y_i)-1)\
p^{} = \underset{x}{min} \ \underset{w}{max} L(x,w)\
d^{*} = \underset{w}{max} \ \underset{x}{min} L(x,w)
$$
$P$ 则指代最大熵模型中的$P(y_i)$，

将 $w$ 作为参数求解 ${\partial L \over \partial P(y_i)} = 0$， 此时偏导的零点为原函数的最小值点，

得到用参数$w = {w_0,w_1}$ 表示的 $P_w(y_i)$。

再使用 $P_w(y_i)$ 表示 $L(P_w,w)$ 。

最后求解 ${\partial L \over \partial w_i} = 0$， 此时偏导的零点为原函数的最大值点，

得到参数 $w$ 的解，将 $w$ 带入 $P_w(y_i)$ 得到随机事件 $X$ 的最大熵模型。

在这个例题中拉格朗日对偶性告诉我们:

由于原问题$min \ -H(P)$ 是一个凸优化问题，

先将 $w$ 作为参数 $P(y_i)$ 作为变量求解问题($d^{*}$)，

和先将 $P(y_i)$ 作为参数 $w$ 作为变量求解问题( $p^{*}$)。

最终的解是一样的($d^{} = p^{}$)。

上述例题在求解对偶问题时可以看到使用了求偏导找零点求最值的过程，

这其实就是在使用 $KKT$ 条件求解强对偶关系问题中最优值的方法。

KKT条件为什么能求出对偶问题最优解?

KKT条件中的梯度为0的条件其实引出了如何构造出拉格朗日函数的问题。

下面以 视频 中的例子结合 知乎 的推导进行讲解。

设有原始问题如下，其中$x=(x_1,x_2)$ 是一个二维向量，讨论仅含有一个等式约束 $h(x)$ 的情况。
$$\begin{aligned} \underset{x\in R^n}{min}\quad & f(x) = x_1^2+x_2^2\ s.t \quad & h(x) = 0\ \end{aligned}$$
下图中蓝色同心圆为 $f(x)$ 的等高线，其梯度$\nabla_x f(x)$为圆上向外的法线，即蓝色箭头。

黄色曲线为等式约束 $h(x)$，其梯度 $\nabla_x h(x)$ 为黄色曲线上的法线，即黄色箭头。

假设已有点$x=(x_1,x_2)$ ，我们想找到符合约束条件 $h(x)$ 的点$x{}=(x_1{},x_2{*})$使得$f(x)$ 最小。

设 $x{*}-x = \delta x$ 那么 $\delta x$ 要满足: $f(x+\delta x) < f(x)$ 且 $h(x+\delta x) = 0$ 。

我们知道从 $x$ 到 $x{*}$ ， $\delta x$ 必须在约束条件 $h(x)$ 上移动，即只能沿着与 $\nabla_x h(x)$ 垂直的方向移动，

所以有等式 $\delta x\nabla_x h(x) = 0$ 。

同时从上图中可以看到在 $\nabla f(x) = \beta \nabla h(x)$ 时能取到符合约束条件的极值点$x{*}$。
$$\because \nabla_x f(x) = \beta \nabla_x h(x),\ \delta x\nabla_x h(x) = 0\ \therefore \delta x \nabla_x f(x) = \delta x \beta \nabla_x h(x) = 0\ \therefore \nabla_x L(x,\beta) = \nabla_x f(x) + \beta \nabla_x h(x) = 0\ \therefore L(x,\beta) = f(x) + \beta h(x)$$
由于在求解最大熵模型中没有涉及到不等式约束，

这里不再展示不等式约束情况下推导拉格朗日函数的具体细节。可以查看视频 6min30s 左右的讲解。

推导最大熵模型的学习过程

相关参考:

李航《统计学习方法》最大熵模型p(y|x)推导的正确过程

前文已经介绍了最大熵模型的定义，现在结合拉格朗日函数以及对偶性求解最大熵模型。

首先写出原始问题以及其约束条件。

统计学习此处给出的约束条件与其推导过程存在问题，此处推导过程主要参考上方参考链接处的方式。
$$
\begin{aligned}
min \ -H(P) &= \sum_{x\in X,y \in Y}\tilde{P}(x)P(y|x)logP(y|x)\
s.t. &\quad 1 - \sum_{x\in X,y\in Y}P(y|x)\tilde{P}(x) = 0\
&\quad E_p(f_i) - E_{\tilde{P} }(f_i) = 0, \ i=1,\cdots,n\\

E_{\tilde{P} }(f) &= \sum_{x\in X,y\in Y}\tilde{P}(x,y)f(x,y)\
E_{P}(f) &= \sum_{x\in X,y\in Y}\tilde{P}(x)P(x|y)f(x,y)
\end{aligned}
$$
此处将$P(X=x_i)$ 简写为 $P(x)$ ，将$P(Y=y_j)$ 简写为 $P(y)$，将 $P(Y=y_j|X=x_i)$ 简写为$P(y|x)$，

将$P(X=x_i, Y=y_j)$ 简写为 $P(x,y)$。

最大熵模型中共有n个特征函数$f_i(x,y)$ ，其中变量$P$ 指代最大熵模型$P(y|x)$。

将上述原始问题用拉格朗日函数改写为等价问题。
$$
\begin{aligned}
L(P,w) =& -H(P) + w_0[1 - \sum_{x\in X,y\in Y}P(y|x)\tilde{P}(x)]+\sum_{i=1}^nw_i(E_p(f_i) - E_{\tilde{P} }(f_i))\

L(P,w) =& \sum_{x\in X,y \in Y}\tilde{P}(x)P(y|x)logP(y|x) + w_0[1 - \sum_{x\in X,y\in Y}P(y|x)\tilde{P}(x)]\
& +\sum_{i=1}^nw_i[\sum_{x\in X,y\in Y}\tilde{P}(x,y)f(x,y) - \sum_{x\in X,y\in Y}\tilde{P}(x)P(x|y)f(x,y)]\\
p^{} =& \underset{P\in C}{min} \ \underset{w}{max} L(P,w)\
d^{} =& \underset{w}{max}\ \underset{P\in C}{min} L(P,w)\
\end{aligned}
$$
最大熵模型的学习最终就是要求出给定训练集$T$ 对应的$P(Y=y_i|X=x_i)$ ，即 $L(P,w)$ 中的 $P$。

根据 $KKT$ 条件，我们需要先求出$\nabla_P L(P,w) = 0$ 时 $P$ 关于参数 $w$ 的表达式。

对每个 $x_i$ 和 $y_j$ 的条件概率 $P(Y=y_i|X=x_i)$ 求 $L(P,w)$ 的偏导，(下文为了简洁用$P(y|x)$表示)。
$$\begin{aligned} {\partial L(P,w) \over \partial P(y|x)} =& \tilde{P}(x)[logP(y|x)+1] - \tilde{P}(x)w_0 + \tilde{P}(x)\sum_{i=1}^n w_i f_i(x,y)\ =&\tilde{P}(x)[logP(y|x) + 1 - w_0 - \sum_{i=1}^n w_i f_i(x,y) ]\ \because &\quad \tilde{P}(x) \not= 0 \quad and \quad {\partial L(P,w) \over \partial P(y|x)}=0\ \therefore &\quad logP(y|x) + 1 - w_0 - \sum_{i=1}^n w_i f_i(x,y) = 0\ \therefore &\quad P_w(y|x) = {exp(\sum_{i=1}^nw_if_i(x,y))\over exp(1-w_0)}\ \because &\quad \sum_{y\in Y}P(y|x) = 1\ \therefore &\quad \sum_{y\in Y}P(y|x) = {\sum_{y\in Y}exp(\sum_{i=1}^nw_if_i(x,y))\over exp(1-w_0) } = 1\ \therefore &\quad Z_w(x) = exp(1-w_0) = \sum_{y\in Y}exp(\sum_{i=1}^nw_if_i(x,y))\ \therefore &\quad P_w(y|x) = {exp(\sum_{i=1}^nw_if_i(x,y))\over Z_w(x)} = {exp(\sum_{i=1}^nw_if_i(x,y))\over \sum_{y\in Y}exp(\sum_{i=1}^nw_if_i(x,y))} \end{aligned}$$
其中 $Z_w(x)$ 表示最优化参数 $w$ 下的规范化因子，$P_w(y|x)$ 表示最优化参数 $w$ 下的最大熵模型。

注意到我们使用$Z_w(x)$ 去替换分母$exp(1-w_0)$ 有一个好处就是能说明 $P_w(y|x)$ 的值与 $w_0$ 无关，

或者说$w_0$ 的值是由$w_i,\ i=1,\cdots,n$ 共同决定的。

目前我们只求出了 $P(y|x)$ 关于 $w$ 的表达式 $P_w(y|x)$，我们需要求解出 $w$ 才能真正求出 $P_w$。

或者说我们只求出了对偶问题中的 $I(w)=\underset{P}{min} \ L(P,w) = L(P_w,w)$ ，还需要求解 $w{*}=\underset{w}{argmax}\ I(w)$。

那么最大熵模型的学习归结为对偶函数 $I(w)$ 的极大化，最终最大熵模型为 $P_{w{*}}(y|x)$。

由于$P_w(y|x)$ 的值与 $w_0$ 无关，且 $w_0[1 - \sum_{x\in X,y\in Y}P(y|x)\tilde{P}(x)]=0$ 对$L(P_w,w)$ 的值没有贡献，

因此此项在化简中可行省略。现在将 $P_w$ 带入$L(P_w,w)$ 并化简:
$$\begin{aligned} L(P_w,w) =& \sum_{x\in X,y \in Y}\tilde{P}(x)P_w(y|x)logP_w(y|x) \ & +\sum_{i=1}^nw_i[\sum_{x\in X,y\in Y}\tilde{P}(x,y)f_i(x,y) - \sum_{x\in X,y\in Y}\tilde{P}(x)P_w(x|y)f_i(x,y)]\ =& \sum_{x\in X,y \in Y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) + \sum_{x\in X,y\in Y}\tilde{P}(x)P_w(y|x)[logP_w(y|x)-\sum_{i=1}^nw_if_i(x,y)]\ =& \sum_{x\in X,y \in Y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) - \sum_{x\in X,y\in Y}\tilde{P}(x)P_w(y|x)logZ_w(x)\\ \because &\quad \sum_yP(y|x) = 1\ \therefore &\quad I(w) = L(P_w,w)= \sum_{x\in X,y \in Y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) - \sum_{x\in X}\tilde{P}(x)logZ_w(x) \end{aligned}$$

统计学习方法在 6.2.4 极大似然估计中证明了对偶函数 $I(w)$ 的极大化等价于最大熵模型的极大似然估计。

设条件概率分布$P_w(y|x)$ 的对数似然函数为$L(P_w)$，那么有以下等式关系:
$$\begin{aligned} L(P_w) =& log\prod_{x\in X,y\in Y} P_w(y|x)^{\tilde{P}(y,x)} \ =& \sum_{x\in X,y\in Y}\tilde{P}(y,x) logP_w(y|x)\ =& \sum_{x\in X,y \in Y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) - \sum_{x\in X}\tilde{P}(x)logZ_w(x)\ \therefore &\quad L(P_w) = I(w) \end{aligned}$$
这样，最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题。

模型学习的最优化算法

常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。

此处主要针对最大熵模型讨论改进的迭代尺度法(IIS)和牛顿法。

相关参考:

深度之眼《李航统计学习方法》课程

最大熵模型原理小结 - 刘建平Pinard

可以想到将$P_w$ 代入原式中再求解 $\nabla_w L(P_w,w) = 0$，

但实际上直接对$L(P_w,w)$ 求 $w$ 的偏导数求解十分困难，需要用到最优化算法求解。

改进的尺度迭代法

改进的尺度迭代法 (IIS) 一般只用于最大熵模型，

它假设当前的参数向量是 $w$ , 我们希望找到一个新的参数向量 $w+\delta$ , 使得对偶函数 $I(w)$ 增大,

重复此操作, 以达到 $\underset{w}{max}\ I(w)$ 的目的。

将这个过程表述为等式:
$$
\begin{aligned}
& I(w+\delta) - I(w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y)-\sum_{x\in X} \tilde{P}(x)log{Z_{w+\delta}(x)\over Z_w(x)}\\

\because & -log\ x \geq 1-x \ ,\ (x>0)\
\therefore & \ I(w+\delta) - I(w) \geq \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x){Z_{w+\delta}(x)\over Z_w(x)}\\

set \ & A(\delta|w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x){Z_{w+\delta}(x)\over Z_w(x)}\
& A(\delta|w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x)\sum_{y\in Y}P_w(y|x)exp\sum_{i=1}^n\delta_if_i(x,y)\
\therefore \ &I(w+\delta) - I(w) \geq A(\delta|w)
\end{aligned}
$$
我们可以最大化$A()$ 来间接找到能使 $I(w)$ 增大最快的 $\delta$ 。

于是想到求解 $A(\delta|w)$ 的最大值，即求出$A(\delta|w)$ 关于 $\delta$ 的导数，找到零点。

但是如果这么做的话会发现，由于$\delta$ 是和 $w$ 同维度的向量，就需要对每个分量$\delta_i$求导。

那么原式中的 $exp\sum_i^n\delta_if_i(x,y)$ 在对$\delta_i$ 求导后就会变成 $f_i(x,y)exp\sum_i^n\delta_if_i(x,y)$ ,

我们发现由于指数函数的存在求导不能将偏导数摆脱其他 $\delta_j$ 分量，使其成为只关于$\delta_i$ 的函数，

我们不能使用未知的 $\delta_j$ 求解$\delta_i$ 的偏导数零点。

为了解决这个问题我们需要引入一个函数：$f^{ # }(x,y) = \sum_if_i(x,y)$

以及一个不等式 Jensen不等式:

对于凸函数 $\phi$ 以及满足$\sum_ia_i = 1$ 的权重 $a_i$，那么就有$\phi(\sum_ia_ib_i)\leq \sum_i a_i\phi(b_i)$
$$
\begin{aligned}
& set \ a_i = {f_i(x,y)\over f^{ # }(x,y)} \ ,\ b_i = \delta_if^{ # }(x,y)\
& A(\delta|w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x)\sum_{y\in Y}P_w(y|x)exp\sum_{i=1}^n a_ix_i\\

\because & \phi(x) = exp(x)\\
\therefore & \phi(\sum_ia_ib_i)\leq \sum_i a_i\phi(b_i)\
\therefore & exp(\sum_i^n {f_i(x,y)\over f^{ # }(x,y)}\delta_if^{ # }(x,y)) \leq \sum_i^n {f_i(x,y)\over f^{ # }(x,y)} exp(\delta_if^{ # }(x,y))\\
& B(\delta|w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x)\sum_{y\in Y}P_w(y|x)\sum_i^n {f_i(x,y)\over f^{ # }(x,y)} exp(\delta_if^{ # }(x,y))\
& A(\delta|w) \geq B(\delta|w)
\end{aligned}
$$
于是我们从 $A(\delta|w)$ 放缩得到 $B(\delta|w)$ , 即有$I(w+\delta) - I(w) \geq B(\delta|w)$ 。

由于现在的指数函数在求和内，那么无关变量$\delta_j$ 就是无关变量对$\delta_i$求导为0，

现在再求$B(\delta|w)$ 对 $\delta_i$ 的偏导数:
$${\part B(\delta|w)\over \part \delta_i} = \sum_{x\in X y\in Y} \tilde{P}(x,y)f_i(x,y) - \sum_{x\in X} \tilde{P}(x)\sum_{y \in Y}P_w(y|x)f_i(x,y)exp(\delta_i f^{ # }(x,y))\ set \quad {\part B(\delta|w)\over \part \delta_i} = 0\ E_{\tilde{P} }(f_i) = \sum_{x\in X y\in Y} \tilde{P}(x,y)f_i(x,y) = \sum_{x\in X,y\in Y} \tilde{P}(x)P_w(y|x)f_i(x,y)exp(\delta_i f^{ # }(x,y))$$
现在只要求解上述关于 $\delta_i$ 的方程就能求出 $w$ 的最优解。

由于$f^{ # }(x,y)$ 并不是对任何$x,y$ 都有 $f^{ # }(x,y)=M$ 因此需要通过牛顿迭代法来求解。

牛顿法与拟牛顿法

相关参考:

优化算法——牛顿法(Newton Method)

首先牛顿法能做什么？

牛顿法可以通过迭代逼近的方法找到函数极值点。

牛顿法如何找到极值点？

牛顿法可以通过泰勒二阶展开推导得到。假设我们要求 $f(x)$ 的极值点, 即 $f’(x)$ 的零点。

我们知道 $f(x)$ 可以通过二阶泰勒展开近似表示为:

$f(x)= f(x_k) + f’(x_k)(x-x_k) + {1\over2}f’’(x_k)(x-x_k)^2$

对上述式子求导并令其为0得到: $f’(x_k) + f’’(x_k)(x-x_k) = 0$ 。

因此有 $x= x_k- {f’(x_k)\over f’’(x_k)}$, 假设我们已经到达了点$(x_k, f(x_k))$ 我们可以用这个等式迭代毕竟极值点。

当然$f(x)$ 需要存在极值点 即存在 $\nabla f(x) = 0$

那么什么是拟牛顿法?

当 $f(x)$ 是一个关于向量 $x$ 的函数时求解其导数和二阶导数会使问题变得复杂。

当 $x$ 为向量时其二阶泰勒展开变为: $f(x) = f(x_k) + g(x_k)(x-x_k) + {1\over2}(x-x_k)^TH(x_k)(x-x_k)$。

其中 $g(x_k)= \nabla f(x_k)$ , $H(x_k)$ 是 $f(x)$ 的海赛矩阵(Hesse matrix):
$$
H(x) =
\begin{bmatrix}
{\part^2f \over \part x_i\part x_j}
\end{bmatrix}{n\times n}
$$
那么迭代公式则改写为: $x{k+1} = x_k - H_k^{-1}g_k$, 其中$H_k = H(x_k)$,$g_k = g(x_k)$

为了求解下一个点$x_{k+1}$ 我们需要反复计算 $n\times n$ 矩阵的逆 $H^{-1}_k$ , 这对计算机非常的不友好。

为了避免求解逆矩阵的运算我们可以将迭代公式稍微变化一下, 于是产生了拟牛顿法。

在统计学习方法的附录中介绍了两种拟牛顿法 DFP算法和 BFGS算法,

其中后者更为流行因此这里仅介绍 BFGS算法。

BFGS算法

记 $y_k = g(x_{k+1}) - g(x_k)$ , $\delta_k = x_{k+1} - x_k$ 。
$$\because \nabla f(x) = g(x_k) + H_k(x-x_k),\quad set \ x= x_{k+1}\ \therefore \nabla f(x_{k+1}) = g(x_{k+1}) \ \therefore g(x_{k+1}) - g(x_k) = H_k(x_{k+1} - x_k)\ \therefore y_k = H_k\delta_k$$
BFGS算法考虑使用$B_{k+1}$ 逼近 $H_k$

将原先的迭代公式改为: $B_{k+1} \delta_k= y_k$

我们假设构造的矩阵$B_k$ 存在这样的递推关系: $B_{k+1} = B_k +P_k+Q_k$

为了满足迭代公式$B_{k+1} \delta_k= y_k$, 则有:
$$B_{k+1}\delta_k = B_k\delta_k +P_k\delta_k + Q_k\delta_k\ P_k\delta_k = y_k\ Q_k\delta_k = - B_k\delta_k\ P_k = { y_k y_k^T\over y_k^T\delta_k}\ Q_k = { B_k \delta_k\delta_k^T B_k \over \delta_k^T B_k\delta_k}$$
当取 $B_0$ 为正定对称矩阵则能保证之后求得的 $B_k$ 都为正定矩阵。

BFGS算法引入了矩阵$B$ 代替海赛矩阵 $H$, 虽然重点推导了$B_k$ 的递推式但是不要忘记

我们最终要求的是令 $g(x_k)=0$ 的解 $x_k$ 。

具体的算法见李航书中附录B，拟牛顿法 —— 算法B.3。

其中第三步中的 $p_k = \delta_k = x_{k+1} - x_k$ , 这里可能会令人疑惑:

为什么会与 $B_k \delta_k = y_k$ 冲突？因为我们要求令 $g(x_{k+1})=0$ 的解$x_{k+1}$ ,

因此我们令 $y_k = g(x_{k-1}) -g(x_k) = 0 - g(x_k)$ , 于是就有了 $B_kp_k=-g_k$ 。

使用拟牛顿算法求解最大熵模型参数$w$

回到最大熵模型的学习问题上。

我们已经求出了最大熵模型 $P(y|x)$ 关于参数 $w$ 的表达式:
$$P_w(y|x) = {exp(\sum_{i=1}^nw_if_i(x,y))\over \sum_{y\in Y} exp(\sum_{i=1}^nw_if_i(x,y))}\ $$
我们希望通过极大化对偶函数$I(w)$ 或似然函数$L(P_w)$ 找到对应的参数 $w$ 。

于是在 改进的迭代尺度法 中我们通过放缩找到了$I(w+\delta) - I(w)$ 的下界函数 $B(\delta|w)$ :
$$B(\delta|w) = \sum_{x\in X, y\in Y}\tilde{P}(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_{x\in X}\tilde{P}(x)\sum_{y\in Y}P_w(y|x)\sum_i^n {f_i(x,y)\over f^{ # }(x,y)} exp(\delta_if^{ # }(x,y))\ $$
我们要做的就是求解$B(\delta|w)$ 的最大值。使用拟牛顿法进行迭代求解,

其中$\delta_i^k=w_i^{k+1}-w_i^{k}$ 表示第k次迭代参数$w_i$ 的增量, $\delta{}_i$为最终解则有:$$
g(\delta_i) = {\part B(\delta|w)\over \part \delta_i} \
g(\delta_i{}) = {\part B(\delta{}|w)\over \part \delta_i{}}=0\
\delta_i^{k+1} = \delta_i^{k} - {g(\delta_i^k) \over g’(\delta_i^k)}
$$
我们也可以不使用改进的迭代尺度算法(IIS) 而是直接针对对偶函数$I(w)$ 使用拟牛顿法求解参数 $w$。

求解最大熵模型$P_w(y|x)$ 要求我们最大化对偶函数 $I(w)$ , 书中设$f(w) = - I(w)$ 有最小值,

则目标函数为 $\underset{w}{min} \ f(w)$, 对$f(w)$ 的一阶导数向量 $g(w)$, 其中$w$ 为n维的向量, $w_i$ 表示第i个分量:
$$\underset{w}{min} \ f(w) = \sum_{x\in X}\tilde{P}(x)logZ_w(x) - \sum_{x\in X,y \in Y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y)\ g(w) = { {\part f(w)\over w_1}, \cdots,{\part f(w)\over w_n} }\ {\part f(w)\over w_i} = \sum_{x\in X y\in Y} \tilde{P}(x)P_w(y|x)f_i(x,y)-\sum_{x\in X y\in Y} \tilde{P}(x,y)f_i(x,y)\ $$
使用BFGS算法求解目标函数最优解过程如下: