逻辑斯谛回归与最大熵模型logistic regression/maximum entropy model

本文是《统计学习方法》李航著学习笔记。
为了叙述方便，将logistic regression mode简称LR，maximum entropy mode简称ME。LR和ME都是判别模型，即将预测实例点分配到“条件概率分布”最大的类中。下述讨论会着重于LR模型和ME模型的学习过程。
逻辑斯谛函数：

l (x) = 1 1 + e - ( x - μ ) / γ ， μ 为 位 置 参 数 ， γ > 0 为 形 状 参 数

逻辑斯谛分布：

X 是连续型随机变量，如

X∼F(x) ，其中

F(x) 是形如上述

l(x) 的逻辑斯谛函数，则称

X 服从逻辑斯谛分布，此时，随机变量

X ：

分 布 函 数 ： F (x) = P (X \leq x) = 1 1 + e - ( x - μ ) / γ

密 度 函 数 ： f (x) = F' (x) = e - ( x - μ ) / γ γ ( 1 + e - ( x - μ ) / γ ) 2

逻辑斯谛回归与最大熵模型logistic regression/maximum entropy model

将上述分布函数变形，并记

1γ=w^，−μγ=b ，则得类似于二类分类问题的logistic模型函数：

F (x) = P (X \leq x) = e 1 γ x - μ γ 1 + e 1 γ x - μ γ = e x p ( w ^ \cdot x + b ) 1 + e x p ( w ^ \cdot x + b )

极大似然估计：
参考 http://blog.csdn.net/cymy001/article/details/78016109

LR模型：

二项LR模型的条件概率分布：

P (Y = 1 | x) = e x p ( w ^ \cdot x + b ) 1 + e x p ( w ^ \cdot x + b ) P (Y = 0 | x) = 1 1 + e x p ( w ^ \cdot x + b )

上述

x=(x(1),x(2),⋯,x(n))T∈Rn 为训练数据的输入，

Y∈{0,1} 为训练数据的输出，

w^∈Rn，b∈R 是需要用训练数据集学习的模型参数。
记

w=(w^T,b)T，x=(x(1),x(2),⋯,x(n),1) ，二项LR模型的条件概率分布进一步化简：

P (Y = 1 | x) = e x p ( w \cdot x ) 1 + e x p ( w \cdot x ) P (Y = 0 | x) = 1 1 + e x p ( w \cdot x )

则对于给定的训练数据集

T=(x1,y1),(x2,y2),⋯,(xN,yN) ，其中

xi∈Rn,yi∈{0,1} ，每个样本点

(xi,yi) 的概率分布为

P (Y = 1 | x i) y i P (Y = 0 | x i) 1 - y i

训练数据集

T 中的样本点联合概率分布为

\prod i = 1 N P (Y = 1 | x i) y i P (Y = 0 | x i) 1 - y i

上式也就是LR模型参数的似然函数，取对数得对数似然函数

L (w) = \sum i = 1 N [y i log P (Y = 1 | x i) + (1 - y i) log P (Y = 0 | x i)] = \sum i = 1 N [y i (w \cdot x i) - log (1 + e x p (w \cdot x i))]

采用极大似然估计求LR模型参数

w ，就是对

L(w) 求极大值，即无约束最优化问题。可以通过梯度下降法、牛顿法等求

w∗=argmaxwL(w) ，将

w∗ 带回

P(Y=1|x),P(Y=0|x) 即是训练数据集

T 学习到的LR模型。

事件的几率：

事 件 的 几 率 = 事 件 发 生 的 概 率 事 件 不 发 生 的 概 率 = 事 件 发 生 的 概 率 1 - 事 件 发 生 的 概 率

事 件 的 对 数 几 率 = log (事 件 的 几 率)

对于二项LR模型，“输出

Y=1 ”这一事件发生的对数几率

log (P ( Y = 1 | x ) 1 - P ( Y = 1 | x )) = w \cdot x

是关于输入

x 的线性函数，这也是LR回归模型的名字由来。

