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

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

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

比如：

• 最小二乘回歸

• 嶺回歸

• LASSO:

• 支持向量機(jī)

• 正則化邏輯斯蒂回歸

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

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

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

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

梯度下降

在理解梯度下降法之前，再給大家復(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ù)。換句話說(shuō)，偏導(dǎo)數(shù)為坐標(biāo)軸方向上的方向?qū)?shù)，其他方向的方向?qū)?shù)為偏導(dǎo)數(shù)的合成。而偏導(dǎo)數(shù)構(gòu)成的向量就稱(chēng)為梯度。

梯度方向是函數(shù)增長(zhǎng)速度最快的方向，那么梯度的反方向就是函數(shù)減小最快的方向。因此，如果想要計(jì)算函數(shù)的最小值，就可以用梯度下降的思想來(lái)做。假設(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ù)存在不可微部分，常會(huì)采用近端梯度下降法。比如   ，其中  是凸的且可微，   是凸的但是不可微或者局部不可微。由于   不可微，我們不能直接用梯度下降法來(lái)尋優(yōu)（PS：次梯度算法可以，就是慢了點(diǎn)），因此近端算法考慮的是將   進(jìn)行近端映射。

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

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

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

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

因此近端梯度算法也就是

對(duì)偶（dual）

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

隨機(jī)化

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

無(wú)約束問(wèn)題的典型算法

梯度下降法

共軛梯度法

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

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

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

擬牛頓法

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

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

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

Proximal gradient（近端梯度）

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

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

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

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

罰函數(shù)法

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

Frank-Wolfe算法

交替方向法ADMM

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

坐標(biāo)下降法

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

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

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

參考書(shū)籍推薦

[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.

 End