牛頓法解機器學習中的Logistic回歸

這仍然是近期系列文章中的一篇。在這一個系列中，我打算把機器學習中的Logistic回歸從原理到應用詳細串起來。最初我們介紹了在Python中利用Scikit-Learn來建立Logistic回歸分類器的方法

Python機器學習之Logistic回歸

此后，我們對上述文章進行了更深一層的探討，介紹了利用Logistic回歸在自然語言處理中的應用（對微博進行Sentiment Analysis）

自然語言處理實戰之微博情感偏向分析

從應用角度介紹了Logistic回歸之后，我們又從源頭介紹了Logistic回歸的數學原理

機器學習之詳解Logistic回歸

在這篇文章的最后，我們得到了一個似然函數為

然后我們的目標是求出使這一似然函數值最大的參數估計，于是對函數取對數，再求一階偏導數得到 

從這個偏導數出發，在實際中有很多方法可以解決前面的似然函數最大化參數估計問題，而我們這里要介紹的就是其中非常重要的一種，即牛頓法和擬牛頓法。

牛頓迭代法解方程的簡單回顧

現代計算中涉及大量的工程計算問題，這些計算問題往往很少采用我們通常在求解計算題甚至是考試時所采用的方法，因為計算機最擅長的無非就是“重復執行大量的簡單任務”，所以數值計算方面的迭代法在計算機時代便有了很大的作用。例如我們之前介紹過的利用“Jacobi迭代法與Gauss-Seidel迭代法”求解方程組的方法。另外一個例子則是利用牛頓迭代法近似求解方程的方法。牛頓迭代又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method）。如果讀者對這部分內容感興趣，可以詳細參閱

牛頓迭代法與一道經典編程問題

我們在此做簡要回顧。有時候某些方程的求根公式可能很復雜（甚至有些方程可能沒有求根公式），導致求解困難。這時便可利用牛頓法進行迭代求解。

假設我們要求解方程f(x)=0的根，首先隨便找一個初始值x0，如果x0不是解，做一個經過(x0,f(x0)) 這個點的切線，與x軸的交點為x1。同樣的道理，如果x1不是解，做一個經過(x1,f(x1))這個點的切線，與x軸的交點為x2。 以此類推。以這樣的方式得到的xi會無限趨近于 f(x)=0 的解。

判斷xi是否是f(x)=0的解有兩種方法：一是直接計算f(xi)的值判斷是否為0，二是判斷前后兩個解xi和xi?1是否無限接近。經過(xi,f(xi))這個點的切線方程為（注意這也是一元函數的一階泰勒展式） 

其中，f′(x)為f(x)的導數。令切線方程等于 0，即可求出

于是乎我們就得到了一個迭代公式，而且它必然在 f(x?)=0處收斂，其中x?就是方程的根，由此便可對方程進行迭代求根。

牛頓法在最優化問題中的應用

假設當前任務是優化一個目標函數 f，也就是求該函數的極大值或極小值問題，可以轉化為求解函數 f 的導數 f′=0 的問題，這樣求可以把優化問題看成方程 f′=0 求解問題。剩下的問題就和前面提到的牛頓迭代法求解很相似了。

這次為了求解方程 f′=0 的根，把原函數 f(x) 的做泰勒展開，展開到二階形式（注意之前是一階）：

當且僅當 Δx 無線趨近于0時，（可以舍得后面的無窮小項）使得等式成立。此時上式等價與： 

注意因為Δx 無線趨近于0，前面的的常數 1/2 將不再起作用，可以將其一并忽略，即 

求解 

得出迭代公式 

在之前的文章中我們也提到最優化問題除了用牛頓法來解之外，還可以用梯度下降法來解。但是通常來說，牛頓法可以利用到曲線本身的信息，比梯度下降法更容易收斂，即迭代更少次數。

再次聯系到我們之前給出的一篇文章“Hessian矩陣與多元函數極值”，對于一個多維向量 X, 以及在點 X0 的鄰域內有連續二階偏導數的多元函數 f(X) ，可以寫出該函數在點 X0 處的（二階）泰勒展開式

其中，o(∥X?X0∥2) 是高階無窮小表示的皮亞諾余項。而 Hf(X0) 是一個Hessian矩陣。依據之前的思路，忽略掉無窮小項，寫出迭代公式即為 

由此，高維情況依然可以用牛頓迭代求解，但是問題是Hessian矩陣引入的復雜性，使得牛頓迭代求解的難度大大增加。所以人們又提出了所謂的擬牛頓法（Quasi-Newton method），不再直接計算Hessian矩陣，而是每一步的時候使用梯度向量更新Hessian矩陣的近似。這一點我們后續還會再討論。

牛頓迭代法求解Logistic回歸

現在回歸到最開始的那個問題上。我們已經求出了Logistic回歸的似然函數的一階偏導數

由于lnL(w)是一個多元函數，變量是 w=w0,w1,?,wn ，所以根據多元函數求極值問題的規則，易知極值點處的導數一定均為零，所以一共需要列出n+1個方程，聯立解出所有的參數。下面列出方程組如下 

當然，在具體解方程組之前需要用Hessian矩陣來判斷極值的存在性。求Hessian矩陣就得先求二階偏導，即

顯然可以用Hessian矩陣來表示以上多元函數的二階偏導數，于是有 

所以得到Hessian矩陣H=XTAX，可以看出矩陣A是負定的。線性代數的知識告訴我們，如果A是負定的，那么Hessian矩陣H也是負定的。也就是說多元函數存在局部極大值，這剛好符合我們的要求的最大似然估計相吻合。于是我們確信可以用牛頓迭代法來繼續求解最優化問題。

對于多元函數求解零點，同樣可以用牛頓迭代法，對于當前討論的Logistic回歸，可以得到如下迭代式 

其中H是Hessian矩陣，U的表達式如下 

由于Hessian矩陣H是對稱負定的，將矩陣A提取一個負號出來，得到 

然后Hessian矩陣H變為H′=XTA′X，這樣H′就是對稱正定的了。那么現在牛頓迭代公式變為 

現在我們需要考慮如何快速地算得(H′)?1U，即解方程組(H′)?1X=U，通常的做法是直接用高斯消元法求解，但是這種方法的效率一遍比較低。而當前我們可以利用的一個有利條件是H′是對稱正定的，所以可以用Cholesky矩陣分解法來解。Cholesky分解原理可以參考線性代數方面的書籍，此處不再贅述。

到這里，牛頓迭代法求解Logistic回歸的原理已經介紹完了，但正如前面所提過的，在這個過程中因為要對Hessian矩陣求逆，計算量還是很大。而在后續的文章里我們會再來詳細探討擬牛頓法原理及應用，它是針對牛頓法的弱點進行了改進，更具實踐應用價值。