梯度下降法求解逻辑回归

梯度下降法(Gradient Descent)是优化问题中一种常用的手段,一般用于凸函数问题(或者可以转换为凸函数的问题)的求解,而逻辑回归问题就可以转换为一个凸函数问题,我们可以使用梯度下降来获得一个较优值(不保证全局最优)。

一、什么是逻辑回归

线性回归(参考 这篇文章 )的输入为单个数据 x_{i}

,返回的结果是 x_{i} 的具体分类 y_{j} ,比如预测男女,输入的是一个人的参数,输出是具体的男或者女。逻辑回归的输入与线性回归相同,但输出为该数据 x_{i} 属于某个分类 y_{j} 的概率,即: P(y_{j}|x_{i})

 

二、模型函数

和其他机器学习算法一样,我们首先要定义我们的模型,然后训练出其参数。

假设我们有数据 x_{i}

,则其属于分类 y_{j} 的概率为: P(y_{j}|x_{i}) = wx_{i} ,既然我们求的是概率,那么我们就要求其范围应该在0到1之间,所以我们需要对该概率公式做一些变换。

构造模型函数的方法有很多种,由于后面我们需要把损失函数确定为凸函数,所以我们使用概率为来构造(其他形式课参考李航老师的《统计学习方法》)。现在我们假设有一个参数 w

,可以满足以下公式:

\frac {p(y=1|x)}{1-p(y=1|x)} = exp^{wx}

对该式进一步变换,我们可以得到:

p(y=1|x) = \frac {exp^{wx}}{1+exp^{wx}}= \frac {1}{1+exp^{-wx}}

\eta (t) = \frac {1}{1+exp^{-t}}

,我们知道 \eta(t) 的图像如下图所示:

即满足了0到1的需求,那么我们的概率公式就可以写成:

P(y=1|x) = \eta (wx)

P(y=0|x) = 1 - \eta (wx)

我们要求解的目标就是 w

参数,那么如何求呢?

 

三、优化问题

我们现在有了概率模型,为了求得最优的 w

,我们需要把求解 w 的问题转换为最优化问题。

既然已经有了 P(y=1|x)

P(y=0|x) ,那么我们要做的就是让所有训练样本的概率最大化即可,即所有正样本的全概率加上所有负样本的全概率:

L(w) = \coprod_{i}^{n}P(y=1|x) + \coprod_{j}^{n}P(y=0|x)

其中 i

是证样本, j 是负样本。

由于所有概率连乘需要计算大量的浮点数,不便于使用,我们吧 L(w)

转换为等价的负对数似然公式,即使用对数的和替代连成,同时加上负号把最大化问题转换为最小化问题:

L(w) = -\sum_{i}^n [I(y_{i}=1)log(P(y=1|x) + I(y_{i}=0)log(P(y=0|x)))]\\=-\sum_{i}^n [I(y_{i}=1)log(\eta (wx_{i}) + I(y_{i}=0)log(1-\eta (wx_{i})))]

为了最小化 L(w)

,我们求出其参数 w 梯度(即对w求导):

\Delta L(w) = -\sum_{i}^n (y_{i}-\eta (wx_{i}))*x_{i}

如果 L(w)

的最优值存在,那么我们只需要另 \Delta L(w)=0 即可得到 w ,但是如大家所见,这个方程的求解函数与样本数相等,直接求解 w 非常困难。

我们观察一下 \Delta L(w)

发现, -\sum_{i}^n (y_{i}-\eta (wx_{i})) 一定是一个0到-1之间的负数,所以对于任意样本 x_{i} 来说,梯度的方向总是与其相反,在“原点”(我们想象的一个坐标系)梯度为0,所以该损失函数 L(w) 一定是一个凸函数,即存在最优解。

四、梯度下降法

现在,我们有了优化目标,即最小化负对数似然函数L(w)。从上一节我们知道不能直接使用其导数为0来求解最优值,我们现在来介绍一种非常常用的求近似最优解的方法:梯度下降法。

梯度下降法的思路其实很简单,假设我们有一个如下图所示的凸函数:

