Applying VC-Dimension Analysis to Object Recognition

Abstract

We analyze the amount of information needed to carry out various model-based recognition tasks, in the context of a probabilistic data collection model. We focus on objects that may be described as semi-algebraic subsets of a Euclidean space, and on a wide class of object transformations, including perspective and affine transformations of 2D objects, and perspective projections of 3D objects. Our approach borrows from computational learning theory. We draw close relations between recognition tasks and a certain learnability framework. We then apply basic techniques of learnability theory to derive upper bounds on the number of data features that (provably) suffice for drawing reliable conclusions. The bounds are based on a quantitative analysis of the complexity of the hypotheses class that one has to choose from. Our central tool is the VC-dimension, which is a well studied parameter measuring the combinatorial complexity of families of sets. It turns out that these bounds grow linearly with the task complexity, measured via the VC-dimension of the class of objects one deals with.