Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.tcs.2006.07.041
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. https://doi.org/10.1016/j.tcs.2006.07.041 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/103740 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.