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.
A Boolean function is a rule that assigns a binary yes-or-no classification to each input point that is presented to it. A familiar example of such a binary classification rule comes from the area of college admissions. Each applicant's information may be encoded as a sequence of responses to yes-or-no questions, such as "Are the applicant's SAT scores at least 1300? at least 1350? at least 1400? Is the applicant's GPA at least 3.5? at least 3.75? at least 3.90? Does the applicant have a leadership role in an extracurricular activity? Is the applicant a varsity athlete?" and so on. The classification rule assigns a yes-or-no output to each input data sequence (such as a recommendation of whether or not to extend the applicant an offer of admission). A special and widely encountered kind of Boolean function is a "monotone increasing" Boolean function. These are functions where changing the response to some question from "no" to "yes" can potentially change the output classification from "no" to "yes" but cannot change the output from "yes" to "no." (The college admissions example from the preceding paragraph is a natural example of this: all other things being equal, having higher SAT scores, or a leadership role in an extracurricular activity, would not cause an applicant who would otherwise have been accepted to be rejected.) This project aimed at developing new algorithms that can learn certain types of monotone increasing Boolean functions from labeled examples. Such algorithms are relevant to a wide range of areas within theoretical computer science, including computational complexity theory, computational learning theory, and cryptography. Such algorithms can also have potential application in a range of real-world learning scenarios (since, as sketched above, many classification rules of interest, which one might wish to learn in the real world, are monotone increasing.) One of the project's main results was that the PI and his collaborators discovered new structural results about "linear threshold functions"; these are special types of monotone Boolean functions which arise in a wide range of areas such as machine learning, voting theory, and elsewhere. Having a better understanding of the structural properties of these functions may help us to develop improved learning algorithms for these functions. Another significant outcome is that the PI and his collaborators came up with new algorithms and lower bounds for testing whether an unknown Boolean function is monotone or not. When presented with a real-life classification problem that one would like to analyze, if the unknown classification rule is far from monotone then algorithms tailored for learning monotone classification rules will not be useful. Thus one would like to have an efficient way of inexpensively testing whether an unknown classification rule is monotone or not (before running a potentially expensive monotone function learning algorithm, which might not work well if the function is not monotone after all). The PI and his collaborators gave both the best known algorithm for testing whether an unknown Boolean function is monotone, and proved new lower bounds showing that no algorithm can perform much better than the testing algorithm which they developed.
