梯度下降法求解逻辑回归

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

一、什么是逻辑回归

首先让我们了解一下线性回归（参考这篇文章）的输入为单个数据xi，返回的结果是xi的具体分类yj，比如预测男女，输入的是一个人的参数，输出是具体的男或者女。逻辑回归的输入与线性回归相同，但输出为该数据xi属于某个分类yj的概率，即：P(yj|xi)。

二、模型函数

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

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

p(y=1|x)1−p(y=1|x)=expwx

对于该式我们进行进一步的变换，可以得到：

p(y=1|x)=expwx1+expwx=11+exp−wx

设η(t)=11+exp−t，我们知道η(t)的图像如下图所示：

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

P(y=1|x)=η(wx)P(y=0|x)=1−η(wx)

我们要求解的目标就是w参数，那么如何求呢？

三、优化问题

我们现在有了概率模型，为了求得最优的w，我们需要把求解w的问题转换为最优化问题。

L(w)=n∐iP(y=1|x)\*n∐jP(y=0|x)

其中i是正样本，j是负样本。

由于所有概率连乘需要计算大量的浮点数，不便于使用，我们吧L(w)转换为等价的负对数似然公式，即使用对数的和替代连成，同时加上负号把最大化问题转换为最小化问题：

(w)=−n∑i\[I(yi=1)log(P(y=1|x)+I(yi=0)log(P(y=0|x)))\]=−n∑i\[I(yi=1)log(η(wxi)+I(yi=0)log(1−η(wxi)))\]

为了最小化L(w)，我们求出其参数w梯度(即对w求导)，这里需要注意的是，如果我们前面定义的负样本为η(wxi)，那么这里的梯度会有变化（根据w算出的最终结果就会变成负样本的概率）：

ΔL(w)=−n∑i(yi−η(wxi))\*xi

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

我们观察一下ΔL(w)发现，$-\sum{i}^n (y{i}-\eta (wx{i}))一定是一个0到−1之间的负数，所以对于任意样本x{i}来说，梯度的方向总是与其相反，在“原点”（我们想象的一个坐标系）梯度为0，所以该损失函数L(w)$一定是一个凸函数，即存在最优解。

四、梯度下降法

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

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

我们首先在函数上任选一点，计算其损失（即我们上面的L(w)） ，然后按照某一规则寻找更低的一点计算新的损失，只要新损失更小（最小化问题），我们就继续下降，直到达到一个可接受的优化目标。

我们的L(w)本质上与上图的求解方式类似，下降方向就是梯度方向Δ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之间的值）。即要满足的条件是：

% <![CDATA[ L_{2} - L_{1} >= B \* | &lt; D_{1}, W_{2}-W_{1} &gt; | %]]>

3-3）如果不能满足 3-2 中的条件，说明我们的步长有问题，通常是步长太长了，我们需要调整该步长。我们设定一个“折半因子” A（A为0到1之间的值），把当前的步长$C{1}进行“折半”，即C{2} = A * C_{1} $，按照新的步长进行第 3-1 步。

3-4）如果满足 3-2 中的条件，我们直接返回新的W2，即当前的下降成功，进入第 4步 。

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

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

五、预测

从第上一节，我们通过梯度下降获得了参数W，剩下的事情就很简单了，就是根据我们的模型函数，预测某一个样本属于某分类的概率：

P(y=1|x)=η(wx)

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