AF: Small: The Boundary of Learnability for Monotone Boolean Functions

机器学习是一个充满活力和快速发展的研究领域，在科学发现、搜索技术、金融、自然语言等各个领域的许多应用中发挥着重要作用。机器学习理论的一个重要目标是了解哪些类型的二进制分类规则（即布尔函数）可以有效地从标记数据中学习，哪些不能。本文描述了从一致随机例子中理解不同类型单调布尔函数的可学习性的详细理论研究方案。从学习的角度来看，单调函数是非常自然的；它们也是计算复杂性理论和布尔函数分析中的核心函数类，其可学习性的研究与这些领域有着密切的联系。近年来，在单调函数学习的有效算法和硬度结果方面都取得了令人兴奋的进展。PI相信，在这一进展的基础上，对单调函数的可学习类和不可学习类之间边界的细粒度理解可能是触手可及的。更准确地说，PI将表明单调DNF公式（深度-2电路）是有效可学习的，而单调深度-3电路则不是。在我们理解这类重要的布尔函数的可学习性方面，建立这一点将是一个里程碑。从积极的方面来看，PI将处理一系列中间问题，最终获得一种用于学习任意多(n)项单调DNF公式的多(n)时间算法：*更好地学习单调决策树。PI将分析一种用于决策树归纳的广泛使用的机器学习启发式算法，并证明它实际上是一种用于学习多(n)大小的单调决策树的有效算法。*学习单调CDNF。利用布尔函数离散傅里叶分析的结果和技术，PI将致力于获得单调布尔函数的多项式时间算法，其CNF（合取范式）大小和DNF（析取范式）大小都是n的多项式（比多(n)大小的单调决策树更广泛的一类）。*学习单调DNF公式。PI开发了一种算法来学习具有次多项式项数的单调DNF公式；使用不同的技术，他还给出了一个聚(n)时间算法，可以学习随机聚(n)大小的单调DNF公式。PI将努力统一这两种方法，以获得一个单一的，更强大的学习单调DNF的算法。*其他方法。PI将研究其他可能对单调函数学习问题有用的方法：1)分析单调函数中“傅立叶权重”的分布；2)应用专门的增强算法学习单调函数；3)使用布尔函数的傅里叶分析中的猜想作为学习结果的工具。在他最近工作的基础上，PI还将建立两种学习单调函数的负结果：加密硬度结果和强统计查询学习的下界。这两种情况的目标都是表明学习深度-3单调回路是困难的；复杂性理论中的单调硬度放大技术有望在这两个方向上发挥作用。

Machine learning is a dynamic and rapidly growing research area that plays an important role in many applications over a diverse range of areas including scientific discovery, search technology, finance, natural language, and more. An important goal in machine learning theory is to understand which types of binary classification rules (i.e. Boolean functions) can be efficiently learned from labeled data, and which cannot. This proposal describes a detailed program of theoretical research on understanding the learnability of different types of monotone Boolean functions from uniform random examples. Monotone functions are highly natural from a learning point of view; they are also a central class of functions in computational complexity theory and the analysis of Boolean functions, and the study of their learnability has close connections to these areas.Recent years have seen exciting advances both on efficient algorithms and on hardness results for learning monotone functions. The PI believes that building on this progress, a fine-grained understanding of the boundary between learnable and unlearnable classes of monotone functions may be within reach. More precisely, the PI will work to show that monotone DNF formulas (depth-2 circuits) are efficiently learnable, while monotone depth-3 circuits are not. Establishing this would be a landmark in our understanding of the learnability of this important class of Boolean functions.On the positive side the PI will work on a range of intermediate problems, leading up to the goal of obtaining a poly(n)-time algorithm for learning arbitrary poly(n)-term monotone DNF formulas:* Learning Monotone Decision Trees Better. The PI will analyze a widely used machine learning heuristic for decision tree induction and work to show that it is in fact an efficient algorithm for learning poly(n)-size monotone decision trees.* Learning Monotone CDNF. Using results and techniques from discrete Fourier analysis of Boolean functions, the PI will work to obtain a polynomial time algorithm for monotone Boolean functions whose CNF (Conjunctive Normal Form) size and DNF (Disjunctive Normal Form) size are both polynomial in n (a broader class than poly(n)-size monotone decision trees).* Learning Monotone DNF Formulas. The PI has developed an algorithm for learning monotone DNF formulas with a subpolynomial number of terms; using different techniques he has also given a poly(n)-time algorithm that can learn random poly(n)-size monotone DNF formulas. The PI will work to unify these two approaches to obtain a single, more powerful, algorithm for learning monotone DNF.* Other approaches. The PI will study other approaches that may be useful for monotone function learning problems: 1) analyzing the distribution of "Fourier weight" in monotone functions; 2) applying specialized boosting algorithms to learn monotone functions; and 3) using conjectures in Fourier analysis of Boolean functions as tools toward learning results.Building on his recent work, the PI will also work to establish two types of negative results for learning monotone functions: cryptographic hardness results, and lower bounds for Strong Statistical Query learning. The goal in both cases is to show that learning depth-3 monotone circuits is hard; techniques for monotone hardness amplification in complexity theory are expected to play a role in both of these directions.