PAC learning of FO definable concepts & nowhere dense graph classes

Date

Dec 11, 2014

Time

1:15 PM - 2:15 PM

Speaker

Prof. Dr. Isolde Adler

Affiliation

Goethe-Universität Frankfurt am Main

Language

en

Main Topic

Mathematik

Other Topics

Mathematik

Host

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

Description

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

Last modified: Dec 4, 2014, 5:01:26 PM