This shows you the differences between two versions of the page.

Link to this comparison view

en:projects:details:phd03 [2010/11/16 12:02]
en:projects:details:phd03 [2016/06/23 11:26]
Line 1: Line 1:
----- dataentry project ---- 
-title : Subtree-based bounds and simulation-based estimations for the partition function 
-contactname:​ Prof. Amin Shokrollahi 
-contactmail_mail:​ amin.shokrollahi@epfl.ch 
-contacttel: 021 6937512 
-contactroom:​ BC 110 
-type : phd thesis 
-status : completed 
-table : projects 
-created_dt : 2003-01-01 
-taken_dt : 
-completed_dt : 2007-01-01 
-by : Mehdi Molkaraie 
-output_media400 : en:​projects:​mehdi_thesis.pdf|Download Mehdi'​s Thesis 
-=== Abstract: === 
-Many different algorithms developed in statistical physics, coding theory, signal processing, ​ 
-and artificial intelligence can be expressed by graphical models and solved (either exactly or  
-approximately) with iterative message-passing algorithms on the model. One quantity of 
- ​interest in these algorithms is the partition function. In graphical models without cycle (trees), ​ 
-the partition function can be computed efficiently by means of message-passing algorithms, ​ 
-like GDL or the sum-product algorithm. In contrast, when graphical models contain cycles, ​ 
-the computation of the partition function is in general intractable. Our contributions in this  
-dissertation are: deriving deterministic upper and lower bounds on partition function, and  
-developing methods to approximate this quantity with Monte Carlo methods. Specifically,​ we  
-obtain subtree-based upper and lower bounds which lead to theoretical results on optimality ​ 
-properties of the minimum entropy sub-tree and finally lead to a greedy algorithm. At last, we 
- ​introduce and analyze a number of estimators that use Gibbs sampling to draw samples from  
-different target distributions to estimate the value of the partition function. In one estimator, we  
-demonstrate a novel strategy which combines Gibbs sampling and message-passing algorithms 
- on trees.