機(jī)器學(xué)習(xí)與優(yōu)化基礎(chǔ)（Machine Learning and Optimization）

機(jī)器學(xué)習(xí)與優(yōu)化

引用大佬Pedro Domingos的說法：機(jī)器學(xué)習(xí)其實(shí)就是由模型的表示，優(yōu)化和模型評估三部分組成。將一個(gè)實(shí)際問題轉(zhuǎn)化為待求解的模型，利用優(yōu)化算法求解模型，利用驗(yàn)證或測試數(shù)據(jù)評估模型，循環(huán)這三個(gè)步驟直到得到滿意的模型。

因此，優(yōu)化算法在機(jī)器學(xué)習(xí)中起著一個(gè)承上啟下的作用！

一般機(jī)器學(xué)習(xí)中涉及的優(yōu)化命題可以表示為：

比如:

• 最小二乘回歸

• 嶺回歸

• LASSO:

• 支持向量機(jī)

• 正則化邏輯斯蒂回歸

還有等等等等機(jī)器學(xué)習(xí)算法也是類似的。

優(yōu)化算法基礎(chǔ)

優(yōu)化算法的階次

所謂優(yōu)化算法的階次其實(shí)指的是優(yōu)化過程利用的是

1. 目標(biāo)函數(shù)本身 (零階)
2. 梯度信息 (一階)
3. hessian信息 (二階)

中的哪些信息。

如果函數(shù)形式未知、梯度難以求或不存在的時(shí)候常常采用零階優(yōu)化算法；在機(jī)器學(xué)習(xí)領(lǐng)域中一般一階算法使用較多，二階算法可能收斂更快但計(jì)算花費(fèi)也更大。

優(yōu)化算法的常見組成

• 梯度下降

在理解梯度下降法之前, 再給大家復(fù)習(xí)一下幾個(gè)非常容易混淆的概念: 導(dǎo)數(shù)是一元函數(shù)的變化率 (斜率)。如果是多元函數(shù)呢? 則為偏導(dǎo)數(shù)。偏導(dǎo)數(shù)是多元函數(shù) “退化"成一元函數(shù)時(shí)的導(dǎo)數(shù), 這里 "退化"的意思是固定其他變量的值, 只保留一個(gè)變量, 依次保留每個(gè)變量, 則 元函數(shù)有 個(gè)偏導(dǎo)數(shù)。如果是方向不是沿著坐標(biāo)軸方向, 而是任意方向呢? 則為方向?qū)?shù)。換句話說, 偏導(dǎo)數(shù)為坐標(biāo)軸方向上的方向?qū)?shù), 其他方向的方向?qū)?shù)為偏導(dǎo)數(shù)的合成。而偏導(dǎo)數(shù)構(gòu)成的向量就稱為梯度。

梯度方向是函數(shù)增長速度最快的方向, 那么梯度的反方向就是函數(shù)減小最快的方向。因此, 如果想要計(jì)算函數(shù)的最小值, 就可以用梯度下降的思想來做。假設(shè)目標(biāo)函數(shù)的梯度為 , 當(dāng)前點(diǎn)的位置為 , 則下一個(gè)點(diǎn)的選擇與當(dāng)前點(diǎn)的位置和它的梯度相關(guān)

其中 為學(xué)習(xí)率, 可以隨著每次迭代改變。（就拓展出了許多相關(guān)的算法AdaGrad、RMSProp、Adam等)

• 近端映射（proximal operator）

當(dāng)目標(biāo)函數(shù)存在不可微部分, 常會采用近端梯度下降法。比如 , 其中 是凸的且可微, 是凸的但是不可微或者局部不可微。由于 不可微, 我們不能直接用梯度下降法來尋優(yōu)（PS：次梯度算法可以, 就是慢了點(diǎn)）, 因此近端算法考慮的是將 進(jìn)行近端映射。

函數(shù) 的近端映射可以定義為

拿個(gè)機(jī)器學(xué)習(xí)中常見的 范數(shù)給大家舉個(gè)例子, （一范數(shù)就是各元素 絕對值之和），對應(yīng)的近端映射表示為

這個(gè)優(yōu)化問題是可分解的! 也就是對每一個(gè)維度求最小值

對 的正負(fù)進(jìn)行分類討論, 然后利用一階最優(yōu)條件（求導(dǎo)令導(dǎo)數(shù)為零）可得

這通常也被稱作軟閾值（soft thresholding）。

因此近端梯度算法也就是

• 對偶（dual）

