手把手教你機器學習凸優化

最優化

隨著大資料的到來， 平行計算的流行， 實際上機器學習領域的很多研究者會把重點放在最優化方法的研究上， 如large scale computation。 那麼為什麼要研究最優化呢？我們先從機器學習研究的目的說起。 機器學習理論主要是設計和分析一些讓電腦可以自動“學習”的演算法， 這些演算法可以從資料中自動分析獲得規律， 並利用規律對未知數據進行預測， 並可用於發現資料之間隱藏的關係， 解釋某些現象的發生。 至於為什麼要讓機器去做這些事情， 原因很簡單， 資料量和維度過于龐大， 無法通過人腦簡單的處理或分析這些資料。

比如， 我們無法通過百萬級的DNA序列分析各序列和疾病發生的關係， 也無法在一定有限的時間內標定出1萬張圖像上人臉的位置。 所以 研究者傾向于建立一些機器學習模型， 通過輸入一個樣本（一個人的DNA序列或者是一副圖片）， 輸出樣本的標籤（是否患病、頭像的位置）。 這些學習模型裡有大量可以調整的參數， 它們通過調整參數組合， 擬合高維空間訓練樣本資料的分佈， 識別出資料和標籤之間複雜的關係。 目前已有的神經網路、支援向量機、AdaBoost、卷積神經網路等演算法， 它們的共同特點是通過調整參數讓模型的目標函數盡可能大或者小（如logistic回歸是使得分類錯誤率儘量小）。 為了達到該目的， 不同的機器學習演算法首先會設定不同的目標函數， 然後給參數賦上隨機初值， 最後用各種下降法更快更好地尋找能讓分類錯誤率更小的參數組合。

所以， 從廣義上講， 機器學習演算法的本質上是優化問題求解， 例如， 梯度下降、牛頓法、共軛梯度法都是常見的機器學習演算法優化方法。 那麼有人肯定會有疑問， 這不還是調參數、選擇參數麼？這個參數優化與之前的調參的概念是不同的， 之前說的調參是針對演算法中的自由參數（即通過經驗指定的參數， 用過weka或者R的人應該知道， 如SVM中的gamma或者logistic回歸中的懲罰因數lamda）， 這些參數主要是控制學習模型的泛化能力， 防止過擬合。 而這裡通過優化演算法反覆運算出的參數則是目標函數中待求解的參數，

例如， 神經網路中各隱含層節點的權值、logistic回歸中各引數的係數。 對於不同目標函數和不同優化演算法， 產生的問題也各不相同， 比如某些目標函數不是凸函數也不是無約束的優化問題， 無法直接利用梯度下降演算法求解， 又例如梯度下降法往往只能保證找到目標函數的局部最小值， 找不到全域最小值， 那麼該怎麼解決這些問題呢？答案是不一味的強行採用梯度下降， 而是引入其他變數（拉格朗日乘子）將有約束問題轉化為無約束問題， 也可以適當爬爬山， 說不定能跳出小水溝（局部極小值）找到真正的深井（全域極小值）， 這種演算法叫類比退火。 也可以增大搜索範圍， 讓一群螞蟻（蟻群演算法）或者鳥兒（粒子群演算法）一齊搜索， 或者讓參數巧妙地隨機改變（遺傳演算法）。 所以， 如何更快的找到目標函數的全域最小值或者全域最大值， 如何避免陷入局部最優解是優化演算法研究的重點。

講了這麼多， 主要是為了說明機器學習與最優化問題的聯繫， 也為大家更好的理解後續機器學習演算法提供基礎。 接下來， 我們會把講解重點放在放在最優化及凸優化理論上。

1. 最優化問題

數值優化問題或者簡稱為優化問題主要是求問題的解， 優化問題具有以下一般形式：

minimize f0(x) subject to fi(x)≤bi,i=1 ,…,m（1.1）

其中， 函數f0為目標函數， 函數 fi：Rn→R 為不等式， 或約束函數。

x=(x1,…,xn)為向量， 是目標函數的待優化參數（optimization variables）， 也稱為優化問題的可行解， 常量b1,…,bm稱為邊界或約束。 當存在向量x*，

