PAC learning of FO definable concepts & nowhere dense graph classes

Datum

11.12.2014

Zeit

13:15 - 14:15

Sprecher

Prof. Dr. Isolde Adler

Zugehörigkeit

Goethe-Universität Frankfurt am Main

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Prof. Dr. M. Bodirsky / Prof. Dr. A. Thom

Beschreibung

In machine learning, the problem of "concept learning" is to identify an unknown set from a given concept class (i.e. a collection of sets). In the model of "probably approximately correct" (PAC) learning, the learner receives a number of samples and must be able to identify the unknown set approximately, in a probabilistic sense. It is well-known the the sample size for PAC learning is characterised by the Vapnik-Cervonenkis (VC) dimension of the concept class. We are interested in the VC dimension of concept classes that are definable in some logic on graph classes. In 2004, Grohe and Turán showed that for any subgraph closed class C, monadic second-order definable concept classes have bounded VC dimension on C if and only if C has bounded tree-width. We show that for any subgraph closed class C, first-order definable concept classes have bounded VC dimension on C if and only if C is nowhere dense.

Links

• Seminar Algebra, Geometrie und Kombinatorik

Letztmalig verändert: 04.12.2014, 17:01:26