最優化

隨著大數據的到來，并行計算的流行，實際上機器學習領域的很多研究者會把重點放在最優化方法的研究上，如large scale computation。那么為什么要研究最優化呢？我們先從機器學習研究的目的說起。機器學習理論主要是設計和分析一些讓計算機可以自動“學習”的算法，這些算法可以從數據中自動分析獲得規律，并利用規律對未知數據進行預測，并可用于發現數據之間隱藏的關系，解釋某些現象的發生。至于為什么要讓機器去做這些事情，原因很簡單，數據量和維度過于龐大，無法通過人腦簡單的處理或分析這些數據。比如，我們無法通過百萬級的DNA序列分析各序列和疾病發生的關系，也無法在一定有限的時間內標定出1萬張圖像上人臉的位置。所以 研究者傾向于建立一些機器學習模型，通過輸入一個樣本（一個人的DNA序列或者是一副圖片），輸出樣本的標簽（是否患病、頭像的位置）。這些學習模型里有大量可以調整的參數，它們通過調整參數組合，擬合高維空間訓練樣本數據的分布，識別出數據和標簽之間復雜的關系。目前已有的神經網絡、支持向量機、AdaBoost、卷積神經網絡等算法，它們的共同特點是通過調整參數讓模型的目標函數盡可能大或者小（如logistic回歸是使得分類錯誤率盡量小）。為了達到該目的，不同的機器學習算法首先會設定不同的目標函數，然后給參數賦上隨機初值，最后用各種下降法更快更好地尋找能讓分類錯誤率更小的參數組合。

所以，從廣義上講，機器學習算法的本質上是優化問題求解，例如，梯度下降、牛頓法、共軛梯度法都是常見的機器學習算法優化方法。那么有人肯定會有疑問，這不還是調參數、選擇參數么？這個參數優化與之前的調參的概念是不同的，之前說的調參是針對算法中的自由參數（即通過經驗指定的參數，用過weka或者R的人應該知道，如SVM中的gamma或者logistic回歸中的懲罰因子lamda），這些參數主要是控制學習模型的泛化能力，防止過擬合。而這里通過優化算法迭代出的參數則是目標函數中待求解的參數，例如，神經網絡中各隱含層節點的權值、logistic回歸中各自變量的系數。對于不同目標函數和不同優化算法，產生的問題也各不相同，比如某些目標函數不是凸函數也不是無約束的優化問題，無法直接利用梯度下降算法求解，又例如梯度下降法往往只能保證找到目標函數的局部最小值，找不到全局最小值，那么該怎么解決這些問題呢？答案是不一味的強行采用梯度下降，而是引入其他變量（拉格朗日乘子）將有約束問題轉化為無約束問題，也可以適當爬爬山，說不定能跳出小水溝（局部極小值）找到真正的深井（全局極小值），這種算法叫模擬退火。也可以增大搜索范圍，讓一群螞蟻（蟻群算法）或者鳥兒（粒子群算法）一齊搜索，或者讓參數巧妙地隨機改變（遺傳算法）。所以，如何更快的找到目標函數的全局最小值或者全局最大值，如何避免陷入局部最優解是優化算法研究的重點。

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

1. 最優化問題

數值優化問題或者簡稱為優化問題主要是求問題的解，優化問題具有以下一般形式：
minimize f₀(x) subject to f_i(x)≤b_i,i=1 ,…,m（1.1）
其中，函數f₀為目標函數，函數 f_i ：Rⁿ→R 為不等式，或約束函數。

x=(x₁,…,x_n)為向量，是目標函數的待優化參數（optimization variables），也稱為優化問題的可行解，常量b₁ ,…,b_m稱為邊界或約束。當存在向量x^*，使得滿足上式約束的任意向量z，存在f₀(x^*)^a,最小二乘問題

最小二乘問題（Least－Square problems）是無約束優化問題，同時，目標函數是具有a_i^Tx-b_i形式的線性表達式的平方和，其一般形式可記為：
minimizef₀(x) =||Ax?b||² =∑_{i=1 k}(a_iTx–bⁱ)² （ 1.2 ）
其中，A?R^k×n , k≥n為觀測樣本集合，向量x為待優化參數。

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

2. 線性規劃

線性規劃是優化問題的另一個重要分支，其一般形式為：
miniminze c_Tx  subject to a_i^Tx≤b_i,i=1,…,m(1.3)
對于線性規劃問題，不存在類似最小二乘問題的一步求解方法，即最小二乘法，但是可用于解決線性規劃問題的方法很多，如simplex方法，內插點法。雖然無法直接一步求解，但是我們可以通過控制迭代次數或設置停止迭代條件來減少運算的時間復雜度，例如，內插點法的時間復雜度為n²m，其中m≥n。另外，采用迭代法求解優化問題不一定能像最小二乘法一樣求得全局最優解，但目前的迭代算法大多場合下可以達到最小二乘法一樣的準確度，而且，可滿足實時計算的需求。

同時，很多優化問題都可以轉換成線性規劃問題，如Chebyshev approximation problem：
minimize max_i=1,…,k∣a_i^Tx–b_i∣(1.4)
其中，x為待優化參數。Chebyshev優化問題與最小二乘問題類似，但最小二乘問題可微（矩陣半正定），而Chebyshev目標函數不可微，所以無法采用最小二乘法求解。我們需要將目標函數進行轉化，即可轉化成線性規劃：
minimizet  subject to a_i^Tx–t≤b_i,–a_i^Tx–t≤?b_i, wherei=1 ,…,k(1.5)
這樣，我們就可采用simplex等方法求解該對偶線性規劃問題。

3.凸優化

凸函數的定義在上面已經介紹過了，即：
minimize f₀(x)  subject to  f_i(x)≤b_i,i=1 ,…,m(1.6)
其中，函數f₀,…,f_m:Rⁿ→R為凸函數。

凸函數定義為：

f_i(tx(1?t)y)≤tf_i(x)(1?t)f_i(y),其中t≥0 （ 1.7 ）

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

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

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

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

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

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

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

更多文章：