擴散過程(diffusion process)以及可信度傳遞推論演算法(belief propagation)在分散式計算系統上的比較

簡易檢索 / 詳目顯示

回結果列表

研究生：	蘇俊成 Jiun-cheng Su
論文名稱：	擴散過程(diffusion process)以及可信度傳遞推論演算法(belief propagation)在分散式計算系統上的比較 The Comparison of Diffusion Process and Belief Propagation on Distributed Computation
指導教授：	鮑興國 Hsing-Kuo Kenneth Pao
口試委員:	李育杰 Yuh-Jye Lee 陳素雲 Su-Yun Huang 張源俊 Yuan-chin Ivan Chang
學位類別：	碩士 Master
系所名稱：	電資學院 - 資訊工程系 Department of Computer Science and Information Engineering
論文出版年：	2008
畢業學年度：	97
語文別：	英文
論文頁數：	57
中文關鍵詞：	隨機漫步、機率圖形模型、馬可夫隨機場、可信度傳遞推論演算法、調和函數、擴散過程
外文關鍵詞：	diffusion process, harmonic function, random walk, probabilistic graphical models, Markov random field, belief propagation
相關次數：	點閱：301 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

擴散過程的概念來自於物理問題以及可信度傳遞推論演算法來自於處理機率圖形模型(probabilistic graphical models)的問題。這兩種方法被廣泛的利用來處理分散式計算系統。在某些情形下，計算非線性或耗費時間的問題時，我們需要利用區域性(locally)以及分散的計算方式來求解完整的答案。舉例來說，影像去雜訊(image restoration)的問題可以利用分散式計算來處理。在這例子之下，影像中每一個像素被視為在一個圖形上的節點，經由計算每一節點以及它鄰近點間相互關係的過程，可以把一張雜訊影像轉換成較清晰的結果。考量到分散式計算的重要性，然而卻不容易找到全面性以及完整探討這兩方法的資料。因此論文主要目的為探討這兩種方法的關係，主要內容可分為以下三個部分。第一部分，我們會簡介以下分散式計算的方法，包含有：擴散過程、隨機漫步(random walk)、能量最小化(energy minimization)、max-product演算法以及sum-product演算法。我們將會探討以上演算法的等價關係。舉例來說，由於max-product以及擴散過程(或是隨機漫步)都是找尋最大機率配置(most probable configuration)的演算法，因此在某些假設下這兩演算法會有相同的結果。我們也會強調能量最小化的能量方程式的功用，Hard constraint以及soft constraint的問題可視為在此方法上的特例。最後，我們會比較以上分散式演算法的等價關係。某些情況會特別去討論到，包含：
如果圖形結構存在迴圈情況、或是勢能函式(potential function)設定為非高斯(non-Gaussian)的形式等情形。我們將會大部分使用影像去雜訊問題作為我們比較以上方法的例子。

Diffusion process from physics and belief propagation from probabilistic graphical models are among two of the most popular methods for distributed computation. In many cases, we need the computation distributed locally in small area so that some tough nonlinear or time-consuming computational problems can be solved as a whole. For instance, we can solve image restoration problem by distributed computation. In the system, a pixel is represented by a node and the noisy image can be restored to a clearer version by the computation involving (only) interactions between neighboring nodes/pixels. Considering the importance of distributed computation, we do not easily find comprehensive and all-in-one materials that discuss all the related topics. The thesis is therefore in three folds. First, we would like to give a friendly introduction to many of the distributed computation methods, including diffusion, random walk, energy minimization, max-product “belief propagation” and sum-product “belief propagation”. We will go through some basic facts including some equivalence statements. For instance, the max-product is equivalent to diffusion process and random walk under some assumptions because all of them try to find the most probable configuration given the evidence. Also, we emphasize a formulation via energy minimization where many of the algorithms such as hard constraint or soft constraint problems can be represented as special cases of the formulation. Finally, we empirically compare between those related algorithms when the assumptions to guarantee equivalence fail. Especially, some cases will be discussed, the structure containing loops, the potential functions not equal to Gaussian, etc. We will concentrate on the problem of image restoration in our comparison.

Introduction
1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 The Labeling Problem . . . . . . . . . . . . . . . . . . . . 2
3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . 4

