Block-Seminar: Kernels for Structured Data

Termine und Dozenten

Inhalt

In vielen Anwendungen des maschinellen Lernen sind die zu analysierenden Daten keine Vektoren, sondern Datenstrukturen wie Strings, Bäume und Graphen. Typische Beispiele sind DNA-Sequenzen in der Bioinformatik, Parsebäume in der Sprachverarbeitung und Graphen in der Chemoinformatik. Eine Möglichkeit zur Analyse dieser Daten bietet das Konzept des kernbasierten Lernen. Die Lernalgorithmen sind hierbei ausschließlich über Kernfunktionen definiert und können auf beliebigen Daten angewendet werden, wenn entsprechende Kernfunktionen zur Verfügung stehen.

Dieses Seminar beschäftigt sich mit Kernfunktionen für strukturierte Daten. Es sollen Kerne für Strings, Bäume und Graphen, ihre Implementierung und entsprechende Anwendungen besprochen werden.

Ablauf

• Die Vorbesprechung findet am 3.11.2010 statt.
• Die Teilnehmer wählen bis spätestens 10.11.2010 ein Thema in Absprache mit dem Betreuer (siehe Themenliste).
• Die Teilnehmer legen bis spätestens 10.1.2011 einen Entwurf des Vortrages vor und besprechen diesen mit dem Betreuer.
• Das Seminar findet als Blockveranstaltung am 20.1.2011 statt.

Vorträge

Jeder Vortrag soll 35 Minuten (+ 10 Minuten Diskussion) dauern. Der Vortrag kann wahlweise auf Deutsch oder Englisch gehalten werden. Ein guter Vortrag führt kurz in das jeweilige Thema ein, stellt die Problemstellung dar und beschreibt zusammenfassend relevante Arbeiten und Lösungen.

Leistungsnachweis

Die Note wird anhand des Vortrages und der Folien festgelegt. Das Seminar ist Wahlpflichtbestandteil der Master-Module "Maschinelles Lernen 1" und "Maschinelles Lernen 2". Bachelor-Studenten können diese Master-Module auf Antrag ebenfalls belegen.

Themen

• String Kernels

  • The Spectrum Kernel: A Kernel for SVM Protein Classification
    Leslie et al. Pacific Symposium on Biocomputing, 2002

  • Text Classification using String Kernels
    Lohdi et al. Journal of Machine Learning Research, 2002

  • Fast Kernels for Strings and Trees
    Vishwanathan & Smola. Advances in Neural Information Processing Systems, 2002

• Tree Kernels

  • Convolution Kernels for Natural Language
    Collins & Duffy, Advances in Neural Information Processing Systems, 2001

  • Route Kernels for Trees
    Aiolli et al., International Conference on Machine Learning, 2009

  • Approximate Tree Kernels
    Rieck et al. Journal of Machine Learning Research, 2010

• Graph Kernels

  • On Graph Kernels: Hardness Results and Efficient Alternatives
    Gärtner et al. Conference on Computational Learning Theory, 2003

  • A Linear-Time Graph Kernel
    Hido & Kashima. International Conference on Data Mining, 2009