guest ::
000953243 001__ 953243 000953243 005__ 20241118112209.0 000953243 0247_ $$2HBZ$$aHT021771774 000953243 0247_ $$2Laufende Nummer$$a42076 000953243 0247_ $$2datacite_doi$$a10.18154/RWTH-2023-02554 000953243 037__ $$aRWTH-2023-02554 000953243 041__ $$aEnglish 000953243 082__ $$a004 000953243 1001_ $$0P:(DE-82)IDM03360$$avan Bergerem, Steffen$$b0$$urwth 000953243 245__ $$aDescriptive complexity of learning$$cvorgelegt von Steffen van Bergerem, Master of Science$$honline 000953243 246_3 $$aDeskriptive Komplexität des Lernens$$yGerman 000953243 260__ $$aAachen$$bRWTH Aachen University$$c2023 000953243 300__ $$a1 Online-Ressource : Illustrationen 000953243 3367_ $$02$$2EndNote$$aThesis 000953243 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd 000953243 3367_ $$2BibTeX$$aPHDTHESIS 000953243 3367_ $$2DRIVER$$adoctoralThesis 000953243 3367_ $$2DataCite$$aOutput Types/Dissertation 000953243 3367_ $$2ORCID$$aDISSERTATION 000953243 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University 000953243 502__ $$aDissertation, RWTH Aachen University, 2023$$bDissertation$$cRWTH Aachen University$$d2023$$gFak01$$o2023-03-10 000953243 5203_ $$aÜ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.$$lger 000953243 520__ $$aSupervised 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.$$leng 000953243 536__ $$0G:(GEPRIS)389872375$$aDFG project 389872375 - Deskriptive Komplexität des Maschinellen Lernens (389872375)$$c389872375$$x0 000953243 588__ $$aDataset connected to Lobid/HBZ 000953243 591__ $$aGermany 000953243 653_7 $$aBoolean classification 000953243 653_7 $$aagnostic probably approximately correct learnin 000953243 653_7 $$afirst-order logic 000953243 653_7 $$afirst-order logic with counting 000953243 653_7 $$afirst-order logic with weight aggregation 000953243 653_7 $$afixed-parameter tractable 000953243 653_7 $$alocality 000953243 653_7 $$aparameterized complexity 000953243 7001_ $$0P:(DE-82)IDM00084$$aGrohe, Martin$$b1$$eThesis advisor$$urwth 000953243 7001_ $$0P:(DE-82)187866$$aSiebertz, Sebastian$$b2$$eThesis advisor 000953243 8564_ $$uhttps://publications.rwth-aachen.de/record/953243/files/953243.pdf$$yOpenAccess 000953243 8564_ $$uhttps://publications.rwth-aachen.de/record/953243/files/953243_source.zip$$yRestricted 000953243 909CO $$ooai:publications.rwth-aachen.de:953243$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery 000953243 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM03360$$aRWTH Aachen$$b0$$kRWTH 000953243 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00084$$aRWTH Aachen$$b1$$kRWTH 000953243 9141_ $$y2023 000953243 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess 000953243 9201_ $$0I:(DE-82)122910_20140620$$k122910$$lLehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme)$$x0 000953243 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1 000953243 961__ $$c2023-03-27T09:57:21.707668$$x2023-03-13T15:21:00.410677$$z2023-03-27T09:57:21.707668 000953243 980__ $$aI:(DE-82)120000_20140620 000953243 980__ $$aI:(DE-82)122910_20140620 000953243 980__ $$aUNRESTRICTED 000953243 980__ $$aVDB 000953243 980__ $$aphd 000953243 9801_ $$aFullTexts