前幾天聽了林周臣老師的報(bào)告，關(guān)于機(jī)器學(xué)習(xí)中的優(yōu)化方法[1]，并做了筆記。推薦機(jī)器學(xué)習(xí)的人去聽。林老師主頁：

機(jī)器學(xué)習(xí)離不開優(yōu)化方法。Pedro 總結(jié)了機(jī)器學(xué)習(xí)與優(yōu)化方法的關(guān)系：

“=++”

最后三項(xiàng)對應(yīng)三個(gè)步驟：構(gòu)建模型、求解模型和驗(yàn)證模型。

1.機(jī)器學(xué)習(xí)中的優(yōu)化問題

首先介紹一下機(jī)器學(xué)習(xí)中常見的優(yōu)化問題

1.分類和回歸問題

\min_{x\in \{R}^n}\frac{1}{n}\sum_{i=1}^nf_i(x)+\ R(x) \\ \tag{1}

許多分類和回歸問題可以寫成問題（1）的一個(gè)特例，例如SVM、正則回歸、多層感知器、線性回歸、嶺回歸、Lasso問題等。

2.

通常數(shù)據(jù)的分類面可能很復(fù)雜，我們可以組合多個(gè)簡單的線性分類器。

\min_{\beta,\gamma}\sum_{i=1}^nloss\left(y_i,\sum_{j=1}^M\(x_i;\)\right) \\

3. 生成對抗網(wǎng)絡(luò)

\min_G\max_D V(D,G) = \{E}_{x\sim p_{數(shù)據(jù)}(x)}[\log D(x)] +\{E}_{z\sim p_{z} (z)}[\log (1-D(G(z))]

4.

自動(dòng)超參數(shù)選擇，這是一個(gè)兩層優(yōu)化問題。

\begin{split} \min_{\}& l_{}(w,\) \\ st & \ \in \{C}_1 \\ & w\in \arg\min_{w\in \{C}_2 } l_{train}(w,\) \end{split} \\

二、算法的順序

根據(jù)需要的信息，算法大致分為零階、一階、二階三種

在機(jī)器學(xué)習(xí)中，一階是最廣泛使用的。當(dāng)然也有零階和二階之分，適合那些特殊結(jié)構(gòu)的問題。

3.機(jī)器學(xué)習(xí)中的優(yōu)化算法

一、基礎(chǔ)模塊：

通常的優(yōu)化算法主要有以下幾個(gè)模塊。以不同的方式組合這些模塊會(huì)導(dǎo)致不同的優(yōu)化方法。

以上四個(gè)模塊形成了許多現(xiàn)有的不同拼接下的優(yōu)化算法。

2. 機(jī)器學(xué)習(xí)中的無約束優(yōu)化算法

考慮無約束問題：

\min_x f(x) \\

假設(shè)函數(shù) f 是平滑的（如果不是，我們可以使用次梯度、平滑等）

0} f(x_k + \alpha d_k) \\ x_{k+1} = & x_k + \ d_k\\ d_{k+1} = & -\nabla f(x_k) + \ d_k \\ \end{split } \\">\begin{split} \ = & \arg\min_{\alpha >0} f(x_k + \alpha d_k) \\ x_{k+1} = & x_k + \ d_k\\ d_{k +1} =& -\nabla f(x_k) + \ d_k \\ \end{split} \\

當(dāng)目標(biāo)函數(shù)是二次的時(shí)，選擇的方向 d_k 是共軛方向。

0} f(x_k + \alpha d_k) \\ x_{k+1} = & x_k + \ d_k\\ \end{split} \\">\begin{split} d_{k+1} = & -H_k \nabla f(x_k) \\ \ = & \arg\min_{\alpha >0} f(x_k + \alpha d_k) \\ x_{k+1} = & x_k + \ d_k\\ \end{split} \\

H_k 是 x_k 處矩陣逆的近似值，需要滿足 H_{k+1}\nabla g_k = \nabla x_k 。有兩種主要類型的近似：秩 1 和秩 2 近似。

上面提到的逆牛頓需要存儲(chǔ)一個(gè)大矩陣H_k，考慮到它是秩1或秩2的近似直線搜索方法,無約束優(yōu)化方法,約束優(yōu)化方法，所以我們可以存儲(chǔ)一些向量來代替。

考慮可分離問題：

\min_x f(x) + g(x) \\ \tag{2} 其中 f 是平滑的，g 是非平滑的。相鄰梯度算法對平滑部分進(jìn)行二次逼近，每一步解決如下問題：

+\frac{1}{2\alpha^k}\|xx^k\|^2 + g(x) \\ &= \mbox{prox}_{\alpha^kg}(x^k - \alpha ^k \nabla f(x^k)) \end{split} \\">\begin{split} x^{k+1} &= \arg\min_x f(x^k)+ +\frac{1 }{2\alpha^k}\|xx^k\|^2 + g(x) \\ &= \mbox{prox}_{\alpha^kg}(x^k - \alpha^k \nabla f (x^k)) \end{拆分} \\

該算法需要假設(shè) g 易于計(jì)算。

3.機(jī)器學(xué)習(xí)中的約束優(yōu)化方法

考慮一般問題：

