深度學習如何影響運籌學？

01-03

最近看到一篇回答，YouTube 已將視頻推薦全面改用深度學習實現。但傳統上，推薦系統落在運籌學的範疇，可以歸結為一個矩陣補全（matrix completion）問題，用半正定規劃（SDP）里的方法，如非負矩陣分解（NMF）解決，而 YouTube 的結果顯示深度學習的預測準確率比傳統方法好很多、快很多。
其他運籌學的問題（如廣告搜索、路徑規劃、定價估值、倉儲物流）、形式（如 LP、CP、SDP、MIP）、和方法（如內點法、割平面法）也會遇到這樣來自深度學習的挑戰嗎？如果會的話，將如何影響？學界和業界有哪些已有的討論和成果？
文中提及回答：王科：YouTube 的視頻推薦演算法是怎樣的？

這個問題比較前沿一些，原來看起來相關性不那麼強的技術領域，機器學習 VS 運籌學，因為深度學習的發展和突破，變得聯繫越來越緊密了。本人是運籌學 PHD 出身，所以想從運籌學這個學科發展和演化的角度，談一下自己的看法。

狹義的運籌學，往往特指採用LP/MILP/MIP/QP/NP 等數學模型建模、採用精確演算法/啟發式演算法在線求解並得到滿意方案以及進行相關理論分析的一類技術。所以，運籌學最早是作為應用數學的一個分支，服務於人們解決各行各業優化問題的一類基本數學工具而存在的。從這個角度看，機器學習（包括深度學習），是運籌學的一個應用領域。例如，SVM 的訓練過程，本質上是求解一個 SQP問題；訓練神經網路的梯度下降演算法，是在使得訓練誤差極小化意義下的一個局部優化演算法。推而廣之，絕大部分機器學習模型的訓練過程，都是首先將其建模為一個運籌學問題，然後採用相應演算法來求解的。

除了機器學習這個應用領域外，運籌學還成功應用於很多行業。典型的有：量化投資（運籌學+金融）、工業產品規格製造流程設計（如飛機結構設計）、生產計劃優化（PlanningScheduling）、配送路線規劃/分單、動態定價等等。本質上，不管做什麼工作，我們都有『把工作做得更好』的追求目標，而運籌學恰恰是實現這一目標的一類基礎數學工具。

在使用運籌學來解決各行各業形形色色問題的過程中，研究者在理論和應用層面發展出了許多類型的優化演算法，也解決了不少實際問題。各類運籌學的期刊、會議有很多，每年至少有幾千篇論文、專利發表出來。然而，除了幾十年前已經發展比較成熟的幾類經典演算法（凸規劃演算法、動態規劃、若干圖演算法、信任域演算法、元啟發式演算法等）之外，個人認為，在基礎演算法層面，並無太大的突破。人們對具有非線性、NP-Hard特點的大規模優化問題，仍然缺少好用的處理工具和通用求解演算法，往往需要研究者結合領域知識，採用模型簡化和變換、分而治之等辦法來近似求解。

而深度學習的出現，為運籌學領域處理上述複雜優化問題提供了一個非常有效的技術途徑。在深度學習和運籌學結合之前，在運籌學的學術研究圈裡，已經出現了不少『運籌學+機器學習』的案例。例如，在工業產品設計領域常使用響應曲面法(RSM)、插值法來根據有限的實驗數據點來建立模型並求解；進化演算法大類中，EDA（Estimation of Distribution Algorithm）演算法通過一些機器學習模型來學習編碼和目標函數之間的近似關係來提升迭代效率，等等。感興趣的同學可以 Google 一下這個領域的論文。

EDA之類的分布概率估計演算法，思想非常好，但是後續並沒有取得很大的成功，原因在於，複雜非線性優化問題的解空間往往非常『崎嶇』，Landscape 非常複雜，通過一些常規的線性模型、核模型、神經網路等，很難對其解空間進行高精度的逼近。所以相應的優化演算法，會有一些改進，但是很難有質的突破。

但是，在給定大量高質量數據的前提下，深度網路和深度學習演算法展現出了相比較傳統機器學習模型精準得多的逼近能力，能夠提供高精度的逼近效果。從本質上說，這一點就是深度學習帶給運籌學的最大影響。在合適的應用場景下，通過深度網路離線學習得到高質量的逼近模型，並把它和符合問題特點的優化演算法相結合，將會帶來意想不到的應用效果。我相信未來幾年內，這方面的論文會湧現出一大批。

