問題的提出

最近我在進行斯坦福cs229的題目練習時候，碰到了一個不容易理解的case：即當面對線性可分的數(shù)據(jù)集的時候，Logistic Regression算法將永遠無法收斂。

剛碰到的時候，心想stanford的題目真不是蓋的，盡然百思不得其解。經(jīng)過了各種google出來的帖子，文章，slides的閱讀，目前算是有了一點點了解，但是還沒真正理解透徹。所以目前先就理解的這部分按照邏輯敘述一下。

先從幾個基本概念的介紹開始。

線性可分的數(shù)據(jù)集(Linealy separable data)

官方得說，就是有一堆標簽數(shù)據(jù)，分別標為“1”，“0”兩種。在其分布的坐標空間中，存在一個超平面可以正好將兩種標簽的數(shù)據(jù)分開，就叫做線性可分的數(shù)據(jù)集。一般情況下，只要這個數(shù)據(jù)是線性可分的，就存在無數(shù)個超平面可以將兩類數(shù)據(jù)分開。

我們用更嚴格的數(shù)學語言描述一下，有一份數(shù)據(jù)項的數(shù)目為m的數(shù)據(jù)集：

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

如果這個數(shù)據(jù)是線性可分(Linear separability)，則存在一個超平面：

$\theta^Tx = 0$

使得上面的數(shù)據(jù)集有如下不等式組成立：

$\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$ ，這個處理主要是為了包含超平面的常數(shù)項，即 $W^Tx + b = 0$

為了更好理解線性可分的概念，我們可以看一個直觀一點的二維數(shù)據(jù)圖：

線性可分

Logistic Regression的基本回顧

Logistic Regression中文叫邏輯回歸，通俗得說就是二元線性回歸或者多元線性回歸后加上sigmoid函數(shù)，輸出為二值分類。主要計算公式是損失函數(shù)：

$\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}$

整個邏輯回歸就是通過梯度下降法或者牛頓法來求出一個最優(yōu)的向量， $\theta$ ，使得上式中的J取最小值。所謂梯度下降法為：

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

分析

假設我們做Logistic Regression所用的是梯度下降法。即剛開始 $\theta$ 值都是隨機的，或者都是0。所以在運用迭代法之前， $\theta$ 所取的值組成的超平面，是無法將數(shù)據(jù)正好分成標記正確的兩部分，所以迭代可以一直進行下去, 直到迭代出一個線性可分的 $\theta$ 。此時繼續(xù)迭代，我們的目標函數(shù)將不能繼續(xù)收斂了。

首先因為當前 $\theta$ 已經(jīng)滿足線性可分，所以損失函數(shù) $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)$ 函數(shù)的趨勢：

$\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}$

又因為之前的關(guān)于 $\theta x$ 與 $y^{(i)}$ 的分析，可知上面兩個式子的各自的兩種情況是一一對應的，即從 $y^{(i)}=1$ 可推出 $\theta x > 0$ ，所以可以知道 $J(\theta)$ 在隨著 $\theta$ 增加，而單調(diào)減，最終減小為0，但是這個過程是當 $\theta$ 取無限大的時候， $J(\theta)$ 的極限才減小到0，所以 $J(\theta)$ 在這種情況下沒有最小值， $\theta$ 會永遠增加下去而無法收斂。