来源 | AI小白入门
作者 | 文杰
编辑 | yuquanle
完整代码见:原文链接
1. Logistic回归
分类问题可以看作是在回归函数上的一个分类。一般情况下定义二值函数,然而二值函数构成的损失函数非凸,一般采用sigmoid函数平滑拟合(当然也可以看作是一种软划分,概率划分):从函数图像我们能看出,该函数有很好的特性,适合二分类问题。至于为何选择Sigmoid函数,后面可以从广义线性模型导出为什么是Sigmoid函数。
逻辑回归可以看作是在线性回归的基础上构建的分类模型,理解的角度有多种(最好的当然是概率解释和最小对数损失),而最直接的理解是考虑逻辑回归是将线性回归值离散化。即一个二分类问题如下:(二值函数)
hθ(x(i))=g(θTx)={1,ifθTx≥t0,ifθTx<th_{\theta}(x^{(i)})=g(\theta^{T}x)=\left\{\begin{matrix} 1 , if \theta^{T}x \geq t\\ 0, if \theta^{T}x < t \end{matrix}\right. hθ(x(i))=g(θTx)={1,ifθTx≥t0,ifθTx<t
1.1 sigmoid函数
g(z)=11+e−z,g‘(z)=g(z)(1−g(z))g(z)=\frac{1}{1+e^{-z}},g^{‘}(z)=g(z)(1-g(z)) g(z)=1+e−z1,g‘(z)=g(z)(1−g(z))
0−10-10−1损失的二分类问题属于一种硬划分,即是与否的划分,而sigmoid函数则将这种硬划分软化,以一定的概率属于某一类(且属于两类的加和为1)。Sigmoid函数将线性回归值映射到 [0,1][0,1][0,1]的概率区间,从函数图像我们能看出,该函数有很好的特性,适合二分类问题。 因此逻辑回归模型如下:
hθ(x(i))=g(θTx)=11+e−θTxh_{\theta}(x^{(i)})=g(\theta^{T}x)=\frac{1}{1+e^{-\theta^{T}x}} hθ(x(i))=g(θTx)=1+e−θTx1
这里对于目标函数的构建不再是最小化函数值与真实值的平方误差了,按分类原则来讲最直接的损失因该是0-1损失,即分类正确没有损失,分类错误损失计数加1。但是0-1损失难以优化,存在弊端。结合sigmoid函数将硬划分转化为概率划分的特点,采用概率hθ(x(i))h_{\theta}(x^{(i)})hθ(x(i))的对数损失(概率解释-N次伯努利分布加最大似然估计),其目标函数如下:
J(θ)=∑i=1m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))minJ(θ)J(\theta)=\sum_{i=1}^{m}-\left ( y^{(i)}log(h_{\theta}(x^{(i)}))+(1-y^{(i)})log(1-h_{\theta}(x^{(i)}))\right) \\ \min J(\theta) J(θ)=i=1∑m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))minJ(θ)
同样采用梯度下降的方法有:
θj:=θj−α∂J(θ)∂θj=θj−α∂∑i=1m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))∂θj=θj−α(−y(i)hθ(x(i))+(1−y(i))(1−hθ(x(i))))∂hθ(x(i))∂θj=θj−α(y(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i))))∂hθ(x(i))∂θj\theta _{j}:=\theta_{j} -\alpha \frac{\partial J(\theta )}{\partial \theta _{j}}\\ =\theta_{j} -\alpha \frac{\partial \sum_{i=1}^{m}-\left ( y^{(i)}log(h_{\theta}(x^{(i)}))+(1-y^{(i)})log(1-h_{\theta}(x^{(i)}))\right) }{\partial \theta _{j}} \\ =\theta_{j}-\alpha \left (-\frac{y^{(i)}}{h_{\theta}(x^{(i)})}+ \frac{(1-y^{(i)})}{(1-h_{\theta}(x^{(i)}))} \right )\frac{\partial h_{\theta}(x^{(i)})}{\partial \theta _{j}}\\ =\theta_{j}-\alpha \left( \frac{y^{(i)}-h_{\theta}(x^{(i)})}{h_{\theta}(x^{(i)}) (1-h_{\theta}(x^{(i)}))} \right)\frac{\partial h_{\theta}(x^{(i)})}{\partial \theta _{j}} θj:=θj−α∂θj∂J(θ)=θj−α∂θj∂∑i=1m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))=θj−α(−hθ(x(i))y(i)+(1−hθ(x(i)))(1−y(i)))∂θj∂hθ(x(i))=θj−α(hθ(x(i))(1−hθ(x(i)))y(i)−hθ(x(i)))∂θj∂hθ(x(i))
又:
∂hθ(x)∂θ=(11+e−θTx)′=(e−θTx)(11+e−θTx)2x=(11+e−θTx)(1−11+e−θTx)x=hθ(x)(1−hθ(x))x\frac{\partial h_{\theta}(x)}{\partial \theta}={\left ( \frac{1}{1+e^{-\theta^{T}x}} \right )}'\\ =\frac{\left ( e^{-\theta^{T}x} \right )}{{\left ( \frac{1}{1+e^{-\theta^{T}x}} \right )}^{2}}x\\ =\left ( \frac{1}{1+e^{-\theta^{T}x}}\right )\left (1- \frac{1}{1+e^{-\theta^{T}x}}\right )x\\ =h_{\theta}(x)\left ( 1-h_{\theta}(x) \right )x ∂θ∂hθ(x)=(1+e−θTx1)′=(1+e−θTx1)2(e−θTx)x=(1+e−θTx1)(1−1+e−θTx1)x=hθ(x)(1−hθ(x))x
所以有:
θj=θj−α(y(i)−hθ(x(i)))x\theta_{j}=\theta_{j}-\alpha \left(y^{(i)}-h_{\theta}(x^{(i)})\right)x θj=θj−α(y(i)−hθ(x(i)))x
1.2 概率解释
逻辑回归的概率解释同线性回归模型一致,只是假设不再是服从高斯分布,而是p(y∣x;θ)p\left ( y|x;\theta \right )p(y∣x;θ)服从0-1分布,由于 ,假设随机变量y服从伯努利分布是合理的 。即:
p(y=1∣x;θ)=hθ(x)p(y=0∣x;θ)=1−hθ(x)p(y∣x;θ)=(hθ(x))y.(1−hθ(x))(1−y)p\left ( y=1|x;\theta \right )=h_{\theta}(x)\\ p\left ( y=0|x;\theta \right )=1-h_{\theta}(x)\\ p\left ( y|x;\theta \right )=\left (h_{\theta}(x) \right )^{y}.\left (1-h_{\theta}(x) \right )^{\left (1-y \right )} p(y=1∣x;θ)=hθ(x)p(y=0∣x;θ)=1−hθ(x)p(y∣x;θ)=(hθ(x))y.(1−hθ(x))(1−y)
所以最大化似然估计有:
maxL(θ)=p(y∣x;θ)=∏i=1mp(y(i)∣x(i);θ)=∏i=1m(hθ(x(i)))y(i).(1−hθ(x(i)))(1−y(i))⇔maxlogL(θ)⇔min−logL(θ)=∑i=1m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))\max L(\theta)=p\left ( y|x; \theta \right )\\ =\prod_{i=1}^{m}p\left ( y^{(i)}|x^{(i)}; \theta \right )\\ =\prod_{i=1}^{m}\left (h_{\theta}(x^{(i)}) \right )^{y^{(i)}}.\left (1-h_{\theta}(x^{(i)}) \right)^{\left (1-y^{(i)} \right )}\\ \Leftrightarrow \max logL(\theta)\\ \Leftrightarrow \min -logL(\theta)=\sum_{i=1}^{m}-\left ( y^{(i)}log(h_{\theta}(x^{(i)}))+(1-y^{(i)})log(1-h_{\theta}(x^{(i)}))\right) maxL(θ)=p(y∣x;θ)=i=1∏mp(y(i)∣x(i);θ)=i=1∏m(hθ(x(i)))y(i).(1−hθ(x(i)))(1−y(i))⇔maxlogL(θ)⇔min−logL(θ)=i=1∑m−(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))
1.3 logistic采用对数损失原因
采用对数损失的原因有二:
1) 从概率解释来看,多次伯努利分布是指数的形式。由于最大似然估计导出的结果是概率连乘,而概率(sigmoid函数)恒小于1,为了防止计算下溢,取对数将连乘转换成连加的形式,而且目标函数和对数函数具备单调性,取对数不会影响目标函数的优化值。
2)从对数损失目标函数来看,取对数之后在求导过程会大大简化计算量。
2. SoftMax回归
2.1 SoftMax回归
Softmax回归可以看作是Logistic回归在多分类上的一个推广。考虑二分类的另一种表示形式:
[k1,1−k1]→[k1k2]\left [ k_{1},1-k_{1} \right ]\rightarrow \begin{bmatrix} k_{1}\\ k_{2} \end{bmatrix} [k1,1−k1]→[k1k2]
当logistic回归采用二维表示的话,那么其损失函数如下:
J(θ)=−∑i=1m∑k=12(y(ik)log(hθk(x(i))∑k=1Khθk(x(i))))minJ(θ)J\left ( \theta \right )=-\sum _{i=1}^{m}\sum _{k=1}^{2}\left ( y^{(ik)} log\left ( \frac{ h_{\theta k}(x^{(i)})}{\sum _{k=1}^{K}h_{\theta k}(x^{(i)})} \right )\right )\\ \min J\left ( \theta \right ) J(θ)=−i=1∑mk=1∑2(y(ik)log(∑k=1Khθk(x(i))hθk(x(i))))minJ(θ)
其中,在逻辑回归中两类分别为k1k_{1}k1,1−k11-k_{1}1−k1二在softmax中采用k1,k_{1},k1,k2k_{2}k2两个随机变量组成二维向量表示,当然隐含约束k1+k2=1k_{1}+k_{2}=1k1+k2=1.为了更好的表示多分类问题,将y∈{1,2,..K}y\in \left \{ 1,2,..K \right \}y∈{1,2,..K}(不一定理解为yyy的取值为kkk,更应该理解为yyy可以取kkk类)多分类问题进行如下表示:
T(k)=[00.1.0]T(k)=\begin{bmatrix} 0\\ 0\\ .\\ 1\\ .\\ 0 \end{bmatrix} T(k)=⎣⎢⎢⎢⎢⎢⎢⎡00.1.0⎦⎥⎥⎥⎥⎥⎥⎤
其中向量的第kkk位为1,其他位为000,也就是当y=ky=ky=k 时将其映射成向量时对应第kkk位为111。采用多维向量表示之后,那么对于每一维就变成了一个单独的二分类问题了,所以softmax函数形式如下:
hθ(x(i))=1∑k=1Kexp(θkTx(i))[exp(θkTx(i))exp(θkTx(i)).exp(θkTx(i))]h_{\theta}(x^{(i)})=\frac{1}{\sum_{ k=1}^{K}exp\left ( \theta _{k}^{T}x^{(i)} \right )}\begin{bmatrix} exp\left ( \theta _{k}^{T}x^{(i)} \right )\\ exp\left ( \theta _{k}^{T}x^{(i)} \right )\\ .\\ exp\left ( \theta _{k}^{T}x^{(i)} \right ) \end{bmatrix} hθ(x(i))=∑k=1Kexp(θkTx(i))1⎣⎢⎢⎡exp(θkTx(i))exp(θkTx(i)).exp(θkTx(i))⎦⎥⎥⎤
其中函数值是一个KKK维的向量,同样采用对数损失(N元伯努利分布和最大似然估计),目标函数形式是logistic回归的多维形式。
J(θ)=−∑i=1m∑k=1K(y(ik)log(hθk(x(i))∑k=1Khθk(x(i))))minJ(θ)J\left ( \theta \right )=-\sum _{i=1}^{m}\sum _{k=1}^{K}\left ( y^{(ik)} log\left ( \frac{ h_{\theta k}(x^{(i)})}{\sum _{k=1}^{K}h_{\theta k}(x^{(i)})} \right )\right )\\ \min J\left ( \theta \right ) J(θ)=−i=1∑mk=1∑K(y(ik)log(∑k=1Khθk(x(i))hθk(x(i))))minJ(θ)
其中yiky^{ik}yik表示第iii个样本的标签向量化后第kkk维的取值000或者111.可以看出Softmax的损失是对每一类计算其概率的对数损失,而logistic回归是计算两类的回归,其本质是一样。Logistic回归和Softmax回归都是基于线性回归的分类模型,两者无本质区别,都是从伯努利分结合最大对数似然估计。只是Logistic回归常用于二分类,而Softmax回归常用于多分类。而且Logistic回归在考虑多分类时只考虑n−1n-1n−1类。
2.2 二分类转多分类思想
对于多分类问题,同样可以借鉴二分类学习方法,在二分类学习基础上采用一些策略以实现多分类,基本思路是“拆解法”,假设N个类别C1,C2,.Ci.,CnC_{1},C_{2},.C_{i}.,C_{n}C1,C2,.Ci.,Cn,经典的拆分算法有“一对一”,“一对多”,“多对多”,
一对一的基本思想是从所有类别中选出两类来实现一个两分类学习器,即学习出CN2=N(N−1)/2C_{N}^{2}=N(N-1)/2CN2=N(N−1)/2个二分类器,然后对新样本进行预测时,对这 CN2C_{N}^{2}CN2个分类器进行投票最终决定属于那一类。
一对多的基本思想是把所有类别进行二分类,即属于CiC_{i}Ci类和非CiC_{i}Ci两类,这样我们就需要N个分类器,然后对新样本进行预测时,与每一个分类器比较,最终决定属于哪一类。这其实就是Softmax的思想,也是SVM多分类的思想。
3. 最大熵模型
之所以把最大熵模型放到这讲,是因为它和Logistic回归和SoftMax回归实在是惊人的相似,同属于对数线性模型。
3.1熵的概念
信息熵:熵是一种对随机变量不确定性的度量,不确定性越大,熵越大。若随机变量退化成定值,熵为0。均匀分布是“最不确定”的分布 。
假设离散随机变量X的概率分布为P(X)P(X)P(X),则其熵为:
H(X)=−∑xP(x)logP(x)H(X)=-\sum_{x}P(x)logP(x) H(X)=−x∑P(x)logP(x)
其中熵满足不等式0≤H(P)≤log∣X∣0\leq H(P) \leq log|X|0≤H(P)≤log∣X∣,∣X∣|X|∣X∣为XXX取值数。
联合熵:对于多个随机变量的不确定性可以用联合熵度量
假设离散随机变量X,YX,YX,Y的联合概率分布为P(X,Y)P(X,Y)P(X,Y),则其熵为:
H(X,Y)=−∑x∑yP(x,y)logP(x,y)H(X,Y)=-\sum_{x}\sum_{y}P(x,y)logP(x,y) H(X,Y)=−x∑y∑P(x,y)logP(x,y)
条件熵:在给定条件下描述随机变量的不确定性
假设离散随机变量X,YX,YX,Y,在给定YYY的条件下XXX的不确定性为条件熵H(X|Y),也就等于H(X,Y)−H(Y)H(X,Y)-H(Y)H(X,Y)−H(Y)
H(X∣Y)=−∑x,yP(x,y)log(P(x∣y))H(X|Y)=-\sum_{x,y}P(x,y)log(P(x|y)) H(X∣Y)=−x,y∑P(x,y)log(P(x∣y))
互信息:衡量两个随机变量相关性的大小I(X,Y)=H(X)+H(Y)−H(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)I(X,Y)=H(X)+H(Y)−H(X,Y)
I(X,Y)=−∑x,yP(x,y)logP(x,y)P(x)P(y)I(X,Y)=-\sum_{x,y}P(x,y)log\frac{P(x,y)}{P(x)P(y)} I(X,Y)=−x,y∑P(x,y)logP(x)P(y)P(x,y)
相对熵(KL散度):衡量对于同一个随机变量两个概率分布p(x),q(x)p(x),q(x)p(x),q(x)的差异性
D(p∣∣q)=∑xp(x)logp(x)q(x)=Ep(x)logp(x)q(x)D(p||q)=\sum_{x}p(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)} D(p∣∣q)=x∑p(x)logq(x)p(x)=Ep(x)logq(x)p(x)
有互信息和相对熵的定义有下式:
I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))I(X,Y)=D(P(X,Y)||P(X)P(Y)) I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))
关于熵的介绍就到此,不细究,虽然上面的这些定义在机器学习中都会遇到,不过后面涉及到的主要还是熵和条件熵,互信息。
3.2最大熵模型
最大熵原理是概率模型学习中的一个准则。最大熵原理认为,学习概率模型时,在所有可能的概率模型分布中(满足所有条件下),熵最大的模型是最好的模型。熵最大即为最均匀的分布,从某种角度讲均匀分布总是符合我们理解的损失风险最小,也就是“不要不所有的鸡蛋放到一个篮子里,均匀的放置”。
给定训练集T={(x1,y1),(x2,y2)..(xm,ym)}T=\{ (x_{1},y_{1}),(x_{2},y_{2})..(x_{m},y_{m})\}T={(x1,y1),(x2,y2)..(xm,ym)},假设X∈χ⊆RnX \in \chi \subseteq R^{n}X∈χ⊆Rn表示输入,y∈ϕy\in \phiy∈ϕ表示输出,分类模型是一个以条件概率分布P(Y∣X)P(Y|X)P(Y∣X)输出YYY,也就是说在满足条件的所有可能集中,条件熵P(Y∣X)P(Y|X)P(Y∣X)最大的模型即为最好的模型。其中条件为隐藏在数据的期望。
一般来讲,最大熵模型常用于处理离散化数据集,定义随机变量X,YX,YX,Y的特征模板,从数据中统计他们的期望作为最大熵模型的条件
特征函数:
f(x,y)={1,x,y满足某一事实0,否则f(x,y)=\left\{\begin{matrix} 1,x,y满足某一事实\\ 0,否则 \end{matrix}\right. f(x,y)={1,x,y满足某一事实0,否则
约束条件:对于任意的特征函数fff,我们可以统计其在数据中的经验分布P~(x,y)\widetilde{P}(x,y)P(x,y)的期望:
Ep~(f)=∑x,yP~(x,y)f(x,y)E_{\widetilde{p}}(f)=\sum_{x,y}\widetilde{P}(x,y)f(x,y) Ep(f)=x,y∑P(x,y)f(x,y)
特征函数fff关于模型P(Y∣X)P(Y|X)P(Y∣X)和先验P~(X)\widetilde{P}(X)P(X)的条件期望:
Ep(f)=∑x,yP~(x)P(y∣x)f(x,y)E_{p}(f)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y) Ep(f)=x,y∑P(x)P(y∣x)f(x,y)
所以,满足约束条件的模型集合为:
Ω≡{P∈P∣Ep(fi)=Ep~(fi),i=1..n}\Omega \equiv \{ P\in \boldsymbol{P}| E_{p}(f_{i})=E_{\widetilde{p}}(f_{i}),i=1..n\} Ω≡{P∈P∣Ep(fi)=Ep(fi),i=1..n}
因此最大熵模型的形式化表示如下:
maxP∈CH(P)=−∑x,yP~(x)P(y∣x)logp(y∣x)⇔minP∈C−H(P)=∑x,yP~(x)P(y∣x)logp(y∣x)s.t.Ep(fi)=Ep~(fi),i=1..n∑yP(y∣x)=1\max_{P\in C} H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)logp(y|x)\\ \Leftrightarrow \min_{P\in C} -H(P)=\sum_{x,y}\widetilde{P}(x)P(y|x)logp(y|x)\\ s.t. E_{p}(f_{i})=E_{\widetilde{p}}(f_{i}) ,i=1..n\\ \sum_{y}P(y|x)=1 P∈CmaxH(P)=−x,y∑P(x)P(y∣x)logp(y∣x)⇔P∈Cmin−H(P)=x,y∑P(x)P(y∣x)logp(y∣x)s.t.Ep(fi)=Ep(fi),i=1..ny∑P(y∣x)=1
由拉格让日乘子法,引入拉格让日乘子,定义拉格让日函数:
L(P,w)=−H(P)+w0(1−∑yP(y∣x))+∑iwi(Ep(fi)−Ep~(fi))=∑x,yP~(x)P(y∣x)logp(y∣x)+w0(1−∑yP(y∣x))+∑iwi(∑x,y(P~(x)P(y∣x)fi(x,y)−∑x,yP~(x,y)fi(x,y))s.t.▽L(P,w)=0(1−∑yP(y∣x))=0∑x,y(P~(x)P(y∣x)fi(x,y)−∑x,yP~(x,y)fi(x,y)=0,i=1..nwi≥0,i=1..nL(P,w)=-H(P)+w_{0}(1-\sum_{y}P(y|x))+\sum_{i}w_{i}(E_{p}(f_{i})-E_{\widetilde{p}}(f_{i}))\\ =\sum_{x,y}\widetilde{P}(x)P(y|x)logp(y|x)\!+\!w_{0}(1\!-\!\sum_{y}P(y|x))\!+\!\sum_{i}w_{i}(\sum_{x,y}(\widetilde{P}(x)P(y|x)f_{i}(x,y)\!-\!\sum_{x,y}\widetilde{P}(x,y)f_{i}(x,y))\\ s.t. \bigtriangledown L(P,w)=0\\ (1-\sum_{y}P(y|x))=0\\ \sum_{x,y}(\widetilde{P}(x)P(y|x)f_{i}(x,y)-\sum_{x,y}\widetilde{P}(x,y)f_{i}(x,y)=0 ,i=1..n\\ w_{i}\geq0 ,i=1..n L(P,w)=−H(P)+w0(1−y∑P(y∣x))+i∑wi(Ep(fi)−Ep(fi))=x,y∑P(x)P(y∣x)logp(y∣x)+w0(1−y∑P(y∣x))+i∑wi(x,y∑(P(x)P(y∣x)fi(x,y)−x,y∑P(x,y)fi(x,y))s.t.▽L(P,w)=0(1−y∑P(y∣x))=0x,y∑(P(x)P(y∣x)fi(x,y)−x,y∑P(x,y)fi(x,y)=0,i=1..nwi≥0,i=1..n
根据拉格朗日乘子法,L(P)≥L(P,w)L(P) \geq L(P,w)L(P)≥L(P,w),当且仅当满足拉格朗日乘子法的所有必要条件等式成立,原问题也就是一个最小化最大问题
minP∈CmaxwL(P,w)\min_{P \in C}\max_{w}L(P,w) P∈CminwmaxL(P,w)
里层是max\maxmax最大化L(P,w)L(P,w)L(P,w),外层的min\minmin最小化L(P)L(P)L(P)。
对偶问题是:
maxwminP∈CL(P,w)\max_{w} \min_{P \in C}L(P,w) wmaxP∈CminL(P,w)
求解对偶问题,第一步最小化内部minP∈CL(P,w)\min_{P \in C}L(P,w)minP∈CL(P,w),minP∈CL(P,w)\min_{P \in C}L(P,w)minP∈CL(P,w)是关于www的函数,最优解记为PwP_{w}Pw:
Pw=argminP∈CL(P,w)=Pw(y∣x)P_{w}=arg\min_{P \in C}L(P,w)=P_{w}(y|x) Pw=argP∈CminL(P,w)=Pw(y∣x)
那么外层最大化目标函数为:
maxwΦ(w)Φ(w)=minp∈CL(P,w)=L(Pw,w)\max_{w}\Phi(w)\\ \Phi(w)=\min_{p \in C}L(P,w)=L(P_{w},w) wmaxΦ(w)Φ(w)=p∈CminL(P,w)=L(Pw,w)
为了求解Pw(y∣x)P_{w}(y|x)Pw(y∣x),根据KKT条件对P(y∣x)P(y|x)P(y∣x)求偏导:
∂L(P,w)∂P(y∣x)=∑x,yP~(x)(logP(y∣x)+1)−∑yw0−∑x,y(P~(x)∑iwifi(x,y))=∑x,yP~(x)(logP(y∣x)+1−w0−∑iwifi(x,y))=0\frac{\partial L(P,w)}{\partial P(y|x)}=\sum_{x,y}\widetilde{P}(x)(logP(y|x)+1)-\sum_{y}w_{0}-\sum_{x,y}\left (\widetilde{P}(x)\sum_{i}w_{i}f_{i}(x,y) \right )\\ =\sum_{x,y}\widetilde{P}(x)\left (logP(y|x)+1-w_{0}-\sum_{i}w_{i}f_{i}(x,y) \right )\\ =0 ∂P(y∣x)∂L(P,w)=x,y∑P(x)(logP(y∣x)+1)−y∑w0−x,y∑(P(x)i∑wifi(x,y))=x,y∑P(x)(logP(y∣x)+1−w0−i∑wifi(x,y))=0
求解得:
P(y∣x)=exp(∑iwifi(x,y)+w0−1)=(exp∑iwifi(x,y))exp(1−w0)P(y|x)=exp\left( \sum_{i} w_{i}f_{i}(x,y) +w_{0}-1 \right)=\frac{ \left(exp \sum_{i} w_{i}f_{i}(x,y)\right)}{exp(1-w_{0})} P(y∣x)=exp(i∑wifi(x,y)+w0−1)=exp(1−w0)(exp∑iwifi(x,y))
这里,虽然我们不知道w0w_{0}w0,但是由于∑yP(y∣x)=1\sum_{y}P(y|x)=1∑yP(y∣x)=1,所以分母一定是对yyy的所有可能的归一化因子
Pw(y∣x)=1zw(x)(exp∑iwifi(x,y))zw(x)=∑yexp(∑iwifi(x,y))P_{w}(y|x)=\frac{1}{z_{w}(x)} \left(exp \sum_{i} w_{i}f_{i}(x,y)\right)\\ z_{w}(x)=\sum_{y}exp(\sum_{i}w_{i}f_{i}(x,y)) Pw(y∣x)=zw(x)1(expi∑wifi(x,y))zw(x)=y∑exp(i∑wifi(x,y))
因此,maxwΦ(w)\max_{w} \Phi(w)maxwΦ(w)的最优解为:
w∗=argmaxwΦ(w)w^* = arg \max_w \Phi(w) w∗=argwmaxΦ(w)
代回Pw(y∣x)P_{w}(y|x)Pw(y∣x),我们可以得到最终的分类模型,同样我们发现最大熵模型也是一个对数线性模型。
回顾对偶函数,内部最小化求解得到了Pw(y∣x)P_{w}(y|x)Pw(y∣x),回到外部目标maxwΦ(w)\max_{w}\Phi(w)maxwΦ(w),将Pw(y∣x)P_{w}(y|x)Pw(y∣x)代回拉格朗日函数有:
Φ(w)=∑x,yP~(x)Pw(y∣x)logPw(y∣x)+∑i=1nwi(∑x,yP~(x,y)fi(x,y)−∑x,yP~(x)Pw(y∣x)fi(x,y))=∑x,yP~(x,y)∑i=1nwifi(x,y)+∑x,yP~(x)Pw(y∣x)(logPw(y∣x)−∑i=1nwifi(x,y))=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑x,yP~(x)Pw(y∣x)logzw(x)=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑xP~(x)logzw(x)∑yPw(y∣x)=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑xP~(x)logzw(x)\begin{aligned} \Phi(w) &=\sum_{x,y}\widetilde{P}(x)P_w(y|x)logP_w(y|x) + \sum^n_{i=1}w_i\left (\sum_{x,y}\widetilde{P}(x ,y)f_{i}(x,y) -\sum_{x,y}\widetilde{P}(x)P_w(y|x)f_{i}(x,y) \right )\\ &= \sum_{x,y} \widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) +\sum_{x,y}\widetilde{P}(x)P_w(y|x)\left (logP_w(y|x) - \sum_{i=1}^nw_if_i(x,y) \right) \\ &=\sum_{x,y} \widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) -\sum_{x,y}\widetilde{P}(x)P_w(y|x)logz_w(x)\\ &=\sum_{x,y} \widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) -\sum_x\widetilde{P}(x)logz_w(x)\sum_yP_w(y|x)\\ &=\sum_{x,y} \widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y) -\sum_x\widetilde{P}(x)logz_w(x)\\ \end{aligned} Φ(w)=x,y∑P(x)Pw(y∣x)logPw(y∣x)+i=1∑nwi(x,y∑P(x,y)fi(x,y)−x,y∑P(x)Pw(y∣x)fi(x,y))=x,y∑P(x,y)i=1∑nwifi(x,y)+x,y∑P(x)Pw(y∣x)(logPw(y∣x)−i=1∑nwifi(x,y))=x,y∑P(x,y)i=1∑nwifi(x,y)−x,y∑P(x)Pw(y∣x)logzw(x)=x,y∑P(x,y)i=1∑nwifi(x,y)−x∑P(x)logzw(x)y∑Pw(y∣x)=x,y∑P(x,y)i=1∑nwifi(x,y)−x∑P(x)logzw(x)
3.3概率解释
已知训练集的经验概率分布P~(x,y)\widetilde{P}(x,y)P(x,y),条件概率分布P(y∣x)P(y|x)P(y∣x)的对数似然函数为:
LP~(Pw)=log∏x,yP(y∣x)P~(x,y)=∑x,yP~(x,y)logP(y∣x),特征统计Logistic:maxlogL(θ)=p(y∣x;θ)=log∏i=1m∏k=1K(hθ(x(i)))y(i),样本统计L_{\widetilde{P}}(P_w) = log\prod_{x,y}P(y|x)^{\widetilde{P}(x,y)} = \sum_{x,y}\widetilde{P}(x,y)logP(y|x) ,特征统计\\ Logistic:\max logL(\theta)=p\left ( y|x; \theta \right )=log\prod_{i=1}^{m}\prod_{k=1}^{K}\left (h_{\theta}(x^{(i)}) \right )^{y^{(i)}},样本统计\\ LP(Pw)=logx,y∏P(y∣x)P(x,y)=x,y∑P(x,y)logP(y∣x),特征统计Logistic:maxlogL(θ)=p(y∣x;θ)=logi=1∏mk=1∏K(hθ(x(i)))y(i),样本统计
其中,我们发现对数似然函数与条件熵的形式一致,最大熵模型目标函数前面有负号(这与最大化对数似然函数完全相反),同时最大熵模型中有约束条件。也正是因为约束条件,我们将原问题转化为对偶问题后发现,在满足约束条件的对偶函数的极大化等价于最大化对数似然函数。
当条件概率P(y∣x)P(y|x)P(y∣x)满足约束条件,在对偶问题求解过程中我们有:
Pw(y∣x)=1zw(x)(exp∑iwifi(x,y))zw(x)=∑yexp(∑iwifi(x,y))P_{w}(y|x)=\frac{1}{z_{w}(x)} \left(exp \sum_{i} w_{i}f_{i}(x,y)\right)\\ z_{w}(x)=\sum_{y}exp(\sum_{i}w_{i}f_{i}(x,y)) Pw(y∣x)=zw(x)1(expi∑wifi(x,y))zw(x)=y∑exp(i∑wifi(x,y))
代入到对数似然函数,同样有:
LP~(Pw)=∑x,yP~(x,y)logP(y∣x)=∑x,yP~(x,y)(∑i=1nwifi(x,y)−logzw(x))=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑x,yP~(x,y)logzw(x)=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑xP~(x)logzw(x)=Φ(w)\begin{aligned} L_{\widetilde{P}}(P_w) &= \sum_{x,y}\widetilde{P}(x,y)logP(y|x)\\ &= \sum_{x,y}\widetilde{P}(x,y)\left ( \sum_{i=1}^n w_if_i(x,y) -logz_w(x)\right )\\ &= \sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n w_if_i(x,y) - \sum_{x,y}\widetilde{P}(x,y)logz_w(x)\\ &= \sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n w_if_i(x,y) - \sum_{x}\widetilde{P}(x)logz_w(x) = \Phi(w) \\ \end{aligned} LP(Pw)=x,y∑P(x,y)logP(y∣x)=x,y∑P(x,y)(i=1∑nwifi(x,y)−logzw(x))=x,y∑P(x,y)i=1∑nwifi(x,y)−x,y∑P(x,y)logzw(x)=x,y∑P(x,y)i=1∑nwifi(x,y)−x∑P(x)logzw(x)=Φ(w)
最后,我们再来看对偶函数表达式,我们发现,第一项其实是X,YX,YX,Y的联合熵H(X,Y)H(X,Y)H(X,Y),第二项是XXX的信息熵H(X)H(X)H(X),回看熵的示意图,我们发现,我们的目标还是最大化条件熵H(Y∣X)H(Y|X)H(Y∣X)。
下面再来对比下Logistic回归,SoftMax回归,最大熵模型:
1)同属于对数线性模型;
2)Logistic回归和SoftMax回归都基于条件概率P(y∣x)P(y|x)P(y∣x),满足一个伯努利分布,N重伯努利分布;而最大熵模型以期望为准,没有该假设;
3)由于都采用线性模型,三者都假设特征之间是独立的。
3.4最大熵模型的优化问题
最大熵模型从拉格朗日乘子法最大化对偶函数,还是从最大化对数似然函数,其目标函数如下:
LP~(Pw)=∑x,yP~(x,y)∑i=1nwifi(x,y)−∑xP~(x)logZw(x)L_{\widetilde{P}}(P_w)= \sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n w_if_i(x,y) - \sum_{x}\widetilde{P}(x)logZ_w(x)\\ LP(Pw)=x,y∑P(x,y)i=1∑nwifi(x,y)−x∑P(x)logZw(x)
常用的梯度优化算法都可以,另外对于最大熵模型也有专门的算法有GIS IIS 算法 。
代码
Logistic回归
int LogReg(){const char *file="data\\LogReg.txt";const string model="gradAscent";const double alpha=0.01;Matrix x;cout<<"loadData"<<endl;cout<<"----------------------"<<endl;x.LoadData(file);Matrix y;y=x.getOneCol(x.col-1);x.deleteOneCol(x.col-1);if(model=="gradAscent")gradAscent_Log(x,y);if(model=="stoGradAscent")stoGradAscent_Log(x,y);return 0;}int gradAscent_Log(Matrix x,Matrix y) {if(y.col!=1){cout<<"logReg is two class"<<endl;return -1;}Matrix weights(x.col,y.col,0.1,"T");Matrix xT = x.transposeMatrix();float alpha=0.01;///迭代步长float error=0;///记录错误率int iter=0;int i,j;Matrix z(y.row,y.col,0,"T");//最好确定矩阵的大小Matrix grad(x.col,y.col,0,"T");for(iter=0; iter<5000; iter++){z = x * weights;for(i=0; i<z.row; i++){z.data[i][0]=sigmoid(z.data[i][0]);}z = y - z;error=0;for(i=0; i<x.row; i++)///统计错误率error+=z.data[i][0];grad = xT * z;///计算负梯度方向for(i=0; i<grad.row; i++)grad.data[i][0]*= alpha;///负梯度方向与步长的乘积确定迭代值weights = weights + grad;///往负梯度方向走一个步长}/**验证算法的正确性**/ int er1=0,er2=0;Matrix train=x * weights;cout<<"test"<<endl;for(i=0; i<y.row; i++){if(train.data[i][0]>0){cout<<1-y.data[i][0]<<endl;er1+=(1-y.data[i][0]);}else {cout<<0-y.data[i][0]<<endl;er2-=(0-y.data[i][0]);}}}
SoftMax回归
int SoftMaxReg(){const char *file="data\\LogReg.txt";const string model="gradAscent";const double alpha=0.01;Matrix x;cout<<"loadData"<<endl;cout<<"----------------------"<<endl;x.LoadData(file);Matrix y;y=x.getOneCol(x.col-1);y=one_hot(y,2);x.deleteOneCol(x.col-1);if(model=="gradAscent")gradAscent_SoftMax(x,y);if(model=="stoGradAscent")stoGradAscent_SoftMax(x,y);return 0;}/**随机梯度下降与梯度下降法不同的是在负梯度方向的确定,梯度下降是根据所有的样本来确定负梯度方向,而随机梯度下降每次只看一个样本点来确定负梯度方向,虽然不完全可信,但随着迭代次数增加,同样收敛**/ int stoGradAscent_SoftMax(Matrix x,Matrix y)//随机梯度下降每一次选择m个样本进行求梯度下降方向,该代码中只选择一个样本进行求解梯度下降方向与数值{Matrix xOneRow(1,x.col,0,"T");Matrix xOneRowT(x.col,1,0,"T");Matrix weights(x.col,y.col,0.1,"T");Matrix z(1,y.col,0,"T");//最好确定矩阵的大小Matrix grad(x.col,y.col,0,"T");double zRowSum=0;double alpha=0.001;///步长double error;int i,j,k,iter;for(iter=0; iter<5000; iter++){for(i=0; i<x.row; i++){xOneRow=x.getOneRow(i);///随机选择一个样本点,这里没有作随机选择,而是按序选择z = xOneRow * weights;zRowSum=0;for(j=0;j<z.col;j++){z.data[0][j]=sigmoid(z.data[0][j]);zRowSum+=z.data[0][j];//求和}for(j=0;j<z.col;j++){z.data[0][j]/=zRowSum;//归一化if(iter%1000==0)cout<<z.data[0][j] <<" s ";}if(iter%1000==0)cout<<endl;for(j=0;j<y.col;j++){z.data[0][j]=y.data[i][j]-z.data[0][j];}xOneRowT = xOneRow.transposeMatrix();grad = xOneRowT * z;///根据一样样本的预测误差来确定负梯度方向for(k=0; k<grad.row;k++){for(j=0;j<grad.col; j++){grad.data[k][j]*= alpha;///负梯度方向与步长的乘积确定迭代值}}weights = weights + grad; ///迭代}}//验证算法的正确性/**验证算法的正确性**/ Matrix test=x * weights;cout<<"test"<<endl;for(i=0; i<y.row; i++){if(test.data[i][0]>test.data[i][1])cout<<0-y.data[i][1]<<" ";else cout<<1-y.data[i][1]<<" ";cout<<endl;}}
欢迎关注【AI小白入门】,这里分享Python、机器学习、深度学习、自然语言处理、人工智能等技术,关注前沿技术,求职经验等,陪有梦想的你一起成长。