英文原文：

https：//

tspace。library。utoronto。ca

/bitstream/1807/89580/1/Yeo_Alexia_201806_MAS_thesis。pdf

相關程式碼：

①

https：//

github。com/kaist-ina/bp

_solver

Practical Message-passing Framework for Large-scale Combinatorial Optimization

②

https：//

github。com/pawelswoboda

/LP_MP

Solving LPs with convergent message passing

③用於機率圖形模型的Python庫PGMPY：Welcome to pgmpy’s documentation！

2。1 機率圖模型

推斷問題的基礎結構是機率圖模型。 本文探討了用於推斷機率圖模型（馬爾可夫隨機場（MRF））的訊息傳遞演算法。 MRF G =（V，E）是無向圖，由透過邊E連線的一組節點V組成，每個節點i∈V可從\mathcal{K} 中的k個可能狀態之一中獲取值。 集合\mathcal{K}是離散的。 我們稱所有奇異節點組成一個叢集，所有由邊連線的節點組成一個叢集，此外，任何相互依賴的節點集合都組成一個叢集。 一個叢集用c表示，所有叢集的集合用\mathcal{C}表示。

該模型用於表示一組變數的聯合機率分佈，其中節點表示分佈的隨機變數。 為每個群集定義勢函式，並對施加在該群集中變數上的關係進行編碼。 從最佳化的觀點來看，節點可被視為問題的變數，勢函式可被視為對目標函式有貢獻的項。 對於圖G =（V，E），我們將為變數x配置的能量函式E（x）定義為所有潛在函式的negative sum：

其中θc是與變數簇c相關聯的勢函式，可以取正或負值。

玻爾茲曼分佈給出了給定系統能量時系統將處於某一狀態的機率，其定義如下：

Z是確保最可能狀態具有機率1的歸一化因子。（2。2）將機率分佈替換表示為勢函式的乘積：

這表明MRF機率分佈對每個定義的勢函式的因子有一個有用的分解。這是一個關鍵屬性，它將用於激勵2。2節中對訊息傳遞演算法的討論。找到系統最可能狀態就相當於使Boltzmann分佈最大化，這是一個最佳化問題。結合（2。1）和（2。3）得：

此最佳化問題通常稱為最大後驗（MAP）問題。

MAP問題是針對圖形模型上的推斷問題提出的，其目標是確定圖中每個節點的狀態。MAP問題經常出現在計算機視覺、糾錯程式碼和計算生物學中。為解決這些領域中的MAP問題，人們開發了訊息傳遞演算法來利用問題的固有圖形結構。

2。2訊息傳遞演算法

訊息傳遞演算法是一類在圖形模型上工作的演算法，它在圖的節點間迭代地傳遞訊息。

我們考慮這樣一個事實，即特定變數Xi的邊際機率由沒有Xi的聯合分佈的和給出：

回顧（2。3），可以根據群集上的勢函式重寫每個邊際機率的表示式：

請注意，對特定變數求和實際上是將該變數從表示式中移除，並允許根據圖中的資訊計算p（Xi）。 從理論上講，p（Xi）可用一種稱為變數消去的蠻力方式來計算。 然而，對於許多簇來說這是很困難的，而且求和的最佳順序也不清楚。相反，對一個特定變數求和並刪除它的過程可看作一個訊息傳遞過程。這樣，從變數j傳遞到變數i的訊息等於變數j上所有隻包含i和j的勢函式乘積及之前傳遞給j的訊息的和：

這裡，N（J）\i指除Xi外連線到xj的所有節點，且muj（Xj）是從節點Xu傳送到xj的先前計算的訊息。 θij（xi，xj）是與形成獨立簇的變數xi和xj相關聯的勢函式。 傳遞到xj的先前訊息僅僅是xj上先前勢總和的結果勢，因此不再包含變數xj。

這樣一來，計算進入變數xi的所有訊息將得到p（Xi）的值。 計算出的邊際機率p也被稱為信念bi（xi）。在實踐中，勢θ被初始化為節點的邊際機率。向θ新增訊息會將其更新為˜θ——節點的最終信念。強調一下，信念bi（xi）是節點xi被髮送訊息後更新的邊際機率。訊息傳遞方法主要是根據信念的更新方式而變化，這相當於改變訊息的傳送方式。它們不限於（2。7）的形式。事實上，（2。7）的信念更新構成了和-積（sum-product）的訊息傳遞演算法。將（2。7）中的求和改為Max運算元，就會產生max-product訊息傳遞演算法，這將在2。3。2節中被再次討論。一般來說，

