Open Collections

Equivalence query learning and the negation of the finite cover property

Banff International Research Station for Mathematical Innovation and Discovery

There are multiple connections between model-theoretic notions of complexity and machine learning. NIP formulas correspond to PAC-learning by way of VC-dimension, and stable formulas correspond to online learning by way of Littlestone dimension, also known as Shelah's 2-rank. We explore a similar connection between formulas without the finite cover property and equivalence query learning. In equivalence query learning, a learner attempts to identify a certain set from a set system by making hypotheses and receiving counterexamples. We use the notion of (strong) consistency dimension, an analogue of the the negation of the finite cover property for set systems. We show that finite (strong) consistency dimension and finite LIttlestone dimension characterize equivalence query learning, drawing on ideas from model theory. We also discuss the role of Littlestone dimension and strong consistency dimension in algorithms.

Mathematics; Mathematical logic and foundations; Combinatorics

video/mp4

Author affiliation: University of Illinois at Chicago

2019-04-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69684

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/