Attribute-efficient learning in query and mistake-bound models

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

Lisa Hellerstein, Nader H. Bshouty

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

Nonnumerical algorithms (68W05) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (10)

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

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

This page was built for publication: Attribute-efficient learning in query and mistake-bound models