Simple learning algorithms using divide and conquer

DOI10.1007/BF01262930zbMath0868.68094MaRDI QIDQ1355381

Nader H. Bshouty

Publication date: 17 August 1997

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

learning algorithmdecision treeexact learningPAC-learningqueriesdivide and conquerDNFboolean functions

Mathematics Subject Classification ID

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

Related Items (8)

On approximating weighted sums with exponentially many terms ⋮ Exact learning from an honest teacher that answers membership queries ⋮ SAT-based invariant inference and its relation to concept learning ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials ⋮ Learning with errors in answers to membership queries ⋮ Learning attribute-efficiently with corrupt oracles ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ The query complexity of finding local minima in the lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Fast learning of \(k\)-term DNF formulas with queries.
• Asking questions to minimize errors
• Exact learning Boolean functions via the monotone theory
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• A theory of the learnable
• Learning read-once formulas with queries
• Learning Decision Trees Using the Fourier Spectrum
• Cryptographic limitations on learning Boolean formulae and finite automata
• Efficient noise-tolerant learning from statistical queries

This page was built for publication: Simple learning algorithms using divide and conquer