使得滿足上式約束的任意向量z， 存在f0(x*)a,最小二乘問題

最小二乘問題（Least－Square problems）是無約束優化問題， 同時， 目標函數是具有aiTx-bi形式的線性運算式的平方和， 其一般形式可記為：

minimizef0(x) =||Ax−b||2=∑i=1 k(aiTx–bi)2（ 1.2 ）

其中， A∋Rk×n, k≥n為觀測樣本集合， 向量x為待優化參數。

最小二乘問題是回歸分析的根本， 最小二乘問題很容易辨認， 當目標函數為二次函數時， 即可認為該優化問題為最小二乘問題。 我們學過的解決該問題的最簡單的方法是最小二乘法， 我們可以將式(1.2)簡化為求解線性等式， (ATA)x=ATb因此， 我們可以獲得求解該問題的解析式x=(ATA)-1ATb。 該方法的時間複雜度為n2k， 當樣本數量以及特徵維度較低時（百維、千維）， 一般電腦會在幾秒內求的最優解， 當使用更好的計算資源時， 對於同樣的樣本量計算時間會呈指數衰減（摩爾定律）。 但是，對於需要滿足即時計算要求時，如果樣本特徵維度高於百萬級別，採用最小二乘法求解就會變的不可行。所以，我們一般會採用梯度下降等反覆運算優化方法求解上述目標函數的可行解，當然為了防止過擬合，可選擇懲罰（regularization）或者偏最小二乘（weighted least－squares）解決該問題。

2. 線性規劃

線性規劃是優化問題的另一個重要分支，其一般形式為：

miniminze cTx subject to aiTx≤bi,i=1,…,m(1.3)

對於線性規劃問題，不存在類似最小二乘問題的一步求解方法，即最小二乘法，但是可用於解決線性規劃問題的方法很多，如simplex方法，內插點法。雖然無法直接一步求解，但是我們可以通過控制反覆運算次數或設置停止反覆運算條件來減少運算的時間複雜度，例如，內插點法的時間複雜度為n2m，其中m≥n。另外，採用反覆運算法求解優化問題不一定能像最小二乘法一樣求得全域最優解，但目前的反覆運算演算法大多場合下可以達到最小二乘法一樣的準確度，而且，可滿足即時計算的需求。

同時，很多優化問題都可以轉換成線性規劃問題，如Chebyshev approximation problem：

minimize maxi=1,…,k∣aiTx–bi∣(1.4)

其中，x為待優化參數。Chebyshev優化問題與最小二乘問題類似，但最小二乘問題可微（矩陣半正定），而Chebyshev目標函數不可微，所以無法採用最小二乘法求解。我們需要將目標函數進行轉化，即可轉化成線性規劃：

minimizet subject to aiTx–t≤bi,–aiTx–t≤−bi, wherei=1 ,…,k(1.5)

這樣，我們就可採用simplex等方法求解該對偶線性規劃問題。

3.凸優化

凸函數的定義在上面已經介紹過了，即：

minimize f0(x) subject to fi(x)≤bi,i=1 ,…,m(1.6)

其中，函數f0,…,fm:Rn→R為凸函數。

凸函式定義為：

fi(tx(1−t)y)≤tfi(x)(1−t)fi(y),其中t≥0 （ 1.7 ）

也就是說，凸函數其函數圖像上方的點集是凸集，函數圖像上的任意兩點確定的弦在其圖像上方，這裡需要點明的是國內某些教材上關於凸函數和凹函數的定義與這裡寫的正好相反，這裡的凸函數是直觀視覺上的凹函數，即碗形函數。凸函數的定義在定義域C上的凸函數可表現為

凸函數的判定方法一般是求解其二階導數（如果存在），如果其二階導數在區間上非負，則該函數為凸函數。當且僅當，二階導數在區間上恒大於0，則函數稱為嚴格凸函數。凸函數具有如下性質：

(1) 凸函數的一階導數在區間內單調不減；

(2) 凸函數具有仿射不變性，即f(x)是凸函數，則g(y)=f(Axb)也是凸函數；

(3) 凸函數的任何 極小值都是最小值，嚴格凸函數最多有一個最小值；

