【深度學(xué)習(xí)】深度學(xué)習(xí)如何影響運籌學(xué)？

作者：郝井華等四人

作者簡介： @郝井華：清華大學(xué)運籌學(xué)博士，現(xiàn)任美團配送算法架構(gòu)師，美團點評研究員。@成豐：北京大學(xué)智能科學(xué)系 碩士 中國國際金融貿(mào)易創(chuàng)新發(fā)展戰(zhàn)略合作研究中心 · 特聘研究員。胖驍： @胖驍 。 @劉嘉耿 ：UCLA數(shù)學(xué)系畢業(yè)生。
責(zé)任編輯： @文雨之 ：東北大學(xué)系統(tǒng)工程博士生， @愛牛氓的帆爺 ：東北大學(xué)系統(tǒng)工程碩士生 。
本篇文章是由以上四位作者在知乎上的優(yōu)秀回答，通過兩位責(zé)任編輯整理修改而成。同時兩位審稿專家也提出了修改建議，并且擴展和補充了一部分內(nèi)容。
敬請關(guān)注和擴散本公眾號及同名專欄，會邀請全球知名學(xué)者陸續(xù)發(fā)布運籌學(xué)、人工智能中優(yōu)化理論等相關(guān)干貨、知乎Live及行業(yè)動態(tài)：

『運籌OR帷幄』大數(shù)據(jù)人工智能時代的運籌學(xué)--知乎專欄：http://t.cn/RlNoO3P

『運籌OR帷幄』專欄有獎?wù)鞲鍖Ｌ?/span>

這個問題比較前沿一些，原來看起來相關(guān)性不那么強的技術(shù)領(lǐng)域，機器學(xué)習(xí) VS 運籌學(xué)，因為深度學(xué)習(xí)的發(fā)展和突破，變得聯(lián)系越來越緊密了。

狹義的運籌學(xué)，往往特指采用LP/MILP/MIP/QP/NP 等數(shù)學(xué)模型建模、采用精確算法/啟發(fā)式算法在線求解并得到滿意方案以及進(jìn)行相關(guān)理論分析的一類技術(shù)。所以，運籌學(xué)最早是作為應(yīng)用數(shù)學(xué)的一個分支，服務(wù)于人們解決各行各業(yè)優(yōu)化問題的一類基本數(shù)學(xué)工具而存在的。

OR/optimization兩個學(xué)科近年的復(fù)興無疑需要歸功于機器學(xué)習(xí)。2005年以來，Lasso等方法的提出正好契合了貝葉斯學(xué)習(xí)的精神；2010年，Boyd 在故紙堆中重新找出分布式ADMM用來求解帶約束機器學(xué)習(xí)問題（矩陣分解等等），成為了傳統(tǒng)機器學(xué)習(xí)的標(biāo)準(zhǔn)范式（objective+regularization）；2014年以來，深度學(xué)習(xí)的興起則直接帶火了一片一階隨機算法：ADAM/RMSprop 等。例如，SVM 的訓(xùn)練過程，本質(zhì)上是求解一個 SQP問題；訓(xùn)練神經(jīng)網(wǎng)絡(luò)的梯度下降算法，是在使得訓(xùn)練誤差極小化意義下的一個局部優(yōu)化算法。由此可以看出，絕大部分機器學(xué)習(xí)模型的訓(xùn)練過程，都是首先將其建模為一個運籌學(xué)問題，然后采用相應(yīng)算法來求解的。從這個角度看，機器學(xué)習(xí)（包括深度學(xué)習(xí)），是運籌學(xué)的一個應(yīng)用領(lǐng)域。

在使用運籌學(xué)來解決各行各業(yè)形形色色問題的過程中，研究者在理論和應(yīng)用層面發(fā)展出了許多類型的優(yōu)化算法，也解決了不少實際問題。各類運籌學(xué)的期刊、會議有很多，每年至少有幾千篇論文、專利發(fā)表出來。然而，除了幾十年前已經(jīng)發(fā)展比較成熟的幾類經(jīng)典算法（凸規(guī)劃算法、動態(tài)規(guī)劃、若干圖算法、信任域算法、元啟發(fā)式算法等）之外， @郝井華 認(rèn)為，在基礎(chǔ)算法層面，并無太大的突破。人們對具有非線性、NP-Hard特點的大規(guī)模優(yōu)化問題，仍然缺少好用的處理工具和通用求解算法，往往需要研究者結(jié)合領(lǐng)域知識，采用模型簡化和變換、分而治之等辦法來近似求解。然而隨著人們對深度學(xué)習(xí)研究的逐步深入，運籌學(xué)問題的求解初步的涌現(xiàn)出了新的思路。本文將簡單的介紹運籌學(xué)和深度學(xué)習(xí)的相互影響，以及近些年涌現(xiàn)出的一些比較有意思的研究成果。