舉個例子，博弈問題如圍棋，就是一個典型的複雜優化問題。而AlphaGo 成功的本質原因，是通過深度網路離線學習得到了對於狀態和落子點價值的較為準確的評估，然後在線地和搜索演算法（蒙特卡洛演算法）相結合，取得了突破性的效果。

所以，回到最開始的問題上，我給出的結論是：1）運籌學學科的發展，需要在優化演算法中越來越多的引入深度網路等機器學習工具，實現離線在線相結合，數據和機理相結合，以取得更好的應用效果，這是運籌學發展的必然趨勢；2）運籌學和深度學習，並不是對立的兩個概念工具，在很多時候需要結合起來使用。

感謝題主的追問：

關於DL對OR本身的影響的問題，我認為其實也有一些改變，一個工業界已經成為基線的例子是：推薦系統以前是做非負矩陣分解（NMF）的，包括以前很多的low rank的做法，現在很多都改成學embedding然後作為deep feature搞進去了。不過這個例子還是在特徵工程的層面上影響較大。直接利用深度學習求解比較難的問題我不了解這方面問題，但是另外一個答主似乎提了一篇用DRL做三維裝箱的問題的，另外我也聽說用DL approximate TSP的。不過這些工作也不是這波deep learning才有，上一個神經網路時代就有了，但是並沒有什麼進展，所以其實我不看好用深度學習直接做OR里的問題。

====================================================

萌新主要從Optimization的不一樣的角度試著回答這個問題。

OR/optimization兩個學科近年的復興無疑需要歸功於機器學習。2005年以來，Lasso等方法的提出正好契合了貝葉斯學習的精神；2010年，Boyd 在故紙堆中重新找出分散式ADMM用來求解帶約束機器學習問題（矩陣分解等等），成為了傳統機器學習的標準範式（objective+regulazation）；2014年以降，深度學習的興起則直接帶火了一片一階隨機演算法：ADAM/RMSprop 等等。

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

其次，機器學習以及深度學習所伴隨的數據集規模（N）一般也很大，例如標準視覺toy數據集ImageNet是120萬*4096，而google，Amazon，阿里巴巴等大廠的的規模則是PB級別的，這甚至已經達到傳統油田，大氣，金融等問題的存儲規模了。數據集大小方面帶來的問題也是不可忽視的，一系列的隨機演算法（SGD-based method), 分散式演算法被提出來應對這些問題。

從計算難度的角度而言，油田大氣金融等問題的計算一般都有很好的formulation，問題求解雖然不見得性質很好（例如解Levy Process因為跳的存在，也涉及到很多0-範數的問題，本質上還是NP-hard的），但是起碼能夠有一些理論的保證。而深度學習由於問題極其扭曲（深），非線性程度很高，所以求解過程收斂速度和收斂性並沒有任何的保證。當然最近也有一些在比較強的假設下，淺層的神經網路到達saddle point或者local minima的一些證明。但是計算上的問題還是一個根本的困難問題。

最近，機器學習界也在反思，Neural Network+BP=AI這麼一個打法究竟是否成立。Hinton直接就跳出來說：「BP在深度學習中不是必要的」，並且提出了一個叫Capsule的東西給大家思考。包括我們也知道有很多non-gradient的方法（粒子群蟻群煙花等等，一度被小圈子玩壞的領域，但是在新時代有無重新興起的可能？）。而OR也確實能夠給機器學習界帶來很大的幫助：例如，以SMO求解SVM等對偶方法現在已經是標準思路。

所以留下幾個開放式的問題：1.如何設計隨機非同步分散式演算法和深度學習結合？2.深度學習的優化演算法有無理論的收斂性收斂速度證明？3.如何構造高效的的分散式演算法來應對不斷增大的數據規模？

因為深度學習也是機器學習的一種，就從機器學習對運籌學的影響講起吧，附帶著講深度學習特有的特點。

