On PAC learning algorithms for rich Boolean function classes

DOI10.1016/J.TCS.2007.05.018MaRDI QIDQ2382283zbMATH OpenOpenAlexFDO

Authors Lisa Hellerstein, Rocco A. Servedio

Publication date 28 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.05.018

zbMATH Keywords

computational learning theoryPAC learningpolynomial threshold function

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Learning juntas
• What circuit classes can be learned with non-trivial savings?
• Learning functions of \(k\) relevant variables
• Learning sparse polynomial functions
• Learning from satisfying assignments

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 446494 (Why is no real title available?)
• scientific article; zbMATH DE number 1511696 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• A decision-theoretic generalization of on-line learning and an application to boosting
• A subexponential exact learning algorithm for DNF using equivalence queries
• A theory of the learnable
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Approximate inclusion-exclusion
• Boosting a weak learning algorithm by majority
• Computing Boolean functions by polynomials and threshold circuits
• Constant depth circuits, Fourier transform, and learnability
• Cryptographic hardness of distribution-specific learning
• Efficient noise-tolerant learning from statistical queries
• Exact learning Boolean functions via the monotone theory
• Learnability and the Vapnik-Chervonenkis dimension
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning Decision Trees Using the Fourier Spectrum
• Learning Integer Lattices
• Learning decision trees from random examples
• Learning functions represented as multiplicity automata
• Learning intersections and thresholds of halfspaces
• Learning regular sets from queries and counterexamples
• Learning with restricted focus of attention
• New degree bounds for polynomial threshold functions
• Occam's razor
• On Learning Ring-Sum-Expansions
• On learning width two branching programs
• On the Fourier spectrum of monotone functions
• On the Size of Weights for Threshold Gates
• PP is closed under intersection
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Theory of majority decision elements

Cited in

(13)

• An Algebraic Perspective on Boolean Function Learning
• scientific article; zbMATH DE number 1966607 (Why is no real title available?)
• Sign-representation of Boolean functions using a small number of monomials
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• scientific article; zbMATH DE number 1895645 (Why is no real title available?)
• On the complexity of compressing obfuscation
• Private data release via learning thresholds
• Agnostically learning Boolean functions with finite polynomial representation
• Learning sparse polynomial functions
• What circuit classes can be learned with non-trivial savings?
• Explaining AI decisions using efficient methods for learning sparse Boolean formulae
• Almost optimal proper learning and testing polynomials
• On learning embedded midbit functions

Describes a project that uses

Uses Software

• AdaBoost.MH

This page was built for publication: On PAC learning algorithms for rich Boolean function classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2382283)