Duales Training nichtlinearer Support-Vektor-Maschinen mit Budget

• Antragsteller: Professor Dr. Tobias Glasmachers
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2016 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 287461288

Maschinelles Lernen beschäftigt sich mit der automatisierten Erstellung von Vorhersagemodellen aus Daten. Diese Disziplin verbindet Statistik, Informatik und Optimierung. Support-Vektor-Maschinen (SVM) haben sich als ein Standardverfahren etabliert. Als Klassifikationsmethode kommen SVM in vielen Bereichen von Wissenschaft und Technik zum Einsatz, z.B. in Bioinformatik, Robotik, (medizinischer) Bildverarbeitung und vielen mehr.SVM-Training mit BudgetDas Training eines SVM-Modells entspricht der Lösung eines Optimierungsproblems. Das etablierte Standardlösungsverfahren ist ein dualer Dekompositionsalgorithmus. Trotz seiner hohen Effizienz kann dieser nicht mit dem schnellen Wachstum der zu behandelnden Datenmengen ("big data") Schritt halten. Dies ist bedingt durch die Form des SVM-Modells als Linearkombination einer mit der Datenmenge wachsenden Zahl von Basisfunktionen.Dieses Wachstum der Basisfunktionen mit der Datenmenge wurde als Haupthindernis für ein effizientes Training von SVM auf großen Datenmengen identifiziert. Budget-Verfahren sind eine relativ neue Näherungsmethode. Sie definiere eine a-priori gewählte Obergrenze (das Budget) für die Anzahl der verwendeten Basisfunktionen. Dadurch laufen einzelne Iterationen des Trainingsalgorithmus deutlich schneller, was zu insgesamt reduzierter Laufzeit führt.Durch die Wahl des Budget-Parameters durch den Benutzer findet eine implizite Abwägung zwischen Rechenzeit pro Iteration und Genauigkeit der Lösung statt. Eine gute Einstellung dieses kritischen Parameters ist für den Lernerfolg entscheidend. Die starke Abhängigkeit dieses Parameterwerts vom Datensatz ist deshalb problematisch. Weiterhin sind Budget-Methoden bisher nur für primale Lösungsverfahren verfügbar, die deutlich langsamer als der duale Standardalgorithmus konvergieren.ProjektzieleEin Ziel des Projekts ist die Entwicklung eines dualen Dekompositionsalgorithmus unter Berücksichtigung der Budget-Bedingung. Dieser Ansatz verspricht, die schnelle Konvergenz des dualen Standardalgorithmus mit den schnellen Iterationen des Budgetverfahrens zu vereinen. Als Ergebnis wird eine deutliche Reduktion der Rechenzeit sowohl gegenüber dem Standardalgorithmus als auch gegenüber primalen Budgetmethoden erwartet.Ein weiteres Ziel ist die Entwicklung von Verfahren zur automatischen Einstellung der Budgetgröße. Der Bedarf für eine solche Methode ist zunächst unabhängig vom Optimierungsalgorithmus. Das Budget wird so eingestellt werden, dass bestmögliche Ergebnisse entweder für gegebene Rechenzeit oder für gegebene Genauigkeit der Lösung erzielt werden. Beide Ansätze erlauben die Spezifikation eines sinnvollen und datenunabhängigen Ziels für Budget-Training.Die im Rahmen des Projekts entwickelten Algorithmen werden durch Untersuchungen zu Konvergenz und Approximationsfehler theoretisch untermauert. Sie werden effizient implementiert und als freie Software zur Verfügung gestellt.

• DFG-Verfahren: Sachbeihilfen