**Authors: Yoshifumi Sakai, Eiji Takimoto, and Akira Maruoka**

**Source: ***Information & Computation* Vol. **152**, No. 2,
1999, 188 - 204.

**Abstract.**
In this paper, we introduce a probabilistic distribution, called a smooth
distribution, which is a generalization of variants of the uniform distribution
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
_{k}^{k}_{n}={*g*(*f*_{1}(v),...,*f*_{k}(v)) | g _{k},
*f*_{v},..., *f*_{k}
_{n}}
in polynomial time for constant *k*, where _{k}
is the class of all Boolean functions of *k* variables and
_{n} is the class of terms over
*n* variables. Although class
_{k}^{k}_{n} was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it
is properly learnable under a distribution-free setting.

©Copyright 1999, Academic Press