16
Maschinelles Lernen mit multiplen Kernen Marius Kloft Technische Universität Berlin Kolloquium zum GI Disserationspreis, Dagstuhl, 14. Mai 2012

Maschinelles Lernen mit multiplen Kernen

  • Upload
    august

  • View
    43

  • Download
    0

Embed Size (px)

DESCRIPTION

Maschinelles Lernen mit multiplen Kernen. Marius Kloft Technische Universität Berlin. Kolloquium zum GI Disserationspreis, Dagstuhl, 14. Mai 2012. TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: A A. Maschinelles Lernen. Beispiel - PowerPoint PPT Presentation

Citation preview

Page 1: Maschinelles Lernen  mit multiplen Kernen

Maschinelles Lernen mit multiplen KernenMarius KloftTechnische Universität Berlin

Kolloquium zum GI Disserationspreis, Dagstuhl, 14. Mai 2012

Page 2: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Zielstellung

▫ Erlernen des Zusammen-hanges zweier Zufallsgrößen und

auf Grundlage von Beobach-tungen

• Kernbasiertes Lernen:

Maschinelles Lernen

1/12

• Beispiel

▫ Erkennung von Objekten in Bildern

Page 3: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Multiple Sichtweisen / Kerne

2/12

Sichtweisen wie kombinieren?

Gewichtungen.

(Lanckriet, 2004)

Form

Raum

Farbe

Page 4: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Bestimmung der Gewichte?

3/12

• Stand der Forschung

▫ „Spärliche“ Gewichtungen

Kerne / Sichtweisen werden komplett ausgeschaltet

▫Aber warum Information verwerfen?

(Bach, 2008)

Page 5: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Von der Vision zur Wirklichkeit?

• Bisher: Spärliches Verfahren

▫ Empirisch ineffektiv in Anwendungen

4/12

(Gehler et al., Noble et al., Shawe-Taylor et al., NIPS 2008)

• Dissertation: Neue Methodologie

▫ hat sich als Standard etabliert

Durch bei Lern-schranken: O(M/n)

Effektiv in Anwendungen

In der Praxis wirk-samer und effektiver

Page 6: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Vorstellung der MethodologieNicht-spärliche, Multiple, Kernbasierte Lernverfahren

Page 7: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Generelle Formulierung

▫ Erstmalig beliebiger Verlust

▫ Erstmalig beliebige Normen

z. B. lp-Normen:

1-Norm führt zu Spärlichkeit:

Neue Methodologie

• Bestimmung der Gewichte?

▫ Model

Kern

▫ Mathematisches Programm

Konvexes Problem.

5/12

(Kloft et al., ECML 2010, JMLR 2011)

Optimierung über Gewichte

Page 8: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Theoretische Fundamente

• Theoretische Klärung

▫ Aktives Thema NIPS Workshop 2010

▫ Wir beweisen :

Theorem (Kloft & Blanchard). Die lokale Rademacher-Kom-plexität von MKL ist be-schränkt durch:

• Folgerungen

▫ Lernschranke mit Rate

bisher beste Rate:

Üblicherweise

Zwei Größenordnungen bes-ser für

6/12

(Kloft & Blanchard, NIPS 2011, JMLR 2012)

(Cortes et al., ICML 2010)

Page 9: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Beweisschritte

1. Abschätzung der Originalklasse durch die zentrierten Klasse

2. Abschätzung der Komplexität der zentrierten Klasse

3. Ungleichungen von Khintchine-Kahane (1964) und Rosenthal (1970)

4. Abschätzung der Komplexität der Originalklasse

5. Umformulierung als Trunkierung der Spektren der Kerne

7/12

Page 10: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Implementierung

▫ In C++ (“SHOGUN Toolbox”)

Matlab/Octave/Python/R support

▫ Laufzeit:

~ 1-2 Größenordnungen effizienter

Optimierung

• Algorithmen

1. Newton-Methode

2. Sequentielle, quadratisch-bedingte Programmierung mit Höhenlinien-Projektionen

3. Blockkoordinaten-Algorithmus

Alterniere Löse (P) bezüglich w

Löse (P) bezüglich %:

Bis Konvergenz

(bewiesen)

8/12