我们首先在函数上任选一点,计算其损失(即我们上面的 L(w)

) ,然后按照某一规则寻找更低的一点计算新的损失,只要新损失更小(最小化问题),我们就继续下降,直到达到一个可接受的优化目标。

我们的 L(w)

本质上与上图的求解方式类似,下降方向就是梯度方向 \Delta L(w) 的反方向,即当函数处在上升阶段时,我们往左边下降,函数下降阶段我们往右边下降(参看上图)。

梯度下降方法分为两个部分 ,第一部分是整体上,我们使用某步长不断下降求损失函数,第二部分是为了防止步长太长导致最后无法收敛,每次当损失上升的时候都调整步长。

以下是梯度下降求解 L(w)

最优值的过程:

1)首先建立坐标系,横轴是我们的目标参数w,纵轴是当前参数情况下的损失L(w):

建立坐标系后,首先随机取一个参数 W_{1}

,同时获得初始损失 L_{1}

2)根据梯度公式,获得初始的梯度 D_{1}

,同时根据梯度方向获得初始的下降方向 Direction_{1} (即往正方像下降):

3)现在,我们有了梯度下降的方向、有了初始损失,下一步只需要按照某步长 C

来往右边调整 W 即可,然后对比两个损失,当他们的差比较小的时候,说明趋于最优值了。

但是这里步长不好取,加入正好把 W

下降到对面,那损失的差虽然很小,显然没有趋于最优,再或者步长取的过长,损失反而上升了,也不行,所以我们第三步的主要目的是调整一个稳定的步长,根据该步长获得新的 W

所以 第三步作为单独的一个目的,要分四小步来做

3.1)设置一个初始的步长 C_{1}

,根据该步长按照梯度对参数 W_{1} 进行下降得到 W_{2} = W_{1} + D_{1}*Direction_{1}

图中 W_{2}

即为新的参数,根据这个新的参数可以获得新的损失 L_{2} ,我们可以看到损失下降的值为 b = L_{1} - L_{2}

为了保证每次下降的质量,我们需要对 b

进行一些限制。

3.2)假如我们按照当前梯度和步长完全下降,即不考虑约束条件,最大可能下降的值为 S = <D_{1},W_{2}-W_{1}> = <D_{1}, a>

,如下图中的S所示:

我们当然不可能要求损失下降的长度为S,这里只需要 L_{1} - L_{2}

大于某个指定的关于S的比例即可,我们这里设置该比例为“容忍度” B(B为0到1之间的值)。即要满足的条件是:

L_{2} - L_{1} >= B * |<D_{1}, W_{2}-W_{1}>|

3.3)如果不能满足 3.2 中的条件,说明我们的步长有问题,通常是步长太长了,我们需要调整该步长。我们设定一个“折半因子” A(A为0到1之间的值),把当前的步长 C_{1}

进行“折半”,即 C_{2} = A * C_{1} ,按照新的步长进行第 3.1 步。

3.4)如果满足 3.2 中的条件,我们直接返回新的 W_{2}

,即当前的下降成功,进入第 4步 。

4)从第 3 步我们得到了新的 W

之后,按照新的参数计算新的损失 L ,对比新的损失与旧损失之间的差值,如果差值较小达到某阈值,说明拟合成功,否则继续进行第 2 步。

以上内容就是基本的梯度下降法的使用了,对于基本梯度下降的改进有很多,其他的博主也不是很熟,就暂时不讨论了,我们通常实践中用的时候,都是用一些开源的大师写好的算法,一般很少需要深度改进,比如使用libsvm可以直接求解逻辑回归。

五、预测

从第上一节,我们通过梯度下降获得了参数 W

,剩下的事情就很简单了,就是根据我们的模型函数,预测某一个样本属于某分类的概率:

P(y=1|x) = \eta (wx)

逻辑回归得到的结果通常是某个样本属于各个分类的概率,这是其比线性回归更加好用的地方之一,更利于我们灵活控制。

六、后记

感觉还有很多内容不是很理解,比如libsvm或svmlight里面的逻辑回归是怎么实现的(没有找到计算参数W的选项,难道只能用默认的?)。

还有具体在CTR预估等地方怎么实践,还需要进一步的研究。

如果你感兴趣

分享该文章

我来评几句
登录后评论

已发表评论数()