Polynomielle Fragekomplexität beim Algorithmischen Lernen II
Das Ziel des Projekts besteht darin, deterministische und
probabilistische Lernalgorithmen - vorwiegend im Kontext von Angluins
Modell des Exakten Query-Lernens sowie Valiants Modell des Pac-Lernens
- zu konzipieren und ihre Komplexität zu analysieren. Eine wichtige
offene Frage ist in diesem Kontext, ob boolesche Schaltkreise
effizient erlernbar sind. Ein vielversprechender Ansatz, diese und
ähnliche Fragen einer Lösung näher zu bringen, besteht darin,
systematisch zu untersuchen, unter welchen Voraussetzungen ein
Lernalgorithmus, der eine polynomial beschränkte Anzahl von Fragen
stellt, in einen Polynomialzeit-Algorithmus verwandelt werden kann.
Weitere Ziele sind die Kombination algorithmischer und
probabilistischer Ansätze sowie die Anwendung von ursprünglich in der
Erlernbarkeitstheorie entwickelten Techniken, um 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 das Laufzeitverhalten in konkreten
praktischen Anwendungen zu pessimistisch abschätzen könnte.
Das Ziel des Projekts besteht darin, deterministische und
probabilistische Lernalgorithmen - vorwiegend im Kontext von Angluins
Modell des Exakten Query-Lernens sowie Valiants Modell des Pac-Lernens
- zu konzipieren und ihre Komplexität zu analysieren. Eine wichtige
offene Frage ist in diesem Kontext, ob boolesche Schaltkreise
effizient erlernbar sind. Ein vielversprechender Ansatz, diese und
ähnliche Fragen einer Lösung näher zu bringen, besteht darin,
systematisch zu untersuchen, unter welchen Voraussetzungen ein
Lernalgorithmus, der eine polynomial beschränkte Anzahl von Fragen
stellt, in einen Polynomialzeit-Algorithmus verwandelt werden kann.
Weitere Ziele sind die Kombination algorithmischer und
probabilistischer Ansätze sowie die Anwendung von ursprünglich in der
Erlernbarkeitstheorie entwickelten Techniken, um 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 das Laufzeitverhalten in konkreten
praktischen Anwendungen zu pessimistisch abschätzen könnte.
Mittelgeber
DFG: Sachbeihilfe
Laufzeit
Projektstart: 11/2001
Projektende: 12/2003
Webseite
http://www.informatik.hu-berlin.de/Institut/struktur/algorithmenII/Forschung/dfg-learning.html
