Logistic Regression

一个事件的几率(odds)是指该事件发生的概率与该事件不发生的概率的比值。例如，如果事件发生概率为 $p$ ，则该事件的几率为 $\frac{p}{1-p}$ 。 事件的对数几率称为 logit 函数 ，即：
$$\mathrm{logit}(p)=\ln \frac{p}{1-p}$$

对于 Logistic 回归模型来说，有：
$$\begin{array}{rl}\mathrm{logit}(p)& =\ln \frac{p}{1-p}\\ & =\ln \frac{P(Y=1\mid \mathit{x})}{1-P(Y=1\mid \mathit{x})}\\ & =\ln \frac{\frac{1}{1+e^{-{\mathit{w}}^{\mathsf{T}}\mathit{x}}}}{1-\frac{1}{1+e^{-{\mathit{w}}^{\mathsf{T}}\mathit{x}}}}\\ & ={\mathit{w}}^{\mathsf{T}}\mathit{x}\end{array}$$
有时，我们用 logit 函数来表示 Logistic 回归模型。

可以用梯度下降法求得损失函数最小时对应的参数值。梯度下降法是一种迭代算法，其参数更新公式为：
$${\theta }_{new}={\theta }_{old}-\mu \mathrm{\nabla }f({\theta }_{old})={\theta }_{old}-\mu {\frac{\partial f}{\partial \theta }|}_{\theta ={\theta }_{old}},\mu >0$$

我们按下面规则迭代更新 Logistic 回归模型参数 $\mathit{w}$ 的每一个分量 $w^{(j)},j=0,1,2,\cdots ,n$ 即可：
$$w_{new}^{(j)}=w_{old}^{(j)}-\mu {\frac{\partial J}{\partial w^{(j)}}|}_{w^{(j)}=w_{old}^{(j)}},\mu >0$$

