Block-Seminar: Kernels for Structured Data

Termine und Dozenten

Inhalt

In vielen Anwendungen des maschinellen Lernens 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 elegante Möglichkeit diese strukturierten Daten zu analysieren bietet das Konzept des kernbasierten Lernens. Die Lernalgorithmen sind hierbei ausschließlich über Kernfunktionen definiert, so dass es genügt Kerne für strukturierte Daten zu entwerfen, um diese zu analysieren. Das Seminar beschäftigt sich mit solchen Kernen. Es werden Kernfunktionen für Strings, Bäume und Graphen, ihre Implementierung und entsprechende Anwendungen besprochen.

Voraussetzungen

Wir empfehlen den vorherigen Besuch der Vorlesung "Maschinelles Lernen 1".

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 18.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

• Kernels for Strings

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

  2. Sparse Spatial Sample Kernel
     Kuksa et al. 19th International Conference on Pattern Recognition, 2008

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

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

• Kernels for Trees

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

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

• Kernels for Graphs

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

  8. Fast Subtree Kernels on Graphs
     Shervashidze & Borgwardt. Advances in Neural Information Processing Systems, 2009

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

• Kernels from Automata and Probabilistic Models

  10. Marginalized kernels for biological sequences
      Tsuda et al. Bioinformatics, 2002

  11. The Fisher Kernel: Exploiting Generative Models in Discriminative Classifiers
      Jaakkola & Hausler. Advances in Neural Information Processing Systems, 1998

  12. Rational Kernels
      Cortes et al. Advances in Neural Information Processing Systems, 2002