== Block-Seminar: Kernels for Structured Data ==

=== Termine und Dozenten ===

|| '''Termin'''|| Vorbesprechung am 3.11.2010 um 11:00 Uhr im Raum FR 6046 ||
|| || Blockseminar am 18.1.2011 von 10:00 bis 18:00 Uhr im Raum FR 6046 ||
|| '''Verantwortlich''' || [[http://ml.cs.tu-berlin.de/~rieck/teaching.html|Dr. Konrad Rieck]], [[http://sonnenburgs.de/soeren|Dr. Soeren Sonnenburg]], [[http://ml.cs.tu-berlin.de/en/klaus/index.html|Prof. Dr. Klaus-Robert Müller]]  ||
|| '''Themenvergabe''' || per Email bis 10.11.2010 in Absprache mit dem Betreuer ||
|| '''Anrechenbarkeit''' || Wahlpflicht LV in den M.Sc. Modulen Maschinelles Lernen 1 & 2 ||

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

=== Programm ===

Seminarplan für Dienstag, den 18. Januar 2011. Das Seminar findet in Raum FR 6046 statt.

|| '''Zeit''' || '''Thema''' || '''Vortragender''' ||
|| 10:00 || ''Begrüßung'' || ||
|| 10:15 || Text Classification using String Kernels || Max Heimel ||
|| 11:00 || Sparse Spatial Sample Kernel || Mahmoud Mabrouk ||
|| 11:45 || ''Kaffeepause'' || ||
|| 12:00 || The Fisher Kernel || Felix Franke ||
|| 12:45 || Marginalized Kernels for Biological Sequences || Arno Onken  ||
|| 13:30 || ''Mittagspause'' || ||
|| 14:30 || Convolution Kernels for Natural Language || Priska Herger ||
|| 15:15 || On Graph Kernels: Hardness Results and Efficient Alternatives  || Vincent Froese ||
|| 16:00 || ''Kaffeepause'' || ||
|| 16:15 || Fast Subtree Kernels on Graphs || Andreas Orthez ||
|| 17:00 || A Linear-Time Graph Kernel  || Danny Panknin ||
|| 17:45 || ''Verabschiedung'' ||  ||

=== 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 3.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. [[http://helix-web.stanford.edu/psb02/leslie.pdf|The Spectrum Kernel: A Kernel for SVM Protein Classification]] <<BR>> Leslie et al. ''Pacific Symposium on Biocomputing'', 2002

  1. [[http://figment.cse.usf.edu/~sfefilat/data/papers/TuAT5.1.pdf|Sparse Spatial Sample Kernel]] <<BR>> Kuksa et al.  19th International Conference on Pattern Recognition, 2008

  1. [[http://jmlr.csail.mit.edu/papers/volume2/lodhi02a/lodhi02a.pdf|Text Classification using String Kernels]] <<BR>> Lohdi et al. ''Journal of Machine Learning Research'', 2002

  1. [[http://books.nips.cc/papers/files/nips15/AA11.pdf|Fast Kernels for Strings and Trees]] <<BR>> Vishwanathan & Smola. ''Advances in Neural Information Processing Systems'', 2002

 * '''Kernels for Trees'''

  1.#5 [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.8830&rep=rep1&type=pdf|Convolution Kernels for Natural Language]] <<BR>> Collins & Duffy, ''Advances in Neural Information Processing Systems'', 2001

  1. [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149.6975&rep=rep1&type=pdf|Route Kernels for Trees]] <<BR>> Aiolli et al., ''International Conference on Machine Learning'', 2009


 * '''Kernels for Graphs'''

  1.#7 [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.8681&rep=rep1&type=pdf|On Graph Kernels: Hardness Results and Efficient Alternatives]] <<BR>> Gärtner et al. ''Conference on Computational Learning Theory'', 2003

  1. [[http://webdav.tuebingen.mpg.de/u/karsten/Veroeffentlichungen/papers/SheBor09.pdf|Fast Subtree Kernels on Graphs]] <<BR>> Shervashidze & Borgwardt. ''Advances in Neural Information Processing Systems'', 2009

  1. [[http://www.trl.ibm.com/people/hido/pdf/091209_Hido_ICDM2009.pdf|A Linear-Time Graph Kernel]] <<BR>> Hido & Kashima. ''International Conference on Data Mining'', 2009

 * '''Kernels from Automata and Probabilistic Models'''

  1.#10 [[http://bioinformatics.oxfordjournals.org/cgi/reprint/18/suppl_1/S268|Marginalized kernels for biological sequences]] <<BR>>Tsuda et al. ''Bioinformatics'', 2002
  1. [[http://people.csail.mit.edu/tommi/papers/gendisc.ps|The Fisher Kernel: Exploiting Generative Models in Discriminative Classifiers]] <<BR>>Jaakkola & Hausler. ''Advances in Neural Information Processing Systems'', 1998
  1. [[http://books.nips.cc/papers/files/nips15/AA15.pdf|Rational Kernels]] <<BR>>Cortes et al. ''Advances in Neural Information Processing Systems'', 2002

Wir danken Marius Kloft für die Betreuung von Andreas Orthey.