三種線性方法的優化

02-09

三種線性方法優化方法

有限記憶BFGS(L-BFGS)

L-BFGS是擬牛頓方法家族裡的一個優化演算法，解決 ${min _{w in {R^d}}}f(w)$ 形式的優化問題。L-BFGS方法以二次方程來逼近目標函數來構造黑塞矩陣，不考慮目標函數的二階偏導數。黑塞矩陣由先前的迭代評估逼近，所以不像直接使用牛頓方法一樣可垂直擴展（訓練特徵的數目）。所以L-BFGS通常比其他一階優化方法能更快收斂。

象限有限記憶擬牛頓(OWL-QN)演算法是L-BFGS的擴展，它可以有效處理L1和彈性網格正則化。

L-BFGS在Spark MLlib中用於線性回歸、邏輯回歸、AFT生存回歸和多層感知器的求解。

加權最小二乘法的正規方程求解器

MLlib通過WeightedLeastSquares提供加權最小二乘法的正規方程求解器。

給定n個加權觀察值（ ${w_i},{a_i},{b_i}$ ）:

${w_i}$ 是第i個觀察值的權重

${a_i}$ 是第i個觀察值的特徵向量

${b_i}$ 是第i個觀察值的標籤。

每個觀察值有m個特徵。我們使用下面的最小二乘法公式：

${min _x}frac{1}{2}sumlimits_{i = 1}^n {frac{{{w_i}{{(a_i^Tx - {b_i})}^2}}}{{sum olimits_{k = 1}^n {{w_k}} }} + frac{1}{2}frac{lambda }{delta }} {({sigma _j}{x_j})^2}$

其中 $lambda$ 是正則化參數， $delta$ 是標籤的總體標準偏差， ${sigma _j}$ 是第j列特徵的總體標準偏差。這個目標函數有一個解析解，它只需要一個收集數據的必要統計量。與原始數據需要唄存儲在分散式系統中不同，如果特徵數量相對較小，統計信息可以存儲在單機中，然後我們可以通過Cholesky分解來解決目標函數。

加權最小二乘僅支持L2正則化，提供選項啟用或禁用正則化和標準化。為了使正則方程逼近是有效的，加權最小二乘要求特徵的數量不超過4096個。對於規模更大的問題，是有L-BFGS。

迭代加權最小二乘法(IRLS)

迭代加權最小二乘法可以用來找到廣義線性模型的極大似然估計，找到魯棒回歸和其他優化問題中的M估計。

它通過下面的步驟迭代地解決具體的優化問題。

1.線性化目標並更新相應的權重

2.解決加權最小二乘問題

3.重複上述步驟直至收斂

因為在第二步中使用了加權最小二乘方法在每次迭代中，所以它同樣要求特徵數量不超過4096個。現在IRLS是廣義線性回歸的默認方法。