Deskriptive Komplexität des Maschinellen Lernens

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389872375

Die deskriptive Komplexitätstheorie stellt eine Beziehung zwischen der algorithmischen und der sprachlichen Komplexität von Berechnungsproblemen her. In diesem Projekt übertragen wir den Ansatz der deskriptiven Komplexitätstheorie auf das maschinelle Lernen: Wir versuchen, effiziente Lernbarkeit anhand der deskriptiven Komplexität der Modelle zu erklären, das heißt, anhand der sprachlichen Ressourcen, die erforderlich sind, um die Modelle zu beschreiben.Unsere Arbeit soll auch als Grundlage für einen stärker deklarativen Zugang zum maschinellen Lernen dienen, in dem die Modelle (Klassen von Hypothesen) von den Lösern (Optimierungsalgorithmen, die die besten Hypothesen berechnen) entkoppelt werden.Anwendungen unseres logischen Rahmens für das maschinelle Lernen sehen wir am ehesten in logik-affinen Gebieten wie der automatischen Verifikation oder den Datenbaksystemen. Wir werden solche Anwendungen aktiv verfolgen.

• DFG-Verfahren: Sachbeihilfen