Lower bound methods and separation results for on-line learning models
From MaRDI portal
Publication:1207301
zbMath0766.68113MaRDI QIDQ1207301
Publication date: 1 April 1993
Published in: Machine Learning (Search for Journal in Brave)
lower boundsconcept learningmachine learningVapnik-Chervonenkis dimensionmembership queriesequivalence queries
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
