<mark id="oztn4"></mark>
0
近期，大巖資本黃鉑博士結合生活實踐中的案例，深入淺出闡釋了最優化算法的前世今生。
從實際生活中最基礎的應用切入，黃鉑將抽象的算法概念生動化，解釋了什么叫最優化問題、凸優化及算法分類、機器學習與人工智能應用。
人生不如意之事十之八九，想達到我們想要達到的目標時，通常都有各種各樣的限制。那么所謂最優化問題，就是指用最優的方式去平衡理想與現實之間的關系。
以簡單的郵差送信問題為例，郵差從A出發，送信到BCD，最后回到A。郵差每天必須經過BCD，而且每個點每天只能經過一次，在這樣的約束條件下，他的目標函數是盡可能以最短的時間完成送信。這個問題非常簡單，只要把所有的路徑枚舉出來，然后取最短時間的方式即可。
根據前面的例子，我們嚴格的將目標函數分為兩大類。
第一類是最大化，包括最大化盈利，最大化效率。另一類是最小化，包括最小化費用、時間和錯誤率。在金融行業，我們可以最大化預測股價的正確率，也可以最小化費用、最小化時間和錯誤率。
當然，我們可以同時最大化盈利，最小化費用和時間。所以通常在很多的優化問題中，這兩種任務可以組合起來出現在同一個問題框架下，這就是對于目標函數的定義。
關于約束條件，理想很美好，現實很骨感，在現實生活中，我們會遇到比如預算有限、時間有限、外部強制性條件等各種各樣的問題，與目標函數一樣，這些限制條件不是單一存在的，也可能同時存在同一個問題里，對于某一個優化問題來講，限制條件越復雜，求解就越困難。
基于此，我們簡單根據它的約束條件以及目標函數變量類型將最優化問題分成兩大類，連續優化和離散優化。
連續優化正如圖上所畫，線中間沒有斷點，而離散優化的變量取值，是一個不連續的記錄，就如同一開始講的郵差送信問題。
兩類相較而言，離散優化會更難解決，因為離散優化多了一條限制條件 -- 不連續的集合。很多時候，我們要求我們的變量是一個整數，或者來自一個給定的區間，所以說離散優化會比連續優化更難解，而兩種算法也會有非常大的不一樣。
從學術角度而言，連續優化與離散優化對應的是兩個比較獨立的學科，離散優化可能更多的應用于統計、大數據相關的場景，連續優化則會跟計算機密碼學相關，更多的與我們現實生活中的運籌優化應用相關。
從目標函數出發，它的最優值也分為兩類，局部最優和全局最優。我們看圖中黃色的點，在局部區域內是最低的，我們管這個值叫做局部最優值，但是當我們看整個圖時，紅色的點才是最低的，所以這個點我們叫全局最優值。
通常來說，取局部最優值是相較容易的，因為基本上你只需要看它臨近一小部分的信息就可以準確判斷是否局部最優，而在現實應用中，其實僅僅知道局部最優值就足以解決很多問題。而更難的問題在于全局最優值，因為前提是你需要看到整個畫面。
所以，對于這一類問題，我們目前沒有一個特別好的解決方法。現實生活中，我們會有比較多的方法去求局部最優值，而往往我們找到的幾乎跟實際上的全局最優值不一樣。
但有一個問題是例外，這類問題它具有比較好的性質，只要找到局部最優值，它就肯定是全局最優值，這類問題就叫凸優化。
凸優化的關鍵字在“凸”，我們要定義什么樣的東西是凸的呢？看上圖，藍色區域代表優化問題里變量可以取值的空間，當取值空間是凸的時候，這是凸優化的一個必要條件。
那么什么樣的集合是凸的集合？我們在集合里任意選兩點X、Y，我們將這兩點連成線，從X到Y的這條線上所有的點都必須在集合里，只有這樣的集合才叫做凸的集合。
相反，如果有任意一個點在集合之外，那就不是凸的集合。而對于一個凸優化的問題而言，它所有的變量取值必須來自于凸的集合。
所以說，對于所有的離散優化而言，它都不是凸優化的，因為它的取值其實不是一個空間，而是一個洞一個洞的，它是很多洞的集合。
所以，通常求解這類問題時很困難，很多時候我們求解的都是一個局部最優值。在實際生活中，我們求解的都是局部優化的問題，而這類問題在所有問題中所占比例是非常非常低的。
如果把整個集合看作一個優化問題的集合，那么相對來講，比較小的一部分是屬于連續優化的問題，其他更大的區域屬于離散優化的問題，而在連續優化的空間里只有很小的一部分屬于凸優化的問題。所以說，在最優化的領域里，我們真正解決的只是實際問題中的冰山一角。
對于凸優化的問題，黃鉑博士給大家介紹幾個最經典的算法。
第一個算法，最速下降法。首先，我們看下圖，這是一個等高線，我們可以把它理解為我們的高樓，每一個圈代表一層，最中心是最高的位置，我們最終目標是用最快的方式上到中心位置。
那么，最速下降法是怎么做的呢？比如從一樓上二樓可以有多種方法，很明顯我們從垂直方向往上跳，在局部來看是最快的，然后以這樣的方法上到最高層。
最速下降法有哪些特點呢？每一步都做到了最優化，但很遺憾的是，對于整個算法而言，它并不是非常好的算法。因為它的收斂速度是線性收斂，線性收斂對于最優化算法而言是一種比較慢的算法，但也是凸優化里最自然的一個算法，最早被應用。
第二個算法，共軛梯度法。與最速下降法相比較（看下圖），綠色的線是最速下降法的迭代，從最外層到中心點可能需要五步迭代，但是共軛梯度法可能只需兩步迭代（紅色線）。
共軛梯度法最大特點是汲取前面的經驗再做下一步的動作，比如從四樓上五樓，我們會考慮方向是否最佳，汲取之前跳過的四步經驗，再探索新的方向往上跳。從數學的角度來講，每一步前進的方向和之前所有走過的路徑都是垂直的，因為這樣的性質，共軛梯度法的收斂速度遠遠高于最速下降法。
第三個算法，牛頓法。前面兩種算法，從數學的角度講，他們只用到了一階導數的信息，對于牛頓法而言，它不僅僅用到了局部一階導的信息，還用到了二階導的信息。
相比前面兩種算法，牛頓法的每一步，它在決定下一步怎么走時，不僅考慮當前的下降速度是否足夠快，還會考慮走完這一步后，下一步坡度是否更陡，下一步是否更難走。可見，牛頓法所看到的區間會更遠，收斂速度更快，屬于二階收斂速度。
如果最速下降法需要100步的話，牛頓法就只需要10步，但也正因為牛頓法使用了二階導的信息，所以它需要更多的運算量。
第四個算法，擬牛頓法。1970年，Broyden、Fletcher、Goldfarb、Shanno四人幾乎同一時間發表了論文，對于傳統的牛頓法進行了非常好的改進，這個算法叫擬牛頓法，它的收斂速度與牛頓法相似，但是它不再需要計算二階導數，所以每一步的迭代速度大大增加。
它是通過當前一階導數的信息去近似二階導數的信息，因此整個運算速度大幅度增加。由于這個算法是四個人幾乎同一時間發現的，所以也叫BFGS算法。下圖中的照片是他們四個人聚在普林斯頓時拍的，很幸運的是，Goldfarb是我博士時期的導師。
實際生活中，被應用最廣的兩種算法，一個是BFGS，另一個就是共軛梯度法。這兩種算法經常會出現在很多的程序包里或者開源代碼里，如果使用在大規模的優化問題或者成千上萬個變量的問題中，也會有非常好的效果。
隨著這些年大數據與人工智能的發展，最優化的算法也隨之進一步發展，接下來幾個應用可能更有意思。
第一個應用叫壓縮感知，首先我們把一個圖去掉80%、90%的像素點，然后如何還原到原有的圖片，這個問題看起來非常困難，但是在實際應用中，壓縮感知的算法就有非常好的效果。與這個問題相關的，還有很多很優美的優化算法，比如稀疏優化，對偶加速算法、Lasso。
這個算法還有另外一個應用，人臉識別。看下圖，這個圖上是同一個人在做各種表情，甚至戴上墨鏡，人臉識別通常會用在海關、捉拿罪犯。當我們原始輸入的人臉有很多噪音時，它會通過最優化算法，將人臉畫像出來，比如當輸入的是戴有墨鏡的人臉，算法會將墨鏡和人臉分離開來。
同樣的算法可以應用在背景分離，比如我們想要一張非常美的海景，但是又不想要太多人在這個照片上，那么就可以通過這個算法將人物和背景分離開。
看下圖右側，這是一個電梯口的監控錄像，背景是靜止的，而來來往往的人是動態的，通過最優化算法就可以將前景和背景分離出來。這項研究是在2009年由微軟研究員的幾名學者一起研究出來的。
最后一部分是深度學習。深度學習有很多層神經網絡，這個算法在97年就已經被提出來了，但是之所以最近才會有非常大規模的應用，因為在算法上會有非常大的提高，我們可以通過GPU來進行加速運算。
另外，我們在優化算法上也有了非常好的進展。其相關的優化算法是隨機優化，顧名思義，它不會優化所有的變量、所有的樣本，而是隨機挑選一個或者幾個樣本進行優化，然后在不需要看完整樣本的情況下就可以有非常好的效果，可以大規模的提高模型訓練速度。
最優化算法，源于生活高于生活，很多應用其實出現在我們每天的日常生活中，希望今天的演講對大家有所幫助。謝謝大家。雷鋒網雷鋒網雷鋒網
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