訊息傳遞演算法的工作動機是反覆消除模型中的變數以計算邊際機率

。在收斂時，透過找到使每個單節點信念最終值最大化的配置，對理想配置進行解碼：

這可以解釋為為每個節點找到最可能的分配。訊息傳遞最初始於Judea Pearl的非loopy圖的信念傳播演算法（1982），並在之後發展為loopy圖的變體，用以近似解決MAP問題。

（下面插2張圖介紹信念傳播，對它不感冒的客官可跳過）

https：//longaspire。github。io/blog/%E6%A6%82%E7%8E%87%E5%9B%BE%E6%A8%A1%E5%9E%8B%E6%80%BB%E8%A7%88/#4-2-2-%E4%BF%A1%E5%BF%B5%E4%BC%A0%E6%92%AD%EF%BC%88Belief-Propagation%EF%BC%89

https：//longaspire。github。io/blog/%E6%A6%82%E7%8E%87%E5%9B%BE%E6%A8%A1%E5%9E%8B%E6%80%BB%E8%A7%88/#4-2-2-%E4%BF%A1%E5%BF%B5%E4%BC%A0%E6%92%AD%EF%BC%88Belief-Propagation%EF%BC%89

2。3近似推斷

在許多實際應用中，執行推斷的圖形模型是迴圈的——一個訊息有可能在整個圖中迴圈多次。這樣一來，收斂性就得不到保證，之前在2。2節描述的精確訊息傳遞方案也不適用。不過幸好我們可透過將原圖分解為其非loopy子部分來近似原圖，並使用精確訊息傳遞方法來解決子問題。採取這種方法的一類訊息傳遞演算法被稱為線性規劃鬆弛。保持原問題二次型形式的二次型規劃鬆弛也已被開發出來，但比起線性規劃鬆弛的對應方法，前者被使用的次數不多。

2。3。1線性規劃鬆弛

MAP推理的線性規劃鬆弛方法展示了傳統最佳化主題和推理主題間的有趣重疊。 線性規劃鬆弛方法的基本組成部分如下：

·將MAP問題構造為線性規劃

·鬆弛線性規劃的integrality約束

·形成拉格朗日對偶函式

·求解拉格朗日問題的方法

我們將從匯出MAP問題的對偶開始討論線性規劃方法。 回想一下（2。4）針對成對MRF G=（V，E）提出了MAP分配問題，其中Xi可從離散集合S中取值：

這一目標可透過引入二進位制指示變數來線性化。 即，對於每個節點i∈V和每個狀態xi∈S，µi（Xi）=1，如果節點i被分配到狀態xi，則µi（Xi）=1，否則µi（Xi）=0。 我們還為連線i和j的每條邊引入µij（xi，xj），以及對每個狀態（xi，xj）具體賦值。 類似地，如果i被分配給狀態xi且j被分配給狀態xj，則µij（xi，xj）=1。如此得到的整數線性規劃如下所示

約束（2。11）和（2。13）強制µ變數為二進位制。 約束（2。12）和（2。14）強制每個變數只能分配給一個狀態，類似地，每條邊只能分配給一對狀態。 約束（2。15）和（2。16）強制每條邊的成對分配彼此一致。 請注意，雖然我們更改了變數，但新問題的解等同於原問題（2。9）。 現在我們放寬完整性約束，使指標變數µ可取區間［0，1］內的任意值。於是公式（2。11）和（2。13）更改如下：

我們將具有這些鬆弛整數約束的MAP問題稱為MAP-LP問題。 剩餘的一致性約束（2。15）和（2。16）可透過拉格朗日擴充合併到目標中。 規範化約束（2。12）和（2。14）是顯式強制實施的。

其中λi→ij（Xi）是與每個一致性約束（2。15）和（2。16）相關聯的拉格朗日引數。 上述Lagrangian是鬆弛整數問題的一種鬆弛。 總之，目前在對x的MAP分配（2。19）的問題間有以下hierarchy：

