On using the Fourier transform to learn disjoint DNF

DOI10.1016/0020-0190(94)90057-4MaRDI QIDQ1318745zbMATH OpenOpenAlexWikidataFDO

Authors Roni Khardon

Publication date 5 April 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90057-4

zbMATH Keywords

computational learningDNFFourier transformlearning algorithmmembership queries

Mathematics Subject Classification ID

Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Learning and adaptive systems in artificial intelligence (68T05)

Review text

This paper addresses the problem of learning DNF expressions using membership queries. We extend previous results by \textit{E. Kushilevitz} and \textit{Y. Mansour} [SIAM J. Comput. 22, No. 6, 1331-1348 (1993)], on learning through Fourier representations, to show learnability of various subsets of DNF. In particular we show the polynomial learnability of disjoint DNF expressions under the uniform distribution, and exact learnability of disjoint \(\log n\) DNF. Disjoint DNF expressions are DNF expressions (disjunctions of conjunctions) in which every truth assignment satisfies at most one term. In disjoint \(\log n\) DNF expressions every conjunct is of length at most \(\log n\). We further show the learnability of \(\log n\) term DNF under the uniform distribution. The learnability of this class is already known but the algorithm and analysis given here are different. The learning algorithm we use is the one given by Kushilevitz and Mansour. The main contribution of this note is a different analysis of the Fourier spectrum of the respective function classes. This enables us to show the learnability of wider classes and with somewhat simplified proofs.

Recommendations

• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• scientific article; zbMATH DE number 1301800
• On the learnability of disjunctive normal form formulas
• Learning random monotone DNF

Cites work

• Fast learning of \(k\)-term DNF formulas with queries.

Cited in

(8)

• On learning monotone DNF under product distributions
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning DNF from random walks
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• scientific article; zbMATH DE number 1301800 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• Learning intersections and thresholds of halfspaces
• Learning unions of (1)-dimensional rectangles

This page was built for publication: On using the Fourier transform to learn disjoint DNF

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