[發明專利]一種GPU上的基于著色優化的置信傳播方法

在審

• 申請號: 202010940174.1
• 申請日: 2020-09-09
• 公開（公告）號: CN112257865A
• 公開（公告）日: 2021-01-22
• 發明（設計）人: 侯駿騰;王樹鵬;吳廣君;張磊;孫嘉偉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06N5/04
• 分類號: G06N5/04;G06T1/20
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

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

1)將需要處理的概率圖數據G(V,E,Ψ)加載到設備內存中；其中V為概率圖的頂點集，E為概率圖的邊集，Ψ為概率集，包括概率圖中每個頂點取不同標記的概率值和每條邊對應的轉移概率值；每個頂點v_i對應于集合x中的一個離散隨機變量X_i，x＝{X₁,X₂,…,X_n}，n為頂點總數，X_i∈A_i，A_i為有限標簽集；每一條邊(v_i,v_j)對應于兩個頂點v_i和v_j上變量不同取值之間的概率關系；設置每次著色操作的迭代次數C_n、判斷信息是否收斂的閾值ξ以及置信傳播結束計算的時間閾值T_ξ；

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

3)用V_color表示頂點的color值，每個頂點的color值初始化為對應頂點的ID；用V_wave表示頂點的wave值并初始化為0，用E_wave表示邊上的wave值并初始化為0；

4)為每個線程分配一個邊信息計算任務，計算對應邊上的信息值并記錄到變量數組M中；

5)為每個線程分配一個頂點v_i任務，將當前頂點v_i的頂點殘差初始化為0，然后遍歷以該頂點v_i為終點的邊，如果該邊上的信息殘差大于該頂點v_i的頂點殘差，則將其賦值給頂點v_i的頂點殘差；

6)根據頂點殘差進行C_n次迭代的著色操作：為每個線程分配一個頂點v_i任務，遍歷以該頂點v_i為終點的邊e_j,i，如果邊e_j,i的起點v_j的頂點殘差大于頂點v_i的頂點殘差，則將頂點v_j的ID賦值給頂點的color值，更新頂點v_i的wave值為頂點v_j的wave值加1、邊e_j,i的wave值為頂點v_i的wave值；此過程迭代進行C_n次，完成C_n次迭代著色操作；

7)先按邊的wave值倒序對邊的信息值進行更新，然后按邊的wave值正序對邊的信息值進行更新；

8)根據變量數組M、緩沖變量數組M’中的信息，計算當前迭代時每條邊上的信息殘差R；然后將變量數組M的值復制到變量數組M’中；M’用于保存上次迭代得到的信息值；

9)根據當前信息殘差R與預設的閾值判斷是否結束計算：如果每條邊的信息殘差R均小于閾值ξ，則結束計算，跳轉到步驟10)；或者如果信息殘差R中小于閾值ξ的變量數趨于穩定，則結束計算，跳轉到步驟10)；如果執行時間大于或等于時間閾值T_ξ，則結束計算，跳轉到步驟10)；否則繼續進行迭代計算；

10)根據最終計算所得的邊的信息值計算出每個頂點取不同變量時的概率值，即每個頂點的置信度。