Maschinelles Lernen mit multiplen KernenMarius KloftTechnische Universität Berlin

Kolloquium zum GI Disserationspreis, Dagstuhl, 14. Mai 2012

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

Marius Kloft (TU Berlin)

Multiple Sichtweisen / Kerne

2/12

Sichtweisen wie kombinieren?

Gewichtungen.

(Lanckriet, 2004)

Form

Raum

Farbe

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)

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

Marius Kloft (TU Berlin)

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

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

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)

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

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)

Marius Kloft (TU Berlin)

• Visuelle Objekterkennung

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

▫ Motivation:

▫  inhaltsbasierter Bildzugriff

Anwendungsgebiet: Maschinelles Sehen

9/12

Flugzeug Fahrrad Vogel

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!

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

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

12/12

Vielen Dank für Ihre Aufmerksamkeit.

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

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)