[發明專利]一種概率圖模型的近似推理算法

在審

• 申請號: 201710175349.2
• 申請日: 2017-03-22
• 公開（公告）號: CN107220709A
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 董建武;何躍鷹;卓子寒;劉中金;李佳;方喆君;趙忠華
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心
• 主分類號: G06N7/00
• 分類號: G06N7/00
• 代理公司: 北京國坤專利代理事務所(普通合伙)11491
• 代理人: 姜彥

技術領域

本發明涉及近似推理算法技術領域，具體為一種概率圖模型的近似推理算法。

背景技術

概率圖模型利用圖論的表示方法來描述聯合概率分布，是對不確定性問題進行建模的有效工具。概率圖模型用節點表示變量，節點之間的邊表示局部變量間的概率依賴關系。在概率圖模型的表示框架下，聯合概率分布表示為定義在局部變量的勢函數的連乘積，該表示框架不僅避免了對復雜系統的聯合概率分布直接進行建模，而且易于在圖模型建模中引入先驗知識。概率圖模型主要包括馬爾可夫隨機場(Markov Random Field,MRF)、貝葉斯網絡(Bayesion Network,BN)、因子圖(Factor Graph,FG)等。概率圖模型推理涉及到圖模型的所有變量，而變量之間的耦合依賴關系是導致推理算法復雜度高的主要原因。在一般的概率圖模型中，由于精確推理是NP難問題，目前的研究聚焦在近似推理算法。概率圖模型被廣泛應用于諸多領域，如自然語言處理、計算機視覺、計算神經學等。

馬爾可夫隨機場的最大后驗概率推理是一個整數規劃問題，因此難以直接求解該優化問題。一種常見的求解思路是，將該問題等價轉化為定義在約束域為邊緣凸多胞形(marginal polytope)的線性規劃問題。由于精確描述邊緣凸多胞形需要的約束數量過于龐大，研究人員將該約束域松弛為局部一致性凸多胞形(local consistency polytope)，該約束域包含有邊和節點邊緣概率的一致性約束。定義在局部一致性凸多胞形上的線性松弛問題，被稱為成對線性規劃松弛(pairwise linear programming relaxation)。松弛后的線性規劃問題可以用優化領域的一些標準優化方法來求解。松弛后的線性規劃問題可以用優化領域的一些標準優化方法來求解。然而，當圖模型的規模很大時，Yanover等人指出用標準的優化方法沒有充分利用圖模型的結構特點，求解速度慢。因此，可以引入對偶分解法來求解線性規劃問題。對偶分解的思路是將原問題分解為若干易于求解的子問題，通過組合子問題的解來近似得到原問題的解。一種常見的子問題是樹狀子圖，不同的樹狀子圖分解方式對應不同的近似推理算法，如樹重置權重消息傳遞(tree-reweighted message passing,TRW)，最大-和擴散(max-sum diffusion，MSD)，最大乘線性規劃(max product linear programming，MPLP)。樹狀子圖的分解方式對應于求解成對線性規劃松弛，而成對線性規劃松弛是對原問題的一個近似，所以這些算法無法保證推理結果的準確性。

為了提高近似推理算法的準確度，可以在原優化問題的約束域引入高階約束。Sontag和Jaakkola提出了一個約束分離算法，該算法在每次迭代過程中選擇一個違反約束最大的k-叉環不等式約束，并將該不等式約束加到局部一致性凸多胞形中，從而使得約束域逐步逼近邊緣凸多胞形。每增加一個約束，該算法利用標準優化方法進行求解。由于該算法直接求解原問題，而沒有利用圖模型的結構特點，因此算法復雜度高。除了在原優化問題的約束域引入高階約束之外，另一個提高近似推理算法準確度的方法是在對偶問題中引入比樹狀子圖更加復雜的子圖。針對二值馬爾可夫隨機場，Batra等人提出了一個更加準確的近似推理算法，該算法將MRF分解為一組覆蓋原圖節點和邊的外平面子圖，每個外平面子圖利用最大權重完美匹配(maximum weight perfect matchings)來求解。最大權重完美匹配算法能快速準確地求解二值外平面子圖的推理問題。但是，Batra等人提出的上述算法依然存在的問題是：算法沒有對外平面子圖對應原問題的約束進行分析，從而無法確定基于外平面子圖分解方式的準確度下界。針對一般的多值MRF，Yarkony等人提出一個新的推理算法，該算法將一個MRF分解為一個“覆蓋樹”，然后逐步增加可以用最大權重完美匹配算法求解的二值平面子圖(binary planar subproblems，BPSP)。由于二值平面子圖的數量龐大，而且不同的BPSP分解對應的算法收斂速度差異很大，因此BPSP的選擇是一個重要的問題。為了解決BPSP的選擇問題，首先要確定BPSP和原問題約束域之間的關系。然而，Yarkony等人的文章并沒有研究BPSP和原問題約束域之間的關系。

發明內容

為實現上述目的，本發明提供如下技術方案：一種概率圖模型的近似推理算法，首先利用分離算法選擇有效的k-叉環不等式約束；然后將這些k-叉環不等式約束對應的環組合到一個平面子圖上，并逐次添加到對偶子問題中；最后通過優化對偶問題來求解原推理問題；