Diff for "Main/WS10_SeminarStructKernel"

Differences between revisions 18 and 26 (spanning 8 versions)

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 16:00 Uhr im Raum FR 6046
Verantwortlich	Dr. Konrad Rieck, Dr. Soeren Sonnenburg, 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.

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
1. Convolution Kernels for Natural Language
  Collins & Duffy, Advances in Neural Information Processing Systems, 2001
2. Route Kernels for Trees
  Aiolli et al., International Conference on Machine Learning, 2009
Kernels for Graphs
1. On Graph Kernels: Hardness Results and Efficient Alternatives
  Gärtner et al. Conference on Computational Learning Theory, 2003
2. Fast Subtree Kernels on Graphs
  Shervashidze & Borgwardt. Advances in Neural Information Processing Systems, 2009
3. A Linear-Time Graph Kernel
  Hido & Kashima. International Conference on Data Mining, 2009
Kernels from Automata and Probabilistic Models
1. Marginalized kernels for biological sequences
  Tsuda et al. Bioinformatics, 2002
2. The Fisher Kernel: Exploiting Generative Models in Discriminative Classifiers
  Jaakkola & Hausler. Advances in Neural Information Processing Systems, 1998
3. Rational Kernels
  Cortes et al. Advances in Neural Information Processing Systems, 2002

IDA Wiki: Main/WS10_SeminarStructKernel (last edited 2011-01-26 11:49:40 by KonradRieck)

-  ⇤ ← Revision 18 as of 2010-08-04 12:52:06 → 
  Size: 4300
  Editor: KonradRieck
  Comment:
+   ← Revision 26 as of 2010-11-01 11:29:34 → ⇥
  Size: 5020
  Editor: KonradRieck
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 6:
-|| || Blockseminar am 20.1.2011 von 10:00 bis 16:00 Uhr im Raum FR 6046 ||
|| '''Verantwortlich''' || [[http://ml.cs.tu-berlin.de/~rieck/teaching.html|Dr. Konrad Rieck]], [[http://ml.cs.tu-berlin.de/en/klaus/index.html|Prof. Dr. Klaus-Robert Müller]]  ||
+|| || Blockseminar am 18.1.2011 von 10:00 bis 16: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]]  ||
 Line 24:
-   * Das Seminar findet als Blockveranstaltung am 20.1.2011 statt.
+   * Das Seminar findet als Blockveranstaltung am 18.1.2011 statt.
 Line 36:
- * '''String Kernels'''
-Line 38:
+Line 37:
-  * [[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
+ * '''Kernels for Strings'''
-Line 40:
+Line 39:
-  * [[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
+. [[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
-Line 42:
+Line 41:
-  * [[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
+. [[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
-Line 45:
+Line 54:
- * '''Tree Kernels'''
+ * '''Kernels for Graphs'''
-Line 47:
+Line 56:
-  * [[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
+.#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
-Line 49:
+Line 58:
-  * [[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
+. [[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
-Line 51:
+Line 60:
-  * [[http://www.jmlr.org/papers/volume11/rieck10a/rieck10a.pdf|Approximate Tree Kernels]] <<BR>> Rieck et al. ''Journal of Machine Learning Research'', 2010
+. [[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
-Line 53:
+Line 62:
+ * '''Kernels from Automata and Probabilistic Models'''
-Line 54:
+Line 64:
- * '''Graph Kernels'''

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

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

  * [[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
+.#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