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

• Kernels from Automata and Probabilistic Models

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

  • The Fisher Kernel: Exploiting Generative Models in Discriminative Classifiers
    Jaakkola and Hausler, 1998

  • Rational Kernels
    Cortes et al., 2002

• 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

• Graph Kernels

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

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

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