# Blog Archives

# Topic Archive: Learning Theory

Model theory seminarFriday, May 9, 201412:30 pmGC6417

# VC-dimension in model theory and other subjects

Université Paris Diderot - Paris 7

Finite VC-dimension, a combinatorial property of families of

sets, was discovered simultaneously by Vapnik and Chervonenkis in the

context of probabilistic learning theory, and by Shelah in model

theory in the context of classification of unstable first-order

theories (where it is called NIP). From the model theoretic point of

view it is a very attractive setting generalizing stability and

o-minimality, and admitting a deep theory which had been recently used

to study ordered and valued fields. I will give an overview of some

results around NIP related to set theory (counting Dedekind cuts in

infinite linear orders), topological dynamics and compression schemes

in computational learning theory.