(Kloft et al., JMLR 2011)

analytisch

(Skizze)

Page 11: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Visuelle Objekterkennung

▫ Zielstellung: Annotation visueller Medien (z. B. Bilder):

▫ Motivation:

▫  inhaltsbasierter Bildzugriff

Anwendungsgebiet: Maschinelles Sehen

9/12

Flugzeug Fahrrad Vogel

Page 12: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Visuelle Objekterkennung

▫ Zielstellung: Annotation visueller Medien (z. B. Bilder):

▫ Motivation:

▫  inhaltsbasierter Bildzugriff

Anwendungsgebiet: Maschinelles Sehen

• Multiple Kerne

▫ basierend auf

Pixelfarben

Formen

(Gradienten)

lokale Merkmale

(SIFT-Wörter)

räumliche Merkmale

9/12

• Empirische Analyse

▫ Datensatz: PASCAL VOC’08

▫ Genauigkeitsgewinn gegenüber uniformer Kerngewichtung:

Gewinner: ImageCLEF 2011 Photo Annotation challenge!

Page 13: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

Zusammenfassung

10/12

Training mit > 100 000 Daten-Punkten und > 1 000 Kernen

Scharfe Lernschranken

Appli-kationen

Visuelle ObjekterkennungAls Standard etabliert: Gewinner des Image-CLEF Wettbewerbs

Bioinformatik

Genauerer TSS-Er-kenner als Gewinner internat. Vergleichs

Page 14: Maschinelles Lernen  mit multiplen Kernen

Referenzen

▫ Abeel, Van de Peer, Saeys (2009).  Toward a gold standard for promoter prediction evaluation. Bioinformatics.

▫ Bach (2008).  Consistency of the Group Lasso and Multiple Kernel Learning. Journal of Machine Learning Research (JMLR).

▫ Kloft, Brefeld, Laskov, Sonnenburg (2008). Non-sparse Multiple Kernel Learning. NIPS Workshop on Kernel Learning.

▫ Kloft, Brefeld, Sonnenburg, Laskov, Müller, Zien (2009). Efficient and Accurate Lp-norm Multiple Kernel Learning. Advances in Neural Information Processing Systems (NIPS).

▫ Kloft, Rückert, Bartlett (2010). A Unifying View of Multiple Kernel Learning. ECML.

▫ Kloft, Blanchard (2011). The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning. Advances in Neural Information Processing Systems (NIPS).

▫ Kloft, Brefeld, Sonnenburg, Zien (2011). Lp-Norm Multiple Kernel Learning. Journal of Machine Learning Research (JMLR).

▫ Kloft, Blanchard (2012). On the Convergence Rate of Lp-norm Multiple Kernel Learning. Journal of Machine Learning Research (JMLR), to appear.

▫ Lanckriet, Cristianini, Bartlett, El Ghaoui, Jordan (2004). Learning the Kernel Matrix with Semidefinite Programming. Journal of Machine Learning Research (JMLR).

11/12

Page 15: Maschinelles Lernen  mit multiplen Kernen

12/12

Vielen Dank für Ihre Aufmerksamkeit.

Für weitere Fragen stehen ich Ihnen gerne zur Verfügung.

Page 16: Maschinelles Lernen  mit multiplen Kernen

Marius Kloft (TU Berlin)

• Detektion von▫ Transkriptionsstartpunkten:

• mittels Kernen basierend auf:

▫ Sequenzalignment

▫ Nukleotidverteilung downstream, upstream

▫ Faltungseigenschaften Bindungsenergien, Winkel

• Empirische Analyse

▫ Detektionsgenauigkeit (AUC):

▫ Höhere Genauigkeiten als spärliches MKL sowie ARTS

ARTS Gewinner eines Vergleichs von 19 Modellen

• Theoretische Analyse

▫ Einfluss von lp-Norm auf Schranke:

▫ Bestätigung des Experimentes:

Stärkere theoretische Garantie für vorgeschlagenen Ansatz (p>1)

Empirie nähert sich Theorie an für Stichprobengröße

Anwendungsgebiet: Bioinformatik

(Abeel et al., 2009)

Abb. aus Alberts et al. (2002)

(Kloft et al., NIPS 2009, JMLR 2011)