0 - 回顾
linear regression如果使用平方错误的话,我们可以很方便的解析出最好的w是什么。即wbest=X†y
1 - 逻辑斯蒂回归问题
1.1 - 问题的提出
从一个人的身体数据来判断这个人有没有心脏病,这是一个典型的二元分类问题。logistic regression关注的是根据一个人的身体状况来给出可能心脏病发的概率。也就是说我们想要知道的是P(+1|x)的值是大小。这样的问题可以称为soft binary classification,因为现在我们想要的结果不单是一个样本所属的类别是 × (是反例)或者是 ◯(是正例)?我们关心的是取值为正例◯的概率的大小:如果这个值接近于1,那么为◯的可能性就大;如果这个值接近于0,那么为◯的可能性就小。
所以logistic regression想做的是对给定特征x下y为正例的概率P(y=1|x)进行建模。或者说目标函数是f(x)=P(y=1|x),我们的任务是找一个最佳的模型(hyperthesis)进行拟合。
1.2 - Soft Binary Classification
我们想要得到的目标函数是f(x)=P(+1|x)⊆[0,1], 即针对一个输入x, 函数给出是正例的可能性,那么我们理想的希望拿到的数据应该是下面这样的:
(x1,y′1=0.9=P(+1|x1))
(x2,y′2=0.2=P(+1|x2))
⋯
(xN,y′N=0.6=P(+1|xN))
这样我们就可以找一个hypothesis g, 让g在data上的表现很好(误差很小),这样g可能就和我们想要的那个未知的target function f很相近。但是实际我们得到的数据和做bianry classification时是一样的。即是下面这样的:
(x1,y′1=1)
(x2,y′2=0)
⋯
(xN,y′N=0)
1.3 - Logistic回归的假设函数
同样的,对每一个样本x=(x0,x1,x2,⋯,xd)的所有的特征加权求和(每一个样本有d个维度的特征,x0表示的bias或者是threshold, 相应的w0=1):
s=∑i=0dwixi
现在我们想要的并不是这个分数的大小(linear regression想要的是这个)。直观上我们想要分数s越高,对应患病风险越高;分数s越低,对应患病的风险越小。并且我们想要的输出是一个介于[0,1]之间的数(拥有概率的意义),所以我们使用logistic函数(或者称为θ函数)来将上述的特征加权和的(−∞,+∞)的输出转为[0,1]。
所以我们要做的就是找到一个logistic hyperthesis来拟合target function。
logistic函数 θ
1.4 - logistic函数:
logistic函数会把分数高的输出为1, 分数低的输出为0。
θ(s)=es1+es=11+e−s
逻辑斯蒂回归从表面上看就是加了一个logistic函数的线性回归。即将线性运算的结果wTx输入到θ函数中,使用h(x)=11+exp(−wTx)来计算在给定x情况下y为正例的概率。
2 - logistic回归的损失函数
2.1 - 三种线性的模型的对比
现在将logistic regression和我们之间接触过的linear regression和linear classification做一些对比。三种线性的模型共同点是都计算特征的加权和:s=wTx
在线性分类方法中,PLA通过关注划分错误的点也就是err0/1来进行分割线的调整;在线性回归中,我们使用平方误差square error来衡量真实值和预测值之间的差距,通过最小化平方误差可以很容易的得到线性回归的解析解;在逻辑斯蒂回归中如何去定义我们想要最小化的Ein(答案是利用似然函数)。
2.2 - 交叉熵损失/logistic损失
我们想要建模的函数表示的是样本为正例的可能性,即h(x)=P(y=1|x)
根据上面给出的等式可以定义:
P(+1|x)=h(x),P(−1|x)=1−h(x)
这样,h(x)描述了在给定的特征x下该样本属于正例(y=1)的概率;1−h(x)则描述了在给定的特征x下该样本属于负例的概率。假设某一个数据集D=(x1,◯),(x2,×),⋯,(xN,×)。那么这个数据集上的似然函数为:
P(◯|x1)×P(×|x2)⋯P(×|xN)
根据上面的定义可以变为:
h(x1)×(1−h(x2))⋯(1−h(xN))
而
=====1−h(x)1−11+e−wTx1+e−wTx−11+e−wTxe−wTx1+e−wTx11+ewTxh(−x)(12)(13)(14)(15)(16)(17)
根据以上的性质似然函数的表达式变为:
likelihood(h)=h(x1)×(1−h(x2))×⋯×(1−h(xN))=h(x1)×h(−x2)×⋯×h(−xN)
那么接下来就可以利用极大似然估计法来估计模型参数。所以我们现在的目标是最大化似然函数h(x1)×h(−x2)×⋯×h(−xN), 极大化似然函数就是令每一个样本属于其真实标记的概率极大化:
极大化x1属于正例的概率h(x1) AND 极大化x2属于负例的概率h(−x2)(即极大化1−h(x2)⟶ 极小化h(x2)⟶极小化x2属于正例的概率) AND⋯ AND极小化xN属于负例的概率。
将每一个样本的y写入上式可以得到似然函数:
likelihood(h)=∏n=1Nh(ynxn)
我们现在的目的就是极大化似然函数:
maxh∏n=1Nh(ynxn)
重写一下逻辑斯蒂函数: θ(x)=11+exp(−x),
重写一下我们的逻辑斯蒂回归模型的假设函数:h(x)=11+exp(−wTx)
那么
∏n=1Nh(ynxn)=∏n=1N11+exp(−ynwTxn)=∏n=1Nθ(ynwTxn)(1)
我们的目标变为寻找参数w使得(1)最大
maxw∏n=1Nθ(ynwTxn)
在机器学习中通常定义损失函数,并最小化,所以取log,并且变为求最小值
maxw ln∏n=1Nθ(ynwTxn)=maxw∑n=1Nlnθ(ynwTxn)=minw∑n=1N−lnθ(ynwTxn)
其中
θ(s)=11+e−s
这样我们就得到了logistic regression的损失函数:
minw∑n=1N−lnθ(ynwTxn)=minw∑n=1N−ln(11+exp(−ynwTxn))=minw∑n=1Nln(1+exp(−ynwTxn))=minw∑n=1Nln(1+exp(−ynwTxn))=minw∑n=1Nerr(w,xn,yn)Ein(w)(18)(19)(20)(21)(22)
这里有一个概念err(w,x,y)=ln(1+exp(−ywx))被定义为cross entropy error。
到这里我们就把想要极大化似然函数的目的变为要极小化Ein。得到了如下的目标,下一小节讲解如何求解使得损失函数最小的w:
minw∑n=1Nln(1+exp(−ynwTxn))
3 - Gradient of Logistic Regression Error
3.1 - 求交叉熵损失的梯度
这里给出一个结果,逻辑斯蒂的损失函数Ein也是一个凸函数。所以当我们想要最小化Ein的时候, 就是要找到该函数的“谷底”,而在“谷底”的时候梯度为0。所以最佳的w就是使得梯度▽Ein(w)等于0的w, 此时Ein最小。
Ein(w)=1N∑n=1Nln(1+exp(−ynwTxn))
所以第一步就是求Ein(w)的梯度。
∂Ein(w)∂wi=1N∑n=1N(∂ln(□)∂□)(∂(1+exp(∘))∂∘)(∂(−ynwTxn)∂(wi))=1N∑n=1N(1□)(exp(∘))(−ynxn,i)=1N∑n=1N(exp(∘)1+exp(∘))(−ynxn,i)=1N∑n=1Nθ(∘)(−ynxn,i)
可以得到:
∂Ein(w)∂w=1N∑n=1Nθ(−ynwTxn)(−ynxn)
-
求解使得梯度为0的w
want ▽Ein(w)=1N∑n=1Nθ(−ynwTxn)(−ynxn)=0
这里可以看到梯度是一个加权和,其中的权值为θ(−ynwTxn)。一种情况是,该梯度要为0,那么所有的权值项都要为0。即θ(−ynwTxn)都要为0。那么此时就要求−ynwTxn非常小,即ynwTxn≫0。所有的ynwTxn都满足远远大于0(wTxn和yn同号),说明该数据必须是线性可分的。所以想要得到解析解是困难的。并且不同于linear regression,在linear regression中我们要求的是一个线性的方程式,但是这里是一个非线性的方程式,所以我们不可能可以得到类似与linear regression的analytic solution。
回顾下PLA算法在寻求最优的w时所使用的方法,不像linear regression可以直接得到analytic solution,PLA是一步一步的对参数w进行修正: 每一次看看w在哪个数据点犯了错, 当发现犯了错误之后就对w做修正,直到不再犯错。 我们可以把以上的这个过程简化的表示如下:
wt+1←wt+1η[[ sign(wTxn)≠yn ]]ynxnv
即如果样本(xn,yn)犯错,那么就根据该样本对方向进行更新;如果没有犯错,那么就不更新。
其中的η是步长,v是更新的方向。当对步长和方向做不同的规定的时候, 就可以得到不同的算法。我们把这样的算法: 一步一步的改进,每一次都决定方向,然后走一小步称为iterative optimization approach。
Quiz
在梯度中:▽Ein(w)=1N∑Nn=1θ(−ynwTxn)(−ynxn),哪一个样本点的权重值是最大的。
answer:
ynwTxn值最小的样本点。
why:
ynwTxn的值最小,有可能是负值,也就是说此时的w在这个样本点上是错的。即,犯错误的点会得到比较大的权重值。
4 - 梯度下降算法
4.1 - 为什么是负梯度方向
iterative optimization要做的事情就是找一个合适的方向v,然后决定一个步长η,通过这样的方式来不断的更新w。
for t=0,1,2,⋯
wt+1=wt+ηv
until stop,return w as g.
其中:
v是方向(为方便计算规范化为长度为1的向量),
η是步长。
logistics regression的损失函数Ein(w)是一个凸函数, 像如下的一个山谷的形状,想象当我们把一个球放在山坡的某一个地方,也就是对应于某一个w,这时更新的方法就是把球慢慢的滚下去(w向谷底的方向移动),当球滚到谷底的时候,我们就找到了梯度为0的点,也就是最佳的w所在的点。所以我们现在的目标就是要把球滚下去,v表示滚下去的方向(长度为1的向量),η表示每一步走多远。
想要最快的到达谷底(达到Ein的最小值),那么对于任意给定的一个步长η>0,一个比较贪心的想法是我们要选择一个“最陡”的下降方向v来做更新(选择一个最陡的方向滚下去)。因为每一步能走的距离是一定的(一步只可以走30公分),所以现在需要的是选择好的方向v:所谓好的方向就是使得沿着这个方向走了一步之后下降了最多:即使得Ein(ww+1)最小:
min||v||=1 Ein(wt+ηvwt+1)
这样的好的方向怎么决定呢?
利用泰勒(Taylor expansion:简单理解为一条曲线可以在很小的范围内被一条直线近似的替代)展开,如果η是足够小的。那么可以得到:
Ein(wt+ηv)≈Ein(wt)+ηvT▽Ein(wt)
这样的话,原来的问题:min||v||=1 Ein(wt+ηv)变为如下的线性问题:
min||v||=1 Ein(wt)known+ηgiven positivevTunknown▽Ein(wt)known
所以现在的情况是:Ein(wt), ▽Ein(wt), η都是已知的。想要知道的是什么样子的v可以使得该式子最小。
因为Ein(wt), η都是已知的, 所以我们的最小化目标可以变为下式:
min||v||=1 vT▽Ein(wt)
要使得该式子最小的最optimal的方向v就是和▽Ein(wt)的方向相反那个向量(两个向量正好方向相反的时候內积会最小),又我们要求v是单位向量, 所以可以得到最好的更新权重的方向是:
v=−▽Ein(wt)||▽Ein(wt)||
即,梯度的负方向!
4.2 - 梯度下降算法
得到了最好的方向, 我们就可以对w来进行更新(就知道了球应该会怎么滚), 对于一个小的η, 权重的更新规则如下:
wt+1=wt−η▽Ein(wt)||▽Ein(wt)||
即,往
梯度的反方向走一小步。这个方法就是gradient descent,只要能算出梯度,这个问题就可以解决。
4.3 - 如何选择步长
已经解决了更新的方向的问题, 现在我们考虑步长的问题。
对于η的设置,太小或者太大都不合适。一个不错的选择是步长最好是正比与梯度。梯度大的时候,步长大一点;梯度小的时候,步长小一点。也就是说比较好的步长应该是这样的η^=λ||▽Ein(wt)||.这样,原来的更新规则:
wt+1=wt−η▽Ein(wt)||▽Ein(wt)||
得到
gradient descent最终的更新规则:
wt+1=wt−η▽Ein(wt)
4.4 - 逻辑斯蒂回归算法
现在我们得到了完整的logistic regression算法的流程如下:
初始化w0
For t=0,1,⋯
- 计算梯度
▽Ein(w)=1N∑n=1Nθ(−ynwTxn)(−ynxn)
- 梯度下降更新权重
wt+1=wt−η▽Ein(wt)
⋯ 直到▽Ein(w)≈0 或者已经更新了足够多的步数
返回最新的wt+1作为g。
在每一个迭代步中,花费最大是计算梯度:所有的样本的θ函数值和样本值的乘积和。
5 - 总结
这篇介绍了logistic regression,从我们想要直接计算P(+1|x)的值这个问题出发,我们使用logistic function作为假设函数,并且定义了cross-entropy error。我们想要最小化这个error,那么就要计算这个error的梯度, 得到的梯度是θ函数和资料的乘积的一个求和平均。但是我们没有办法直接得到梯度为0时候w的解,所以就引出了gradient descent这样的iterative optimization approach可以帮助我们找到最佳的权重值w, 从而构造模型。