Learning functions of k relevant variables

摘要

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function that depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples that runs in time roughly (nk)ωω+1, where ω<2.376 is the matrix multiplication exponent. We thus obtain the first-polynomial factor improvement on the naive nk time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.