多项LR模型：
输出随机变量 Y 的取值范围是 {1,2,⋯,K} ，对应的LR模型是

P (Y = k | x) = e x p ( w k \cdot x ) 1 + \sum k = 1 K - 1 e x p ( w k \cdot x ), k = 1, 2, \dots, K - 1

P (Y = K | x) = 1 1 + \sum k = 1 K - 1 e x p ( w k \cdot x )

其中

x，wk∈Rn+1 。

—————————————————————————

最大熵原理：
学习概率模型时，在所有可能的概率分布模型中，熵最大的模型是最好的。在满足约束条件的模型集合中，选择熵最大的模型。熵的最大化表示等可能性。

模型获取训练数据集信息：
1.)给定训练数据集 T ，联合分布 P(X,Y) 的经验分布 P˜(X,Y) ，边缘分布 P(X) 的经验分布 P˜(X) 依次为：

P ˜ (X = x, Y = y) = ν ( X = x , Y = y ) | T |, P ˜ (X = x) = ν ( X = x ) | T |

其中

ν(X=x,Y=y) 表示训练数据集中样本

(x,y) 出现的频数，

ν(X=x) 表示训练数据集中样本输入

x 出现的频次，

|T| 表示训练数据集样本容量。
2.)定义特征函数

f(x,y) 满足：

f (x, y) = {1, 0, x 与 y 满 足 某 一 事 实 否 则

soso，若“特征函数 f(x,y) 关于经验分布 P˜(X,Y) 的期望”：

E P ˜ (f) = \sum x, y P ˜ (x, y) f (x, y)

与“特征函数

f(x,y) 关于学习到的条件概率分布模型

P(Y|X) 和经验分布

P˜(X) 的期望”：

E P (f) = \sum x, y P ˜ (x) P (y | x) f (x, y)

相等，则表示“模型能够获取训练数据集的信息”，即

EP˜(f)=EP(f) 。

ME模型：

ME模型就是“满足 EP˜(f)=EP(f) 条件，并且使条件熵

H (P) = - \sum x, y P ˜ (x) P (y | x) log P (y | x)

最大的条件概率分布

P(Y|X) 模型”。

⇔ 如下优化问题：

max P \in C H (P) = \sum x, y P ˜ (x) P (y | x) log P (y | x) s . t . E P (f i) = E P ˜ (f), \sum y P (y | x) = 1 i = 1, 2, \dots, n .

将上述优化问题转化成极小化

minP∈C−H(P) ，再有Lagrange乘子法，可得Lagrange函数

L(P,w) ：

L (P, w) = - H (P) + w 0 (1 - \sum y P (y | x)) + \sum i = 1 n (E P ˜ (f) - E P (f i))

则上述优化问题可

⇔ 转化为无约束优化问题：

min P \in C max w L (P, w)

由于

L(P,w) 是

P 的凸函数，进一步，优化问题可以转化成对偶问题：

max w min P \in C L (P, w)

a.)先求

minP∈CL(P,w) 得关于

w 的条件概率分布

Pw(y|x) ：

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ \partial L ( P , w ) \partial P ( y | x ) = 0 P ˜ (x) = 0 \sum y P (y | x) = 1 \Rightarrow ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ P w (y | x) = 1 Z w ( x ) e x p (\sum i = 1 n w i f i (x, y)) Z w (x) = \sum y e x p (\sum i = 1 n w i f i (x, y))

上式

Pw(y|x) 即为 最大熵模型，记

Φ (w) = min P \in C L (P, w) = L (P w, w) = \sum x, y P ˜ (x, y) \sum i = 1 n w i f i (x, y) - \sum x P ˜ (x) log Z w (x)

称

Φ(w) 为“对偶函数”，此时优化目标可转化为

max w Φ (w)

b.)到此为止，就可以采用改进的迭代尺度法或者拟牛顿法求解“

Φ(w) 关于

w 的极大值问题”了。
改进的迭代尺度法：
假设最大熵模型的当前参数向量

