Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, October 19, 2010 - 4:30pm

Andrew Nobel

University of North Carolina

Location

University of Pennsylvania

DRL 4C6

The Vapnik-Chervonenkis (VC) dimension measures the ability of a family of sets to separate finite collections of points. The VC dimension plays a foundational role in machine learning, empirical processes and combinatorial geometry. In this talk we describe recent results concerning the structure of families with finite VC dimension. Our principal result states the following: for any family of measurable sets in a probability space, either (i) the family has infinite VC dimension or (ii) every set in the family can be approximated to within a given error by a fixed, finite partition. Immediate corollaries include the fact that families with finite VC dimension have finite bracketing numbers, and satisfy uniform laws of large numbers for ergodic processes. We will briefly discuss analogous results for VC major and VC graph families of functions. The talk will include the definition and examples of the VC dimension and related quantities. Joint work with Terry M. Adams