本文是《统计学习方法》李航著学习笔记。
为了叙述方便，将logistic regression mode简称LR，maximum entropy mode简称ME。LR和ME都是判别模型，即将预测实例点分配到“条件概率分布”最大的类中。下述讨论会着重于LR模型和ME模型的学习过程。
逻辑斯谛函数：
l(x)=11+e−(x−μ)/γ，μ为位置参数，γ>0为形状参数
逻辑斯谛分布：
X是连续型随机变量，如
X∼F(x)，其中
F(x)是形如上述
l(x)的逻辑斯谛函数，则称
X服从逻辑斯谛分布，此时，随机变量
X：
分布函数：F(x)=P(X≤x)=11+e−(x−μ)/γ
密度函数：f(x)=F′(x)=e−(x−μ)/γγ(1+e−(x−μ)/γ)2
将上述分布函数变形，并记
1γ=w^，−μγ=b，则得类似于二类分类问题的logistic模型函数：
F(x)=P(X≤x)=e1γx−μγ1+e1γx−μγ=exp(w^⋅x+b)1+exp(w^⋅x+b)
极大似然估计：
参考
http://blog.csdn.net/cymy001/article/details/78016109
LR模型：
二项LR模型的条件概率分布：
P(Y=1|x)=exp(w^⋅x+b)1+exp(w^⋅x+b)P(Y=0|x)=11+exp(w^⋅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)=exp(w⋅x)1+exp(w⋅x)P(Y=0|x)=11+exp(w⋅x)
则对于给定的训练数据集
T=(x1,y1),(x2,y2),⋯,(xN,yN)，其中
xi∈Rn,yi∈{0,1}，每个样本点
(xi,yi)的概率分布为
P(Y=1|xi)yiP(Y=0|xi)1−yi
训练数据集
T中的样本点联合概率分布为
∏i=1NP(Y=1|xi)yiP(Y=0|xi)1−yi
上式也就是LR模型参数的似然函数，取对数得对数似然函数
L(w)=∑i=1N[yilogP(Y=1|xi)+(1−yi)logP(Y=0|xi)]=∑i=1N[yi(w⋅xi)−log(1+exp(w⋅xi))]
采用极大似然估计求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⋅x
是关于输入
x的线性函数，这也是LR回归模型的名字由来。
多项LR模型：
输出随机变量Y的取值范围是{1,2,⋯,K}，对应的LR模型是
P(Y=k|x)=exp(wk⋅x)1+∑k=1K−1exp(wk⋅x),k=1,2,⋯,K−1
P(Y=K|x)=11+∑k=1K−1exp(wk⋅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)的期望”：
EP˜(f)=∑x,yP˜(x,y)f(x,y)
与“特征函数
f(x,y)关于学习到的条件概率分布模型
P(Y|X)和经验分布
P˜(X)的期望”：
EP(f)=∑x,yP˜(x)P(y|x)f(x,y)
相等，则表示“模型能够获取训练数据集的信息”，即
EP˜(f)=EP(f)。
ME模型：
ME模型就是“满足EP˜(f)=EP(f)条件，并且使条件熵
H(P)=−∑x,yP˜(x)P(y|x)logP(y|x)
最大的条件概率分布
P(Y|X)模型”。
⇔如下优化问题：
maxP∈CH(P)=∑x,yP˜(x)P(y|x)logP(y|x)s.t.EP(fi)=EP˜(f),∑yP(y|x)=1i=1,2,…,n.
将上述优化问题转化成极小化
minP∈C−H(P)，再有Lagrange乘子法，可得Lagrange函数
L(P,w)：
L(P,w)=−H(P)+w0(1−∑yP(y|x))+∑i=1n(EP˜(f)−EP(fi))
则上述优化问题可
⇔转化为无约束优化问题：
minP∈CmaxwL(P,w)
由于
L(P,w)是
P的凸函数，进一步，优化问题可以转化成对偶问题：
maxwminP∈CL(P,w)
a.)先求
minP∈CL(P,w)得关于
w的条件概率分布
Pw(y|x)：
⎧⎩⎨⎪⎪⎪⎪⎪⎪∂L(P,w)∂P(y|x)=0P˜(x)=0∑yP(y|x)=1⇒⎧⎩⎨⎪⎪⎪⎪⎪⎪Pw(y|x)=1Zw(x)exp(∑i=1nwifi(x,y))Zw(x)=∑yexp(∑i=1nwifi(x,y))
上式
Pw(y|x)即为
最大熵模型，记
Φ(w)=minP∈CL(P,w)=L(Pw,w)=∑x,yP˜(x,y)∑i=1nwifi(x,y)−∑xP˜(x)logZw(x)
称
Φ(w)为“对偶函数”，此时优化目标可转化为
maxwΦ(w)
b.)到此为止，就可以采用改进的迭代尺度法或者拟牛顿法求解“
Φ(w)关于
w的极大值问题”了。
改进的迭代尺度法：
假设最大熵模型的当前参数向量
w=(w1,w2,⋯,wn)T，希望找到一个新的参数向量
w+δ=(w1+δ1,w2+δ2,⋯,wn+δn)，使模型的对偶函数值
Φ(w+δ)>Φ(w)。
Φ(w+δ)−Φ(w)=∑x,yP˜(x,y)∑i=1nδifi(x,y)−∑xP˜(x)logZw+δ(x)Zw(x)≥∑x,yP˜(x,y)∑i=1nδifi(x,y)+1−∑xP˜(x)∑yPw(y|x)exp(∑i=1nδifi(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)=∑x,yP˜(x,y)∑i=1nδifi(x,y)+1−∑xP˜(x)∑yPw(y|x)exp(f♯(x,y)∑i=1nδifi(x,y)f♯(x,y))≥∑x,yP˜(x,y)∑i=1nδifi(x,y)+1−∑xP˜(x)∑yPw(y|x)∑i=1nfi(x,y)f♯(x,y)exp(δif♯(x,y))≜B(δ|w)
由上式可见
B(δ|w)关于
δi求导可分离其余
δj,j≠i，则由
∂B(δ|w)∂δi=0得：
∑x,yP˜(x,y)fi(x,y)=∑x,yP˜(x)Pw(y|x)fi(x,y)exp(δif♯(x,y))
由此式求解
δi即可，这是一个一元函数求零点问题，当解析解不易求解时，可通过牛顿法、二分法等求解。
拟牛顿法BFGS算法：
minw∈Rn−Φ(w)=maxw∈RnΦ(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的联合概率分布的对数似然函数” ⇔ “对偶函数”，所以“对偶函数的极大化”⇔“最大熵模型的极大似然估计”：
