Einsatz algebraischer Methoden beim Algorithmischen Lernen
Final Report Abstract
Das Projekt "Einsatz algebraischer Methoden beim Algorithmischen Lernen" ging von zwei zentralen Fragestellungen aus. Zum einen sollte untersucht werden, inwieweit eine (von einem informationstheoretischen Standpunkt aus fast-optimale) "Master-Strategie" zum Lernen im SQ-Modell (Lernen mit statistischen Anfragen) effzient umgesetzt werden kann. Zum anderen sollten Querbeziehungen aufgespürt werden zwischen Techniken, die auf Fourierreihen basieren und solchen, die auf der Singulärwertzerlegung von Matrizen aufsetzen. Im Projekt sollte eine möglichst einheitliche Theorie entwickelt werden, die herausarbeitet, welche algebraischen Kenngrößen zur Einschätzung der inhärenten Härte eines Lernproblems herangezogen werden können. Bei der ersten Fragestellung wurden von unserer Arbeitsgruppe die folgenden Fortschritte erzielt. Es zeigte sich, dass eine stark vereinfachte Definition der sogenannten starken "SQ-Dimension" bereits ausreichend ist, um die Lernbarkeit im SQ-Modell zu beurteilen. Weiterhin zeigte sich, dass jeder konsistente Lernalgorithmus mit einer informationstheoretisch fast-optimalen Anzahl von statistischen Anfragen auskommt. Der resultierende Master-Algorithmus ist wesentlich effzienter als der urspüngliche (welcher auf der komplizierteren Definition der starken SQ-Dimension beruhte). Parallel zu unseren Arbeiten wurde von Vitaly Feldman ein überraschender Zusammenhang zwischen dem SQ-Modell und Valiants Modell der Evolvierbarkeit einer "Konzeptklasse" (Lernen auf der Basis von Mutation und Selektion) nachgewiesen. Bei der zweiten Fragestellung zeigte es sich, dass das Studium der Singulärwerte einer Matrix das Studium der Fourierkoeffzienten einer Booleschen Funktion als Spezialfall enthält (indem man von der Booleschen Funktion übergeht zur Matrix, die zu jeder Spiegelung der Funktion eine Spalte vorsieht). Diesen Zusammmenhang haben wir ausgenutzt, um kernbasierte Verfahren zu analysieren, die mit einer spiegelungsinvarianten Kernfunktion operieren. Wir haben zudem herausgearbeitet, welche zentrale Rolle die Randabstandskomplexität (margin complexity) einnimmt, wenn es darum geht, die auf Orthogonalität basierende Härte eines Lernproblems zu beurteilen. Parallel zu unseren Arbeiten gab es ebenso Erfolge anderer Arbeitsgruppen bei der Analyse der inhärenten Härte von Lernproblemen anhand algebraischer Parameter (mit zu unseren Ergebnissen unabhängigen Resultaten). Die Bedeutung der von uns in diesem Projekt erzielten Eregebnisse ist in der Entwicklung einer mathematischen Theorie zu sehen, welche anhand algebraischer Kenngrößen die Möglichkeiten und Grenzen bestimmter Lernmethoden aufzeigt.
Publications
- Dimension and Margin Bounds for Reflection-invariant Kernels. In Proceedings of the 21’st Annual Conference on Learning Theory, 157–167, 2008
Thorsten Doliwa, Michael Kallweit, and Hans Ulrich Simon
- Characterizing Statistical Query Learning: Simplified Notions and Proofs. In Proceedings of the 20’th International Conference on Learning Theory, 186–200, 2009
Balázs Szörényi
