Relação entre VC Dimension e menor testemunha

Abstract

The VC-dimension is an important combinatorial measure that, in a sense, indicates the complexity of a family of binary functions. It was originally defined in 1971 by Vapnik and Chervonenkis (VC) and gave rise to the so-called “Vapnik-Chervonenkis Theory”. It is of fundamental importance in Statistical Learning Theory, being used, for example, to predict probabilistic upper bounds for classification tests. Another important concept, now in Computational Learning Theory, is the “Teaching Dimension” (TD). It is related to the notion of “witnesses” for a family of binary functions. More precisely, if H is a set of binary functions with domain X, we say that S ⊆ X is a witness for a certain h ∈ H if it is possible to identify h (among the elements of H) from its restriction to S; that is, if no other function in H has the same restriction as h on S. Defining TDmin(H,h) as the size of the smallest witness for h, the Minimal Teaching Dimension of H, denoted by TDmin(H), is equal to the minimum value of TDmin(H,h) as h varies. The RTD (“Recursive Teaching Dimension”) conjecture relates the two above parameters, stating that the value of the Teaching Dimension of any family H, with finite domain, is less than or equal to the VC-dimension of H multiplied by an absolute constant. In this dissertation, we study the history and recent advances regarding this conjecture.