深度學(xué)習(xí)的出現(xiàn)，為運籌學(xué)領(lǐng)域處理上述復(fù)雜優(yōu)化問題提供了一個非常有效的技術(shù)途徑。在深度學(xué)習(xí)和運籌學(xué)結(jié)合之前，在運籌學(xué)的學(xué)術(shù)研究圈里，已經(jīng)出現(xiàn)了不少『運籌學(xué)+機器學(xué)習(xí)』的案例。例如，在工業(yè)產(chǎn)品設(shè)計領(lǐng)域常使用響應(yīng)曲面法(RSM)、插值法來根據(jù)有限的實驗數(shù)據(jù)點來建立模型并求解；進(jìn)化算法大類中，EDA（Estimation of Distribution Algorithm）
算法通過一些機器學(xué)習(xí)模型來學(xué)習(xí)編碼和目標(biāo)函數(shù)之間的近似關(guān)系來提升迭代效率，等等。感興趣的同學(xué)可以 Google 一下這個領(lǐng)域的論文。

EDA之類的分布概率估計算法，思想非常好，但是后續(xù)并沒有取得很大的成功，原因在于，復(fù)雜非線性優(yōu)化問題的解空間往往非常『崎嶇』，Landscape 非常復(fù)雜，通過一些常規(guī)的線性模型、核模型、神經(jīng)網(wǎng)絡(luò)等，很難對其解空間進(jìn)行高精度的逼近。所以相應(yīng)的優(yōu)化算法，會有一些改進(jìn)，但是很難有質(zhì)的突破。

首先，與傳統(tǒng)運籌學(xué)關(guān)注的問題相比，一個典型的深度學(xué)習(xí)問題參數(shù)量（待求解的變量個數(shù)M）一般很大（例如，用于視覺識別的Alexnet參數(shù)量大約在100M這個量級），而凸優(yōu)化算法一般能夠高效解決的變量個數(shù)一般在1k-100k這個量級。因為很多算法一旦涉及到求Hessian/Jacobian矩陣就會涉及到存儲和計算效率問題了，這正是很多傳統(tǒng)算法的瓶頸之處，而這也是新世紀(jì)以來一階算法重新興起的一個背景。正是由于這樣的原因，LBFGS一度作為標(biāo)準(zhǔn)的優(yōu)化算法在現(xiàn)代機器學(xué)習(xí)界應(yīng)用較少：每步迭代需要一個O(M^2)變量的更新的代價太大了！

其次，機器學(xué)習(xí)以及深度學(xué)習(xí)所伴隨的數(shù)據(jù)集規(guī)模（N）一般也很大，例如標(biāo)準(zhǔn)視覺toy數(shù)據(jù)集ImageNet是120萬*4096，而google，Amazon，阿里巴巴等大廠的的規(guī)模則是PB級別的，這甚至已經(jīng)達(dá)到傳統(tǒng)油田，大氣，金融等問題的存儲規(guī)模了。數(shù)據(jù)集大小方面帶來的問題也是不可忽視的，一系列的隨機算法（SGD-based method)、分布式算法被提出來應(yīng)對這些問題。

從計算難度的角度而言，油田、大氣、金融等問題的計算一般都有很好的formulation，問題求解雖然不見得性質(zhì)很好（例如解Levy Process因為跳的存在，也涉及到很多0-范數(shù)的問題，本質(zhì)上還是NP-hard的），但是起碼能夠有一些理論的保證。而深度學(xué)習(xí)由于問題極其扭曲（深），非線性程度很高，所以求解過程收斂速度和收斂性并沒有任何的保證。當(dāng)然最近也有一些在比較強的假設(shè)下，淺層的神經(jīng)網(wǎng)絡(luò)到達(dá)saddle point或者local minima的一些證明，但是計算上的問題還是一個根本的困難問題。

然而，在給定大量高質(zhì)量數(shù)據(jù)的前提下，深度網(wǎng)絡(luò)和深度學(xué)習(xí)算法展現(xiàn)出了相比較傳統(tǒng)機器學(xué)習(xí)模型精準(zhǔn)得多的逼近能力，能夠提供高精度的逼近效果。從本質(zhì)上說，這一點就是深度學(xué)習(xí)帶給運籌學(xué)的最大影響。在合適的應(yīng)用場景下，通過深度網(wǎng)絡(luò)離線學(xué)習(xí)得到高質(zhì)量的逼近模型，并把它和符合問題特點的優(yōu)化算法相結(jié)合，將會帶來意想不到的應(yīng)用效果。我相信未來幾年內(nèi)，這方面的論文會涌現(xiàn)出一大批。

