Learning from positive examples

Learning from positive examples - Anindya De

Anindya De
Institute for Advanced Study; Member, School of Mathematics
November 5, 2013

We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube {1,1}n. As in the standard PAC learning model, a learning problem in our framework is defined by a class C of Boolean functions over {1,1}n, but unlike the standard PAC model, in our model the learning algorithm is given uniform random satisfying assignments of an unknown fC and its goal is to output a high-accuracy approximation of the uniform distribution over f1(1). This distribution learning problem may be viewed as a demanding variant of standard Boolean function learning, where the learning algorithm only receives positive examples and --- more importantly --- must output a hypothesis function which has small *multiplicative* error (i.e. small error relative to the size of f1(1)). As our main results, we show that the two most widely studied classes of Boolean functions in computational learning theory ---linear threshold functions and DNF formulas---have efficient distribution learning algorithms in our model. Our algorithm for linear threshold functions runs in time poly(n,1/eps) and our algorithm for polynomial-size DNF runs in time quasipoly(n,1/eps). On the other hand, we prove complementary hardness results which shows that under cryptographic assumptions, learning monotone 2-CNFs, intersections of 2 halfspaces and degree-2 PTFs. This shows that our algorithms are close to what is efficiently learnable in this model. Joint work with Ilias Diakonikolas and Rocco Servedio.