最優(yōu)化

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

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

講了這么多，主要是為了說(shuō)明機(jī)器學(xué)習(xí)與最優(yōu)化問(wèn)題的聯(lián)系，也為大家更好的理解后續(xù)機(jī)器學(xué)習(xí)算法提供基礎(chǔ)。接下來(lái)，我們會(huì)把講解重點(diǎn)放在放在最優(yōu)化及凸優(yōu)化理論上。

1. 最優(yōu)化問(wèn)題

數(shù)值優(yōu)化問(wèn)題或者簡(jiǎn)稱(chēng)為優(yōu)化問(wèn)題主要是求問(wèn)題的解，優(yōu)化問(wèn)題具有以下一般形式：
minimize f₀(x) subject to f_i(x)≤b_i,i=1 ,…,m（1.1）
其中，函數(shù)f₀為目標(biāo)函數(shù)，函數(shù) f_i ：Rⁿ→R 為不等式，或約束函數(shù)。

x=(x₁,…,x_n)為向量，是目標(biāo)函數(shù)的待優(yōu)化參數(shù)（optimization variables），也稱(chēng)為優(yōu)化問(wèn)題的可行解，常量b₁ ,…,b_m稱(chēng)為邊界或約束。當(dāng)存在向量x^*，使得滿(mǎn)足上式約束的任意向量z，存在f₀(x^*)^a,最小二乘問(wèn)題

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

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

2. 線性規(guī)劃

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

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

3.凸優(yōu)化

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

凸函數(shù)定義為：

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

也就是說(shuō)，凸函數(shù)其函數(shù)圖像上方的點(diǎn)集是凸集，函數(shù)圖像上的任意兩點(diǎn)確定的弦在其圖像上方，這里需要點(diǎn)明的是國(guó)內(nèi)某些教材上關(guān)于凸函數(shù)和凹函數(shù)的定義與這里寫(xiě)的正好相反，這里的凸函數(shù)是直觀視覺(jué)上的凹函數(shù)，即碗形函數(shù)。凸函數(shù)的定義在定義域C上的凸函數(shù)可表現(xiàn)為

凸函數(shù)的判定方法一般是求解其二階導(dǎo)數(shù)（如果存在），如果其二階導(dǎo)數(shù)在區(qū)間上非負(fù)，則該函數(shù)為凸函數(shù)。當(dāng)且僅當(dāng)，二階導(dǎo)數(shù)在區(qū)間上恒大于0，則函數(shù)稱(chēng)為嚴(yán)格凸函數(shù)。凸函數(shù)具有如下性質(zhì)：

(1) 凸函數(shù)的一階導(dǎo)數(shù)在區(qū)間內(nèi)單調(diào)不減；

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

(3) 凸函數(shù)的任何 極小值都是最小值，嚴(yán)格凸函數(shù)最多有一個(gè)最小值；

(4) 凸函數(shù)在區(qū)間內(nèi)（凸集內(nèi)部）是正定的。最小二乘問(wèn)題和線性規(guī)劃問(wèn)題都屬于凸優(yōu)化問(wèn)題。

因?yàn)橥购瘮?shù)具有局部最優(yōu)解就是全局最優(yōu)解的優(yōu)良性質(zhì)，我們可以在求解過(guò)程不用過(guò)多考慮局部最優(yōu)解和全局最優(yōu)解的問(wèn)題，因此，現(xiàn)有優(yōu)化問(wèn)題研究更多放在將一般形式的目標(biāo)函數(shù)轉(zhuǎn)化為凸函數(shù)后求解。而對(duì)于凸優(yōu)化問(wèn)題，我們可以采用熟知的內(nèi)插法、梯度下降法、牛頓拉斐遜算法以及BFGS算法等。這些算法以及如何將優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)換為凸函數(shù)是本系列博客的主要闡述的問(wèn)題。

更多文章：