On Exact Learning Monotone DNF from Membership Queries

DOI10.1007/978-3-319-11662-4_9MaRDI QIDQ2938727zbMATH OpenOpenAlexFDO

Authors Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi

Publication date 14 January 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0792

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Abstract: In this paper, we study the problem of learning a monotone DNF with at most $s$ terms of size (number of variables in each term) at most $r$ ($s$ term $r$-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing. We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with query complexities that are almost optimal. All the algorithms we present in this paper run in time linear in the query complexity and the number of variables $n$. In addition, all of the algorithms we present in this paper are asymptotically tight for fixed $r$ and/or $s$.

Recommendations

• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• 10.1162/153244303768966094
• scientific article; zbMATH DE number 1804124
• Learning nearly monotone k-term DNF
• scientific article; zbMATH DE number 1256727
• scientific article; zbMATH DE number 2077165
• On exactly learning disjunctions and DNFs without equivalence queries
• On learning monotone DNF formulae under uniform distributions
• More efficient PAC-learning of DNF with membership queries under the uniform distribution

Cited in

(14)

• Exact learning of linear combinations of monotone terms from function value queries
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• The learnability of exclusive-or expansions based on monotone DNF formulas
• Non-adaptive learning of a hidden hypergraph
• A subexponential exact learning algorithm for DNF using equivalence queries
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• Exact learning from an honest teacher that answers membership queries
• Non-adaptive learning of a hidden hypergraph
• 10.1162/153244303768966094
• scientific article; zbMATH DE number 1804124 (Why is no real title available?)
• Error-tolerant non-adaptive learning of a hidden hypergraph
• Lower bounds for graph reconstruction with maximal independent set queries
• On learning graphs with edge-detecting queries

This page was built for publication: On Exact Learning Monotone DNF from Membership Queries

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