Proper Learning Algorithm for Functions of k Terms under Smooth Distributions |
| |
Authors: | Yoshifumi Sakai Eiji Takimoto Akira Maruoka |
| |
Affiliation: | Department of Information and Computer Sciences, Faculty of Engineering, Toyo University, 2100 Kujirai, Kawagoe, 350-8585, Japanf1;Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan, f2 |
| |
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 kkn={g(f1(v), …, fk(v)) | gk, f1, …, fkn} 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 kkn 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|