On Ordinal VC-Dimension and Some Notions of Complexity

Authors: Eric Martin, Arun Sharma and Frank Stephan.

Source: Lecture Notes in Artificial Intelligence Vol. 2842, 2003, 54 - 68.

Abstract. We generalize the classical notion of VC-dimension to ordinal VC-dimension, in the context of logical learning paradigms. Logical learning paradigms encompass the numerical learning paradigms commonly studied in Inductive inference. A logical learning paradigm is defined as a set of structures over some vocabulary, and a set of first-order formulas that represent data. The sets of models of in , where varies over , generate a natural topology W over .

We show that if is closed under boolean operators, then the notion of ordinal VC-dimension offers a perfect characterization for the problem of predicting the truth of the members of in a member of , with an ordinal bound on the number of mistakes. This shows that the notion of VC-dimension has a natural interpretation in Inductive Inference, when cast into a logical setting. We also study the relationships between predictive complexity, selective complexity-a variation on predictive complexity-and mind change complexity. The assumptions that is closed under boolean operators and that W is compact often play a crucial role to establish connections between these concepts.

Keywords: Inductive inference, logical paradigms, VC-dimension, predictive complexity, mind change bounds.

©Copyright 2003 Springer