Markov models on graphs represent a model class widely applied in many areas of computer science, such as computer networks, data security, robotics and pattern recognition. The first part of the course covers inference and learning for Markov models on chains and trees. All these tasks including structure learning can be solved by efficient algorithms. The second part addresses graphical models on general graphs. Here on the contrary, practically all inference and learning tasks are NP-complete. The focus is therefore on efficient approximative algorithms.

**18.01.12**Written exam is corrected**06.12.11**Exam date: Thursday, January 12, 9:15-10:45, room G205**15.11.11**Doodle poll exam date**15.11.11**Seminar on Wednesday 16.11. is moved to 9:15-10.45, G205

**Teacher:**Boris Flach web-page**Prerequisites:**Basics of probability theory, graphs and graph algorithms**Time and Location:**lectures: Mon, 14:30, E-127, seminars: Wed, 16:15, E-128**Course format:**(2/1/1)**Lectures:**See here for the syllabus**Seminars:**Exercises/Assignments will be provided here prior to every seminar. Students are expected to deal with these, trying to solve them before the seminar. Solutions will be discussed at the seminar.**Lab project:**Projects will be done in teams of 2 or 3 students. Each team can choose an application from a list provided at the begin of the semester.Each of these apps can (and should) be solved by modeling an appropriate (hidden) Markov model on a chain. Students are expected to code the core inference and learning algorithms from the scratch in C/C++ or Java. On the other hand, any available Open Source software can be used for the infrastructure/environment part. Finally, each group has to present its results at an presentation and competition session organized at the end of the semester.**Grading/Credits:**- Lab project (50% = Written report 30% + Oral presentation 20%)
- Written exam (50%) example
- 6 CP

**Textbooks and References:**- Michail I. Schlesinger, Vaclav Hlavač, Ten Lectures on Statistical and Structural Pattern Recognition [Schlesinger-TLPR2002]
- Stan Z. Li, Markov Random Field Modeling in Image Analysis [Li-MRFIA2009]
- Daphne Koller, Nir Friedman, Probabilistic Graphical Models Principles and Techniques [Koller-PGM2009]
- Christopher M. Bishop, Pattern Recognition and Machine Learning (for additional reading) [Bishop-PRML2006]
- Gerhard Winkler, Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction (for additional reading) [Winkler-IARF2006]
- A web-page with links to some tutorials at upenn