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