Einsatz algebraischer Methoden beim Algorithmischen Lernen

• Antragsteller: Professor Dr. Hans Ulrich Simon
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 44585580

In den zurückliegenden zwanzig Jahren wurden in der algorithmischen Lerntheorie wesentliche Fortschritte mit algebraischen Methoden erzielt. Zum Beispiel benutzt Jackson s Algorithmus (namens „harmonisches Sieb ) zum Lernen von Booleschen Formeln in disjunktiver Normalform die diskrete Fourierreihenentwicklung einer Booleschen Punktion. Die Klasse der Funktionen, die mit dem harmonischen Sieb gelernt werden können, lasst sich ebenfalls algebraisch charakterisieren. Beim Studium der linearen Arrangements für Boolesche Konzeptklassen und bei der Bestimmung der Komplexität von Problemen im Modell des „Lernens durch statistische Anfragen waren die Schlüsselresultate erneut algebraischer Natur. Dabei erwiesen sich Lernprobleme als „hart , wenn es viele Konzepte in der betrachteten Konzeptklasse gibt, die untereinander nur schwach korreliert sind und somit (geometrisch ausgedrückt) fast orthogonal aufeinander stehen. In dem hier beantragten Projekt stellen wir uns zwei Hauptziele. Zum einen wollen wir eine von uns bereits entwickelte „Master-Strategie zum Lernen im Modell mit statistischen Anfragen, die universell und informationstheoretisch fast-optimal (aber auch ineffizient) ist, systematisch weiterentwickeln, um zu einer effizienten Strategie für eine breite Klasse von Konzeptklassen zu gelangen. Zum anderen wollen wir Querbeziehungen zwischen den Fourierreihen-basierten Techniken und den auf Singulärwertzerlegung von Matrizen beruhenden Techniken aufspüren. Beide Ansätze wurden im Rahmen von lerntheoretisch relevanten Fragen bisher eher disparat verfolgt. Wir beabsichtigen zu einem stärker einheitlichen Ansatz zu gelangen und Methoden aus beiden Bereichen wechselseitig nutzbar zu machen.

• DFG-Verfahren: Sachbeihilfen