Proper learning algorithm for functions of k terms under smooth distributions

In this paper, we introduce a probabilistic distribution, called a smooth d istribution, which is a generalization of variants of the uniform distribut ion such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as F-k . J(n)(k) = {g( f(1)(V),..., f(k)(v)) g is an element of f(k), f(1), ..., f(k) is an element of J(n)}in polynomi al time for constant k, where F-k is the class of all Boolean functions of k variables and J(n) is the class of terms over n variables. Although class F-k . J(n)(k) was shown by Slum and Singh to be learned using DNF as the h ypothesis class, it has remained open whether it is properly learnable unde r a distribution-free setting. (C) 1999 academic Press.