Please use this identifier to cite or link to this item:
Title: On ordinal VC-dimension and some notions of complexity
Authors: Martin, E.
Sharma, A.
Stephan, F. 
Keywords: Generalized VC-dimension
Inductive inference
Predictive complexity
Issue Date: 2-Nov-2006
Citation: Martin, E., Sharma, A., Stephan, F. (2006-11-02). On ordinal VC-dimension and some notions of complexity. Theoretical Computer Science 364 (1) : 62-76. ScholarBank@NUS Repository.
Abstract: We generalize the classical notion of Vapnik-Chernovenkis (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 W of structures over some vocabulary, and a set D of first-order formulas that represent data. The sets of models of φ{symbol} in W, where φ{symbol} varies over D, generate a natural topology W over W. We show that if D 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 D in a member of W, 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 D is closed under boolean operators and that W is compact often play a crucial role to establish connections between these concepts. We then consider a computable setting with effective versions of the complexity measures, and show that the equivalence between ordinal VC-dimension and predictive complexity fails. More precisely, we prove that the effective ordinal VC-dimension of a paradigm can be defined when all other effective notions of complexity are undefined. On a better note, when W is compact, all effective notions of complexity are defined, though they are not related as in the noncomputable version of the framework. © 2006 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
ISSN: 03043975
DOI: 10.1016/j.tcs.2006.07.041
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Apr 4, 2020


checked on Mar 19, 2020

Page view(s)

checked on Mar 28, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.