Diffusion Process and Random Walk
1 Diffusion Process and Energy Function . . . . . . . . . . . 6
1.1 Diffusion Process and a Simple Simulation . . . . . 6
2 Diffusion process via Energy Minimization . . . . . . . . . 10
2.1 Energy Minimization by Matrix Inversion . . . . . 10
2.2 Hard Constraint and Soft Constraint Problems . . . 12
3 Related to Random Walk . . . . . . . . . . . . . . . . . . . 13
3.1 Random Walk and Markov Chain . . . . . . . . . . 13
3.2 Matrix Inversion and Random Walk . . . . . . . . . 14
3.3 Tuning the Parameter alpha . . . . . . . . . . . . . . . 17

Graphical Models and Belief Propagation
1 Markov Random Field . . . . . . . . . . . . . . . . . . . . 21
2 Probabilistic Inference . . . . . . . . . . . . . . . . . . . . 23
3 Sum-product Algorithm . . . . . . . . . . . . . . . . . . . 26
3.1 The Elimination Algorithm . . . . . . . . . . . . . 27
3.2 Sum-product Algorithm . . . . . . . . . . . . . . . 28
4 Max-product Algorithm . . . . . . . . . . . . . . . . . . . 32
5 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

The Link between Random Walk and Belief Propagation
1 Random walk and Max-product Algorithm on Tree Graphs 36
1.1 The Equivalent Results of Random Walk and Max-product
            Algorithm on Tree Graphs . . . . . . . . . 37
1.2 The Difference of Random Walk and Belief Propagation
            Algorithms . . . . . . . . . . . . . . . . . . . 38
1.3 Summary and Questions . . . . . . . . . . . . . . . 39
2 The Equivalence of Random Walk and Belief Propagation
      on Loopy Graphs . . . . . . . . . . . . . . . . . . . . . . . 40
3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Experimental Results
1 Sum-product and Max-product on Image Restoration . . . 44
2 Gaussian Belief propagation and Laplace Belief Propagation
      in Image Restoration . . . . . . . . . . . . . . . . . . 50

Conclusion and Future Work
1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 55

                                

[1] C. M. Bishop. Pattern Recognition and Machine Learning. Springer,
2006.

[2] D. Comaniciu and P. Meer. Mean shift: A robust approach toward
feature space analysis. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 2002.

[3] J. Crank. The Mathematics of Diffusion. Clarendon Press, 1979.

[4] P. G. Doyle and J. L. Snell. Random walks and electric networks.
Arxiv preprint math, 2000.

[5] R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Biological se-
quence analysis. Cambrige university, 1998.

[6] P. F. Felzenszwalb and D. P. Huttenlocher. E±cient belief propaga-
tion for early vision. IJCV, 2006.

[7] S. Geman and D. Geman. Stochastic relaxation, gibbs distributions,
and the bayesian restoration of images. IEEE Trans, 1984.

[8] M. I. Jordan. An introduction to probabilistic graphical models. in
preparation.

[9] M. I. Jordan and Y. Weiss. Graphical models: Probabilistic inference.
The Handbook of Brain Theory and Neural Networks, 2nd edition,
2002.

[10] J. G. Kemeny and J. L. Snell. Finite Markov Chain. Springer-Verlag,
1976.

[11] S. Z. Li. Markov Random Field Modeling in Image Analysis`.
Springer, 2001.

[12] L. Lovasz. Random walks on graphs: a survey. Combinatorics, 1993.

[13] C. D. Meyer. Matrix Analysis and Applied Linear Algebra. Siam,
2000.

[14] B. Mohar. Some applications of laplace eigenvalues of graphs. Graph
Symmetry: Algebraic Methods and Applications book, 1997.

[15] H.-K. Pao. A Continuous Model for Salient Shape Selection and Rep-
resentation. PhD thesis, New York University, 2001.

[16] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference. Morgan Kaufmann, 1988.
[17] J. Sun, H. Y. Shum, and N. N. Zheng. Stereo matching using belief
propagation. PAMI, 2003.

[18] Y. Weiss and W. T. Freeman. Correctness of belief propagation in
Gaussian graphical models of arbitrary topology. 2001.

[19] Y. Weiss and W. T. Freeman. On the optimality of solutions of the
max-product belief propagation algorithm in arbitrary graphs. IEEE
Transactions on Information Theory, 2001.

[20] E. C. Zachmanoglou and D. W. Thoe. Introduction to Partial Equa-
tions with Applications. The Williams and Wilkins, 1976.

簡易檢索 / 詳目顯示

相關論文