首先不得不說機器學習讓一系列優化演算法變得火熱起來了，用Princeton ORFE的某位faculty的話說，『machine learning is all about optimization』。當然了『機器學習讓運籌學復興』這種觀點就不太站得住腳了，按照這個邏輯，金融危機也讓運籌里的金融工程復興了一下。。但是具體到深度學習，目前深度學慣用到的優化演算法在機理上並不新穎，而且對於這個高度非凸的目標函數，求解全局最優解概率渺茫。目前深度學習的加速更多的是靠分散式演算法以及硬體的升級，而且做機器學習的運籌學教授也沒有把求解深度神經網路全局最優作為重點問題（廢話，連簡單神經網路都不好解）。我所見到的科研包括：更快速度收斂的演算法，更難解決的優化模型（比如加各種奇怪的Penalty function和限制條件），以及準度和速度兼備在線學習演算法等等。這樣的優化理論不一定會幫助深度學習，但是顯然是未來其他演算法的building block，而且因為機器學習大火而得到了足夠的關注度。

再說應用層面。我認為機器學習在『預測』上比傳統運籌和統計模型表現好是必然的，這是因為傳統模型往往基於簡單的假設，因為複雜的假設可能無法快速的解出最優解。更多的參數意味著更好的擬合程度，雖然有過擬合的風險，但是機器學習又有個調參的過程，所以預測結果好是必然的。當然了，預測好並不是一個模型的全部，比如相對於傳統的統計模型他缺少可解釋性和insight。如果研究社會問題的人對著數據調調參數，把結果弄到支持自己的結論為止，這樣的研究也就毫無意義了（不過貌似碼農們覺得這就是經濟學家們在做的事情，所以他們才會覺得相關專業都很水吧┑(￣Д ￣)┍）

在『預測』之外的應用上，機器學習的影響相當有限。先預測再用預測結果做決策的問題就不多說了，其實本質上只是把輸入的數據用機器學習模型預處理了一下，決策過程還是一個運籌學問題。說說大放異彩的強化學習好了。強化學習其實就是動態規劃的近似解，它給很多理論上可以建模實際上完全不可解的馬爾科夫決策過程提供了近似解。這類應用也是深度學習最有前途的地方，比如圍棋，無人車等等。但是另一方面，強化學習的模型很少有問題可以有理論保證(theoretical bound)，比如保證無人車翻車率依概率收斂到0這種，對於無人車這種複雜的工程太難了。這樣的模型在運籌學界很不討喜（連個bound或者convergence都沒有，確實很難發paper).哥大某位優化大牛就說過他絕不會坐深度學習訓練出來的無人車，因為這種沒有理論保證的模型即使訓練樣本再多也依然無法根除出錯的風險。

但是另一方面，基於機器學習理念來改進傳統模型的研究越來越多了。比如在過去，人們認為決策模型的參數是給定的，然後得到一些很優雅的解。如果用機器學習的話，那就等於把所有決策試很多遍，找最優決策，這樣的試錯成本太高了。所以目前有很多研究就把學習和決策結合起來，比如對於一個新產品的定價，就有了『learning and pricing』的過程，然後證明這個過程的試錯成本有理論上限。這樣的模型和機器學習研究的問題無關，更多的是理念的結合，在現實生活中應用很廣。

所以呢，我的結論是運籌學依然一如既往地為機器學習貢獻著優化理論，同時也在吸取機器學習的理念來更好的解決傳統的問題。具體到深度學習，其實它對學界的關注點影響有限，研究優化的目前不能根本性解決深度學習的痛點，研究應用的更注重理論保證，但是感謝機器學習和深度學習讓運籌學裡的很多成果被人重視起來 : )

我感覺這個問題很棒，自己也一直在思索。以下只是個人的愚見：

現實中我們遇到的優化問題可以分為：1）靜態優化；2）動態優化。

第一種優化問題，它的特點是決策信息是固定的。比如最簡單的旅行商問題、背包問題。因為圖的節點，物品的價值等這些信息是確定的。就算是考慮參數的隨機性或者不確定性，只是描述參數的方式不一樣，從確定的值變為隨機變數，或者不確定性集合。這些信息不會隨著時間，或者某種事件發生而變化。在這種靜態決策優化下，運籌學的方法是最為直觀的。建立目標、約束，然後求解；

第二種優化問題下，決策信息隨著時間而變化。比如航班恢復問題，實時調度。這些優化問題除了需要高質量的解以外，更加要滿足實時性。我們人類通常做決策應對突發事件是依靠什麼？依靠本能的反應。而本能的反應其實來源於「日常訓練」。既然談到了訓練，那麼深度學習，或者更廣一些，機器學習就自然而然有用武之地了。

所以我認為，靜態優化領域深度學習難以取代運籌學，但是動態領域會逐步成為主要的工具。

