ICMS Workshop on the Vapnik Chervonenkis Dimension Scientific Aims

Overview

The Vapnik Chervonenkis is a combinatorial parameter of a class of predicates or set system, which has been shown to characterise the expressibility of the class, or the learnability of the class from examples [2]. (See below for more detail.) The concept was originally developed within the field of statistics, but has since found application in a number of other areas. It is closely related, for example, to the notion of ϵ-nets used in computational geometry [5] to characterise the complexity of a number of problems. The determination of the VC dimension for specific classes may make use of powerful tools from logic and algebraic topology.

There has already been significant interaction between the different fields making use of this concept. Hence, for example computational geometry, combinatorics and learning theory have fed from each other, mostly via the theory of ϵ-nets. More recently, deep results in logic have been used to demonstrate the finiteness of the VC dimension of classes of functions defined by sigmoidal Neural Networks and using results from differential topology to obtain a bound on its size. Applications have also been found in Computational Complexity, in analysing the relationship between deterministic and randomised algorithms.

At the same time, the concept is being generalised in some of the application areas. Hence, for real valued functions, the concept of the pseudo-dimension and fat-shattering dimensions have been introduced to characterise function learning in various guises [1]. An example of its use in the analysis of algorithms has been in real valued complexity theory, where the finiteness of the VC dimension of a class of functions has been used to show that a deterministic circuit can simulate a probabilistic one by a suitable choice of representative inputs [3].

Aims and structure of the workshop

The aim of the workshop is to bring together theoreticians from all the disciplines that have reason to study the VC dimension, in order to exchange techniques, results and directions of research. It is also planned to include researchers working on the design of neural and other learning systems, who can benefit from the insights afforded by the theoretical analysis. We anticipate that there will be overlap in the developments made in different disciplines which can usefully profit from a comparison. At the same time, the questions that are of interest to one branch may well be most easily solved by techniques from a different branch. In short, there is an opportunity for a strong interdisciplinary meeting with significant interaction at a technical as well as informational level.

It is anticipated that around 40 people will attend the workshop. A number of these would be from the ESPRIT Neural and Computational Learning (NeuroCOLT) Working Group, who would be funded by that project. In order to give adequate time for presentations and interdisciplinary discussions, the workshop will last for five days. Each day will be based around a theme: the tone will be set by an invited talk by a distinguished researcher, and developed in contributed talks and discussions. Invited talks will be given by Shai Ben-David (Technion, Haifa) David Haussler (UC, Santa Cruz), Jiří Matoušek (Prag) and Vladimir Vapnik (AT&T Bell Labs, NJ).

The scope of the workshop in greater detail

Let S be a set of k points, in general position, in n-dimensional Euclidean space. How many subsets of S may be realised by intersecting S with a halfspace H, i.e., how many distinct sets are there of the form S ∩ H? When k is small in relation to n the answer is all 2^{k} possible subsets, and when this occurs we say that S is shattered. But when k is large, the geometry of the situation cuts in, and limits the number of subsets that can be obtained. More precisely: for k ≤ n + 1 there exists a set S of k points that is shattered— indeed, any set of k points in general position will do—whereas for k > n + 1 the number of realisable subsets of S is O(k^{n}). Exponential growth in the number of realisable subsets up to a certain point (in this case k = n + 1) followed by polynomial growth is in fact a widespread phenomenon.

The general situation is as follows: for a set system C ⊆ 2^{Ω}, the Vapnik-Chervonenkis (VC) dimension of C is defined to be the largest integer k such that there exists some set S ∈ Ω of cardinality k that is shattered by C, i.e., such that |{S ∩ C : C ∈ C}| = 2^{k}. (The VC dimension is ∞ if finite sets of all sizes are shattered.) Sauer’s lemma states that

|\{S ∩ C : C ∈ C\}| ≤ \binom{k}{0} + \binom{k}{1} + ⋯ + \binom{k}{d} = O(k^{d}),

where d is the VC dimension of C. Since the VC dimension of the collection of all halfspaces in Euclidean n-space is n+1, the number of realisable subsets of a set of k points is O(k^{n+1}). (As hinted earlier, the true answer is O(k^{n}), so the VC dimension does not quite capture all the geometry in this case.)

The notion of VC dimension first arose in the study of empirical processes. Let P be a probability distribution on Ω, and C ⊆ 2^{Ω} be a class of measurable sets or events. Suppose a sequence x_{1}, x_{2}, … of independent samples is drawn from P; then the empirical distribution P_{n} is obtained by assigning probability mass n^{−1} to each of the n points x_{1}, …, x_{n}. For any fixed event A ∈ C, the strong law of large numbers asserts that |P_{n}(A)−P (A)| → 0 almost surely as n → ∞. The condition for convergence to be uniform over all events A ∈ C is precisely that the VC dimension d of C is finite [11, 8]. In this case, given ε, δ > 0, there is a sample size n = n(ε, δ, d) such that |P_{n}(A) − P (A)| ≤ ε for all A ∈ C, with probability 1 − δ. The important point to note is that n is independent of P. Thus, provided the VC dimension is finite, the empirical distribution P_{n} converges uniformly to P on the events C in a strong sense.

