Logistic Regression(逻辑回归)

以前在学校学到Logistic Regression的时候，虽然最后会使用，但是对于许多地方有很多的疑惑，今天在这里详细梳理一下Logistic Regression的过程：

---

回归的思想

Logistic Regression和线性回归一样，是回归中常见的算法。很多人刚接触Logistic Regression，不知道回归的含义。其实在念中学的时候学到的用最小二乘法求解线性回归方程，就是我们最早接触到的回归。在二维平面上有很多的点 <x1,y1>,<x2,y2>...<xn,yn> <script type="math/tex" id="MathJax-Element-11428"> , ... </script>，从这些点中选出一条直线，来很好的拟合这些点。通过求解，最后得到的回归方程形式是 $y=bx+a$，然后来一个新的新的 $x$，通过这个函数，能够计算得到对应的$y$的值。

所以一种常见的回归就是通过一系列的点，计算得到一条合适的线。当有新的输入时，可以直接计算得到输出。不局限于二维平面的话，点可以表示为 <x1→,y1>,<x2→,y2>...<xn→,yn> <script type="math/tex" id="MathJax-Element-11432"><\vec {x_1},y_1>,<\vec {x_2},y_2>...<\vec {x_n},y_n></script>，$\vec{x_1}$是一个$d$维的向量。对于线的表示都不尽相同，线性回归得到的预测函数形式是$y=\vec w^T * \vec x + a$，对于Logistic 回归，是一条“S”型曲线，在接下来会讲到。

还有一些回归不是通过得到一条线。比如使用决策树来回归。就是把一些点分布到树的节点上。每个节点的平均值就是作为回归值。

简单来说，回归就是根据输入预测一个值。

Logistic Regression形式

Logistic Regression最常见的应用场景就是预测概率。比如知道一个人的 年龄、性别、血压、胆固醇水平、体重，想知道这个人患心脏病的概率。首先很容易想到通过线性回归，根据这一组值来计算得到一个分数。对于病人的特征$(x_0, x_1, x_2,...,x_d)$，计算得到危险分数是

$$s=\sum_{i=0}^{d}w_ix_i$$
计算得到的分数越高，风险越大，分数越低，风险越小。s的取值是 $[-\infty,+\infty]$的值，但是我们想要的是一个 $[0,1]$之间的值。因此需要一个转换函数来把这个分数转换成 $[0,1]$之间的值。这个函数称为Logistic 函数，Logistic函数是一个S形的函数。
形状如下图所示：

这个函数也称为sigmoid函数。函数能够把s映射到 $[0,1]$之间，我们把这个函数称为 $\theta(s)$。Logistic函数形式为：
$$\theta(s)=\frac{e^s}{1+e^s}=\frac{1}{1+e^{-s}}$$
其中 $e$即是自然常数。
因此整个Logistic Regression的函数形式为：
$$h(\vec{x})=\frac{1}{1+e^{-\vec w^T\vec x}}$$

损失函数

在Logistic Regression函数中，我们使用最大似然方式来求解模型的参数。有关最大似然，维基百科有定义。
我们把真实模型称为$f$，学习得到的模型为$h$，$f$是未知的，要用$h$去拟合$f$。Logistic Regression的目标函数是，在已知$x$的条件下，输出$y=+1$的概率，$y=+1$即为$f(x)$，$y=-1$的概率为$1-f(x)$。对于数据集$D=\{(\vec x_1,+1),(\vec x_2,-1),...,(\vec x_n,-1)\}$，抽取到该数据集的概率为

$$P(\vec x_1)f(\vec x_1)P(\vec x_2)(1-f(\vec x_2))...P(\vec x_n)(1-f(\vec x_n))$$
因为 $f$是真正产生这个数据集的，$f$产生这个数据集的概率应该是很大的(最大似然估计的思想)。如果我们用 $h$来代替$f$，那么得到该数据集的概率为
$$P(\vec x_1)h(\vec x_1)P(\vec x_2)(1-h(\vec x_2))...P(\vec x_n)(1-h(\vec x_n))$$ ，这个概率我们称为似然函数 $likelihood(h)$。需要找到的最终的函数 $h$应该是$likelihood(h)$取最大值的那个 $h$。即我们要求解$likelihood(h)$最大值，然后得到 $h$即为我们想要的。

$$likelihood(h)=P(\vec x_1)h(\vec x_1)P(\vec x_2)(1-h(\vec x_2))...P(\vec x_n)(1-h(\vec x_n))$$
其中，根据Logistic函数的对称性有 $1-h(\vec x)=h(-\vec x)$。从而有
$$likehood(h) \propto \prod_{i=1}^{n}h(y_i \vec {x_i})(正比关系)$$
我们要求解 $\max \limits_hlikelihood(h)$，即需要求解 $\max \limits _h\prod_{i=1}^{n}h(y_i \vec {x_i})$，我们需要的是求得 $\vec w$这个参数，因此转换得到
$$likehood(w) \propto \prod_{i=1}^{n}\theta(y_i \vec w^T \vec{x_i})$$
这是一个连乘，两边取对，即可转换成连加。
$$ln(likehood(w)) \propto \sum_{i=1}^{n}ln(\theta(y_i \vec w^T \vec{x_i})) \propto \frac{1}{n}\sum_{i=1}^{n}ln(\theta(y_i \vec w^T \vec{x_i}))$$
求解上式的最大值，等价于求解
$$\min \limits_{\vec w} \frac{1}{n} \sum_{i=1}^{n}-ln(\theta(y_i \vec w^T \vec{x_i}))$$
把 $\theta$函数定义代入，得到
$$\min \limits_{\vec w} \frac{1}{n} \sum_{i=1}^{n}-ln(1+e^{-y_i \vec w^T \vec{x_i}})$$
定义 $$E_{in}(\vec w)=\sum_{i=1}^{n}-ln(1+e^{-y_i \vec w^T \vec{x_i}})$$

