相信度網路L-S演算法平行處理之研究

L-S Parallel Algorithm for Computating Probability in Belief Network

吳復強(Ful-Chiang Wu)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(1992年)

摘要

在無向性圖形上處理機率計算的問題是運用網路圖形結構中所涵蓋的
馬可夫性質，去做一連串局部的運算來減少計算過程。建立在類似無向圖
形結構-Triangulated graph上的演算法(L-S演算法) 能迅速有效的計算
大型稀疏網路的機率計算問題。基本上此演算是透過局部的表示之間的轉
換，運用triangulated graph中所含有的running intersection
property來吸收和傳導資迅。隨著平行處理技術和平行計算機的出現和發
展，為平行計算機上求解問題(即平行計算)創造了條件。在相信度網路上
解決機率計算的問題，利用平行計算的方式，將可達到更高的效率。本論
文的研究目的在於分析無向演算法平行處理之可行性，並且設計出平行處
理的方式，同時做平行演算法計算複雜度的分析。

關鍵字

相信度網路 ； 馬可夫性質 ； 最大鄰接點搜尋法 ； 平行處理

並列摘要

The purpose of the search is to design a parallel algorithm on
probability computations in belief networks and analyze its
computational complexity. Our study will aim at Lauritzen and
Spiegelhalter's algorithm(undirected mathod). Ross D. Shachter'
s algorithm(directed method) does not fit parallel concept
because it requires creation of barren nodes sequentially.
Pearl's algorithm(directed method) on the case of singly
connected network is well fit to parallel idea,but the
undirected method is aeneralization of his idea and useful for
general sparse networks. Pearl and Shachter proposed the idea
"cut set conditioning" to solve general sparse network but they
didn't discuss algorithmically how to obtain cut sets and
combine computed probabilities with cut sets. The idea is used
by viewing the graphical structure case by case. In this
search, we found that the only graphical operation in
undirected method which can't be parallelized is maximum
cardinality search of which the whole steps must keep in
sequential order. The computational complexity using parallel
concept for all graphical operation of undirected method is
thus O(|V|^2),where |V| is the total number of nodes in a
network. The probability computation is O(maximum clique size)
provided that there are enough parallel processors. We also
present simulation results for the distributions of cliques in
general sparse belief networks,which can be used as a reference
to see what the average time a parallel algorithm will take for
probability computations.

並列關鍵字

Belief network ； Markov property ； Maximum cardinality search ； Parallel processing