其中z是各個最佳化問題的最優目標值。 現在，我們希望收緊這一上限，以接近原始地圖目標函式值。 這可以透過尋找最小化拉格朗日值的拉格朗日引數來實現。 在傳統的最佳化中，這個問題是對偶問題：

將（2。19）、（2。21）與重排相結合，得到以下具有明確子問題的對偶表示式。 為得到（2。23），透過對最大化µ來消除它們。

從（2。22）中，我們觀察到與每個單節點和每條邊相關聯的子問題。由於拉格朗日引數的工作是加強子問題間的一致性，它們代表子問題間傳送的訊息。因此，它們用子指令碼來表示它們傳送的訊息。訊息的傳送是為了更新信念。當信念最優且子問題一致時，（2。22）中的拉格朗日引數就會抵消：

θc是原始勢函式，˜θc是更新勢函式。 θc的值根據它接收到的傳入訊息更改為˜θc。 現在我們將討論如何更新訊息（對偶變數），從而解決對偶問題（2。21），並得出一致的信念（2。23）。

2。3。2Max-Product線性規劃演算法

Globerson和Jaakola開發的最大乘積線性規劃演算法（MPLP）是一種訊息更新方法，其結果是使解（2。21）的對偶目標逐漸減小，這是透過座標下降方法實現。除了特定的λij→i（Xi）， 固定所有對偶變數λ，並求解最小化對偶（2。21）的λij→i（Xi）。 當然，這涉及解決固定任務下的各個子問題。 這是用第2。2節中描述的Max-Product演算法以精確方式完成的。 將座標下降和精確的Max-Product演算法相結合，可得到能夠有效利用的傳遞訊息的閉合形式表示式。 演算法中給出了MPLP演算法的虛擬碼。

注意，雖然座標下降演算法在每次迭代時都減少了對偶目標，但它們通常不能保證收斂到對偶最優。 因為對偶目標雖然是凸的，但不一定是嚴格凸的。 這意味著最小化座標值可能不是唯一的。 因此，在收斂時，MPLP可能找不到對偶最優解，這是該方法的一個缺點。

2。3。3收緊LP鬆弛

上述對映的線性規劃方法假設當整數約束鬆弛時得到的線性規劃是緊的，如（2。17）和（2。18）。

不幸的是，對於一般問題，這是不能保證的。 對於緊線性規劃，對偶目標與精確對映解間的integrality gap為零。 在實踐中，我們可透過注意由此產生的integrality gap來評估我們線性規劃的緊密性。 Sontag提出的一種加強線性規劃鬆弛的方法是群集追蹤法。 回想一下，在上一節中，對偶被分解為僅涉及成對群集的子問題。

群集追蹤的總體思想是，新增更高級別的群集（例如，三個節點的群集）將有助於強制子問題間的區域性一致性，從而導致更緊密的鬆弛。 這是透過動態實施變數間的關係直到鬆弛的可行域等於整數可行域來實現的。我們期望整數可行域可以被近似，而不必強制實施所有先前放鬆的約束。 此外，僅新增保證收緊邊界（降低雙重目標值）的群集。 在實踐中，我們預定了要新增的可能群集的列表，並根據它們改變邊界的程度計算分數。 對群集進行排序並將其新增到排隊列表中。 演算法2中給出了收緊Lp鬆弛的虛擬碼，該程式碼基於Sontag概述的方法。

2。4帶約束的近似推斷

我們之前對訊息傳遞的討論主要集中在僅具單節點和成對群集的MRF。 但是在實踐中，我們可能會遇到高階叢集表示該叢集中所有節點間的關係的問題。 我們稱之為約束MRF。 這可以假設為以下具有|K|個約束的組合最佳化問題：

我們可以天真地透過將約束（2。25）合併到目標（2。24）來解決上述問題，方法是計算哪些配置違反了約束，併為這些配置分配負無窮大的值。 如果配置滿足約束，我們為其賦值為零。 這樣，我們仍在嘗試尋找x的最可能賦值。不滿足約束的賦值只是被賦予一個較低的值：

