選自TowadsDataScience
作者：Marin Vlastelica Pogančić
機器之心編譯
參與：郭元晨、魔王
如何將組合求解器無縫融入深度神經網絡？ICLR 2020 spotlight 論文《Differentiation of Blackbox Combinatorial Solvers》探討了這一難題，論文一作 Marin Vlastelica 撰文介紹了其主要思想。
論文鏈接：https://arxiv.org/abs/1912.02175
GitHub 鏈接：https://github.com/martius-lab/blackbox-backprop
機器學習研究現狀表明，基於深度學習的現代方法和傳統的人工智能方法並不一樣。深度學習被證實可在多個領域中作為特徵提取的強有力工具，如計算機視覺、強化學習、最優控制、自然語言處理等。不幸的是，深度學習有一個致命弱點，即它不能處理需要組合泛化能力（combinatorial generalization）的問題。例如，將地圖作為圖像輸入，學習預測 Google Maps 上的最快路線，這是最短路徑問題的一個實例。這樣的問題還有很多，如 (Min,Max)-Cut 問題、最小損失完美匹配問題（Min-Cost Perfect Matching）、旅行商問題、圖匹配問題等。
如果只是要孤立地解決此類組合問題，我們有很棒的求解器工具箱可以使用，從高效的 C 語言實現的算法，到更通用的 MIP（mixed integer programming）求解器，如 Gurobi。求解器需要定義明確的結構化輸入，因此求解器面臨的主要問題是輸入空間的表示形式。
儘管組合問題是機器學習研究領域的課題之一，但對於解決此類問題的關注卻一直有所不足。這並不意味著社區未把組合泛化問題視為通往智能系統路上的關鍵挑戰。理想情況下，人們能夠以端對端、沒有任何妥協的方式，通過強大的函數逼近器（如神經網絡）將豐富的特徵提取與高效的組合求解器結合起來。這正是我們在論文《Differentiation of Blackbox Combinatorial Solvers》中所實現的目標，我們因此獲得了很高的評審分數，並將在 ICLR 2020 會議上做 spotlight 演講。
讀者在閱讀下文時需要注意，我們並不是在嘗試改進求解器，而是要將函數逼近和現有求解器協同使用。
假設黑盒求解器（blackbox solver）是一個可以輕鬆插入深度學習的結構模塊。
黑盒求解器的梯度
我們依據從連續輸入（如圖中的邊權重）到離散輸出（如最短路徑、選中的圖中的邊）之間的映射來考慮組合優化器，定義如下
求解器最小化某種損失函數 c(ω,y)，如路徑的長度。更具體地，求解器求解如下優化問題：
現在，假設 ω 是神經網絡的輸出，即我們要學習的某種表示。直觀上，ω 表示什麼？ω 旨在定義組合問題的實例。例如，ω 可以是用來定義圖中邊權重的向量。在這種情況下，求解器可以解決最短路徑問題、旅行商問題，或者其他指定邊損失的問題。我們想實現的是通過 ω 來作出正確的問題描述。
自然地，我們想優化該表示，使它最小化損失，即關於求解器輸出的函數 L(y)。我們馬上要面臨的問題是損失函數是分段恆定的，這意味著對於表示 ω，該函數的梯度幾乎處處為 0，並且在損失函數的跳躍處梯度未被定義。說白了，這樣的梯度對於最小化損失函數沒有用。
到目前為止，已經出現一些依賴於求解器鬆弛（solver relaxation）的方法，但它們不得不在最優性上作出一定犧牲。而我們提出了一種不影響求解器最優性的方法。我們通過定義原始目標函數的分段仿射插值來實現這一目的，其中插值本身由超參數 λ 控制，如下圖所示：
如圖，f（黑色）是分段恆定的。插值（橙色）以合理的方式連接恆定區域。例如，我們可以注意到最小值並沒有變化。
當然，f 的域是多維的。這樣，我們可以觀察到 f 取相同值時輸入 ω 的集合是一個多面體。自然地，在 f 的域中有許多這樣的多面體。超參數 λ 有效地通過擾動求解器輸入 ω 來使多面體偏移。定義了分段仿射目標的插值器 g 將多面體的偏移邊界與原始邊界相連。
下圖描述了這種情況，取值 f(y2) 的多面體邊界偏移至了取值 f(y1) 處。這也直觀地解釋了為什麼更傾向使用較大的 λ。偏移量必須足夠大才能獲得提供有用梯度的內插器 g。（詳細證明過程參見原論文。）
首先，我們定義該擾動優化問題的解，其中擾動由超參數 λ 控制：
如果我們假設損失函數 c(ω,y) 是 y 和 ω 之間的點積，則我們可將插值目標定義為：
請注意，損失函數的線性度並不像乍一看那樣有限制性。所有涉及邊選擇的問題都屬於此類別，這類問題中損失是邊權重之和。最短路徑問題（SPP）和旅行商問題（TSP）都屬於此類問題。
在這個動畫中，我們可以看到插值隨 λ 增加的變化情況。
算法
使用該方法，我們可以通過簡單地通過修改反向傳播來計算梯度，從而消除經典組合求解器和深度學習之間的斷裂。
<code>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_/<code>
在前向傳播中，我們只需給嵌入求解器提供 ω，然後將解向前傳遞。此外，我們保存了 ω 和在前向傳播中計算得到的解 y_。
<code>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)da/<code>
至於反向傳播，我們只需使用縮放係數為 λ 的反向傳播梯度來擾動 ω，並取先前解與擾動問題解之差即可。
計算插值梯度的計算開銷取決於求解器，額外的開銷出現在前向傳播和反向傳播中，每個過程均調用了一次求解器。
實驗
我們使用包含一定組合複雜度的綜合任務來驗證該方法的有效性。在以下任務中，我們證明了該方法對於組合泛化的必要性，因為簡單的監督學習方法無法泛化至沒有見過的數據。同樣，其目標是學習到正確的組合問題描述。
對於魔獸爭霸最短路徑問題，訓練集包含《魔獸爭霸 II》地圖和地圖對應的最短路徑作為目標。測試集包含沒有見過的《魔獸爭霸 II》地圖。地圖本身編碼了 k × k 網格。地圖被輸入卷積神經網絡，網絡輸出地圖頂點的損失，然後將該損失送入求解器。最後，求解器（Dijkstra 最短路徑算法）以指示矩陣的形式在地圖上輸出最短路徑。
自然地，在訓練開始時，網絡不知道如何為地圖塊分配正確的損失，但是使用該新方法後，我們能夠學習到正確的地圖塊損失，從而獲得正確的最短路徑。下列直方圖表明，相比於 ResNet 的傳統監督訓練方法，我們的方法泛化能力明顯更好。
MNIST 最小損失完美匹配問題的目標是，輸出 MNIST 數字組成網格的最小損失完美匹配。具體而言，在最小損失完美匹配問題中，我們應該選擇一些邊，使得所有頂點都恰好被包含一次，並且邊損失之和最小。網格中的每個單元都包含一個 MNIST 數字，該數字是圖中具備垂直和水平方向鄰近點的一個節點。垂直向下或水平向右讀取兩位數字，即可確定邊損失。
對於這個問題，卷積神經網絡（CNN）接受 MNIST 網格圖像作為輸入，並輸出被轉換為邊損失的頂點損失網格。接著將邊損失提供給 Blossom V 完美匹配求解器。
求解器輸出匹配中所選邊的指示向量。右側的匹配損失為 348（水平為 46 + 12，垂直為 27 + 45 + 40 + 67 + 78 + 33）。
同樣，在以下性能對比圖中，我們注意到在神經網絡中嵌入真正的完美匹配求解器帶來了明顯的優勢。
我們還研究了一個旅行商問題，其中網絡應該輸出各個國家首都的最佳 TSP 旅行線路。對於該問題，重要的是學習正確的首都位置隱表示。我們的數據集由國旗（即原始表示）和對應首都的最優旅行線路組成。一個訓練示例包含 k 個國家。在這種情況下，將各個國家的國旗輸入卷積神經網絡，然後網絡輸出最優旅行線路。
在下面的動畫中，我們可以看到訓練期間學習到的各個國家首都在地球上的位置。最初，位置是隨機分散的，但是在訓練後，神經網絡不僅學習輸出了正確的 TSP 線路，還學習到了正確的表示，即各個首都正確的三維座標。值得注意的是，這僅僅是通過在監督訓練過程中使用 Hamming 距離損失，以及對網絡輸出使用 Gurobi 中的 MIP 實現的。
總結
實驗證明，事實上，在某些關於求解器損失函數的假設下，可以通過黑盒組合求解器傳播梯度。這使得我們獲得基於傳統有監督方法的標準神經網絡架構無法實現的組合泛化能力。
我們正在嘗試說明，該方法在解決需要組合推理能力的現實問題中有著廣泛的應用。我們已經給出了一種針對排名度量優化的應用 [2]。然而，問題在於（無論從理論還是實踐上）我們可以沿著求解器損失的線性假設這一方向走多遠。未來工作的另一個問題是，我們能否學習到組合問題的底層約束，例如 MIP 組合問題。
參考文獻
[1] Vlastelica, Marin, et al.「Differentiation of Blackbox Combinatorial Solvers arXiv preprint arXiv:1912.02175 (2019).
[2]Rolínek, Michal, et al.「Optimizing Rank-based Metrics with Blackbox Differentiation.」arXiv preprint arXiv:1912.03500 (2019).
https://towardsdatascience.com/the-fusion-of-deep-learning-and-combinatorics-4d0112a74fa7
閱讀更多 機器之心Pro 的文章
