Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Parameterisierte Geometrische Optimierung: Kombinatorik, Algorithmen und Anwendungen im Maschinellen Lernen

Fachliche Zuordnung Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
Förderung Förderung von 2008 bis 2018
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 86443165
 
Erstellungsjahr 2018

Zusammenfassung der Projektergebnisse

Das maschinelle Lernen bietet viele Beispiele von parametrisierten Optimierungsproblemen. Dabei wird, um ein Modell aus Daten zu lernen, meistens eine Verlustfunktion minimiert bzw. eine Likelihood-Funktion maximiert. Bessere Modelle erhält man oft dadurch, dass man zu der Verlustfunktion noch einen geeigneten Regularisierungsterm addiert. Das richtige Verhältnis von der Minimierung der Verlustfunktion und der Regularisierung wird durch einen Regularisierungsparameter eingestellt. In der Praxis muss also ein zweistufiges Optimierungsproblem gelöst werden. Für einen festen Regularisierungsparameter muss die regularisierte Verlustfuktion über Trainingsdaten minimiert werden. Dann muss eine gute Lösung, zum Beispiel im Sinne der Vorhersagequalität des Modells auf Validierungsdaten, über dem Raum der Regularisierungsparameter gefunden werden. Der zweite Schritt wird oft heuristisch angegangen, indem nur ein paar Werte für den Regularisierungsparameter ausprobiert werden. Die Optimierung für einen festen Regularisierungsparameter ist dagegen oft ein einfaches, konvexes Problem, das effizient, exakt oder mit Approximationsgarantien gelöst werden kann. In der parametrisierten Optimierung will man auch das zweistufige Problem mit Garantien lösen. In der Regel kann die exakte Lösungsgesamtheit, d.h. die optimale Lösung für jeden Parameterwert, nicht effizient berechnet werden. Deshalb haben wir Approximationsverfahren untersucht, die den Parameterraum so abtasten, dass die Lösungen an den Abtaststellen die Lösungsgesamtheit mit vorgegebener Güte approximieren. Wir konnten zeigen, dass Ω(1/√ε) viele Abtastpunkte notwendig sind, um die Lösungsgesamtheit einer großen Klasse von regularisierten Verfahren aus dem maschinellen Lernen mit vorgebener Approximationsgute ε > 0 zu lösen. Wir konnten auch zwei robuste, effiziente Algorithmen angeben, der die vorgegebene Approximationsgüte mit O(1/√ε) Abtastpunkten erreichen. Regularisierte Verlustfunktionsminimierung ist ein recht einfaches Beispiel eines parametrisierten Optimierungsproblems, da die Parametrisierung linear im Regularisierungsparameter ist. Das maschinelle Lernen bietet auch viele Beispiele von nicht-linearen Parametrisierungen. In die zuvor beschriebene Verlustminimierung müssen die Daten nicht direkt eingehen, sondern sie können vorher auch nicht-linear transformiert werden. Eine nicht-lineare Datentransformation kann effizient durch eine sogenannte Kernfunktion erreicht werden. Viele Kernfunktionen, zum Beispiel der oft genutzte Gauß-Kern, hängen selbst nicht-linear von einem Parameter ab. Die Nutzung von parametrisierten Kernfunktionen führt wieder auf das schon zuvor beschriebene zweistufige Verfahren. Zum einen, die Verlustminimierung für einen festen Kernparameter auf Trainingsdaten, und zum anderen, die Optimierung des Kernparameters auf Testdaten. Unser Ziel war auch hier wieder die exakte Lösungsgesamtheit des parametrisierten Problems mit vorgegebener Güte zu approximieren. Für den nicht-linearen Fall konnten wir zeigen, dass Ω(1/ε) Abtastpunkte notwendig sind, um die Lösungsgesamtheit einer großen Klasse von nicht-linear transformierten Problemen aus dem maschinellen Lernen mit vorgebener Approximationsgüte zu lösen. Wir konnten auch einen Algorithmus angeben, die die Approximationsgute mit O(1/ε) Abtastpunkten erreicht. In der Praxis verbindet man oft regularisierte Verlustminimierung mit einer nicht-linearen Transformation der Daten. Es kommt auch vor, dass mehr als ein Regularisierungsterm vorhanden ist. Das heißt, in der Praxis ist die Parametrisierung oft nicht nur über einem Interval, sondern über einer Teilmenge eines höherdimensionalen Euklidischen Raums. Auch für diesen Fall wollten wir die exakte Lösungsgesamtheit des parametrisierten Problems mit vorgegebener Güte approximieren. Wir konnten zeigen, dass die Problemkomplexität als Funktion der Approximationsgüte das Produkt der Problemkomplexitäten der eindimensionalen Probleme ist. Zum Beispiel braucht man Ω (ε^−3/2) Abtastpunkte für Probleme mit einem Regularisierungs- und einem Kernparameter. Für Probleme mit zwei Regularisierungsparametern braucht man dementsprechend Ω(1/ε) Abtastpunkte. Wir konnten auch einen effizienten Algorithmus angeben, der die vorgegebene Approximationsgute asymptotisch mit der theoretisch minimal notwendigen Anzahl von Abtastpunkten erreicht. Alle unsere Algorithmen wurden implementiert und zeigen in der Praxis auf vielen Problemen und Datensatzen eine sehr gute Übereinstimmung mit der Theorie.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung