Fall 2018 - Reading Seminar

Vapnik-Chervonenkis dimension and the independence property

Organizer: Joris Roos, 513 VV.
E-Mail: jroos at math...

The Vapnik-Chervonenkis dimension is a combinatorial quantity that originated in probability theory and is central to computational learning theory. The independence property is a concept from model theory (mathematical logic). In the early 1990s, over twenty years after their respective initial discovery, M. C. Laskowski observed that the two concepts are actually intimately connected: a first-order formula does not have the independence property if and only if the associated class of definable sets has finite Vapnik-Chervonenkis dimension. As a consequence, certain results from model theory have direct applications in computational learning theory.

The goal of this seminar is to understand and explore this connection. The first step will be to review fundamentals of model theory and learning theory.

While some previous exposure to either mathematical logic or Vapnik-Chervonenkis theory is recommended, background in both is not expected.
The intended audience are graduate students in mathematics, statistics or computer science.

We will meet once a week for about an hour to jointly discuss a previously assigned reading text (such as a paper or a book chapter). The first organizational meeting will be in the second week of lectures. Time and location will be discussed separately with those who are interested.

If you are interested please send me a message until Sunday, Sept. 9 which contains your status (program and year of study) and a brief description of relevant previous experience. Please note that due to the nature of a reading seminar, space is very limited.

Note that this seminar is not for credit.

Schedule

We meet Wednesdays 7 pm in VV B235 unless noted otherwise.

Date	Text
Sep 12	(Introduction and organizational meeting)
Sep 19	Marker - Ch. 1
Oct 3	Marker - Ch. 2.1, 2.2, 2.3, 3.1
Oct 10	Marker - Ch. 4.1(, 4.2, 4.3)
Oct 17	Guingona - Ch. 1, 2.1
Oct 31	Guingona - Ch. 2.2, 2.3, 2.4
Nov 7	Tressl - focus on sections 1 and 8
Nov 20, 7.15 pm (Tue)	Macintyre-Sontag (1993), Laskowski (1992)
Dec 4, 7.25 pm (Tue)	Chase-Freitag (2018) [and kernels..]
Dec 11, 7.25 pm (Tue)	Wrap-up and further directions

References and related literature

M. Anthony, P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
M. Aschenbrenner, A. Dolich, D. Haskell, D. Macpherson, S. Starchenko. VC density in some theories without the independence property, I. Trans. Amer. Math. Soc. 368(8), 5889-5949, 2016.
H. Chase, J. Freitag. Model theory and machine learning. Preprint, arXiv:1801.06566, 2018.
C. C. Chang, H. J. Keisler. Continuous model theory, Ann. Math. Studies 58, Princeton University Press, 1966.
V. Guingona. NIP Theories and Computational Learning Theory. Preprint lecture notes.
H. R. Johnson, M. C. Laskowski. Compression schemes, stable definable families and o-minimal structures, Discrete Comput. Geom. 43(4), 914-926, 2010.
M. C. Laskowski. Vapnik-Chervonenkis classes of definable sets. J. London Math. Soc. (2) 45, 377-384, 1992.
A. Macintyre, E. D. Sontag. Finiteness results for sigmoidal "neural" networks, Proc. STOC, 325-334, 1993.
D. Marker. Model Theory: An Introduction. Springer, GTM 217, 2002.
P. Simon. A guide to NIP theories. Cambridge University Press, 2015.
M. Tressl. Introduction to o-minimal structures and an application to neural network learning. Preprint lecture notes, 2010.
V. N. Vapnik, A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16(2), 264-280, 1971.
B. Yaacov. Continuous and random Vapnik-Chervonenkis classes. Isr. J. Math. 173, 309-333, 2009.