(4) 凸函數在區間內（凸集內部）是正定的。最小二乘問題和線性規劃問題都屬於凸優化問題。

因為凸函數具有局部最優解就是全域最優解的優良性質，我們可以在求解過程不用過多考慮局部最優解和全域最優解的問題，因此，現有優化問題研究更多放在將一般形式的目標函數轉化為凸函數後求解。而對於凸優化問題，我們可以採用熟知的內插法、梯度下降法、牛頓拉斐遜演算法以及BFGS演算法等。這些演算法以及如何將優化目標函數轉換為凸函數是本系列博客的主要闡述的問題。

但是，對於需要滿足即時計算要求時，如果樣本特徵維度高於百萬級別，採用最小二乘法求解就會變的不可行。所以，我們一般會採用梯度下降等反覆運算優化方法求解上述目標函數的可行解，當然為了防止過擬合，可選擇懲罰（regularization）或者偏最小二乘（weighted least－squares）解決該問題。

2. 線性規劃

線性規劃是優化問題的另一個重要分支，其一般形式為：

miniminze cTx subject to aiTx≤bi,i=1,…,m(1.3)

對於線性規劃問題，不存在類似最小二乘問題的一步求解方法，即最小二乘法，但是可用於解決線性規劃問題的方法很多，如simplex方法，內插點法。雖然無法直接一步求解，但是我們可以通過控制反覆運算次數或設置停止反覆運算條件來減少運算的時間複雜度，例如，內插點法的時間複雜度為n2m，其中m≥n。另外，採用反覆運算法求解優化問題不一定能像最小二乘法一樣求得全域最優解，但目前的反覆運算演算法大多場合下可以達到最小二乘法一樣的準確度，而且，可滿足即時計算的需求。

同時，很多優化問題都可以轉換成線性規劃問題，如Chebyshev approximation problem：

minimize maxi=1,…,k∣aiTx–bi∣(1.4)

其中，x為待優化參數。Chebyshev優化問題與最小二乘問題類似，但最小二乘問題可微（矩陣半正定），而Chebyshev目標函數不可微，所以無法採用最小二乘法求解。我們需要將目標函數進行轉化，即可轉化成線性規劃：

minimizet subject to aiTx–t≤bi,–aiTx–t≤−bi, wherei=1 ,…,k(1.5)

這樣，我們就可採用simplex等方法求解該對偶線性規劃問題。

3.凸優化

凸函數的定義在上面已經介紹過了，即：

minimize f0(x) subject to fi(x)≤bi,i=1 ,…,m(1.6)

其中，函數f0,…,fm:Rn→R為凸函數。

凸函式定義為：

fi(tx(1−t)y)≤tfi(x)(1−t)fi(y),其中t≥0 （ 1.7 ）

也就是說，凸函數其函數圖像上方的點集是凸集，函數圖像上的任意兩點確定的弦在其圖像上方，這裡需要點明的是國內某些教材上關於凸函數和凹函數的定義與這裡寫的正好相反，這裡的凸函數是直觀視覺上的凹函數，即碗形函數。凸函數的定義在定義域C上的凸函數可表現為

凸函數的判定方法一般是求解其二階導數（如果存在），如果其二階導數在區間上非負，則該函數為凸函數。當且僅當，二階導數在區間上恒大於0，則函數稱為嚴格凸函數。凸函數具有如下性質：

(1) 凸函數的一階導數在區間內單調不減；

(2) 凸函數具有仿射不變性，即f(x)是凸函數，則g(y)=f(Axb)也是凸函數；

(3) 凸函數的任何 極小值都是最小值，嚴格凸函數最多有一個最小值；

(4) 凸函數在區間內（凸集內部）是正定的。最小二乘問題和線性規劃問題都屬於凸優化問題。

因為凸函數具有局部最優解就是全域最優解的優良性質，我們可以在求解過程不用過多考慮局部最優解和全域最優解的問題，因此，現有優化問題研究更多放在將一般形式的目標函數轉化為凸函數後求解。而對於凸優化問題，我們可以採用熟知的內插法、梯度下降法、牛頓拉斐遜演算法以及BFGS演算法等。這些演算法以及如何將優化目標函數轉換為凸函數是本系列博客的主要闡述的問題。