另外，從優化的方法角度出發，深度學習也會影響運籌學。比如把搜索演算法和神經網路融合。這裡的搜索演算法可以包括：分支定界，元啟發式演算法。這一分支，題主可以關注一下「計算智能（Computational Intelligence）」。okay，說了那麼多，舉個例子：

這是一個遊戲AI領域的優化問題。星際爭霸1中，神族的建造順序優化問題。（Building Order Optimization Problem）。比如開局的時候，需要最快建造出黑暗聖堂武士，那麼這個問題實際上是一個靜態優化問題，和OR中調度問題很像，在以下視頻中你可以看到一個Branch Bound解決了這個問題。

同樣是一個遊戲AI領域的優化問題。飛龍 vs 聖堂武士。沒錯，你可以規劃每一條飛龍的路徑，攻擊的目標，攻擊次數。但是攻擊目標也在動。這就是所謂的「動態」。要解決這個優化問題，視頻中就用到了機器學習，可以看看效果，非常nice。

個人認為深度學習能夠從求解和擴大學科外延兩個方面影響運籌學。

求解來說主要指求解速度和解的質量。對於複雜的動態優化問題，很難獲得解析解，只能依靠數值演算法獲得數值解。雖然現有演算法對於不太複雜的問題能夠較快獲得質量較好的解，但如何更快的獲得更複雜問題質量更好的解將會始終是運籌學領域一個重要的問題。

其次就是擴大學科外延。對於複雜的現實，現階段運籌學能解決的問題還是屈指可數的。運籌學能解決問題的極限就可以認為是目前運籌學的邊界。深度學習可能給予學者或者從業者更多啟發，讓他們獲得解決現在運籌學解決不了的問題的思路，從而拓展這個學科的外延。

以上為本人的一點拙見

深度學習里用了很多優化演算法，這點沒錯。

但是優化演算法的門檻其實很低，簡單學習就能掌握。

優化里真正門檻高的是優化理論。不過真正的深度學習里的優化問題，都不是現有的優化理論能夠解釋證明的。

所以很遺憾地說，優化的確為深度學習提供了很多工具。但真正解決深度學習里的優化問題還是要靠深度學習圈裡懂真優化的人。

感覺是人類的退化。

曾經我們蒙昧的以為現實的問題都是黑箱，手足無措。然後先賢們建立了一系列的物理模型去描述現實，以為抓住了一角。

現在深度學習告訴大家，你的模型還不如我的黑箱有用。

未來的趨勢或許是

運籌學+隨機分析+機器學習+行業

這樣一個萬金油模型吧

運籌學與機器的深度學習我覺得沒啥矛盾

一個是理論支撐一個是應用方法吧

我的感覺是，運籌學原來關注經典運籌問題，即變數少，約束少，目標少的「三少問題」，深度學習關注「三多問題」；

運籌學關注精確的模型表達，優先考慮精確求解方法，深度學習以效果好、出錯率少為目標，涉及分類和預測模式問題；這一部分，運籌學未來需要深入研究演算法的可擴展性，包括同一預測目標下的多種演算法的關聯等。

從數理邏輯方面研究運籌學可能是未來方向。運籌學演算法分析也許是進入深度學習的基礎，但需要擴展至監督和無監督模式。

僅是感覺，供參考。另外，傍大腿的做法不可取。深度學習的演算法擴展性和因果關係是兩個難以克服的大bug。舉個例子，你能用深度學習預測出針管的銷售量趨勢大到什麼程度，以決策供應量，但背後可能是吸毒人群擴張所導致，也可能是病人多導致，決策是能一樣嗎？有時參考價值不大，甚至是更大危害的來源，需警示。

深度學習會挑戰運籌學的。運籌學在眾多領域都有很明確的方法和模型，問題在於參數和約束很難像神經網路那樣用數據集不斷演化。運籌學工具一般邊界都比較清晰，用有效的演算法可以達到優化目標。

很多相同的東西有不同名字罷了，你也可以說運籌學門優化學科，那本質就和很多傳統機器學習差不多，深度學習也是用優化的思想。

很多重要事件決策的做出不是簡單的概率判斷~~運籌學是涉及哲學、心理學等多學科的~這些未來可能會有真正意義上的人工智慧可以挑戰運籌學~但現在的初級的以計算和概率判斷為基礎的所謂人工智慧是不可能挑戰夾雜社會工程學的社會科學~~~