w=(w1,w2,⋯,wn)T ，希望找到一个新的参数向量

w+δ=(w1+δ1,w2+δ2,⋯,wn+δn) ，使模型的对偶函数值

Φ(w+δ)>Φ(w) 。

Φ (w + δ) - Φ (w) = \sum x, y P ˜ (x, y) \sum i = 1 n δ i f i (x, y) - \sum x P ˜ (x) log Z w + δ ( x ) Z w ( x ) \geq \sum x, y P ˜ (x, y) \sum i = 1 n δ i f i (x, y) + 1 - \sum x P ˜ (x) \sum y P w (y | x) e x p (\sum i = 1 n δ i f i (x, y)) ≜ A (δ | w)

由于指数项

exp(∑ni=1δifi(x,y)) 关于

δi 求导时无法分离

δj,j≠i ，所以利用Jensen不等式进一步降低下限，记

f♯(x,y)=∑ifi(x,y) 为所有特征在

(x,y) 出现的次数，于是有：

A (δ | w) = \sum x, y P ˜ (x, y) \sum i = 1 n δ i f i (x, y) + 1 - \sum x P ˜ (x) \sum y P w (y | x) e x p (f ♯ (x, y) \sum i = 1 n δ i f i ( x , y ) f ♯ ( x , y )) \geq \sum x, y P ˜ (x, y) \sum i = 1 n δ i f i (x, y) + 1 - \sum x P ˜ (x) \sum y P w (y | x) \sum i = 1 n f i ( x , y ) f ♯ ( x , y ) e x p (δ i f ♯ (x, y)) ≜ B (δ | w)

由上式可见

B(δ|w) 关于

δi 求导可分离其余

δj,j≠i ，则由

∂B(δ|w)∂δi=0 得：

\sum x, y P ˜ (x, y) f i (x, y) = \sum x, y P ˜ (x) P w (y | x) f i (x, y) e x p (δ i f ♯ (x, y))

由此式求解

δi 即可，这是一个一元函数求零点问题，当解析解不易求解时，可通过牛顿法、二分法等求解。

拟牛顿法BFGS算法：

min w \in R n - Φ (w) = max w \in R n Φ (w)

不同于改进的迭代尺度法，拟牛顿法直接处理的是多元函数的优化问题，记

g(w)=−∇Φ(w) ，则由拟牛顿条件

Bkpk=−gk 更新参数

wk 每一步的迭代方向；由一维精确或不精确线性搜索方法进行步长搜索更新

f(w(k)+λkpk)=minλ≥0f(w(k)+λkpk) ；由BFGS公式对类Hessian矩阵进行更新。

ME模型生成算法的问题转化：

（1.）学习概率模型时，在满足已有事实条件下，不确定部分按照“等可能”处理，转化成“最大熵原理”。
（2.）“最大熵模型”也就是“在满足约束的条件下，使条件熵最大的条件概率分布模型”，这是一个含等式约束的优化问题，通过Lagrange乘子法求解，进而转化成“对偶问题”，可以先求出“含参数的最大熵条件概率分布模型”。
（3.）对“含参数的最大熵条件概率分布模型”确定的“对偶函数”关于参数求极大值。A.)一种方法，可以通过“改进的迭代尺度法”求迭代参数序列，使“对偶函数”递增。以降低“对偶函数”增加幅度为代价，将“多变量参数优化”通过Jensen不等式转化成“单变量参数优化”问题。B.)另一种方法，可以直接利用拟牛顿法的BFGS等算法对“对偶函数”关于参数求极值。

最后，由于“最大熵模型 P(y|x) 关于训练数据集 T 的联合概率分布的对数似然函数” ⇔ “对偶函数”，所以“对偶函数的极大化” ⇔ “最大熵模型的极大似然估计”：

秒客网

逻辑斯谛回归与最大熵模型logistic regression/maximum entropy model

LR模型：

ME模型：

ME模型生成算法的问题转化：

相关文章