上式中的 $\frac{\partial J}{\partial w^{(j)}}$ 求解过程如下：
$$\begin{array}{rl}\frac{\partial J}{\partial w^{(j)}}& =\frac{\partial }{\partial w^{(j)}}(-\sum _{i=1}^N[y_i\ln \pi ({\mathit{x}}_{\mathit{i}})+(1-y_i)\ln (1-\pi ({\mathit{x}}_{\mathit{i}}))])\\ & =\frac{\partial }{\partial w^{(j)}}(-\sum _{i=1}^N[y_i({\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}})-\ln (1+e^{{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}})])\\ & =-\sum _{i=1}^N\frac{\partial }{\partial w^{(j)}}(y_i({\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}})-\ln (1+e^{{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}))\\ & =-\sum _{i=1}^N\frac{\partial }{\partial w^{(j)}}(y_i(w^{(0)}{x}_i^{(0)}+w^{(1)}{x}_i^{(1)}+\cdots +w^{(j)}{x}_i^{(j)}+\cdots +w^{(n)}{x}_i^{(n)})-\ln (1+e^{w^{(0)}{x}_i^{(0)}+w^{(1)}{x}_i^{(1)}+\cdots +w^{(j)}{x}_i^{(j)}+\cdots +w^{(n)}{x}_i^{(n)}}))\\ & =-\sum _{i=1}^N(y_i{x}_i^{(j)}-\frac{\partial }{\partial w^{(j)}}(\ln (1+e^{w^{(0)}{x}_i^{(0)}+w^{(1)}{x}_i^{(1)}+\cdots +w^{(j)}{x}_i^{(j)}+\cdots +w^{(n)}{x}_i^{(n)}})))\\ & =-\sum _{i=1}^N(y_i{x}_i^{(j)}-\frac{1}{1+e^{w^{(0)}{x}_i^{(0)}+w^{(1)}{x}_i^{(1)}+\cdots +w^{(j)}{x}_i^{(j)}+\cdots +w^{(n)}{x}_i^{(n)}}}{e}^{w^{(0)}{x}_i^{(0)}+w^{(1)}{x}_i^{(1)}+\cdots +w^{(j)}{x}_i^{(j)}+\cdots +w^{(n)}{x}_i^{(n)}}{x}_i^{(j)})\\ & =-\sum _{i=1}^N(y_i{x}_i^{(j)}-\frac{e^{{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}}{1+e^{{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}}{x}_i^{(j)})\\ & =-\sum _{i=1}^N(y_i{x}_i^{(j)}-\pi ({\mathit{x}}_{\mathit{i}})x_i^{(j)})\\ & =-\sum _{i=1}^N((y_i-\pi ({\mathit{x}}_{\mathit{i}})x_i^{(j)}))\end{array}$$

说明 1：上面的推导过程仅仅用了求导的一些基本知识，如复合函数求导的链式法则(Chain rule)，求导公式 $(\ln x{)}^{\prime }=\frac{1}{x},(e^x{)}^{\prime }=e^x$ 等等。
说明 2：本文中， ${\mathit{x}}_{\mathit{i}}$ 表示训练数据集 $N$ 条记录中的某一条，而 $x_i^{(j)}$ 则表示这条记录的第 $j$ 个特征。这种表示方法和李航著作“统计学习方法”一致；但和 Andrew Ng 的机器学习课程中的表示不一致（Andrew Ng 的课程可参考http://cs229.stanford.edu/notes/cs229-notes1.pdf）。

所以，最后可以得到 Logistic 回归模型参数 $\mathit{w}$ 的每一个分量 $w^{(j)},j=0,1,2,\cdots ,n$ 的迭代更新公式为：
$$w_{new}^{(j)}=w_{old}^{(j)}+\mu {\sum _{i=1}^N((y_i-\pi ({\mathit{x}}_{\mathit{i}})x_i^{(j)}))|}_{w^{(j)}=w_{old}^{(j)}},\mu >0$$
其中， $\pi ({\mathit{x}}_{\mathit{i}})=\frac{1}{1+e^{-{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}},y_i\in \{0,1\}$

前面得到的随机梯度下降法参数迭代公式中有 $\sum _{i=1}^N$ ，即用梯度下降法每次更新参数 $\mathit{w}$ 都要遍历整个训练数据集！如果训练数据非常大时，这将很耗时。
一种改进办法是采用随机梯度下降法(Stochastic Gradient Descent, SGD)， 随机梯度下降法每次仅使用一个训练数据来更新参数。 随机梯度下降法的参数迭代公式为：
$$w_{new}^{(j)}=w_{old}^{(j)}+\mu {(y_i-\pi ({\mathit{x}}_{\mathit{i}})x_i^{(j)})|}_{w^{(j)}=w_{old}^{(j)}},\mu >0$$
其中， $\pi ({\mathit{x}}_{\mathit{i}})=\frac{1}{1+e^{-{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}},y_i\in \{0,1\}$

说明 1：随机梯度下降法可以在新训练数据到来时，对 Logistic 回归分类器进行增量式更新，所以 随机梯度下降法是一个“在线”学习算法 ；与“在线”学习相对应，一次处理所有训练数据的方式被称为是“批处理”。
说明 2：应该注意上面的参数迭代公式有一个前提是分类标记 $y_i\in \{0,1\}$ ，如果给定的训练数据不是这样（例如为 $y_i\in \{-1,1\}$ ），则在使用上面的参数迭代公式时应该把-1 转换为 0。

梯度下降公式中的学习率（又称步长） $\mu$ 比较难决定，太小，则更新太慢；太大，则容易矫枉过正。如图 2 （图中用 $\eta$ 表示学习率）所示。

如何选择合适的步长？这个问题没有标准答案，基本上需要通过测试确定。 简单的做法是选择随迭代次数增加而逐渐减小的 $C/t,C/t^2$ 等。

参考：
http://www.cs.rpi.edu/~magdon/courses/LFD-Slides/SlidesLect09.pdf
https://www.quora.com/What-is-the-best-way-to-choose-the-step-size-in-stochastic-gradient-descent

如果使用平方损失函数，则每个数据产生的损失（误差）为：

其中， $\pi ({\mathit{x}}_{\mathit{i}})=\frac{1}{1+e^{-{\mathit{w}}^{\mathsf{T}}{\mathit{x}}_{\mathit{i}}}},y_i\in \{0,1\}$

使用平方误差和 $\sum err$ 作为损失也是可以的，但它是关于参数 $\mathit{w}$ 的非凸函数(non-convex function)，这里不证明它。
而对于非凸函数的优化是非常困难的（注：梯度下降法要求被优化函数是凸函数）。非凸函数由于存在很多个局部最小点，比较难去做最优化（求全局最小点）。所以 Logistic 回归不使用平方损失函数。

参考：
http://beader.me/2014/05/03/logistic-regression/
http://www.holehouse.org/mlclass/06_Logistic_Regression.html

前面已经介绍过梯度下降法和随机梯度下降法最小化损失函数。牛顿法(Newton method)和拟牛顿法(Quasi-Newton method)也是求解无约束最优化问题的常用方法，可以用来最小化 Logistic 回归模型的损失函数。这里不详细介绍。

牛顿法和拟牛顿法的优点在其收敛速度一般比梯度下降法更快，而且无需手动选择学习率（即步长）。 不过牛顿法和拟牛顿法的计算相对比梯度下降法复杂。

实际应用时，我们数据的维度可能很高， L1 正则化的一个重要优点是能产生稀疏解（即有很多权重为零），这可以实现“特征选择”。

为了便于可视化，我们考虑两维的情况，如图 4 所示。在 $(w^{(1)},w^{(2)})$ 平面上画出目标函数的等高线（在图中带有颜色的圈圈上任取 $(w^{(1)},w^{(2)})$ 后，用它们计算的目标函数值是相等的，离这些圈圈的中心越近，目标函数值越小，在圈圈中心处的目标函数值最小），而约束条件则成为平面上半径为 C 的一个 norm ball 。等高线与 norm ball 首次相交的地方就是最优解。图 4 中的 l1-ball 和 l2-ball 包含的区域是解空间。我们只能在这个解空间中，寻找使得目标函数最小的 $w^{(1)}$ 和 $w^{(2)}$ 值。

可以看到，l1-ball 与 l2-ball 的不同在于它和每个坐标轴相交的地方都有“角”出现，而目标函数的测地线除非位置摆得非常好，大部分时候都会在角的地方相交。注意到在角的位置为产生稀疏性，例如图中的相交点就有 $w^{(1)}=0$ ，而更高维的时候（想象一下三维的 l1-ball 是什么样的？）除了角点以外，还有很多边的轮廓也是既有很大的概率成为第一次相交的地方，又会产生稀疏性。

相比之下，l2-ball 就没有这样的性质，因为没有角，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么 L1 regularization 能产生稀疏性，而 L2 regularization 不易产生稀疏性的原因了。

参考：
Pattern Recognition and Machine Learning, 3.1.4 Regularized least squares
http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization
http://blog.csdn.net/zouxy09/article/details/24971995