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

在審

• 申請(qǐng)?zhí)枺?/td>: 201710175349.2
• 申請(qǐng)日: 2017-03-22
• 公開(kāi)（公告）號(hào): CN107220709A
• 公開(kāi)（公告）日: 2017-09-29
• 發(fā)明（設(shè)計(jì)）人: 董建武;何躍鷹;卓子寒;劉中金;李佳;方喆君;趙忠華
• 申請(qǐng)（專利權(quán)）人: 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心
• 主分類號(hào): G06N7/00
• 分類號(hào): G06N7/00
• 代理公司: 北京國(guó)坤專利代理事務(wù)所(普通合伙)11491
• 代理人: 姜彥

1.一種概率圖模型的近似推理算法，其特征在于：首先利用分離算法選擇有效的k-叉環(huán)不等式約束；然后將這些k-叉環(huán)不等式約束對(duì)應(yīng)的環(huán)組合到一個(gè)平面子圖上，并逐次添加到對(duì)偶子問(wèn)題中；最后通過(guò)優(yōu)化對(duì)偶問(wèn)題來(lái)求解原推理問(wèn)題；

假設(shè)由分離算法得到m個(gè)環(huán)，記為C₁,C₂,...,C_m；遍歷每個(gè)環(huán)C_i，記錄環(huán)C_i中每個(gè)節(jié)點(diǎn)的狀態(tài)劃分；如果C_i的某個(gè)節(jié)點(diǎn)的狀態(tài)劃分和之前的環(huán)不一致，則不組合環(huán)C_i至當(dāng)前BPSP，同時(shí)，利用平面圖判定算法檢驗(yàn)增加環(huán)C_i至BPSP是否會(huì)導(dǎo)致當(dāng)前BPSP變?yōu)榉瞧矫鎴D，若是，不組合環(huán)C_i至當(dāng)前BPSP；

考慮任意一節(jié)點(diǎn)p，其變量取值記為X_p(X_p∈{1,2,...,K})；假設(shè)邊(p,q)的變量取值為X_p＝u,X_q＝v，記(S₁,S₂)分別為節(jié)點(diǎn)(p,q)的狀態(tài)空間子集，即同時(shí)假設(shè)利用平面子圖選擇準(zhǔn)則逐次構(gòu)造了N個(gè)平面子圖，考慮所有這些平面子圖，并將所有平面子圖中邊(p,q)的狀態(tài)空間子集的集合記為A；記

Spq;uv={(S1,S2):(S1,S2)∈A,(u∈S1)⊕(v∈S2)}]]>

在所有的平面子圖中，將邊(p,q)的狀態(tài)空間劃分為(S₁,S₂)的平面子圖集合表示為：

針對(duì)第k個(gè)平面子圖，定義一個(gè)示性函數(shù)：

X^pqk=(Xpk∈Spk)⊕(Xqk∈Sqk)]]>

其中為第k個(gè)平面子圖中節(jié)點(diǎn)p的狀態(tài)取值；

類似地，定義樹(shù)狀子圖的示性函數(shù)：

X^pq;S1S2t=(Xpt∈S1)⊕(Xqt∈S2)]]>

其中為節(jié)點(diǎn)p在樹(shù)狀子圖t中的狀態(tài)取值；

將一個(gè)網(wǎng)格MRF分解為“行”、“列”樹(shù)狀子圖{t}和若干平面子圖{k}，對(duì)偶目標(biāo)函數(shù)為：

max{θt,θk}min{Xt,Xk}Σt(ΣpΣuθp;utXp;ut+Σ(p,q)Σ(u,v)θpq;uvtXp;utXq;vt)+Σk(Σ(p,q)Σ(u,v)θpq;uvtXp;utXq;vt)]]>

s.t.Σtθp;ut=θp;u,∀p∈Vθpq;uvt+Σkθpq;uvk=θpq;uv,∀pq∈E]]>

利用平面子圖選擇準(zhǔn)則增加平面子圖，每增加一個(gè)平面子圖，優(yōu)化上述目標(biāo)函數(shù)。