Polynomielle Fragekomplexität beim Algorithmischen Lernen

• Antragsteller: Professor Dr. Johannes Köbler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2005
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5190858

Es sollen deterministische und probabilistische Lernalgorithmen vorwiegend im Kontext von Angluins Modell des 'Exakten QueryLernens' konzipiert und ihre Komplexität analysiert werden. Obwohl für eine Reihe von konkreten Konzeptklassen effiziente Lernalgorithmen bekannt sind, ist die effiziente Erlernbarkeit wichtiger Konzeptklassen wie etwa boolescher Schaltkreise weitgehend offen. Um diese und ähnliche Fragen einer Lösung näher zu bringen, soll systematisch untersucht werden, welche Konzeptklassen mit einer polynomiell beschränkten Anzahl von Fragen erlernbar sind und unter welchen Voraussetzungen hieraus bereits auf die Erlernbarkeit in Polynomialzeit geschlossen werden kann. Umgekehrt erwarten wir, neue Anwendungen von in der Erlernbarkeitstheorie entwickelten Lösungsstrategien in der Komplexitätstheorie zu finden. Des weiteren soll der Ressourcenverbrauch von Lernalgorithmen im average-case untersucht werden, da eine worst-case-Analyse in manchen Fällen für die Praxis nur wenig aussagekräftig ist. Dabei erwarten wir, neue Zusammenhänge zwischen offenen Fragen der Komplexitätstheorie und Fragestellungen der Erlernbarkeitstheorie herstellen zu können.

• DFG-Verfahren: Sachbeihilfen