关于Logistic Regression对于线性可分的数据集的不收敛性的分析

问题的提出

最近我在进行斯坦福cs229的题目练习时候，碰到了一个不容易理解的case：即当面对线性可分的数据集的时候，Logistic Regression算法将永远无法收敛。

刚碰到的时候，心想stanford的题目真不是盖的，尽然百思不得其解。经过了各种google出来的帖子，文章，slides的阅读，目前算是有了一点点了解，但是还没真正理解透彻。所以目前先就理解的这部分按照逻辑叙述一下。

先从几个基本概念的介绍开始。

线性可分的数据集(Linealy separable data)

官方得说，就是有一堆标签数据，分别标为“1”，“0”两种。在其分布的坐标空间中，存在一个超平面可以正好将两种标签的数据分开，就叫做线性可分的数据集。一般情况下，只要这个数据是线性可分的，就存在无数个超平面可以将两类数据分开。

我们用更严格的数学语言描述一下，有一份数据项的数目为m的数据集：

$\{(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), ... , (x^{(m)}, y^{(m)})\}, y^{(i)} \in \{0,1\}$

如果这个数据是线性可分(Linear separability)，则存在一个超平面：

$\theta^Tx = 0$

使得上面的数据集有如下不等式组成立：

$\begin{cases} \theta^Tx^{(i)} > 0, \quad \ \ & If (y^{(i)}=1)\\ \theta^Tx^{(i)} < 0, \quad \ \ & If (y^{(i)}=0)\\ \end{cases}$

其中 x向量中有一项为1 ，即 $x_0 = 1$ ，这个处理主要是为了包含超平面的常数项，即 $W^Tx + b = 0$

为了更好理解线性可分的概念，我们可以看一个直观一点的二维数据图：

线性可分

Logistic Regression的基本回顾

Logistic Regression中文叫逻辑回归，通俗得说就是二元线性回归或者多元线性回归后加上sigmoid函数，输出为二值分类。主要计算公式是损失函数：

$\begin{cases} J = \frac{1}{m} \sum_{i=1}^m (- y^{(i)} \log(h_\theta(x^{(i)})) - (1-y^{(i)} ) \log(1-h_\theta(x^{(i)}))) \\ h_\theta(x) = \frac{1}{1+e^{-\theta x}} \\ \end{cases}$

整个逻辑回归就是通过梯度下降法或者牛顿法来求出一个最优的向量， $\theta$ ，使得上式中的J取最小值。所谓梯度下降法为：

$\theta := \theta - \alpha\frac{\partial J(\theta)}{\partial \theta}$

分析

假设我们做Logistic Regression所用的是梯度下降法。即刚开始 $\theta$ 值都是随机的，或者都是0。所以在运用迭代法之前， $\theta$ 所取的值组成的超平面，是无法将数据正好分成标记正确的两部分，所以迭代可以一直进行下去, 直到迭代出一个线性可分的 $\theta$ 。此时继续迭代，我们的目标函数将不能继续收敛了。

首先因为当前 $\theta$ 已经满足线性可分，所以损失函数 $J$ 将简化成如下式子：

$\begin{equation} J(\theta)=\begin{cases}\ \frac{1}{m} \sum_{i=1}^m (- y^{(i)} \log(h_\theta(x^{(i)}))) &when \ y^{(i)}=1\\ \frac{1}{m} \sum_{i=1}^m (-(1-y^{(i)} ) \log(1-h_\theta(x^{(i)}))) &when \ y^{(i)}=0\\ \end{cases} \end{equation}$

我们再分析一下当 $\theta$ 增加时， $h_\theta(x)$ 函数的趋势：

$\begin{equation} h_\theta(x)=\frac{1}{1+e^{-\theta x}}=\begin{cases}\ increase &when \ \theta x > 0 \\ decrease &when \ \theta x < 0 \\ \end{cases} \end{equation}$

又因为之前的关于 $\theta x$ 与 $y^{(i)}$ 的分析，可知上面两个式子的各自的两种情况是一一对应的，即从 $y^{(i)}=1$ 可推出 $\theta x > 0$ ，所以可以知道 $J(\theta)$ 在随着 $\theta$ 增加，而单调减，最终减小为0，但是这个过程是当 $\theta$ 取无限大的时候， $J(\theta)$ 的极限才减小到0，所以 $J(\theta)$ 在这种情况下没有最小值， $\theta$ 会永远增加下去而无法收敛。

后记

这篇收敛性的分析写得还是比较匆忙，仅仅是流水账地做了一点推理，很难做到逻辑缜密。而且我的思路的正确性有有待验证。

最后编辑于：2019.01.08 00:07:55