Title: Learning Random DNF over the Uniform Distribution
Speaker: Linda Sellie, Polytechnic Institute of NYU
Date: Wednesday, September 23, 2009 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, we show that randomly generated c log(n)-DNF formula can be learned exactly in proba- bilistic polynomial time using randomly generated examples. Our notion of randomly generated is with respect to a uniform distribution. To prove this we extend the concept of well behaved c log(n)-Monotone DNF formulae to c log(n)-DNF, and show that almost every DNF formula is well-behaved, and that there exists a probabilistic Turing machine that exactly learns all well behaved c log(n)-DNF formula. This is the ям?rst algorithm that learns a large class of DNF with a polynomial number of terms from random examples alone.