在求解一個(gè)優(yōu)化命題時(shí)，如果其對偶形式便于求解，常常可以通過求解對偶問題來避免直接對原問題進(jìn)行求解。比如機(jī)器學(xué)習(xí)中典型的SVM就涉及到對偶理論，以及拉格朗日乘子法、KKT條件等概念。首先簡單通俗地說說這幾個(gè)概念是干嘛的

1. 對偶理論：對偶也就是孿生雙胞胎，一個(gè)優(yōu)化命題也就有其對應(yīng)的兄弟優(yōu)化命題。
2. 拉格朗日函數(shù)：將原本優(yōu)化命題的目標(biāo)函數(shù)和約束整合成一個(gè)函數(shù)。
3. KKT條件：函數(shù)的最優(yōu)值滿足的性質(zhì)。

如果原問題是凸問題，則KKT條件為充要條件，也就是說滿足KKT條件的點(diǎn)也就是原問題和對偶問題的最優(yōu)解，那就能夠在滿足KKT條件下用求解對偶問題來替代求解原問題。（具體推導(dǎo)和細(xì)節(jié)就不展開了，下次可以單獨(dú)寫一篇）

• 隨機(jī)化

當(dāng)遇到大規(guī)模問題時(shí), 如果使用梯度下降法(批量梯度下降法), 那么每次迭代過程中都要對 個(gè)樣本進(jìn)行求梯度, 所以開銷非常大, 隨機(jī)梯度下降的思想就是隨機(jī)采樣一個(gè)樣本來更新參數(shù), 那么計(jì)算開銷就從 下降到 。

無約束問題的典型算法

• 梯度下降法

上面提到過了就不重復(fù)了。

• 共軛梯度法

梯度下降法可能存在的一個(gè)問題是為了收斂到解附近,同樣的迭代方向可能走了不止一次（導(dǎo)致收斂慢）。共軛梯度就可以理解為選擇一系列線性無關(guān)的方向去求得最優(yōu)解。因此共軛梯度法把共軛性與最速下降方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜素，求出目標(biāo)函數(shù)的極小點(diǎn)。

方向的構(gòu)造方法為：

其中當(dāng)初始化的時(shí)候相當(dāng)于梯度下降法（因?yàn)槌跏紩r(shí)刻只有梯度方向）。這里末知項(xiàng)是這個(gè)系數(shù) , 它的計(jì)算公式為

有了搜索方向，那么每次次迭代為

• 擬牛頓法

在說擬牛頓法前先簡單介紹一下牛頓法，牛頓法最初是為了求解方程的根而推導(dǎo)出來的公式。它的主要思想是 基于當(dāng)前位置的切線來確定下一次的位置。比如要求 的解，可以迭代求解

如果對應(yīng)到求解優(yōu)化命題, 我們要使得 取最小值, 也就是函數(shù)的一階導(dǎo)數(shù)為零 , 帶入牛頓法求根公式就是

由于牛頓法每次都要計(jì)算二階導(dǎo)數(shù)（Hessian矩陣）的逆，計(jì)算量太大了，因此有了擬牛頓法。簡單的說，擬牛頓法其實(shí)就是用近似Hessian矩陣來進(jìn)行迭代。

比如說令 ，再利用擬牛頓條件（對一階導(dǎo)數(shù)進(jìn)行泰勒展開） 對近似矩陣進(jìn)行修正就可以避免Hessian矩陣的求逆了。因此每次迭代為

在實(shí)際應(yīng)用當(dāng)中，使用最為廣泛的擬牛頓法應(yīng)該是L-BFGS算法了。

• Proximal gradient（近端梯度）

上面提到過了就不重復(fù)了。

約束問題的經(jīng)典算法

• 投影梯度下降法（Projected gradient descent）

看名字可以知道這個(gè)方法的思想其實(shí)就是梯度下降再加上投影操作來滿足約束?？梢岳斫鉃槭且粋€(gè)兩階段的算法，

第一階段先進(jìn)行梯度下降

第二階段進(jìn)行投影

也就是說在約束范圍內(nèi)找一個(gè)與無約束條件下最近的解，或者說將無約束解投影到約束范圍內(nèi)。

• 罰函數(shù)法

罰函數(shù)法的思想也可以從它的名字進(jìn)行解釋，其實(shí)就是將違反約束的代價(jià)放入目標(biāo)函數(shù)中，從而把約束問題轉(zhuǎn)化為無約束問題。轉(zhuǎn)化后的無約束問題為

其中 是連續(xù)函數(shù), 且對于任意 罰函數(shù)非負(fù), 當(dāng) 滿足約束, 即 時(shí)

