[發(fā)明專利]一種基于概率矩陣分解的貝葉斯網(wǎng)絡(luò)推理方法

在審

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

1.一種基于概率矩陣分解的貝葉斯網(wǎng)絡(luò)推理方法，分為三個步驟：

一、概率矩陣分解：

貝葉斯網(wǎng)絡(luò)的聯(lián)合概率表示為概率矩陣的乘積：

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

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

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

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

定理1：一個任意極值概率矩陣描述變量之間的獨立或確定性關(guān)系。

二、概率矩陣分解算法：

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

三、基于概率矩陣分解的貝葉斯網(wǎng)絡(luò)推理方法：

利用概率矩陣分解方法可以把貝葉斯網(wǎng)絡(luò)進行分解簡化：

定理3：貝葉斯網(wǎng)絡(luò)的聯(lián)合概率分布可以表示為子網(wǎng)絡(luò)聯(lián)合概率分布的加權(quán)和：

。

2.根據(jù)權(quán)利要求1所述一種中和酸的檢測方法，其特征在于：概率矩陣分解算分為三個矩陣分解的算法：

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

最小化分解后極值概率矩陣的數(shù)量，可以表示為以下優(yōu)化問題：

min N

0≤ρ_i≤1,i＝1,2,...,N

文本提出了最小行搜索算法來優(yōu)化上述問題。最小行搜索算法是一個迭代分解方法：

(1)輸入：m×n維概率矩陣T；

(2)輸出：特定數(shù)量的極值概率矩陣E＝{E_k}，及相應(yīng)的權(quán)重ρ＝{ρ_k}；

(3)初始化T＝(t_ij)_m×n,k＝0；

(4)while T≠0 do；

(5)K＝k+1；

(6)查找T的最小非零元素t_ij；

(7)ρ_k＝t_ij；E_k＝0；

(8)記錄矩陣T每一行最小非零元素的位置，將E_k在位置p的值設(shè)為1；

(9)ρ＝ρ∪{ρ_k}；

(10)E＝E∪{E_k}；

(11)T＝T-ρ_kE_k；

(12)end while。

算法2：最大行分解算法：

概率矩陣分解后得到的極值概率矩陣權(quán)重往往各不相同，如果權(quán)重集中在少數(shù)極值概率矩陣，權(quán)重較小的極值概率矩陣可以近似忽略，從而實現(xiàn)了對原貝葉斯網(wǎng)絡(luò)的近似分解，為了實現(xiàn)將權(quán)重集中在少量的極值概率矩陣，本文提出了最大行搜索算法，該算法流程為：記錄概率矩陣每行的最大元素所在的位置，將極值概率矩陣在相應(yīng)位置設(shè)為1，其余位置設(shè)為0；極值概率矩陣的權(quán)重設(shè)置為每行最大元素的最小值，依次迭代分解，得到若干帶權(quán)重的極值概率矩陣，由算法2得到的極值概率矩陣，其權(quán)重主要集中在編號較小的極值概率矩陣；

(1)輸入：m×n維概率矩陣T；

(2)輸出：特定數(shù)量的極值概率矩陣E＝{E_k}，及相應(yīng)的權(quán)重ρ＝{ρ_k}；

(3)初始化T＝(t_ij)_m×n,k＝0；

(4)while T≠0 do；

(5)k＝k+1；

(6)E_k＝0；

(7)記錄矩陣T每一行最大非零元素的位置p，將E_k在位置p的值設(shè)為1；

(8)ρ＝ρ∪{ρ_k}；

(9)E＝E∪{E_k}；

(10)T＝T-ρ_kE_k；

(11)end while。

算法3：最大獨立分量分解算法：

為了將極值矩陣的權(quán)重集中在獨立極值矩陣中，本文提出了最大獨立分量分解算法，利用最大獨立分量分解算法對貝葉斯網(wǎng)絡(luò)進行分解，可以將原帶環(huán)的貝葉斯網(wǎng)絡(luò)近似為樹狀貝葉斯網(wǎng)絡(luò)；

(1)輸入：m×n維概率矩陣T；

(2)輸出：獨立分量概率矩陣及相應(yīng)權(quán)重T_I,ρ_I，確定性矩陣及權(quán)重{E_k},{ρ_k}；

(3)初始化T_I＝0,ρ_I＝0,

(4)for j＝1:n do；

(5)

(6)E_j＝0；；

(7)將E_j的第j列設(shè)為1；

(8)end for；

(9)

(10)

(11)T＝T-ρ_IT_I；

(12){E_k},{ρ_k}＝最大行分解算法(T)。