\min_{x\in \{X}}f(x) \\ 其中 \{X} 是一個(gè)約束集。

x_{k+1} = \pi_{\{X}}(x_k - \ \nabla f(x_k)) \\

首先采取漸變步驟，然后再投影。

\min_x f(x)+ \ P(x) \\

約束集通過懲罰參數(shù)放置在目標(biāo)函數(shù)上，其中 P 必須滿足一些條件：連續(xù)非負(fù)，并且 P(x)=0 iff x\in \{X} 。此方法依賴于懲罰參數(shù)。

\\ x^{k+1} &= x^k + \eta_k (s^k - x^k) \\ \end{split} \\">\begin{split} s^{k} &= \ arg\min_{x\in\{X}} \\ x^{k+1} &= x^k + \eta_k (s^k - x^k) \\ \end{split} \\

其中 \{X} 必須是緊集（相當(dāng)于歐幾里得空間中的有界閉集）。方向 s^k 的解等價(jià)于函數(shù) f 的泰勒展開。該算法適用于稀疏的低秩問題。此時(shí)直線搜索方法,無約束優(yōu)化方法,約束優(yōu)化方法，\{X} 可能是一個(gè)低秩范數(shù)球。這時(shí)候有一個(gè)非常高效的算法來求解s^k。

當(dāng)約束為線性且可分時(shí)，可以使用 ADMM，考慮以下問題：

\min_x f(x) + g(z) \\ \mbox{st} Ax + Bz = b \\

相應(yīng)的增廣拉格朗日函數(shù)為：

\{L}_{\alpha} (x,z;y) = f(x) +g(z)+ (y)^T(Ax+Bz-b) + \frac{\alpha}{2}\ |Ax+Bz-b\|^2 \\

ADMM 算法交替更新新的廣義拉格朗日函數(shù)中的三個(gè)變量：

\left\{ \begin{split} x^{k+1} &= \arg\min_x\{L}_{\}(x,z^k;y^k) \\ z^{k+1} &= \arg\min_z \{L}_{\}(x^{k+1},z;y^{k})\\ y^{k+1} &= y^{k} + \ ( Ax^{k+1}+Bz^{k+1}-b) \end{split}\right.\\

如果仍然難以求出 x,z，我們可以將后面的二次項(xiàng)線性化，得到線性化的 ADMM。

如果問題中的變量可以分為多個(gè)部分，例如：

\min_{x\in \{X}} f(x_1,x_2,\cdots,x_n) \\

在這種情況下，可以采用塊坐標(biāo)下降法：本質(zhì)上是交替最小值的擴(kuò)展。

x_i^{k+1} = \arg\min_{x_i\in \{X}_i}f(x_{1}^{k+1},\cdots,x_{i-1}^{k+1} ,x,x_{i+1}^k,\cdots,x_n^k)\\

4. 大數(shù)據(jù)處理

考慮以下形式的問題：

\min_x \left\{f(x):=\sum_{i=1}^n f_i(x) \right\}\\

只要滿足 \{E}(v_k) = \nabla f(x)，就可以在 v_k 方向找到一個(gè)近似梯度。有很多變種，adam,,,ada...

四、加速算法

通常的加速策略是使用插值和外推。

1.好的

x_{k+1} = x_k - \eta \nabla f(x_k) + \beta (x_k - x_{k-1}) \\ 調(diào)用后一項(xiàng)。

\begin{split} y_k = & x_k + \(x_k - x_{k-1}) \\ x_{k+1} = &y_k - \eta \nabla f(y_k) \end{split}\\

加速度應(yīng)用于非光滑可分問題（2）：

\begin{split} y_k = & x_k + \(x_k - x_{k-1}) \\ x_{k+1} = & \mbox{prox}_{\eta g}(y_k - \eta \nabla f (y_k)) \end{拆分}\\

2.隨機(jī)

認(rèn)為鄰接：

\min_x \left\{f(x):=\frac{1}{n}\sum_{i=1}^n f_i(x) \right\}\\

我們可以使用梯度法： x^{k+1} = x^k - \alpha \nabla f(x^k) ，如果n太大，每一步的計(jì)算量太大，

然后我們使用最原始的隨機(jī)梯度法： x^{k+1} = x^k - \alpha \nabla f_{i_k}(x^k) ，即一次選擇一個(gè)去。

這兩種方法似乎都是極端的，因此介于兩者之間。考慮如何在減少計(jì)算量的同時(shí)保持計(jì)算量增長過快。這里有幾種從這個(gè)角度入手的方法。

這種方法的思想是每隔一段時(shí)間計(jì)算一次完整的梯度，并利用這個(gè)信息來修正每一步的隨機(jī)梯度方向。

該方法是加速度和 .

請注意，在第 3 步中，您可以使用任何可計(jì)算的方法來解決第 3 步中的問題

這比 SVRG 的方差小。

五、展望

大規(guī)模優(yōu)化的前景主要包括這幾點(diǎn)

最后，林老師推薦了機(jī)器學(xué)習(xí)的人應(yīng)該學(xué)習(xí)哪些優(yōu)化書籍，最后一本是林老師自己的。

我的專欄

參考

【1】/video/?t=3131