0
作者 | Marin Vlastelica
編譯 | 蔣寶尚
（雷鋒網作品）目前，在計算機這個學科中有兩個非常重要方向：一個是離散優化的經典算法-圖算法，例如SAT求解器、整數規劃求解器；另一個是近幾年崛起的深度學習，它使得數據驅動的特征提取以及端到端體系結構的靈活設計成為可能。
那么能否將組合器與深度學習相結合？
ICLR 2020 spotlight 論文《Differentiation of Blackbox Combinatorial Solvers》探討了這一問題。
論文下載地址：https://arxiv.org/abs/1912.02175
在論文中，作者試著將組合求解器無縫融入深度神經網絡，并在魔獸爭霸最短路徑問題、最小損失完美匹配問題以及旅行商問題中進行了測試。測試結果顯示，其組合求解器+深度學習的方法達到的效果比傳統的方法要好。
另外，論文的一作Marin Vlastelica，在Medium上撰文介紹了這篇論文的主要思想，雷鋒網 AI科技評論作了有刪改的編譯，以下是原文請欣賞~
機器學習的研究現狀表明，基于深度學習的現代方法與傳統的人工智能方法確實存在不一致的地方。深度學習在計算機視覺、強化學習、自然語言處理等領域的特征提取方面有著強大的功能。雖然如此，但其在組合泛化問題（combinatorial generalization）上一直是研究者所詬病。
例如，將地圖作為輸入從而在 Google Maps 上預測最快路線的最短路徑的規劃問題；（Min,Max)-Cut 問題、最小損失完美匹配問題（Min-Cost Perfect Matching）、旅行商問題、圖匹配問題等等。如果單獨解決上述每一個問題，我們有很多工具可以選擇：你可以用C語言，可以使用更通用的 MIP（mixed integer programming）求解器。當然求解器需要考慮輸入空間問題，畢竟它需要定義良好的結構化輸入。雖然組合問題已經成為機器學習研究領域的關注點，但對此類問題的研究力度尚且不足。
這也不是說研究者不重視組合泛化問題，畢竟它仍然是智能系統的關鍵挑戰之一。理想情況下，研究者能夠以端對端方式，通過強大的函數逼近器（如神經網絡）將豐富的特征提取與高效的組合求解器結合起來。這也正是論文《Differentiation of Blackbox Combinatorial Solvers》中所實現的，另外，這篇論文獲得了很高的評審分數，并入選為 ICLR 2020 spotlight 論文。文章接下來的部分，并不是在試圖改進求解器，而是要將函數逼近和現有求解器協同使用。
假設黑盒求解器（blackbox solver）是一個可以輕松插入深度學習的結構模塊。
將連續輸入到離散輸出之間的映射作為求解器的方式，另外，連續輸入可以是圖邊的權重，離散輸出可以是最短路徑、選定的圖邊。其中，映射的定義如下
求解器可以將最小化一些損失函數c(ω,y)，這些損失函數可以是路徑的長度。用公式這種優化問題表示如下：
上式中，w為神經網絡的輸出，也就是神經網絡學習的某種表示，例如可以是圖邊權重的某個向量。在最短路徑問題、旅行商問題中，ω可以用來作出正確的問題描述。優化問題的關鍵是最小化損失函數，現在的問題是損失函數是分段表示的，也就是說存在跳躍間斷點。這意味著對于表示 ω，該函數的梯度幾乎處處為 0，并且在跳躍間斷點處，梯度尚未被定義。目前，利用求解器松弛（solver relaxation）的方法能夠解決這個問題，但會損失最優性。論文中提出了一種不影響求解器最優性的方法。即對原始目標函數的分段處用仿射插值來定義，另外插值由超參數 λ 控制，如下圖所示：
如上所示，函數圖像的黑色部分是原函數給出的值，橙色部分是利用插值法給出的值。最小值沒有變化。
當然，f的域是多維的。因此，對于同一個f的取值，可以有多個w相對應。也就是說輸入的ω的集合是一個多面體，輸出的f可以是相同的值。自然地，在 f 的域中有許多這樣的多面體。超參數 λ 有效地通過擾動求解器輸入 ω 來使多面體偏移。定義了分段仿射目標的插值器 g 將多面體的偏移邊界與原始邊界相連。
如下圖所示，取值 f(y2) 的多面體邊界偏移至了取值 f(y1) 處。這也直觀地解釋了為什么更傾向使用較大的超參數λ。偏移量必須足夠大才能獲得提供有用梯度的插值器g
首先，定義一個擾動優化問題的解決方案，其中擾動由超參數λ控制，公式如下：
如果假設損失函數c（ω，y）是y和ω之間的點積，則可以定義插值目標：
損失函數的線性度并不像乍一看那樣有限制性。例如，在邊選擇問題中，損失函數要考慮所有邊權重的和，具體事例參考旅行商問題和最短路徑問題。
雷鋒網注：如上圖所示，插值隨著超參數λ的變化而變化
使用該方法，可以通過修改反向傳播來計算梯度，從而消除經典組合求解器和深度學習之間的不一致性。
def forward(ctx, w_):
"""
ctx: Context for backward pass
w_: Estimated problem weights
"""
y_ = solver(w_)
# Save context for backward pass
ctx.w_ = w_
ctx.y_ = y_ return y_
在前向傳播中，只需給嵌入求解器提供 ω，然后將解向前傳遞。此外，我們保存了 ω 和在前向傳播中計算得到的解 y_。
def backward(ctx, grad):
"""
ctx: Context from forward pass
"""
w = ctx.w_ + lmda*grad # Calculate perturbed weights
y_lmda = solver(w)
return -(ctx.y_ - y_lmda)/lmda
在后向傳遞中，用超參數λ的反向傳播梯度來擾動 ω，并取先前解與擾動問題解之間的差值
計算插值梯度的計算開銷取決于求解器，額外的開銷有兩次，一次是在前向傳播過程中調用的一次求解器，另一次是在后向傳播過程中調用的一次求解器。
為了驗證該方法，設計了具有一定程度復雜度的合成任務進行驗證。
另外，因為簡單的監督學習方法無法泛化至沒有見過的數據，所以在下面的任務中，已經證明了此方法對于組合泛化的必要性。
對于最短路徑問題，測試任務為魔獸爭霸，訓練集包括《魔獸爭霸 II》地圖，任務目標為地圖對應的最短路徑問題。具體而言，測試集包含了未知的《魔獸爭霸 II》地圖。地圖本身編碼為K*K網格。卷積神經網絡的輸入是地圖，輸出地圖是頂點的損失，然后將該損失作為求解器的輸入。最后，求解器（Dijkstra 最短路徑算法）以指示矩陣的形式在地圖上輸出最短路徑。
在訓練的開始，神經網絡不知道如何為地圖的圖塊分配正確的損失，但是使用組合求解器+深度學習能夠得到正確的成本，從而找到正確的最短路徑。下列直方圖表明，相比于 ResNet 的傳統監督訓練方法，此方法的組合泛化能力更棒。
在最小損失完美匹配問題上，使用的數據集是MNIST，任務目標是輸出 MNIST 數字組成網格的最小損失完美匹配。具體而言，在此問題上，選擇的邊應該讓所有的頂點都能夠恰好被包含一次，另外還能夠讓損失之和最小。另外，網格中的每個單元都包含一個 MNIST 數字，該數字是圖中具備垂直和水平方向鄰近點的一個節點。最后，邊的損失由垂直向下或水平向右的兩位數字決定。
求解器輸出匹配中所選邊的指示向量。右側的匹配損失為 348（水平為 46 + 12，垂直為 27 + 45 + 40 + 67 + 78 + 33）。
在下面這張性能圖上，我們可以清晰看到在神經網絡中嵌入真實的完美匹配求解器能夠達到更好的效果。
在旅行商問題中，訓練數據集是國旗（即原始表示）和對應首都的最優旅行線路。神經網絡的輸出是各個國家首都的最佳旅行線路。神經網絡在訓練的過程，最重要的學習首都位置的隱表示。包含K個國家的訓練示例如下圖所示。
將各個國家的國旗輸入卷積神經網絡，然后網絡輸出最優旅行線路。
在下面的動畫中，也可以看到神經網絡訓練期間各國首都在全球范圍內的位置。
起初，位置是隨機分布的，但經過訓練后，神經網絡不僅學習輸出正確的TSP旅行線路，而且學習輸出正確的表示，即各個首都的正確3D坐標。值得注意的是，這僅僅是通過在監督訓練過程中使用 Hamming 距離損失，以及對網絡輸出使用 Gurobi 中的 MIP 實現的。
實際上，已經證明在求解器損失函數的某些假設下，可以通過黑盒組合求解器傳播梯度。這能夠讓傳統有監督方法的標準神經網絡架構實現的組合泛化能力。
深度學習+組合求解器的學習方法能夠在一些需要組合推理的現實問題上得到廣泛的應用。然而問題在于求解器損失的線性這一假設前提上，在此假設下我們究竟可以走多遠？未來工作的重點以及問題在于我們能否學習到組合問題的潛在約束，例如 MIP 組合問題。
參考文獻
Vlastelica, Marin, et al. “Differentiation of Blackbox Combinatorial Solvers” arXiv preprint arXiv:1912.02175 (2019). (http://bit.ly/35IowfE)
Rolínek, Michal, et al. “Optimizing Rank-based Metrics with Blackbox Differentiation.” arXiv preprint arXiv:1912.03500 (2019). (http://bit.ly/35EXIMN)
https://towardsdatascience.com/the-fusion-of-deep-learning-and-combinatorics-4d0112a74fa7
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
