在上一篇文章《機器學習算法推導&實現——邏輯斯蒂回歸》中，我們分別使用瞭梯度下降法和牛頓法來求解對數似然函數的最優化問題，從實例中我們也能發現牛頓法的收斂速度遠快於梯度下降法，但是在上文中，直接使用瞭牛頓法的結果，並沒有進行相應推導，故本文一方面是補上牛頓法的推導，另一方面是展開討論下擬牛頓法。
牛頓法推導
- 牛頓法的推導得先從泰勒公式說起：
泰勒公式
- 假設現在函數f(x)迭代瞭k次的值為X(k)，則在X(k)上進行二階泰勒展開可近似得到以下公式：
泰勒二階展開
- 我們要求得f(x)的極小值，則必要條件是f(x)在極值點處的一階導數為0，即：
- 因為我們把每輪迭代求得的滿足目標函數極小值的x作為下一輪迭代的值，因此我們可以假設第k+1輪的值就是最優解：
- 代入二階泰勒展開並求導可得：
- 令：
一階導數二階導數
- 可得最終的優化公式為：
牛頓法迭代
- 雖然根據推導，我們已經知道瞭牛頓法的迭代方法，但是在實際應用過程中，我們會發現海塞矩陣的逆矩陣往往計算比較復雜，於是又有瞭擬牛頓法來簡化這一過程。
擬牛頓法的原理
- 在擬牛頓法中，我們考慮優化出一個n階矩陣D來代替海塞矩陣的逆矩陣，首先我們得先來看看替代矩陣D要滿足什麼條件：
- 首先根據二階泰勒展開，我們令：
- 代入f(x)，並求導，可得：
泰勒二階展開
- 再令：
- 最終可得矩陣D需滿足的條件：
替代矩陣Dk需滿足的條件
- 另外在每次迭代中可以更新矩陣D，故可以假設以下更新條件：
- 由此我們可以發現海塞矩陣逆矩陣的近似矩陣D(x)的選擇條件比較靈活，可以有多種具體的實現方法。
1、DFP算法（Davidon-Fletcher-Powell）推導
- 在DFP算法中，我們假設：
- 兩邊乘以 Delta{g_k} 可得：
- 為瞭滿足上式要求，我們不妨令：
- 我們先來求P矩陣，最簡單的就是令：
- 接著兩邊乘以 Delta{g_k} 可得：
- 求得 alpha ，並代入P矩陣，可求得：
- 同樣的方法我們求解下Q矩陣：
- 最終，DFP算法的迭代公式為：
DFP算法替代海塞矩陣逆矩陣的迭代公式
python實現DFP算法
- 我們繼承上一篇文章邏輯回歸算法的類，並且增加擬牛頓法的優化算法。
- 我們先看下算法的主函數部分，在繼承邏輯回歸類的基礎上主要有2點改動：一是把"method"參數提前，在實例化的時候就要求定位好優化算法；二是重寫瞭train方法，衍生出其他擬牛頓算法。
from ML_LogisticRegression import LogisticRegressionSelf as logit
import numpy as np
class allLogitMethod(logit):
def __init__(self, method):
"""init class"""
super().__init__()
self.method = method
self.graList = [] #記錄梯度模長的列表
#重寫下train方法
def train(self, X, y, n_iters=1000, learning_rate=0.01):
"""fit model"""
if X.ndim < 2:
raise ValueError("X must be 2D array-like!")
self.trainSet = X
self.label = y
if self.method.lower() == "gradient":
self._LogisticRegressionSelf__train_gradient(n_iters, learning_rate)
elif self.method.lower() == "newton":
self._LogisticRegressionSelf__train_newton(n_iters)
elif self.method.lower() == "dfp":
self.__train_dfp(n_iters, learning_rate)
else:
raise ValueError("method value not found!")
return