LisMath Seminar 

27/03/2015, 16:00 — 17:00 — Room B3-01, Interdisciplinary Complex, Universidade de Lisboa
Sílvia Reis, LisMath Programme, Universidade de Lisboa

Vanik-Chervonenkis theory and the independence property in model theory.

Vapnik-Chervonenkis dimension is a measure of complexity of a family of sets. Informally, it measures how many subsets of an arbitrary finite set the family can recognise. VC-theory was developed as a foundation for statistical learning theory in the early 1970's, and still provides the theoretical basis for the classical approach to classification problems in machine learning. At heart of VC-theory lies a simple but surprising combinatorial lemma, that was proved independently and simultaneously in three different papers [1],[2],[3].

Model theory provides a different perspective on VC-theory. The compactness theorem allows to investigate asymptotic behaviour of finite sets via infinite sets with a particularly nice homogeneous structure (indiscernible sequences). This allowed Shelah to prove in his original paper [3] results that were thought by combinatorists to be open for over ten years afterwards (the connection between Shelah's paper [3] and the work [1],[2] was only made in mid-80's).

The goal of the seminar would be to introduce the basics of VC-theory, and to explain the connection between this subject and model theory. The seminar will follow mostly a recent account [4].

Bibiography

1. V. Vapnik and A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." Theory of Probability and its Applications, 16(2):264–280, 1971.

2. Shelah, Saharon, "A combinatorial problem; stability and order for models and theories in infinitary languages", Pacific Journal of Mathematics 41: 247–26, 1972.

3. Sauer, N., "On the density of families of sets", Journal of Combinatorial Theory, Series A 13: 145–147, 1972.

4. Hans Adler, "An introduction to theories without the independence property", Archive for Math Logic, to appear.

See also

LisMath Seminar_silvia_reis.pdf