這對於大型群集是不容易處理的，因為我們需要為所有可能的配置|S||c|計算hk（Xc）（|S|是Xi可採取狀態的數目，|c|是群集的大小）。 最近已經發展了一些方法來對具有大簇的一般約束MRF進行推理［1，26，50］。

［1］ Aguiar P， Xing P， Figueiredo M， Smith A， Martins A （2011） An augmented lagrangian approach to constrained MAP inference。 International Conference on Machine Learning

［26］ Lim Y， Jung K， Kohli P （2014） Efficient energy minimization for enforcing label statistics。 IEEE Transactions on Pattern Analysis and Machine Intelligence

［50］ Zhang Z， Shi Q， McAuley J， Wei W， Zhang Y， Yao R， van den Hengel A （2017） Solving constrained combinatorial optimization problems via MAP inference without high-order penalties。 AAAI Conference on Artificial Intelligence

［1］在（2。19）中向拉格朗日函式添加了二次違反約束的懲罰。 由於拉格朗日不再因二次項而分解為子問題，因此 ［1］提出了一種新的極大化方法——乘子交替方向法。

［26］提出了一種利用割面的方法。 在最小化的情況下，將問題約束合併到拉格朗日函式（2。19）中。 在每次迭代中，［26］計算最優最大化拉格朗日引數和MAP分配，並新增割以將其作為解刪除。 在收斂時，我們得到了最小化拉格朗日的解，所有的最大值都被預先去掉了。 不幸的是，該方法假設可以在每次迭代中計算出MAP問題的精確解，這一般來說並不可行。

［50］也在拉格朗日中加入了約束違反的懲罰，但採用了另一種方式，仍然可進行對偶分解。 每次迭代也不需要MAP的精確解。 與［1，26］相比，Zhang等人的［50］方法被證明在收斂時間和解質量方面具有良好效能。

2。4。1 Zhang et al方法 ［50］

為避免具有大量節點的叢集， ［50］提出一種新的訊息傳遞方法，將（2。24）中的整數問題放鬆為忽略新增大簇的約束（2。25）的線性問題。 約束（2。25）被重新公式化，以跨越只有一個或兩個節點的叢集。 然後用結合了先前忽略的約束的拉格朗日引數γ來擴充線性問題的對偶，以得到以下新的對偶公式

［50］透過兩種方法解決了最優信念˜θ和最優拉格朗日引數γ的對偶問題：

1。透過2。3。2節描述的MPLP座標下降方案更新信念˜θ。 這確保了每次迭代中的對偶減少。

2。採用二分法更新拉格朗日引數γ。 這確保瞭解的可行性。

由於MPLP已經在2。3。2節中進行了描述，現在我們將詳細介紹如何使用二進位制搜尋來確保可行解。 在實踐中，我們使用座標下降來首先更新信念˜θ，並修復除特定γk之外的所有γ以在［50］上最大化。 在每次迭代中，我們可基於當前計算的信念和當前γ解碼每個子問題的當前解：

驗證該解是否滿足約束條件。 對於每個約束k，如果存在衝突，則增加引數γk的值，否則減小其值。 我們最終會找到確保強制執行k所需的γk的最小值。 當不能再減少對偶目標時，演算法終止［50］。 此時，解被解碼，如（2。8）所示。 需要強調的是，由於我們正在解決原始整數問題的鬆弛問題，因此預計解將是次優的。 因此，我們可使用2。3。3節中討論的線性規劃緊縮法來改進解。演算法3［50］中Zhang的方法虛擬碼如下：

2。5訊息傳遞在最佳化問題中的應用

到目前為止，在本章中，我們已詳細地描述瞭如何有效解決在圖中尋找最大化位勢和的最優變數分配的抽象MAP問題。 MAP問題是一個組合最佳化問題。 透過這種方式，其他組合最佳化問題被重新表述為MAP問題，並使用上述的訊息傳遞技術進行求解。 現在，我們討論在組合最佳化和它們的圖形模型表示之間建立聯絡的已有工作。 將這項工作分為兩類：一類是基於線性規劃鬆弛的方法，另一類是根據問題結果圖形結構的特殊性質可匯出特定於問題的訊息傳遞過程的方法。