$$err(\vec w,y,\vec x)=ln(1+e^{-y_i \vec w^T \vec{x_i}})$$
$err(\vec w,y,\vec x)$为在极大似然估计下，Logistic方程的误差，称为cross entropy error。而让 $E_{in}(\vec w)$最小的 $\vec w$是我们希望得到的Logistic Regression模型的参数。

最小化$E_{in}(\vec w)$

根据以上的推导，损失函数$E_{in}(\vec w)$为

$$E_{in}(\vec w)=\sum_{i=1}^{n}-ln(1+e^{-y_i \vec w^T \vec{x_i}})$$
从数学上可以推导出 $E_{in}(\vec w)$是连续平滑的，可微，且二次可微的，也是凸函数(来自林轩田老师视频)。要求 $E_{in}(\vec w)$的最小值，就对 $E_{in}(\vec w)$求微分，然后计算微分等于0的点。
对 $E_{in}(\vec w)$在 $\vec w$每一个方向分量 $w_j$上求偏微分
$$\frac{\partial E_{in}(\vec w)}{\partial w_j}=\frac{1}{n}\sum_{i=1}^{n}\theta(-y_i \vec w^T \vec{x_i})(-y_i x_{i,j})$$
把偏微分中的 $x_{i,j}$换成向量，则可以得到一阶微分：
$$\nabla E_{in}(\vec w)=\frac{1}{n}\sum_{i=1}^{n}\theta(-y_i \vec w^T \vec{x_i})(-y_i \vec {x_{i}})$$

$\nabla E_{in}(\vec w)$属于该损失函数的梯度，在二维空间的话我们称为斜率。如果直接令：

$$\nabla E_{in}(\vec w)=0$$
来求解的话，是很难求解出 $\vec w$的值的，因此需要使用其他方式。

梯度下降法

直接求解是无法求解出$\vec w$的，一种思想是采用迭代的方式求最小的$E_{in}(\vec w)$。每次改变$\vec w$一点，尽可能使这个改变让$E_{in}(\vec w)$朝着变得更小，这样逐步使$E_{in}(\vec w)$趋近于最小值。如第$t$次到$t+1$次迭代，权重更新的形式如下：

$$\vec w_{t+1}=\vec w_t +\eta \vec v$$
其中 $\vec v$是一个单位向量， $\eta$是步长。 $E_{in}(\vec w_{t+1})$应该要比 $E_{in}(\vec w_t)$更小，这样的更新才有意义。因为我们是要找到 $E_{in}(\vec w)$的最小值。
$E_{in}(\vec w_{t+1})$代入 $\vec w_t$，得到 $E_{in}(\vec w_t +\eta \vec v)$。现在有 $E_{in}(\vec w)$的一阶微分，可以对 $E_{in}(\vec w_t +\eta \vec v)$采用泰勒展开，如下：
$$E_{in}(\vec w_t +\eta \vec v)\approx E_{in}(\vec w_t)+\eta \vec v^T\nabla E_{in}(\vec w_t)$$

忘记泰勒展开没关系，可以从直观上来理解这个式子。根据以上的结论，$E_{in}(\vec w)$是存在最小值的，同时是光滑连续，可微及二次可微的。其曲线类似于下图：

任何一条曲线，如果只看一小段的话，可以把这一小段曲线看成是一个线段。从数学上来讲，一个函数在某一点到附近的另外一点，可以用一个线段来表示。附近点的值为该点的值加上一小段线段的梯度，就得到了上式。

要使$E_{in}(\vec w_t)+\eta \vec v^T\nabla E_{in}(\vec w_t)$比$E_{in}(\vec w_t)$小很多，必须$\eta \vec v^T\nabla E_{in}(\vec w_t)$取最小值，$\eta$是不变的，两个向量相乘需要得到最小值，很显然方向相反时，向量乘积取得最小值。因此$\vec v$需要和$\nabla E_{in}(\vec w_t)$方向相反，同时$\vec v$是单位向量，因此在$w_t$点时有

$$\vec v=-\frac{\nabla E_{in}(\vec w_t)}{\parallel \nabla E_{in}(\vec w_t)\parallel}$$

因此有$\vec w$的更新方式为

$$\vec w_{t+1}=\vec w_t -\eta \frac{\nabla E_{in}(\vec w_t)}{\parallel \nabla E_{in}(\vec w_t)\parallel}$$

到此，梯度下降总体思想结束了。梯度下降主要有两种方法，一种是随机梯度下降，一种是批量梯度下降。批量梯度下降每次更新权重需要训练完所有的数据，随机梯度下降每次训练完一条记录，就可以计算对应梯度，更新权重。在实际使用中，推荐使用随机梯度，收敛速度快。同时有关步长$\eta$的设置需要注意，设置太大会引起抖动，太小收敛速度太慢，可以采用动态的步长，比如一开始比较大，慢慢的缩小。迭代更新的停止条件从理论上来说是找不到更小的$E_{in}(\vec w)$，在实际使用可以直接设置一个比较大的迭代次数，或者根据经验设置一个迭代次数，一般都会收敛。当然这些都是工程上的东西了。

总结

到此基本讲完了Logistic Regression大部分内容了。当时在学校学完之后怎么也没懂，损失函数为什么是这样，为什么要使用随机梯度下降等等这些问题一直没有解决，虽然看看博客也能够做实验把代码写完(南京大学数据挖掘课程很赞啊)。最近在看林轩田老师的视频，慢慢弄，基本搞懂了。Logistic Regression作为常见的一类回归，其中的思想在很多算法中都用到。欢迎大家一起讨论。