• Frank-Wolfe算法

這個(gè)算法的思想和它的名字就不好聯(lián)系上了，基本思想是將目標(biāo)函數(shù)作線性近似，

通過求解線性規(guī)劃

求得可行下降方向

因此每次迭代的公式為

• 交替方向法ADMM

ADMM的思想是以先分解再結(jié)合的形式求解問題，即先把原問題分解成若干個(gè)相對原問題較簡單的子問題，再把子問題的解結(jié)合起來得到原問題的全局解。主要針對的問題是可分塊優(yōu)化命題，如

寫出其增廣拉格朗日函數(shù)

用交替方法（只優(yōu)化一個(gè)變量，固定其他變量）的方式進(jìn)行優(yōu)化，即

• 坐標(biāo)下降法

坐標(biāo)上升法的思想和ADMM有點(diǎn)點(diǎn)類似的地方，就是在每次優(yōu)化時(shí)只優(yōu)化一個(gè)或者一部分變量，然后固定其他變量，即

這就有點(diǎn)像一個(gè)高維坐標(biāo)系，你一個(gè)維度一個(gè)維度按順序優(yōu)化。

當(dāng)優(yōu)化問題遇到大數(shù)據(jù)

當(dāng)數(shù)據(jù)量較大的時(shí)候，簡單的處理辦法就是利用隨機(jī)化的思想，比如梯度下降法就可以改為隨機(jī)梯度下降，坐標(biāo)上升法就可以改為隨機(jī)坐標(biāo)上升。

加速優(yōu)化與展望

所謂的加速優(yōu)化研究的是在不作出更強(qiáng)假設(shè)的情況下改進(jìn)算法提高收斂速度。常見的比如有重球法（Heavy-Ball method）、Nesterov的加速梯度下降法、加速近端梯度法（APG）、隨機(jī)方差減小梯度法等等。這些算法可能有點(diǎn)超綱了，感興趣或者專門研究這類問題的可以參考林宙辰老師的新書（參考書籍4）。

對于大規(guī)模優(yōu)化的一些研究可以從以下幾個(gè)角度展開：隨機(jī)優(yōu)化、分布式優(yōu)化、異步優(yōu)化、基于學(xué)習(xí)的優(yōu)化等等。

參考書籍推薦

[1] Nesterov Y. Introductory lectures on convex optimization: A basic course[M]. Springer Science & Business Media, 2013.

[2] Optimization for machine learning[M]. Mit Press, 2012.

[3] Nocedal J, Wright S. Numerical optimization[M]. Springer Science & Business Media, 2006.

[4] Zhouchen Lin. Accelerated Optimization for Machine Learning[M]. Springer, 2020.

博客內(nèi)容主要根據(jù)林宙辰老師的講座內(nèi)容進(jìn)行梳理，在此表示感謝。

    

     下載1：OpenCV-Contrib擴(kuò)展模塊中文版教程
     

    
    

     在「小白學(xué)視覺」公眾號后臺回復(fù)：擴(kuò)展模塊中文教程，即可下載全網(wǎng)第一份OpenCV擴(kuò)展模塊教程中文版，涵蓋擴(kuò)展模塊安裝、SFM算法、立體視覺、目標(biāo)跟蹤、生物視覺、超分辨率處理等二十多章內(nèi)容。
    
    

     

    
    

     下載2：Python視覺實(shí)戰(zhàn)項(xiàng)目52講
    
    

     在「小白學(xué)視覺」公眾號后臺回復(fù)：Python視覺實(shí)戰(zhàn)項(xiàng)目，即可下載包括圖像分割、口罩檢測、車道線檢測、車輛計(jì)數(shù)、添加眼線、車牌識別、字符識別、情緒檢測、文本內(nèi)容提取、面部識別等31個(gè)視覺實(shí)戰(zhàn)項(xiàng)目，助力快速學(xué)校計(jì)算機(jī)視覺。
    
    

     

    
    

     下載3：OpenCV實(shí)戰(zhàn)項(xiàng)目20講
    
    

     在「小白學(xué)視覺」公眾號后臺回復(fù)：OpenCV實(shí)戰(zhàn)項(xiàng)目20講，即可下載含有20個(gè)基于OpenCV實(shí)現(xiàn)20個(gè)實(shí)戰(zhàn)項(xiàng)目，實(shí)現(xiàn)OpenCV學(xué)習(xí)進(jìn)階。
    
    

     

    
交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計(jì)算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細(xì)分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進(jìn)入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~