Another topic in which the VC dimension plays a key role is computational learning theory. The PAC or “Probably Approximately Correct” learning model was proposed by Valiant as a mathematical basis for the study of inductive inference [10]. A learner is provided with a sequence of examples (the “learning set”) drawn from a sample space Ω, each example classified as positive or negative according to some hidden concept C ⊆ Ω. (An example x ∈ Ω is positive if x ∈ C, and negative otherwise.) The learner is required to produce a hypothesis H ⊆ Ω that is a close approximation to the hidden concept C.

Two features to the model are important to the current discussion. (1) The model is probabilistic, examples being drawn from a fixed (but unknown) probability distribution. This assumption can be viewed as providing the learner with a time-invariant environment in which past observations can form a legitimate basis for future predictions. It also provides a natural measure of the closeness of a hypothesis H to a concept C, namely the probability of the symmetric difference of C and H viewed as an event in Ω. (2) Concepts are drawn from a restricted “concept class” C appropriate to the learning situation. The choice of concept class plays an important role in the theory, the intention being that the representation should encapsulate the prior assumptions and expectations which are a prerequisite for learning.

There are two barriers to learning in the PAC sense: (a) a large learning set may be necessary in order to acquire sufficient information about the hidden concept; but then,

(b) even if a small learning set suffices in principle, the task of extracting a suitable hypothesis H may be computationally intractable. These barriers may be termed informationtheoretic and complexity-theoretic, respectively. Blumer, Ehrenfeucht, Haussler and Warmuth showed that the information-theoretic considerations are neatly captured by the VC dimension d of the concept class C [2]. More particularly, they provided upper and lower bounds (as a function of ε, δ, and d) on the number of samples required to obtain a hypothesis H that is an ε-approximation to the hidden concept C, with probability at least 1−δ. These bounds, which are closely related to those obtained by Vapnik and Chervonenkis, were later improved by Shawe-Taylor, Anthony and Biggs [9].

Combinatorial geometry and computational geometry are further fertile areas for the application of the VC dimension and related notions such as ε-nets and ε-approximations. One of the most successful approaches to the design of simple and fast algorithms for geometric problems is the randomised incremental technique, which has been applied to the computation of, for example, Voronoi diagrams and convex hulls. In general the aim is to compute a geometric structure induced by a set S of geometric objects. For example, the set S might be a set of points in Euclidean n-space, and the induced structure the convex hull of S, i.e., the smallest convex set containing S. The idea is to process the elements of S in random order, maintaining the partial structure induced by the elements so far considered. This approach has been treated by Mulmuley [7], amongst others, in a quite abstract setting. The key to the effectiveness of the method is that the class of geometric objects being processed has small VC dimension.

Given the range of applications, some of which have been sketched above, it is obviously of some interest to study techniques for evaluating (or at least closely bounding) the VC dimension in specific cases. Goldberg and Jerrum [4] combined Milnor-like bounds with a simple observation to give a general upper bound on the VC dimension of set systems over ℝ^{n} that are definable in the first-order theory of the reals (without exponentiation). Karpinski and Macintyre extended the bound to set systems definable with exponentiation using deep results from logic [6]. As a corollary, they obtained the first good upper bound on the discriminating power of artificial neural networks with sigmoidal activation functions.

References

[1] Alon, N. , Ben-David, S. , Cesa-Bianchi, N. and Haussler, D. (1993). Scale-sensitive dimensions, uniform convergence, and learnability. In Proceedings of the 1993 IEEE Symposium on Foundations of Computer Science, IEEE Press.

[2] Blumer, A. , Ehrenfeucht, A. , Haussler, D. and Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM 36(4): 929–965.

[3] J F Cucker, P Koiran, M Karpinski, T Lickteig and K Werther, On real Turing Machines that toss coins, NeuroCOLT Technical Report NC-TR-95-018, to appear in the Proceedings of STOC’95, 1995.

[4] Paul Goldberg and Mark Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Machine Learning 18 (1995), pp. 131– 148.

[5] David Haussler and Emo Welzl, ϵ-Nets and Simplex Range Queries, Discrete and Computational Geometry, 2 (1987) 127–151.

[6] Marek Karpinski and Angus Macintyre, Polynomial lower bounds for VC dimension of sigmoidal neural nets, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press 1995, pp. 200–208.

[7] Ketan Mulmuley, Computational Geometry: an Introduction through Randomized Algorithms, Prentice-Hall 1994.

[8] David Pollard, it Convergence of Stochastic Processes, Springer-Verlag, 1984.

[9] John Shawe-Taylor, Martin Anthony and Norman Biggs, Bounding Sample Size with the Vapnik-Chervonenkis Dimension, Discrete Applied Mathematics 42 (1993) pp. 65– 73.

[10] L. G. Valiant, A theory of the learnable, Communications of the ACM 27 (1984), pp. 1134–1142.

[11] V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications 16, 264–280.