Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

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 F k ∘ T k n ={g(f 1(v), …, fk (v))| g∈ F k, f 1, …, fk ∈ T n } in polynomial time for constant k, where F k is the class of all Boolean functions of k variables and T n is the class of terms over n variables. Although class F k ∘ T 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.

Authors

• Yoshifumi Sakai
• Eiji Takimoto
• Akira Maruoka

Keywords

No keywords are indexed for this paper.