Descriptive complexity of learning

van Bergerem, Steffen; Grohe, Martin; Siebertz, Sebastian

doi:42076

Descriptive complexity of learning = Deskriptive Komplexität des Lernens

van Bergerem, Steffen^RWTH*

2023

Verantwortlichkeitsangabevorgelegt von Steffen van Bergerem, Master of Science

ImpressumAachen : RWTH Aachen University 2023

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2023

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Siebertz, Sebastian (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2023-03-10

Online
DOI: 10.18154/RWTH-2023-02554
URL: https://publications.rwth-aachen.de/record/953243/files/953243.pdf

Einrichtungen

Projekte

DFG project 389872375 - Deskriptive Komplexität des Maschinellen Lernens (389872375) (389872375)

Inhaltliche Beschreibung (Schlagwörter)
Boolean classification (frei) ; agnostic probably approximately correct learnin (frei) ; first-order logic (frei) ; first-order logic with counting (frei) ; first-order logic with weight aggregation (frei) ; fixed-parameter tractable (frei) ; locality (frei) ; parameterized complexity (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

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.

Supervised learning is a field in machine learning that strives to classify data based on labelled training examples. In the Boolean setting, each input is to be assigned to one of two classes, and there are several fruitful machine-learning methods to obtain a classifier. However, different algorithms usually come with different types of classifiers, e.g. decision trees, support-vector machines, or neural networks, and this is cumbersome for a unified study of the intrinsic complexity of learning tasks. This thesis aims at strengthening the theoretical foundations of machine learning in a consistent framework. In the setting due to Grohe and Turán (2004), the inputs for the classification are tuples from a relational structure and the search space for the classifiers consists of logical formulas. The framework separates the definition of the class of potential classifiers (the hypothesis class) from the precise machine-learning algorithm that returns a classifier. This facilitates an information-theoretic analysis of hypothesis classes as well as a study of the computational complexity of learning hypotheses from a specific hypothesis class. As a first step, Grohe and Ritzert (2017) proved that hypotheses definable in first-order logic (FO) can be learned in sublinear time over structures of small degree. We generalise this result to two extensions of FO that provide data-aggregation methods similar to those in commonly used relational database systems. First, we study the extension FOCN of FO with counting quantifiers. Then, we analyse logics that operate on weighted structures, which can model relational databases with numerical values. For that, we introduce the new logic FOWA, which extends FO by weight aggregation. We provide locality results and prove that hypotheses definable in a fragment of the logic can be learned in sublinear time over structures of small degree. To better understand the complexity of machine-learning tasks on richer classes of structures, we then study the parameterised complexity of these problems. On arbitrary relational structures and under common complexity-theoretic assumptions, learning hypotheses definable in pure first-order logic turns out to be intractable. In contrast to this, we show that the problem is fixed-parameter tractable if the structures come from a nowhere dense class. This subsumes numerous classes of sparse graphs. In particular, we obtain fixed-parameter tractability for planar graphs, graphs of bounded treewidth, and classes of graphs excluding a minor.

OpenAccess:
PDF
(additional files)