下载掌阅APP，畅读海量书库
立即打开
逻辑斯谛回归（logistic regression）是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型（maximum entropy model）。逻辑斯谛回归模型与最大熵模型都属于对数线性模型。本章首先介绍逻辑斯谛回归模型，然后介绍最大熵模型，最后讲述逻辑斯谛回归与最大熵模型的学习算法，包括改进的迭代尺度算法和拟牛顿法。
首先介绍逻辑斯谛分布（logistic distribution）。
定义6.1（逻辑斯谛分布） 设 X 是连续随机变量， X 服从逻辑斯谛分布是指 X 具有下列分布函数和密度函数：
式中， µ 为位置参数， γ >0为形状参数。
逻辑斯谛分布的密度函数
f
（
x
）和分布函数
F
（
x
）的图形如图6.1所示。分布函数属于逻辑斯谛函数，其图形是一条S形曲线（sigmoid curve）。该曲线以点
为中心对称，即满足
图6.1 逻辑斯谛分布的密度函数与分布函数
曲线在中心附近增长速度较快，在两端增长速度较慢。形状参数 γ 的值越小，曲线在中心附近增长得越快。
二项逻辑斯谛回归模型（binomial logistic regression model）是一种分类模型，由条件概率分布 P （ Y|X ）表示，形式为参数化的逻辑斯谛分布。这里，随机变量 X 取值为实数，随机变量 Y 取值为1或0。我们通过监督学习的方法来估计模型参数。
定义6.2（逻辑斯谛回归模型） 二项逻辑斯谛回归模型是如下的条件概率分布：
这里， x ∈ R n 是输入， Y ∈{0,1}是输出， w ∈ R n 和 b ∈ R 是参数， w 称为权值向量， b 称为偏置， w · x 为 w 和 x 的内积。
对于给定的输入实例 x ，按照式（6.3）和式（6.4）可以求得 P （ Y =1| x ）和 P （ Y =0| x ）。逻辑斯谛回归比较两个条件概率值的大小，将实例 x 分到概率值较大的那一类。
有时为了方便，将权值向量和输入向量加以扩充，仍记作 w ， x ，即 w =（ w (1) , w (2) ,…, w ( n ) , b ） T ， x =（ x (1) , x (2) ,…, x ( n ) ,1） T 。这时，逻辑斯谛回归模型如下：
现在考查逻辑斯谛回归模型的特点。一个事件的几率（odds）是指该事件发生的概率与该事件不发生的概率的比值。如果事件发生的概率是
p
，那么该事件的几率是
，该事件的对数几率（log odds）或logit函数是
对逻辑斯谛回归而言，由式（6.5）与式（6.6）得：
这就是说，在逻辑斯谛回归模型中，输出 Y =1的对数几率是输入 x 的线性函数。或者说，输出 Y =1的对数几率是由输入 x 的线性函数表示的模型，即逻辑斯谛回归模型。
换一个角度看，考虑对输入 x 进行分类的线性函数 w · x ，其值域为实数域。注意，这里 x ∈ R n +1 ， w ∈ R n +1 。通过逻辑斯谛回归模型定义式（6.5）可以将线性函数 w · x 转换为概率：
这时，线性函数的值越接近正无穷，概率值就越接近1；线性函数的值越接近负无穷，概率值就越接近0（如图6.1所示）。这样的模型就是逻辑斯谛回归模型。
逻辑斯谛回归模型学习时，对于给定的训练数据集 T ={（ x 1 , y 1 ）,（ x 2 , y 2 ）,…,（ x N , y N ）}，其中， x i ∈ R n ， y i ∈{0,1}，可以应用极大似然估计法估计模型参数，从而得到逻辑斯谛回归模型。
设
P （ Y =1| x ）= π （ x ）, P （ Y =0| x ）=1− π （ x ）
似然函数为
对数似然函数为
对 L （ w ）求极大值，得到 w 的估计值。
这样，问题就变成了以对数似然函数为目标函数的最优化问题。逻辑斯谛回归学习中通常采用的方法是梯度下降法及拟牛顿法。
假设
w
的极大似然估计值是
，那么学到的逻辑斯谛回归模型为
上面介绍的逻辑斯谛回归模型是二项分类模型，用于二类分类。可以将其推广为多项逻辑斯谛回归模型（multi-nominal logistic regression model），用于多类分类。假设离散型随机变量 Y 的取值集合是{1,2,…, K }，那么多项逻辑斯谛回归模型是
这里， x ∈ R n +1 ， w k ∈ R n +1 。
二项逻辑斯谛回归的参数估计法也可以推广到多项逻辑斯谛回归。
最大熵模型（maximum entropy model）由最大熵原理推导实现。这里首先叙述一般的最大熵原理，然后讲解最大熵模型的推导，最后给出最大熵模型学习的形式。
最大熵原理是概率模型学习的一个准则。最大熵原理认为：学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。
假设离散随机变量 X 的概率分布是 P （ X ），则其熵（参照5.2.2节）是
熵满足下列不等式：
0≤ H （ P ）≤log| X |
式中，| X |是 X 的取值个数，当且仅当 X 的分布是均匀分布时右边的等号成立。这就是说，当 X 服从均匀分布时，熵最大。
直观地，最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。“等可能”不容易操作，而熵是一个可优化的数值指标。
首先，通过一个简单的例子来介绍一下最大熵原理 [1] 。
例6.1 假设随机变量 X 有5个取值{ 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 ）=1
满足这个约束条件的概率分布有无穷多个。如果没有任何其他信息，仍要对概率分布进行估计，一个办法就是认为这个分布中取各个值的概率是相等的：
等概率表示了对事实的无知。因为没有更多的信息，这种判断是合理的。
有时，能从一些先验知识中得到一些对概率值的约束条件，例如：
P （ A ）+ P （ B ）+ P （ C ）+ P （ D ）+ P （ E ）=1
满足这两个约束条件的概率分布仍然有无穷多个。在缺少其他信息的情况下，可以认为 A 与 B 是等概率的， C ， D 与 E 是等概率的，于是，
如果还有第3个约束条件：
P （ A ）+ P （ B ）+ P （ C ）+ P （ D ）+ P （ E ）=1
可以继续按照满足约束条件下求等概率的方法估计概率分布。这里不再继续讨论。以上概率模型学习的方法正是遵循了最大熵原理。
图6.2提供了用最大熵原理进行概率模型选择的几何解释。概率模型集合 P 可由欧氏空间中的单纯形（simplex） [2] 表示，如左图的三角形（2-单纯形）。一个点代表一个模型，整个单纯形代表模型集合。右图上的一条直线对应一个约束条件，直线的交集对应满足所有约束条件的模型集合。一般地，这样的模型仍有无穷多个。学习的目的是在可能的模型集合中选择最优模型，最大熵原理则给出最优模型选择的一个准则。
图6.2 概率模型集合
最大熵原理是统计学习的一般原理，将它应用到分类得到最大熵模型。
假设分类模型是一个条件概率分布 P （ Y|X ）， X ∈ X ⊆ R n 表示输入， Y ∈ Y 表示输出， X 和 Y 分别是输入和输出的集合。这个模型表示的是对于给定的输入 X ，以条件概率 P （ Y|X ）输出 Y 。
给定一个训练数据集
T ={（ x 1 , y 1 ）,（ x 2 , y 2 ）,…,（ x N , y N ）}
学习的目标是用最大熵原理选择最好的分类模型。
首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布
P
（
X,Y
）的经验分布和边缘分布
P
（
X
）的经验分布，分别以
和
表示。这里，
其中， ν （ X = x,Y = y ）表示训练数据中样本（ x,y ）出现的频数， ν （ X = x ）表示训练数据中输入 x 出现的频数， N 表示训练样本容量。
用特征函数（feature function） f （ x,y ）描述输入 x 和输出 y 之间的某一个事实。其定义是
它是一个二值函数
，当
x
和
y
满足这个事实时取值为1，否则取值为0。
特征函数
f
（
x,y
）关于经验分布
的期望值用
表示：
特征函数
f
（
x,y
）关于模型
P
（
Y|X
）与经验分布
的期望值用
E
P
（
f
）表示：
如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即
或
我们将式（6.10）或式（6.11）作为模型学习的约束条件。假如有 n 个特征函数 f i （ x,y ）， i =1,2,…, n ，那么就有 n 个约束条件。
定义6.3（最大熵模型） 假设满足所有约束条件的模型集合为
定义在条件概率分布 P （ Y|X ）上的条件熵为
则模型集合 C 中条件熵 H （ P ）最大的模型称为最大熵模型。式中的对数为自然对数。
最大熵模型的学习过程就是求解最大熵模型的过程。最大熵模型的学习可以形式化为约束最优化问题。
对于给定的训练数据集 T ={（ x 1 , y 1 ）,（ x 2 , y 2 ）,…,（ x N , y N ）}以及特征函数 f i （ x,y ）， i =1,2,…, n ，最大熵模型的学习等价于约束最优化问题：
按照最优化问题的习惯，将求最大值问题改写为等价的求最小值问题：
求解约束最优化问题（6.14）~（6.16）得出的解就是最大熵模型学习的解。下面给出具体推导。
这里，将约束最优化的原始问题转换为无约束最优化的对偶问题
，通过求解对偶问题求解原始问题。
首先，引入拉格朗日乘子 w 0 , w 1 , w 2 ,…, w n ，定义拉格朗日函数 L （ P,w ）：
最优化的原始问题是
对偶问题是
由于拉格朗日函数 L （ P,w ）是 P 的凸函数，原始问题（6.18）的解与对偶问题（6.19）的解是等价的。这样，可以通过求解对偶问题（6.19）来求解原始问题（6.18）。
首先，求解对偶问题（6.19）内部的极小化问题
。
是
w
的函数，将其记作
Ψ （ w ）称为对偶函数。同时，将其解记作
具体地，求 L （ P,w ）对 P （ y|x ）的偏导数：
令偏导数等于0，在
的情况下，解得：
由于
，得：
其中，
Z w （ x ）称为规范化因子， f i （ x,y ）是特征函数， w i 是特征的权值。由式（6.22）、式（6.23）表示的模型 P w = P w （ y|x ）就是最大熵模型。这里， w 是最大熵模型中的参数向量。
之后，求解对偶问题外部的极大化问题：
将其解记为 w * ，即
这就是说，可以应用最优化算法求对偶函数
Ψ
（
w
）的极大化，得到
w
*
，用来表示
P
*
∈
C
。这里，
是学习到的最优模型（最大熵模型）。也就是说，最大熵模型的学习归结为对偶函数
Ψ
（
w
）的极大化。
例6.2 学习例6.1中的最大熵模型。
解 为了方便，分别以 y 1 , y 2 , y 3 , y 4 , y 5 表示 A ， B ， C ， D 和 E ，于是最大熵模型学习的最优化问题是
引入拉格朗日乘子 w 0 , w 1 ，定义拉格朗日函数：
L
（
P,w
）=
根据拉格朗日对偶性，可以通过求解对偶最优化问题得到原始最优化问题的解，所以求解
首先求解 L （ P,w ）关于 P 的极小化问题。为此，固定 w 0 , w 1 ，求偏导数：
令各偏导数等于0，解得：
P （ y 1 ）= P （ y 2 ）=e −w 1 −w 0 − 1
P （ y 3 ）= P （ y 4 ）= P （ y 5 ）=e −w 0 − 1
于是，
再求解 L （ P w , w ）关于 w 的极大化问题：
分别求 L （ P w , w ）对 w 0 , w 1 的偏导数并令其为0，得到：
于是得到所要求的概率分布为
从以上最大熵模型学习中可以看出，最大熵模型是由式（6.22）、式（6.23）表示的条件概率分布。下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。
已知训练数据的经验概率分布
，条件概率分布
P
（
Y|X
）的对数似然函数表示为
当条件概率分布
P
（
y|x
）是最大熵模型（式（6.22）和式（6.23））时，对数似然函数
为
再看对偶函数 Ψ （ w ）。由式（6.17）及式（6.20）可得：
最后一步用到
。
比较式（6.26）和式（6.27），可得：
既然对偶函数
Ψ
（
w
）等价于对数似然函数
，于是证明了最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计这一事实。
这样，最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题。
可以将最大熵模型写成更一般的形式：
其中，
这里， x ∈ R n 为输入， y ∈{1,2,…, K }为输出， w ∈ R n 为权值向量， f i （ x,y ）， i =1,2,…, n 为任意实值特征函数。
最大熵模型与逻辑斯谛回归模型有类似的形式，它们又称为对数线性模型（logarithmic linear model）。模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计。
逻辑斯谛回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化的观点看，这时的目标函数具有很好的性质。它是光滑的凸函数，因此多种最优化的方法都适用，保证能找到全局最优解。常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快。
下面介绍基于改进的迭代尺度法与拟牛顿法的最大熵模型学习算法，梯度下降法参阅附录A。
改进的迭代尺度法（improved iterative scaling，IIS）是一种最大熵模型学习的最优化算法。
已知最大熵模型为
其中，
对数似然函数为
目标是通过极大似然估计学习模型参数，即求对数似然函数的极大值
。
IIS的想法是：假设最大熵模型当前的参数向量是 w =（ w 1 , w 2 ,…, w n ） T ，我们希望找到一个新的参数向量 w + δ =（ w 1 + δ 1 , w 2 + δ 2 ,…, w n + δ n ） T ，使得模型的对数似然函数值增大。如果能有这样一种参数向量更新的方法 τ ： w→w + δ ，那么就可以重复使用这一方法，直至找到对数似然函数的最大值。
对于给定的经验分布
，模型参数从
w
到
w
+
δ
，对数似然函数的改变量是
利用不等式
−log α ≥1− α,α >0
建立对数似然函数改变量的下界：
将右端记为
于是有
L （ w + δ ）− L （ w ）≥ A （ δ|w ）
即 A （ δ|w ）是对数似然函数改变量的一个下界。
如果能找到适当的
δ
使下界
A
（
δ|w
）提高，那么对数似然函数也会提高。然而，函数
A
（
δ|w
）中的
δ
是一个向量，含有多个变量，不易同时优化。IIS试图一次只优化其中一个变量
δ
i
，而固定其他变量
δ
j
，
。
为达到这一目的，IIS进一步降低下界 A （ δ|w ）。具体地，IIS引进一个量 f # （ x,y ）：
因为 f i 是二值函数，故 f # （ x,y ）表示所有特征在（ x,y ）出现的次数。这样， A （ δ|w ）可以改写为
利用指数函数的凸性以及对任意
i
，有
且这一事实，根据Jensen不等式，得到：
于是式（6.30）可改写为
记不等式（6.31）右端为
于是得到：
L （ w + δ ）− L （ w ）≥ B （ δ|w ）
这里， B （ δ|w ）是对数似然函数改变量的一个新的（相对不紧的）下界。
求 B （ δ|w ）对 δ i 的偏导数：
在式（6.32）里，除 δ i 外不含任何其他变量。令偏导数为0得到：
于是，依次对 δ i 求解方程（6.33）可以求出 δ 。
这就给出了一种求 w 的最优解的迭代算法，即改进的迭代尺度算法IIS。
算法6.1（改进的迭代尺度算法IIS）
输入：特征函数
f
1
,
f
2
,…,
f
n
，经验分布
，模型
P
w
（
y|x
）。
输出：最优参数值
，最优模型
。
（1）对所有 i ∈{1,2,…, n }，取初值 w i =0。
（2）对每一个 i ∈{1,2,…, n }：
（a）令 δ i 是方程
的解，这里，
（b）更新 w i 值： w i ← w i + δ i 。
（3）如果不是所有 w i 都收敛，重复步骤（2）。
这一算法关键的一步是步骤（a），即求解方程（6.33）中的 δ i 。如果 f # （ x,y ）是常数，即对任何 x,y ，有 f # （ x,y ）= M ，那么 δ i 可以显式地表示成
如果
f
#
（
x,y
）不是常数，那么必须通过数值计算求
δ
i
。简单有效的方法是牛顿法。以
g
（
δ
i
）=0表示方程（6.33），牛顿法通过迭代求得
，使得
。迭代公式是
只要适当选取初始值
，由于
δ
i
的方程（6.33）有单根，因此牛顿法恒收敛，而且收敛速度很快。
最大熵模型学习还可以应用牛顿法或拟牛顿法，参阅附录B。
对于最大熵模型而言，
目标函数为
梯度为
其中，
相应的拟牛顿法BFGS算法如下。
算法6.2（最大熵模型学习的BFGS算法）
输入：特征函数
f
1
,
f
2
,…,
f
n
，经验分布
，目标函数
f
（
w
），梯度
g
（
w
）=
∇
f
（
w
），精度要求
ε
。
输出：最优参数值
w
*
，最优模型
。
（1）选定初始点 w (0) ，取 B 0 为正定对称矩阵，置 k =0；
（2）计算 g k = g （ w ( k ) ），若‖ g k ‖< ε ，则停止计算，得 w * = w ( k ) ；否则，转步骤（3）；
（3）由 B k p k =− g k 求出 p k ；
（4）一维搜索：求 λ k 使得
（5）置 w ( k +1) = w ( k ) + λ k p k ；
（6）计算 g k +1 = g （ w ( k +1) ），若‖ g k +1 ‖< ε ，则停止计算，得 w * = w ( k +1) ；否则，按下式求出 B k +1 ：
其中，
y k = g k +1 − g k , δ k = w ( k +1) − w ( k )
（7）置 k = k +1，转步骤（3）。
1．逻辑斯谛回归模型是由以下条件概率分布表示的分类模型，可以用于二类或多类分类。
这里， x 为输入特征， w 为特征的权值。
逻辑斯谛回归模型源自逻辑斯谛分布，其分布函数 F （ x ）是S形函数。逻辑斯谛回归模型是由输入的线性函数表示的输出的对数几率模型。
2．最大熵模型是由以下条件概率分布表示的分类模型，也可以用于二类或多类分类。
其中， Z w （ x ）是规范化因子， f i 为特征函数， w i 为特征的权值。
3．最大熵模型可以由最大熵原理推导得出。最大熵原理是概率模型学习或估计的一个准则。最大熵原理认为在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。
最大熵原理应用到分类模型的学习中，有以下约束最优化问题：
求解此最优化问题的对偶问题得到最大熵模型。
4．逻辑斯谛回归模型与最大熵模型都属于对数线性模型。
5．逻辑斯谛回归模型及最大熵模型学习一般采用极大似然估计或正则化的极大似然估计。逻辑斯谛回归模型及最大熵模型学习可以形式化为无约束最优化问题，求解该最优化问题的算法有改进的迭代尺度法、梯度下降法、拟牛顿法。
逻辑斯谛回归的介绍参见文献 [1] ，最大熵模型的介绍参见文献 [2] 和文献 [3] 。逻辑斯谛回归模型与朴素贝叶斯模型的关系参见文献 [4] ，逻辑斯谛回归模型与AdaBoost的关系参见文献 [5] ，逻辑斯谛回归模型与核函数的关系参见文献 [6] 。
6.1 确认逻辑斯谛分布属于指数分布族。
6.2 写出逻辑斯谛回归模型学习的梯度下降算法。
6.3 写出最大熵模型学习的DFP算法（关于一般的DFP算法参见附录B）。
［1］ BERGER A, DELLA PIETRA S D, PIETRA V D.A maximum entropy approach to natural language processing[J]. Computational Linguistics, 1996, 22(1)：39–71.
［2］ BERGER A. The improved iterative scaling algorithm：a gentle introduction[R/OL].http：//www.cs.cmu.edu/afs/cs/user/aberger/www/ps/scaling.ps.
［3］ HASTIE T, TIBSHIRANI R，FRIEDMAN J. The elements of statistical learning：data mining, inference, and prediction[M].范明，柴玉梅，昝红英，等译. Springer, 2001.
［4］ MITCHELL T M. Machine learning[M].曾华军，张银奎，等译. McGraw-Hill Companies, Inc. 1997.
［5］ COLLINS M, SCHAPIRE R E, SINGER Y. Logistic regression, AdaBoost and Bregman distances[J]. Machine Learning, 2002，48(1–3)：253–285.
［6］ CANU S, SMOLA A J. Kernel method and exponential family[J]. Neurocomputing, 2005, 69：714–720.
[2] 单纯形是在 n 维欧氏空间中的 n +1个仿射无关的点的集合的凸包。