Differences between revisions 24 and 122 (spanning 98 versions)
⇤ ← Revision 24 as of 2009-03-27 22:49:04 →
Size: 2976
Editor: TobiasLang
Comment:
← Revision 122 as of 2009-06-30 09:45:57 → ⇥
Size: 6386
Editor: MarcToussaint
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:
 ||<(^|2> '''Vorlesung:''' || Dienstag 14.00-16.00 ||  ||<(^|2> '''Vorlesung:''' || Dienstag 14.00-16.00 ||<^|6> {{attachment:bn.png|Bayesian Planning|width=190}} ||
Line 8: Line 8:
 ||<(^|2>'''Dozenten:''' || [[http://user.cs.tu-berlin.de/~brefeld|Dr. Ulf Brefeld]], [[http://user.cs.tu-berlin.de/~mtoussai|Dr. Marc Toussaint]] ||  ||<(^|2>'''Dozenten:''' || [[http://user.cs.tu-berlin.de/~mtoussai|Dr. Marc Toussaint]], [[http://user.cs.tu-berlin.de/~brefeld|Dr. Ulf Brefeld]] ||
Line 10: Line 10:

Line 15: Line 17:
auf gerichteten/ungerichteten Graphen und erlauben somit
die explizite Modellierung von Variablen (=Knoten) und
Korrelationen zwischen Variablen (=Kanten).		 auf gekoppelten Variablen. Die gerichtete oder ungerichtete Graphstruktur erlaubt somit
eine sehr flexible Modellierung von Variablen (=Knoten) und
Anhängigkeiten zwischen Variablen (=Kanten).
Line 19: Line 21:
Zusammen mit einer mächtigen Inferenzmaschinerie (z.B. Viterbi
Algorithmus, Junction Tree Algorithmus) erlauben graphische
Modelle die direkte Modellierung von natürlich auftretenden
Problemstellungen. Sie werden beispielsweise in der Handlungs-
planung von Robotern, und der maschinellen Sprach- und Bild-
verarbeitung erfolgreich eingesetzt. Desweiteren basieren viele		 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
Line 29: Line 30:
Die Vorlesung stellt graphische Modelle anhand von praktischen
Beispielen aus den genannten Gebieten (Robotik, Sprach- und Bild-
verarbeitung) vor. Thematisch beginnen wir mit einfachen Bayesschen		 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
Line 34: Line 34:
her. Am Ende sollen die Teilnehmer in der Lage sein beliebige her. Am Ende sollen die Teilnehmer in der Lage sein, beliebige
Line 41: Line 41:
gute Mathematikkenntnisse; Statistikkenntnisse sind nützlich aber nicht zwingend erforderlich. gute Mathematikkenntnisse; Statistikkenntnisse sind nützlich, aber nicht zwingend erforderlich.
Line 43: Line 43:


=== Ü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'''
Line 46: Line 55:
 || '''Datum''' || '''Beschreibung''' ||
 || 21.04. || Einführung mit Überblick ||
 || || ||
 || 28.04. || Diskrete Wahrscheinlichkeitsverteilungen, Bedingte und Gesamtwahrscheinlichkeiten, Graphische Modelle, Faktorgraphen ||
 || 05.05. || Inferenz, Eliminierungsalgorithmus, Evidenzen ||
 || 12.05. || Summen-Produkt-Algorithmus, Junction Tree Alg. (JTA) ||
 || 19.05. || Beliefpropagierung in zyklischen Graphen, Mean-Field Alg. ||
 || || ||
 || 26.05. || Hidden Markov Models (HMMs), Forward-Backward Alg., Viterbi, Expectation-Maximization (EM) ||
 || 02.06. || Bedingte Wahrscheinlichkeiten, (Kernel-) Conditional Random Fields (k-CRFs), Features, Optimierung ||
 || 09.06. || Optimierung (Fortsetzung), Strukturiertes Perzeptron ||
 || || ||
 || 16.06. || Strukturierte Support-Vector Maschinen (S-SVMs) ||
 || 23.06. || Influence Diagramme ||
 || 30.06. || Markov Decision Processes (MDPs) ||
 || 07.07. || Inferenz für Planen, Optimale Handlungsanweisungen (Policies) ||
 || || ||
 || 14.07. || Zusammenfassung und Fragestunde ||		  || '''Datum''' || '''Beschreibung''' || Vorlesung || Übung ||
 || 21.04. || Einführung mit Überblick (Motivation, Zufallsvariablen, Bedingte und Verbundwahrscheinlichkeit, Bayes) || [[attachment:01.pdf|vl01]] [[attachment:01_4up.pdf|vl01_4up]] || [[attachment:ex1.pdf|ex1]] ||
 || 28.04. || (konditionale) Unabh&auml;ngigkeit, Bayesische Netzwerke, Inferenz, Beispiele || [[attachment:02.pdf|vl02]] [[attachment:02_4up.pdf|vl02_4up]] || [[attachment:ex2.pdf|ex2]] ||
 || 05.05. || Faktorgraphen, Eliminierungsalgorithmus, Belief Propagation || [[attachment:03.pdf|vl03]] [[attachment:03_4up.pdf|vl03_4up]] || [[attachment:ex3.pdf|ex3]] [[attachment:hmm.tgz|code]] ||
 || 12.05. || Beispiele: 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. || Lernen & 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-Optimierung, Strukturiertes Perzeptron || [[attachment:07.pdf|vl07]] [[attachment:07_4up.pdf|vl07_4up]] || [[attachment:ex7.pdf|ex7]] [[attachment:esp.data2_10-40|data]] ||
 || 16.06. || Perzeptron, Strukturierte Support-Vektor-Maschinen (SSVMs) || [[attachment:08.pdf|vl08]] [[attachment:08_4up.pdf|vl08_4up]] || frei ||
 || 23.06. || Strukturierte 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 || || ||
 || 07.07. || Markov Decision Processes (MDPs), EM für optimale Handlungsanweisungen (Policies) || || ||
 || || || || ||
 || 14.07. || Zusammenfassung und Fragestunde || || ||

=== extra material ===

 * [[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]]

=== web material ===

 * 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"]]
 * [[http://research.microsoft.com/apps/pubs/default.aspx?id=69588|Heckerman: A Tutorial on Learning With Bayesian Networks]]
 * Kevin'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]]
 * inference software: [[http://user.cs.tu-berlin.de/~mtoussai/links.html]] and [[http://www.stat.duke.edu/courses/Spring99/sta294/sw.html]]
 * Max Welling's class notes [[http://www.ics.uci.edu/~welling/classnotes/classnotes.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]]
 * Davis and Jones, ML Estimation for the Multinomial Distribution, Teaching Statistics 14(3), 1992 [[http://www3.interscience.wiley.com/cgi-bin/fulltext/119984860/PDFSTART]]

Describe Main/SS09_GraphicalModels here.

Vorlesung "Einführung in Graphische Modelle"

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

Termine

  • Datum

    Beschreibung

    Vorlesung

    Übung

    21.04.

    Einführung mit Überblick (Motivation, Zufallsvariablen, Bedingte und Verbundwahrscheinlichkeit, Bayes)

    vl01 vl01_4up

    ex1

    28.04.

    (konditionale) Unabhängigkeit, Bayesische Netzwerke, Inferenz, Beispiele

    vl02 vl02_4up

    ex2

    05.05.

    Faktorgraphen, Eliminierungsalgorithmus, Belief Propagation

    vl03 vl03_4up

    ex3 code

    12.05.

    Beispiele: HMMs, Markov Random Fields; building Junction Trees

    vl04 vl04_4up code

    ex4

    19.05.

    Lernen & Likelihood Maximization

    vl05 vl05_4up

    ex5

    26.05.

    HMMs, Forward-Backward, Viterbi, Expectation-Maximization, (Kernel-) Conditional Random Fields, Features

    vl06 vl06_4up

    ex6

    09.06.

    CRF-Optimierung, Strukturiertes Perzeptron

    vl07 vl07_4up

    ex7 data

    16.06.

    Perzeptron, Strukturierte Support-Vektor-Maschinen (SSVMs)

    vl08 vl08_4up

    frei

    23.06.

    Strukturierte Support-Vektor-Maschinen (SSVMs)

    vl09 vl09_4up

    ex9

    30.06.

    Learning with missing data, Expectation Maximization

    07.07.

    Markov Decision Processes (MDPs), EM für optimale Handlungsanweisungen (Policies)

    14.07.

    Zusammenfassung und Fragestunde

extra material

web material

IDA Wiki: Main/SS09_GraphicalModels (last edited 2009-07-22 10:46:20 by MarcToussaint)