Parameterisierte Analyse in der Künstlichen Intelligenz

Eine grundlegende Aufgabe in der Informatik ist der Entwurf und die Analyse exakter Algorithmen, nicht nur für, im Sinne der Komplexitätstheorie, leichte Probleme, sondern auch für sogenannte schwere Probleme. Über die Jahre haben sich im Wesentlichen zwei Verfahren herausgebildet, solch schwere Probleme anzugehen. Erstere werden approximative Verfahren, oder Approximationsalgorithmen genannt. Sie versuchen Lösungen zu finden, welche nicht optimal sind, jedoch beweisbar nahe am Optimum liegen. Die zweite Richtung fokussiert darauf, durch besseres Verstehen der Probleme und ihrer Struktur nützliche Eigenschaften zu identifizieren. Die Hoffnung ist dann, dass solche Eigenschaften sich ausnutzen lassen, um effizientere Algorithmen zu finden. Es stellt sich heraus, dass viele für die Praxis relevante Instanzen solche teils versteckten Strukturen aufweisen. Um die Jahrtausendwende wurde diese zweite Grundidee genauer formalisiert und führte zur Entstehung des Feldes der parametrisierten Komplexitätstheorie. Durch ihre Einführung und Erforschung konnte das Verständnis vieler fundamentaler Probleme stark erweitert werden. Auch schnellere und praxisrelevante Algorithmen gingen aus dieser Forschungsrichtung hervor. Um so erstaunlicher scheint es, dass gerade im Feld der künstlichen Intelligenz, einem Gebiet, welches allgegenwärtiger Teil unserer Gesellschaft geworden ist, wenig bis gar keine Forschung in diese Richtung existiert, obwohl eine Vielzahl geeigneter Probleme vorhanden ist. Unser Projekt verfolgt das Ziel dies zu ändern, indem eine Basis geschaffen wird für eine parametrisierte Komplexitätstheorie der künstlichen Intelligenz (KI). Nicht nur wird dies unser Verständnis, welche Probleme und Ansätze des KI effizient gelöst werden können, stark erweitern, sondern auch die problemspezifischen Bedingungen aufzeigen, unter denen solche effizienten Verfahren existieren. Zudem sollen innerhalb des Projektes nicht nur bereits bekannte und standardisierte Methoden aus der parametrisierten Komplexitätstheorie in die Welt der KI übertragen werden, sondern auch eine Theorie der parametrisierten Sample Complexity entwickelt werden. Das heißt, es werden mathematische Werkzeuge und Techniken erforscht, welche es uns erlauben werden, genaue Schranken anzugeben, wie viele Daten ein gegebener Lernalgorithmus benötigt um gute Ergebnisse zu liefern. Einige nichttriviale Herausforderungen müssen sicherlich überwunden werden, um dieses Ziel zu erreichen. Jedoch ist der potenzielle Gewinn enorm: am Ende stehen also nicht nur bessere und schnellere Algorithmen, sondern auch ein besseres Verständnis, welche Probleme durch KI effizient bearbeitet werden können.