[發明專利]一種基于概率矩陣分解的貝葉斯網絡推理方法

在審

• 申請號: 201810437038.3
• 申請日: 2018-05-09
• 公開（公告）號: CN108647715A
• 公開（公告）日: 2018-10-12
• 發明（設計）人: 董建武;孫波;房婧;杜雄杰;劉成;方喆君;余肇飛;劉健;司成祥;王億芳;侯美佳
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心;北京大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N5/04
• 代理公司: 北京久維律師事務所 11582
• 代理人: 邢江峰

本發明公開了一種基于概率矩陣分解的貝葉斯網絡推理方法，包括概率矩陣分解、概率矩陣分解算法和基于概率矩陣分解的貝葉斯網絡推理方法三個步驟，該方法可以用于分析變量間的獨立性和確定性關系，本文證明了貝葉斯網絡的聯合概率分布可以等價表示為一系列子圖聯合概率分布的線性組合，在此基礎上，提出了一個新的推理框架，在這個新的框架下，任意貝葉斯網絡可以分解為若干帶權重的貝葉斯子網絡，如果原圖被分解為樹狀子圖，可以得到精確的推理結果；如果原圖被分解為若干仍然帶環的子圖，近似推理的準確性高于主流的信度傳播算法。

技術領域

本發明涉及貝葉斯網絡領域，尤其涉及一種基于概率矩陣分解的貝葉斯網絡推理方法。

背景技術

貝葉斯網絡是一種有向概率圖模型，它起源于人工智能領域的研究，近年來，貝葉斯網絡被廣泛應用于人工智能、模式識別、故障診斷、圖像視頻處理等各個領域，貝葉斯網絡用節點表示變量，用節點之間的邊表示變量之間的依賴關系，其核心思想是在圖模型上定義一個聯合概率分布，而該聯合概率分布可以表示為圖模型上節點和邊上勢函數的乘積，這一結構特性使得概率圖模型能夠通過描述局部變量間的依賴關系，來刻畫系統整體的聯合概率分布，貝葉斯網絡的基礎理論主要包括模型表示、概率推理和模型學習，概率推理是其中的核心問題，具有重要的理論和實際研究意義，貝葉斯網絡的推理難題是由網絡中存在耦合的環引起的，因此許多近似推理方法都試圖去掉環的影響，而概率矩陣是貝葉斯網絡中表示局部變量間依賴關系的參數。

發明內容

針對上述問題，本發明提供了一種基于概率矩陣分解的貝葉斯網絡推理方法。

為解決上述技術問題，本發明所采用的技術方案是：

一、概率矩陣分解：

貝葉斯網絡的聯合概率表示為概率矩陣的乘積：

概率矩陣描述了貝葉斯網絡局部變量之間的概率依賴關系，概率矩陣分解的主要思想是將概率矩陣分解為若干帶權重的極值概率矩陣，其中極值概率矩陣的元素只包含0和1，通過概率矩陣分解，變量之間的依賴關系被分解為獨立關系或確定性關系，通過分解，變量之間的耦合關系能夠得到簡化，原來含有環的貝葉斯網絡能夠變成無環網絡；因此，可以利用矩陣分解，將一個帶環的貝葉斯網絡分解為樹狀貝葉斯網絡，從而將復雜推理問題轉化為樹狀貝葉斯網絡的推理問題；

以下給出概率矩陣的數據定義，貝葉斯網絡中某個節點的概率矩陣記為T＝(t_ij)_m×n，概率矩陣的元素為非負數，且概率矩陣的每行滿足

定義1：T為概率矩陣，如果T的所有元素取值為0或1，則T為極值概率矩陣，極值矩陣蘊含著變量之間的獨立性或確定性關系，極值概率矩陣的數學定義如下：

任意一個概率矩陣T可以分解為特定數量的獨立和確定性極值矩陣的加權和：

定理1：一個任意極值概率矩陣描述變量之間的獨立或確定性關系。二、概率矩陣分解算法：

對于任意一個m×n維概率矩陣，可以被分解為n^m個可能的極值矩陣，分解后的極值矩陣數量隨著矩陣維度呈指數增長，從而限制了該方法在概率推理中的應用。

三、基于概率矩陣分解的貝葉斯網絡推理方法：

利用概率矩陣分解方法可以把貝葉斯網絡進行分解簡化：

定理3：貝葉斯網絡的聯合概率分布可以表示為子網絡聯合概率分布的加權和：

進一步的，分為三個算法：

算法1：最小行分解算法：