相關基礎：概率圖模型中的推斷https://zhuanlan.zhihu.com/p/252169479
英文原文：https://tspace.library.utoronto.ca/bitstream/1807/89580/1/Yeo_Alexia_201806_MAS_thesis.pdf
相關代碼
①https://github.com/kaist-ina/bp_solverPractical Message-passing Framework for Large-scale Combinatorial Optimization
②https://github.com/pawelswoboda/LP_MPSolving LPs with convergent message passing
③用于概率圖形模型的Python庫PGMPY：Welcome to pgmpy’s documentation!
其他資源安利：
Message Passing and Combinatorial Optimization by Siamak Ravanbakhsh 博士答辯屁屁踢 https://www.siamak.page/assets/pdf/thesis_presentation.pdf

1.什么時候應該用概率圖模型、消息傳遞替代傳統組合優化求解器？

分枝定界法在為較小規模COP上是很有效的，但隨著搜索樹大小增加，通過收緊邊界來證明最優性變得十分有挑戰性。 相比之下，消息傳遞產生的次優布局始終在距精確的分支定界解的5%以內，并且可通過實施群集收緊過程更快地提供關于最佳值的更嚴格的界限。 總之，消息傳遞算法是計算窮舉分支定界方法的一種可伸縮替代方案，特別是當人們對具有某些最優性保證的快速次優解感興趣時。

雖然概率圖模型提供了一種直觀且approachable的方式來捕獲問題的變量依賴關系，但將消息傳遞用作一般整數規劃求解器仍存在局限性。 主要是因為

1.消息傳遞比較依賴流行的線性松弛方法從而不能保證緊密性，我們必須利用額外的緊縮方法來得出好的解決方案。

2.此外，對偶解不能保證是最優的，因此也不能保證收斂到精確解。

3.算法還局限于目標和約束可很容易地分解成單個或成對（pair-wise）節點群集上的勢函數的問題。

其他觀點：

from Message Passing and Combinatorial Optimization by Siamak Ravanbakhsh的博士論文
本論文研究了圖形模型中推理的一般形式，比較強調代數抽象。文章將很多推理問題的重要子集組織在一個推理層次下，并研究了分配律允許以消息傳遞的形式進行特定近似的settings。文章使用1)變分公式和循環校正（loop correction）；2)調查傳播（survey propagation）；3)混合技術，研究了在環圖中改善逼近的不同方法。最后，文章研究了組合優化問題在直接推理模式下的圖形建模。
與其他任何推理和優化框架一樣，圖形建模也有其優點和缺點。使用圖形模型求解組合優化問題的缺點主要有兩方面 a)與其他標準技術如使用整數編程求解器相比，實現消息傳遞程序更為復雜和耗時（這不和上文的違背哈，因為雖然每一步耗時但可能獲得較優解所需迭代輪次較少）；b)缺乏標準的準則來設計因子圖表示法以使計算復雜度最小化或提高消息傳遞解的質量。事實上，此文作者用了很多技巧來近似求解問題；例如，通過替代歸一化、增強、變量和因子同步消息更新、引入輔助變量、使用阻尼和減法（alternative normalization, augmentation, variable and factor-synchronous message update, introduction of auxiliary variables, using damping and decimation ）等來簡化BP消息。
另一方面，圖形建模的優點是：當處理大規模和高難度優化問題時，我們不得不求助于conceptual和computational decomposition，而圖形建模和消息傳遞技術是直接的候選方法。消息傳遞是大規模并行，可擴展的，且往往能得到高質量的解決方案。此論文也是試圖通過為一組多樣化的組合問題提供因子圖，從而建立消息傳遞的普遍性。當然了，其中有些特定問題比其他問題更適合于圖形建模，所以對它們的計算復雜度和結果質量往往更好。表5.1總結了此論文提出或評述的組合問題的消息傳遞解的一些重要信息。

2.未來工作

（基于將消息傳遞應用于約束優化問題實驗中觀察到的結果）

[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

·用[50]的方法求解表示目標函數全局約束的約束馬爾可夫隨機場是一個相對較新的研究。 與張等人的方法相同。 由于[50]依賴于約束條件能夠完全分解為單數或對數的節點集，因此需要進行納入更多一般約束條件的研究。此外，還必須進行尋找最優約束參數γ的研究，使增加約束條件不會降低問題的緊密性。

·由于消息傳遞的線性規劃松弛方法依賴于求解原始問題的松弛，因此有機會開發出比集群緊縮（cluster tightening）更有效的其他收緊方案。 此外，在集群緊縮中，我們需要對最優集群緊縮計劃以及一次應該添加的集群的大小和數量進行更多的研究。

·在許多消息更新規則中，由于在每個節點采取最大信念來解碼整數解時可能會出現ties，因此可能不會解碼最優解。 由于目前的實現方式通常通過隨機取值來打破平局，因此必須進行進一步的研究，以創造更好的tie-braking方法。

·由于測量的量通常含有一定的不確定性，因此文獻中對組合問題的魯棒性研究尤為主要。雖然優化界針對離散和連續問題開發了魯棒優化算法，但在圖形模型推斷的背景下，這些算法還沒有得到廣泛研究。將目光錨定馬爾科夫隨機場背后的底層概率結構，可能是研究魯棒信息傳遞算法的下一個有趣工作。

·結合圖同態及其在對稱中的應用，特別是它與其他方法如隨機分塊模型和譜技術的關系。

總結

以上是生活随笔為你收集整理的为什么lp的最优解是一个概率_什么时候应该用概率图模型、消息传递替代传统组合优化求解器？未来工作？（持续更新）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。