Lower bound methods and separation results for on-line learning models

zbMath0766.68113MaRDI QIDQ1207301

Wolfgang Maass, György Turán

Publication date: 1 April 1993

Published in: Machine Learning (Search for Journal in Brave)

zbMATH Keywords

lower boundsconcept learningmachine learningVapnik-Chervonenkis dimensionmembership queriesequivalence queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Learning elementary formal systems with queries., On-line learning of rectangles and unions of rectangles, Exact learning from an honest teacher that answers membership queries, Revising threshold functions, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, On the complexity of function learning, The bounded injury priority method and the learnability of unions of rectangles, Efficient learning with virtual threshold gates, Combinatorial results on the complexity of teaching and learning, Learning unions of tree patterns using queries, Unnamed Item, Complexity parameters for first order classes, Queries revisited., Learning unions of tree patterns using queries, Learning conditional preference networks, Structural results about exact learning with unspecified attribute values, Noise-tolerant parallel learning of geometric concepts, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, Exact Learning of Discretized Geometric Concepts, General lower bounds on the query complexity within the exact learning model, The query complexity of finding local minima in the lattice, Theory revision with queries: Horn, read-once, and parity formulas