從應(yīng)用層面來說，機器學(xué)習(xí)在‘預(yù)測’上比傳統(tǒng)運籌和統(tǒng)計模型表現(xiàn)好是必然的，原因是傳統(tǒng)模型基于簡單的假設(shè)，因為復(fù)雜的假設(shè)可能無法快速的解出最優(yōu)解。更多的參數(shù)意味著這更好的擬合程度，雖然有過擬合的風(fēng)險，但機器學(xué)習(xí)模型可以通過模型增加正則化，Bagging, Boosting等一些列方式防止過擬合，從而達(dá)到很好的預(yù)測效果。當(dāng)然了，預(yù)測好并不是一個模型的全部，相對于傳統(tǒng)的統(tǒng)計模型所缺少的是可解釋性和insight。

舉個例子，博弈問題如圍棋，就是一個典型的復(fù)雜優(yōu)化問題。而AlphaGo 成功的本質(zhì)原因，是通過深度網(wǎng)絡(luò)離線學(xué)習(xí)得到了對于狀態(tài)和落子點價值的較為準(zhǔn)確的評估，然后在線地和搜索算法（蒙特卡洛樹搜索算法）相結(jié)合，取得了突破性的效果。

最近，機器學(xué)習(xí)界也在反思，Neural Network+BP=AI這么一個打法究竟是否成立。Hinton直接就跳出來說：“BP在深度學(xué)習(xí)中不是必要的”，并且提出了一個叫Capsule的東西給大家思考。包括我們也知道有很多non-gradient的方法（粒子群蟻群優(yōu)化等，一度被小圈子玩壞的領(lǐng)域，但是在新時代有無重新興起的可能？而OR也確實能夠給機器學(xué)習(xí)界帶來很大的幫助：例如，以SMO求解SVM等對偶方法現(xiàn)在已經(jīng)是標(biāo)準(zhǔn)思路。

整數(shù)規(guī)劃作為運籌學(xué)理論體系中很重要的一部分，對解決實際工業(yè)需求中的問題提供了強有力的建模方式，但機器學(xué)習(xí)模型可以通過模型增加正則化，Bagging, Boosting等一些列方式防止過擬合，從而達(dá)到很好的預(yù)測效果。

Branch-and-Bound(B&B)和 Cutting Plane方法是求解整數(shù)規(guī)劃精確解的兩種常用的方法。一直以來，這兩種方法對機器學(xué)習(xí)理論的發(fā)展和應(yīng)用都起到非常重要的作用。例如，B&B可以用在MAP 估計、場景理解、和dependency parsing中。機器學(xué)習(xí)的發(fā)展同樣對整數(shù)規(guī)劃理論具有很強的推動作用，尤其在整數(shù)模型求解過程中所涉及到的決策部分，機器學(xué)習(xí)模型將越來越發(fā)揮重要的作用。

例如，在使用算法或者商用求解器求整數(shù)模型的精確解時，通常會涉及到以下三種決策：

-Cutting Plane: 會有很多有效的割平面，但如何只選擇其中一部分加入求解過程中。

-Node Selection：如何在現(xiàn)有產(chǎn)生的Node中選擇一個，進(jìn)行下一步的松弛。

-Branching：在每個Node中，選擇哪個變量進(jìn)行Branch.

當(dāng)前的商用求解器比如Cplex, Gurobi 和開源非商用求解器Scip在處理三種決策時，通常使用Heuristic的方法進(jìn)行處理。例如，在Cut Selection中，一般使用一個多變量打分系統(tǒng)對每個Valid Cut進(jìn)行打分做出選擇，這樣的處理方式是非常的主觀的。現(xiàn)有求解器在進(jìn)行Node selection 時, 通常默認(rèn)使用best-bound 和best-estimate 兩種方式，根本沒有考慮求解模型的特性。同樣的問題存在Branching rule的設(shè)計中。

機器學(xué)習(xí)的發(fā)展，為整數(shù)規(guī)劃的算法中涉及到?jīng)Q策的部分提供了一種新的思路。比如可以通過定義合適的reward 和transition function, 可以用Online learning 算法，模擬node selection過程。可以用非監(jiān)督模型對整數(shù)模型進(jìn)行Danzig-Wolfe 分解。也可以通過學(xué)習(xí)Surrogate 評價函數(shù)，來學(xué)習(xí)Strong Branching過程，從而減少求解時間。

