Describe Main/SS09_GraphicalModels here.
== Vorlesung "Einführung in Graphische Modelle" (Introduction to Graphical Models) ==

''lecture slides are in English''

 ||<(^|2> '''Vorlesung:''' || Dienstag 14.00-16.00 ||<^|6> {{attachment:bn.png|Bayesian Planning|width=190}} ||
 || FR-6535 ||
 ||<(^|2> '''Übung:''' || Dienstag 16.00-18.00 ||
 || FR-4061 ||
 ||<(^|2>'''Dozenten:''' || [[http://user.cs.tu-berlin.de/~mtoussai|Dr. Marc Toussaint]], [[http://user.cs.tu-berlin.de/~brefeld|Dr. Ulf Brefeld]] ||
 || [[http://user.cs.tu-berlin.de/~lang|Tobias Lang]] (Übung)||




=== Inhalt ===

Graphische Modelle definieren Warscheinlichkeitsfunktionen
auf gekoppelten Variablen. Die gerichtete oder ungerichtete Graphstruktur erlaubt somit
eine sehr flexible Modellierung von Variablen (=Knoten) und
Anhängigkeiten zwischen Variablen (=Kanten).

In den letzten Jahren wurden eine Reihe sehr mächtiger Inferenzalgorithmen (z.B. Viterbi
Algorithmus, Junction Tree Algorithmus) entwickelt, die es uns erlauben graphische
Modelle direkt für die Modellierung von natürlich auftretender
Problemstellungen zu nutzen. Sie werden beispielsweise in der Handlungsplanung von Robotern
und der maschinellen Sprach- und Bildverarbeitung erfolgreich eingesetzt. Desweiteren basieren viele
aktuelle Verfahren des maschinellen Lernens wie z.B. Hidden
Markov Models (HMM), Conditional Random Fields (CRFs) oder
Structured Support Vector Machines (SSVM) auf graphischen Modellen.

Die Vorlesung führt in die Grundlagen Graphischer Modelle ein und stellt sie anhand von praktischen
Beispielen aus den genannten Gebieten (Robotik, Sprach- und Bildverarbeitung) vor. Thematisch beginnen wir mit einfachen Bayesschen
Netzwerken, lernen dann verschiedene Inferenzmechanismen kennen und
leiten schliesslich aktuelle Lernverfahren wie HMMs, CRFs und SSVMs
her. Am Ende sollen die Teilnehmer in der Lage sein, beliebige
Problemstellungen mit Hilfe von graphischen Modellen zu kodieren
und zu lösen. 


=== Voraussetzungen ===

gute Mathematikkenntnisse; Statistikkenntnisse sind nützlich, aber nicht zwingend erforderlich.



=== Übung ===

Es gibt jede Woche ein Übungsblatt. Voraussetzung zur Teilnahme an der Prüfung am Semesterende ist die erfolgreiche Bearbeitung der Hälfte aller Übungsaufgaben. Erfolgreiche Bearbeitung bedeutet, dass es ersichtlich wird, dass man sich mit der Aufgabe auseinandergesetzt und die zugrundeliegenden Themen prinzipiell verstanden hat. Blätter sind einzeln zu bearbeiten. Zu Beginn jeder Übung ist auf einer Liste anzukreuzen, welche Aufgaben man bearbeitet hat. Unter den möglichen Kandidaten wird einer per Zufall bestimmt, der die Aufgabe an der Tafel vorrechnet. Falls man an der Teilnahme der Übung verhindert ist, kann man ausnahmsweise seine Bearbeitung in der Vorlesung zuvor abgeben.


=== Projekte ===
 * [[attachment:dialogProjekt.pdf|Projektskizze]] fuer eine '''Diplom/MSc-Arbeit'''

=== Schedule ===

 || '''Date''' || '''Topics''' || '''Slides''' || '''Excercises''' ||
 ||  21.04. || Intruduction and overview (motivation, random variables, conditional and joint probabilties, Bayes) || [[attachment:01.pdf|vl01]]  [[attachment:01_4up.pdf|vl01_4up]] || [[attachment:ex1.pdf|ex1]] ||
 ||  28.04. || (conditional) independence, Bayesian Networks, inference, examples || [[attachment:02.pdf|vl02]] [[attachment:02_4up.pdf|vl02_4up]] || [[attachment:ex2.pdf|ex2]]  ||
 ||  05.05. || Factor graphs, elimination algorithm, belief propagation || [[attachment:03.pdf|vl03]]  [[attachment:03_4up.pdf|vl03_4up]]  ||  [[attachment:ex3.pdf|ex3]] [[attachment:hmm.tgz|code]] ||
 ||  12.05. || Examples: HMMs, Markov Random Fields; building Junction Trees || [[attachment:04.pdf|vl04]]  [[attachment:04_4up.pdf|vl04_4up]] [[attachment:hmm-bin.tgz|code]] || [[attachment:ex4.pdf|ex4]]  ||
 ||  19.05. || Learning & Likelihood Maximization || [[attachment:05.pdf|vl05]]  [[attachment:05_4up.pdf|vl05_4up]]   || [[attachment:ex5.pdf|ex5]] ||
 || || ||  ||  ||
 ||  26.05. || HMMs, Forward-Backward, Viterbi, Expectation-Maximization, (Kernel-) Conditional Random Fields, Features || [[attachment:06.pdf|vl06]]  [[attachment:06_4up.pdf|vl06_4up]]  || [[attachment:ex6.pdf|ex6]] ||
 ||  09.06. || CRF optimization, structured Perceptron || [[attachment:07.pdf|vl07]]  [[attachment:07_4up.pdf|vl07_4up]] || [[attachment:ex7.pdf|ex7]]  [[attachment:esp.data2_10-40|data]] ||
 ||  16.06. || Perceptron, structured Support-Vektor-Maschinen (SSVMs) || [[attachment:08.pdf|vl08]]  [[attachment:08_4up.pdf|vl08_4up]]  || frei ||
 ||  23.06. || Structured Support-Vektor-Maschinen (SSVMs) || [[attachment:09.pdf|vl09]]  [[attachment:09_4up.pdf|vl09_4up]]  ||  [[attachment:ex9.pdf|ex9]]   ||
 || || ||  ||  ||
 ||  30.06. || Learning with missing data, Expectation Maximization || [[attachment:10.pdf|vl10]]  [[attachment:10_4up.pdf|vl10_4up]]  ||   [[attachment:ex10.pdf|ex10]]   ||
 ||  07.07. || Markov Decision Processes (MDPs), EM for optimal policies || [[attachment:11.pdf|vl11]]  [[attachment:11_4up.pdf|vl11_4up]] ||  [[attachment:ex11.pdf|ex11]]  ||
 || || || || ||
 ||  14.07. || Summary, open problems || [[attachment:12.pdf|vl12]] ||  ||

=== recommended reading ===

 * on inference in general:
  * [[http://user.cs.tu-berlin.de/~mtoussai/notes/belief-propagation.pdf|lecture notes on factor graphs and belief propagation]]
  * Bishop: [[attachment:bishop-chapter8.pdf|Chapter 8 of his book]], [[attachment:bishop-chapter8.pdf|corresponding lecture slides]]
  * !MacKay: [[http://www.inference.phy.cam.ac.uk/itprnn/book.html|Information Theory, Inference, and Learning Algorithms]]

 * on Bayes rule and Bayesian networks:
  * Bayes Rule: [[http://www.cs.ubc.ca/~murphyk/Bayes/bayesrule.html]]
  * [[http://www.cs.ubc.ca/~murphyk/Bayes/Charniak_91.pdf|Charniak: "Bayesian Networks without Tears"]]

 * related lectures:
  * Kevin Murphy's lecture: [[http://www.cs.ubc.ca/~murphyk/Teaching/CS532c_Fall04/Lectures/index.html]], his notes on Bayes etc [[http://www.google.de/search?q=site:www.cs.ubc.ca/~murphyk/Bayes]]
  * Max Welling's class notes [[http://www.ics.uci.edu/~welling/classnotes/classnotes.html]]
  * Chris Williams' PRM lecture: [[http://www.inf.ed.ac.uk/teaching/courses/pmr/]]
  * Zoubin Ghahramani's tutorials and teaching material: [[http://learning.eng.cam.ac.uk/zoubin/]]

 * on learning:
  * [[http://research.microsoft.com/apps/pubs/default.aspx?id=69588|Heckerman: A Tutorial on Learning With Bayesian Networks]]
  * [[http://learning.eng.cam.ac.uk/zoubin/bayesian.html|Zoubin Ghahramani: Bayesian Machine Learning]]
  * Davis and Jones, ML Estimation for the Multinomial Distribution, Teaching Statistics 14(3), 1992 [[http://www3.interscience.wiley.com/cgi-bin/fulltext/119984860/PDFSTART]]

 * software:
  * inference software: [[http://user.cs.tu-berlin.de/~mtoussai/links.html]] and [[http://www.stat.duke.edu/courses/Spring99/sta294/sw.html]]
  * [[http://www.cs.cmu.edu/~javabayes/Home/|JavaBayes software]] -- directly test the [[http://www.cs.cmu.edu/~javabayes/Home/applet.html|online java applet]]