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 oflearning a general hypergraph using hyperedge-detecting queries, a problemmotivated by applications arising in chemical reactions and genome sequencing. We first present new lower bounds for this problem and then presentdeterministic and randomized adaptive algorithms with query complexities thatare almost optimal. All the algorithms we present in this paper run in timelinear in the query complexity and the number of variables $n$. In addition,all of the algorithms we present in this paper are asymptotically tight forfixed $r$ and/or $s$.
展开▼
机译：在本文中，我们研究了从成员资格查询中学习单调DNF的问题，该单调DNF的大小项最多为$ s $个项（每个项中的变量数），最多为$ r $个（$ s $ term $ r $ -MDNF个）。该问题等同于使用超边缘检测查询来学习通用超图的问题，该问题是由化学反应和基因组测序中出现的应用引起的。我们首先提出该问题的新下界，然后提出具有几乎最佳查询复杂性的确定性和随机化自适应算法。我们在本文中介绍的所有算法在查询复杂度和变量$ n $的数量上都是线性运行的。此外，我们在本文中介绍的所有算法都是渐近严格的固定$ r $和/或$ s $。
展开▼
