Attribute-efficient learning in query and mistake-bound models

DOI10.1006/jcss.1998.1571zbMath0945.68530MaRDI QIDQ1271616

Nader H. Bshouty, Lisa Hellerstein

Publication date: 27 September 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1571

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Computational sample complexity and attribute-efficient learning, Theory revision with queries: Horn, read-once, and parity formulas, Learning conditional preference networks, Attribute-efficient learning in query and mistake-bound models, On parallel attribute-efficient learning., More efficient PAC-learning of DNF with membership queries under the uniform distribution, Identification of partial disjunction, parity, and threshold functions, Revising threshold functions, Learning attribute-efficiently with corrupt oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Learning Boolean functions in an infinite attribute space
• An explicit construction of short monotone formulae for the monotone symmetric functions
• Attribute-efficient learning in query and mistake-bound models
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
• Learning in the presence of finitely or infinitely many irrelevant attributes
• Queries and concept learning
• Parity, circuits, and the polynomial-time hierarchy
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Learning read-once formulas with queries