［12］ Dhoot A （2016） Wind farm layout optimization using approximate inference in graphical models。 Dissertation， University of Toronto

［25］ Lazic N， Frey B， P。 Aarabi （2010） Solving the uncapacitated facility location problem using message passing algorithms。 International Conference on Artificial Intelligence and Statistics

［36］ Sontag， D （2008） Tightening LP Relaxations for MAP using Message-Passing。 Conference in Uncertainty in Artificial Intelligence， 2008

［46］ Yanover C， Meltzer T， Weiss Y （2006） Linear programming relaxations and belief propagation–an empirical study。 The Journal of Machine Learning Research 7：887-1907

［47］ Yanover C， Weiss Y （2002） Approximate inference and protein-folding。 Advances in neural information processing systems

·［25］將訊息傳遞應用於設施選址問題。 將問題表示為機率圖模型，並比較了基於MPLP和最大和訊息更新過程的解決方案。 結果表明，基於基準資料集的已知精確結果，MPLP為該問題提供了較好的近似解。

·［12］應用訊息傳遞來最佳化電網中的風電場佈局。 該問題是一個帶約束的二元二次整數問題。 使用線性規劃鬆弛和LP收緊。 約束被併入了一種類似於Aguair等人的方法［1］。 與精確的分支定界求解器比較的結果表明，訊息傳遞提供了良好的次優解，且收斂速度明顯快於分支定界。

·［36］採用簇緊縮法，成功地恢復了蛋白質設計問題的近似最優解和精確解。 據說這個問題太大了，不能用分支定界演算法來處理。

粗糙翻譯：

·［46］［47］還探討了蛋白質設計問題和立體視覺問題。 在立體視覺問題中，我們得到兩幅影象，並希望找出每個畫素的視差。 這相當於使能量函式最小化。 MAP問題是用線性規劃方法表示和求解的。 對於這兩個問題，都使用了訊息傳遞，並將其收斂為解決方案。 此外，標準解算器無法按比例解決同樣大的問題。

·在張等人中。 Al的論文［50］發展了2。4。1節中討論的約束訊息傳遞方案，並對具有五個約束的二次揹包問題進行了測試。 他們觀察到了接近最優的解，其特徵是完整性差距很小。 此外，在最優差距和時間方面，它們的表現優於商業解決方案。

·桑哈維等人（Sanghavi et al。）。 ［34］提出了一種利用變種最大乘積演算法求解最大權獨立集問題的演算法。 將問題約束鬆弛，形成線性規劃，並對最大乘積演算法進行修正。

·Moallemi［28］開發了一個訊息傳遞過程來解決資源分配問題。 將資源分配給活動的問題用圖形模型直觀地表示出來，開發並應用了特定於問題的訊息傳遞演算法。 與啟發式方法相比，訊息傳遞在收斂時表現出更好的最優性差距，並且比其他表現出更多差距的方法更穩定。

·Ravanbakhsh［32］［33］探討了旅行商問題，並將其表示為機率圖模型。 匯出該圖唯一的訊息傳遞過程。 結果表明，與精確分枝定界法相比，該方法能夠得到近似最優解。

在這些調查中，我們觀察到兩個共同主題。 首先，不少相關論文稱訊息傳遞可獲得接近最優解，並且優於特定於問題的啟發式方法。 其次，訊息傳遞可解決標準商業解算器（即分支定界）無法解決的問題。

2。6討論

在本章中，我們討論了訊息傳遞背後的理論，以證明用線性規劃鬆弛方法可有效求得組合圖最佳化問題的良好次優解。 這是因為圖形模型可分解成容易求解的子問題。 對由此產生的寬鬆問題的緊密性的擔憂可透過LP tightening schemes來解決。 此外，問題中涉及的約束可成功併入訊息傳遞過程。 正是由於這些原因，訊息傳遞已成功應用於一系列最佳化問題。

簡言之，透過將最佳化問題建模為MRF並將原始目標重新表述為MAP最佳化問題，可將訊息傳遞應用於最佳化問題。 在MAP形式中，問題的圖形結構被明確地突出顯示，可對其應用訊息傳遞演算法來利用該結構。作者的下一個動機是研究投資組合最佳化問題。