Hulu機器學習問題與解答系列 | 十六：經典優化演算法

」經典優化演算法「

[場景描述]

針對我們遇到的各類優化問題，研究者們提出了多種有各自適用場景的求解演算法，並逐漸發展出了有嚴格理論支撐的研究領域——凸優化[1]。在這眾多的演算法中，有幾種經典的優化演算法是值得被牢記的，了解它們的適用場景有助於我們在面對新的優化問題時有求解思路。

[問題描述]

有一道無約束優化問題擺在你面前

其中目標函數 L(·) 是光滑的。請問求解該問題的優化演算法有哪些？它們的適用場景是什麼？

先驗知識：微積分、線性代數、凸優化基本概念

[解答與分析]

經典的優化演算法可以分為兩大類：直接法和迭代法。

直接法，顧名思義，就是能夠直接給出優化問題最優解的方法。這個方法聽起來非常厲害的樣子，但它不是萬能的。直接法要求目標函數滿足兩個條件。第一個條件是，L(·)是凸函數。什麼是凸函數呢？它的嚴格定義可以參見文獻[1]的第3章：對任意x和y，任意0≤λ≤1，都成立

一個直觀的解釋是，任取函數曲面上的兩點連接成線段，該線段的任意一點都不會處於函數曲面的下方，示意圖如下

若 L(·) 是凸函數，則文獻[1]第140頁的一個結論是，θ*是優化問題最優解的充分必要條件是 L(·) 在θ*處的梯度為0，即

因此，為了能夠直接求解出θ*，第二個條件是，上式有閉式解。同時滿足這兩個條件的經典例子是嶺回歸（ridge regression），其中目標函數為

稍加推導就能得到最優解為（要試著自己推導喲）

直接法的這兩個要求限制了它的廣泛應用，因此在很多實際問題中，我們會採用迭代法。這類方法迭代地修正對最優解的估計，即假設當前的估計為θt，我們希望求解優化問題

從而得到更好的估計θt+1＝θt﹢δt。迭代法又可以分為兩類，一階法和二階法。

一階法對函數 L(θt﹢δ) 做一階泰勒展開，得到近似式

由於該近似式僅在δ較小時才比較準確，我們可以求解帶l2正則的近似優化問題

因此一階法的迭代更新公式是

一階法也稱為梯度下減法，梯度是目標函數的一階信息。

二階法對函數 L(θt﹢δ) 做二階泰勒展開，得到近似式

其中

是函數 L(·) 在θt處的Hessian矩陣。我們可以求解近似優化問題

從而得到二階法的迭代更新公式

二階法也稱為牛頓法，Hessian矩陣是目標函數的二階信息。二階法的收斂速度一般要遠快於一階法，但是在高維情況下Hessian矩陣求逆的計算複雜度更大，而且當目標函數非凸時，二階法有可能會收斂到鞍點（saddle point）。

[擴展閱讀]

俄羅斯著名數學家Yurii Nesterov於1983年提出了對一階法的加速演算法[2]，該演算法的收斂速率能夠達到一階法收斂速率的理論界。針對二階法矩陣求逆的計算複雜度過高的問題，Charles George Broyden，Roger Fletcher，Donald Goldfarb和David Shanno四人於1970年分別獨立提出了後來被稱為BFGS的偽牛頓演算法[3-6]，1989年擴展為低存儲的L-BFGS演算法[7]。

[參考文獻]

[1] Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[2] Nesterov, Yurii. "A method of solving a convex programming problem with convergence rate O (1/k2)." Soviet Mathematics Doklady. Vol. 27. No. 2. 1983.

[3] Broyden, Charles G. "The convergence of a class of double-rank minimization algorithms: 2. The new algorithm." IMA journal of applied mathematics 6.3 (1970): 222-231.

[4] Fletcher, Roger. "A new approach to variable metric algorithms." The computer journal 13.3 (1970): 317-322.

[5] Goldfarb, Donald. "A family of variable-metric methods derived by variational means." Mathematics of computation 24.109 (1970): 23-26.

[6] Shanno, David F. "Conditioning of quasi-Newton methods for function minimization." Mathematics of computation 24.111 (1970): 647-656.

[7] Liu, Dong C., and Jorge Nocedal. "On the limited memory BFGS method for large scale optimization." Mathematical programming 45.1 (1989): 503-528.

下一題預告

【隨機梯度下降演算法之經典變種】

[場景描述]

提到Deep Learning中的優化方法，人們都會想到Stochastic Gradient Descent (SGD)，但是SGD並不是理想的萬金油，反而有時會成為一個坑。當你設計出一個deep neural network時，如果只知道用SGD來訓練，不少情況下你得到一個很差的訓練結果，於是你放棄繼續在這個深度模型上投入精力。但可能的原因是，SGD在優化過程中失效了，導致你喪失了一次新發現的機會。

[問題描述]

Deep Learning中最常用的優化方法是SGD，但是SGD有時候會失效，無法給出滿意的訓練結果，這是為什麼？為了改進SGD，研究者都做了哪些改動，提出了哪些SGD變種，它們各有哪些特點？

歡迎留言提問或探討

關注「Hulu」微信公眾號，點擊菜單欄「機器學習」獲得更多系列文章