+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************

Zeit: Freitag, 10. März 2023, 11.00 Uhr Ort: Raum 9222, Gebäude E3, Ahornstr. 55 Zoom: https://rwth.zoom.us/j/95679484581?pwd=Q0N4SUFZQ21jVERZMDAwc2cyQXpzZz09

Referent: Steffen van Bergerem, M.Sc. Lehrstuhl für Informatik 7

Thema: Descriptive Complexity of Learning

Abstract:

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.

Es laden ein: die Dozentinnen und Dozenten der Informatik