近些年，越來越多這樣的成果涌現(xiàn)出來，但大部分成果還都是在各大計算機頂尖會議上進(jìn)行發(fā)表，其中以佐治亞理工計算機系的Song Le， Bistra Dilkina團隊和工業(yè)工程系George Nemhauser團隊最為突出。在兩個人工智能專家和傳統(tǒng)優(yōu)化大師聯(lián)合指導(dǎo)下，組內(nèi)的博士生使用最前沿的深度學(xué)習(xí)在傳統(tǒng)整數(shù)規(guī)劃領(lǐng)域做出了突出的成果。也從側(cè)面證明了，運籌學(xué)要和人工智能深度的結(jié)合，才有可能突破現(xiàn)在理論所遇到的問題。

此外，在很多行業(yè)中，受問題規(guī)模、復(fù)雜度以及響應(yīng)時間的制約，很多規(guī)劃問題需要大量應(yīng)用啟發(fā)式規(guī)則/程序(heuristics)來近似求解。這些啟發(fā)式規(guī)則/程序往往來自對系統(tǒng)長期的觀察和思考，其質(zhì)量可能對系統(tǒng)性能至關(guān)重要。運籌學(xué)中演化計算領(lǐng)域中有一個“演化規(guī)劃”分支，試圖利用演化計算的方法來探索和生成更優(yōu)的啟發(fā)式規(guī)則，如genetic programming 等，類似的研究還包括approximate
dynamic programming、決策樹等。近年，這一領(lǐng)域越來越多的學(xué)者開始結(jié)合深度學(xué)習(xí)的方法，尤其是深度增強學(xué)習(xí)，也取得了一些有趣的進(jìn)展。

1）運籌學(xué)學(xué)科的發(fā)展，需要在優(yōu)化算法中越來越多的引入深度網(wǎng)絡(luò)等機器學(xué)習(xí)工具，實現(xiàn)離線在線相結(jié)合，數(shù)據(jù)和機理相結(jié)合，以取得更好的應(yīng)用效果，這是運籌學(xué)發(fā)展的必然趨勢。

2）運籌學(xué)為機器學(xué)習(xí)貢獻(xiàn)優(yōu)化理論，同時吸取機器學(xué)習(xí)的理念來更好的解決傳統(tǒng)問題，而深度學(xué)習(xí)也對現(xiàn)有的運籌學(xué)理論進(jìn)行了新的發(fā)展。

3）運籌學(xué)和深度學(xué)習(xí)，并不是對立的兩個概念&工具，在很多時候需要結(jié)合起來使用。

感謝審稿人楊昌鵬 @Changpeng Yang, 新加坡南洋理工大學(xué)/加州大學(xué)伯克利分校聯(lián)合培養(yǎng)博士，現(xiàn)任順豐科技----航空和物流優(yōu)化 ，為本文添加了機器學(xué)習(xí)與整數(shù)規(guī)劃結(jié)合的一些成果這一小節(jié)的內(nèi)容以及對整體文章的建議和修改。

感謝審稿人 @王孟昌 阿里巴巴運籌優(yōu)化算法專家-調(diào)度優(yōu)化，整數(shù)規(guī)劃，為本文添加了機器學(xué)習(xí)與整數(shù)規(guī)劃結(jié)合的一些成果這一小節(jié)的內(nèi)容以及對整篇文章的框架的處理和建議。

來源：知乎用戶：深度學(xué)習(xí)如何影響運籌學(xué)？https://www.zhihu.com/question/65151551/answer/240063280

參考文獻(xiàn)：
[1]Khalil E B. Machine Learning for Integer Programming[C]//IJCAI. 2016: 4004-4005.
[2]Khalil E B, Dilkina B, Nemhauser G L, et al. Learning to run heuristics in tree search[C]//Proceedings of the international joint conference on artificial intelligence. AAAI Press, Melbourne, Australia. 2017.
[3]He H, Daume III H, Eisner J M. Learning to search in branch and bound algorithms[C]//Advances in neural information processing systems. 2014: 3293-3301.
[4]Comments on: On learning and branching: a survey
[5]Lodi A, Zarpellon G. On learning and branching: a survey[J]. TOP, 2017: 1-30.
[6]Dai H, Khalil E B, Zhang Y, et al. Learning Combinatorial Optimization Algorithms over Graphs[J]. arXiv preprint arXiv:1704.01665, 2017.

往期精彩回顧




適合初學(xué)者入門人工智能的路線及資料下載
(圖文+視頻)機器學(xué)習(xí)入門系列下載
中國大學(xué)慕課《機器學(xué)習(xí)》（黃海廣主講）
機器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印
《統(tǒng)計學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯
機器學(xué)習(xí)交流qq群955171419，加入微信群請掃碼