[發(fā)明專利]GPU上的基于邊著色與信息更新率優(yōu)化的置信傳播方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010940904.8
• 申請(qǐng)日: 2020-09-09
• 公開（公告）號(hào): CN112257866A
• 公開（公告）日: 2021-01-22
• 發(fā)明（設(shè)計(jì)）人: 侯駿騰;王樹鵬;吳廣君;張磊;孫嘉偉
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06N5/04
• 分類號(hào): G06N5/04;G06T1/20
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 司立彬

1.一種GPU上的基于邊著色的置信傳播方法，其步驟包括：

1)將需要處理的概率圖數(shù)據(jù)G(V,E,Ψ)加載到設(shè)備內(nèi)存中；其中V為概率圖的頂點(diǎn)集，E為概率圖的邊集，Ψ為概率集，包括概率圖中每個(gè)頂點(diǎn)取不同標(biāo)記的概率值和每條邊對(duì)應(yīng)的轉(zhuǎn)移概率值；每個(gè)頂點(diǎn)v_i對(duì)應(yīng)于集合中的一個(gè)離散隨機(jī)變量X_i，n為頂點(diǎn)總數(shù)，X_i∈A_i，A_i為有限標(biāo)簽集；每一條邊(v_i,v_j)對(duì)應(yīng)于兩個(gè)頂點(diǎn)v_i和v_j上變量不同取值之間的概率關(guān)系；設(shè)置判斷信息是否收斂的閾值ξ以及置信傳播結(jié)束計(jì)算的時(shí)間閾值T_ξ；

2)初始化信息變量數(shù)組M及其緩沖變量數(shù)組M’均為0，為每個(gè)線程分配一個(gè)邊信息計(jì)算任務(wù)，計(jì)算每個(gè)邊上的信息值并記錄到變量數(shù)組M中；第一次迭代時(shí)根據(jù)變量數(shù)組M當(dāng)前值和M’中的初始值，計(jì)算第一次迭代時(shí)每條邊上的信息殘差R；然后將變量數(shù)組M的值復(fù)制到變量數(shù)組M’中；后續(xù)每次迭代時(shí)進(jìn)行步驟3)～6)；

3)用E_color表示邊的color值，每條邊的color值初始化為對(duì)應(yīng)邊的ID；

4)為每個(gè)線程分配一個(gè)邊任務(wù)，線程根據(jù)分配的邊e_i,j任務(wù)，遍歷以該邊e_i,j的起點(diǎn)v_i為終點(diǎn)的邊e_k,i及以該邊e_i,j的終點(diǎn)v_j為起點(diǎn)的邊e_j,l；如果邊e_k,i或邊e_j,l的信息殘差值大于邊e_i,j的信息殘差值，則將邊e_i,j的color值設(shè)為信息殘差值更大的邊的ID；

5)為每個(gè)線程分配一個(gè)邊任務(wù)，如果邊的color值與該邊的ID相同，則更新該邊的信息值，并將更新結(jié)果記錄到變量數(shù)組M中；

6)根據(jù)變量數(shù)組M、緩沖變量數(shù)組M’中的信息，計(jì)算當(dāng)前迭代時(shí)每條邊上的信息殘差R；然后將變量數(shù)組M的值復(fù)制到變量數(shù)組M’中；M’用于保存上次迭代得到的信息值；

7)根據(jù)當(dāng)前信息殘差R與預(yù)設(shè)的閾值判斷是否結(jié)束計(jì)算：如果每條邊的信息殘差R均小于閾值ξ，則結(jié)束計(jì)算，跳轉(zhuǎn)到步驟8)；或者如果信息殘差R中小于閾值ξ的變量數(shù)趨于穩(wěn)定，則結(jié)束計(jì)算，跳轉(zhuǎn)到步驟8)；如果執(zhí)行時(shí)間大于或等于時(shí)間閾值T_ξ，則結(jié)束計(jì)算，跳轉(zhuǎn)到步驟8)；否則繼續(xù)進(jìn)行迭代計(jì)算；

8)根據(jù)最終計(jì)算所得的邊的信息值計(jì)算出每個(gè)頂點(diǎn)取不同變量時(shí)的概率值，即每個(gè)頂點(diǎn)的置信度。

2.如權(quán)利要求1所述的方法，其特征在于，按照公式計(jì)算或更新每個(gè)邊上的信息值m_i→j；按照公式計(jì)算第t次迭代時(shí)邊e_i,j上的信息殘差其中，x_i為變量X_i的一個(gè)取值，x_i所對(duì)應(yīng)的一元?jiǎng)莺瘮?shù)ψ_i(x_i)表示為x_i、x_j之間的二元?jiǎng)莺瘮?shù)ψ_i,j表示為x_j為變量X_j的一個(gè)取值，X_j∈A_j，A_j為有限標(biāo)簽集；Γ_i表示頂點(diǎn)v_i的鄰接頂點(diǎn)。

3.如權(quán)利要求2所述的方法，其特征在于，根據(jù)公式計(jì)算頂點(diǎn)v_i取不同變量時(shí)的概率值。