Approximate inference in Graphical Models

Taken by: Bogdan Stroe
Completed by: Bogdan Stroe

Graphical Models are unifying framework for inference and learning for different applications such as Bioinformatics, speech processing, image processing, coding, and control theory. Many methods have been proposed for exact and approximate inference in graphical models. However, in most cases the exact inference is intractable and therefore the approximate inference methods are the focus of research in this area. One class of of approximate inference method is based on Linear and semidefinite programming relaxation of the problem. The aim of this project is to study and implement this method for general graphical models. Furthermore, the student should assess the performance, of this method on different datasets. The proportion of theoretical and empirical (programming, simulation) work in this project is 50-50 percent.


  • Good familiarity with probability theory
  • Strong programming skills
  • Familiarity with graph algorithms

What will you learn

  • Learning and Inference in Graphical Models
  • Semidefinite Programming (SDP)
  • Second-Order Cone Programming (SOCP)
  • Fast implementation of inference algorithms for graphical models
  • Using and interfacing to existing efficient solvers

Suggested Readings and References