Descriptive complexity of learning

• Deskriptive Komplexität des Lernens

van Bergerem, Steffen; Grohe, Martin (Thesis advisor); Siebertz, Sebastian (Thesis advisor)

Aachen : RWTH Aachen University (2023)
Doktorarbeit

Dissertation, RWTH Aachen University, 2023

Kurzfassung

Überwachtes Lernen ist ein Teilgebiet des maschinellen Lernens, in dem Daten anhand von gelabelten Trainingsbeispielen klassifiziert werden. Bei der Boole'schen Klassifikation werden die Eingaben in zwei Kategorien einsortiert und es gibt mehrere effektive Lernmethoden, um einen Klassifikator zu erhalten. Unterschiedliche Methoden liefern allerdings oft unterschiedliche Arten von Klassifikatoren, wie z.B. Entscheidungsbäume, Support Vector Machines oder neuronale Netzwerke, was eine einheitliche Untersuchung der intrinsischen Komplexität von Lernproblemen sehr erschwert. Ziel dieser Dissertation ist ein Ausbau der theoretischen Grundlagen des maschinellen Lernens innerhalb eines konsistenten formalen Rahmens. Im von Grohe und Turán (2004) eingeführten Modell sind die zu klassifizierenden Eingaben Tupel aus einer relationalen Struktur und der Suchraum für Klassifikatoren besteht aus logischen Formeln. Der Ansatz trennt die Definition der Klasse von möglichen Klassifikatoren (die Hypothesenklasse) vom konkreten Lernalgorithmus. Dies ermöglicht eine informationstheoretische Analyse der Hypothesenklassen sowie eine Untersuchung der Komplexität des Problems, Hypothesen aus einer bestimmten Klasse zu lernen. Grohe und Ritzert zeigten 2017, dass in Prädikatenlogik erster Stufe (FO) definierbare Hypothesen in sublinearer Zeit auf Strukturen von kleinem Grad lernbar sind. Wir verallgemeinern das Resultat auf zwei FO-Erweiterungen, die Methoden zum Aggregieren von Daten liefern, welche denen in relationalen Datenbanksystemen ähneln. Zunächst untersuchen wir die Logik FOCN, die FO um Zählquantoren erweitert. Dann analysieren wir Logiken, die auf gewichteten Strukturen operieren, welche numerische Werte in relationalen Datenbanken modellieren können. Dazu führen wir die neue Logik FOWA ein, welche FO um Methoden zur Gewichtsaggregation erweitert. Wir präsentieren Lokalitätsergebnisse und zeigen, dass in einem Fragment der Logik definierbare Hypothesen in sublinearer Zeit auf Strukturen von kleinem Grad lernbar sind. Um die Komplexität von Lernproblemen auf allgemeineren Strukturen besser zu verstehen, untersuchen wir dann die parametrisierte Komplexität der Probleme. Unter weit verbreiteten komplexitätstheoretischen Annahmen stellt sich heraus, dass das Lernproblem für FO-definierbare Hypothesen auf beliebigen relationalen Strukturen nicht effizient lösbar ist. Im Gegensatz dazu zeigen wir, dass es auf Klassen von Strukturen, die nirgends dicht (nowhere dense) sind, einen im Sinne der parametrisierten Komplexität effizienten Algorithmus für das Problem gibt. Dies umfasst zahlreiche Klassen von dünnen Graphen, darunter planare Graphen, Graphen mit beschränkter Baumweite und Klassen von Graphen, die je einen Minoren ausschließen.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme) [122910]