TY - JOUR

T1 - Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

AU - Sakai, Yoshifumi

AU - Takimoto, Eiji

AU - Maruoka, Akira

PY - 1999/8/1

Y1 - 1999/8/1

N2 - 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 ○ script T signkn = {g(f1(v), ..., fk(v))\g∈ ℱk, f1, ..., fk ∈ script T signn} in polynomial time for constant k, where ℱk is the class of all Boolean functions of k variables and sript T signn is the class of terms over n variables. Although class ℱk ○ script T signkn 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.

AB - 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 ○ script T signkn = {g(f1(v), ..., fk(v))\g∈ ℱk, f1, ..., fk ∈ script T signn} in polynomial time for constant k, where ℱk is the class of all Boolean functions of k variables and sript T signn is the class of terms over n variables. Although class ℱk ○ script T signkn 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.

UR - http://www.scopus.com/inward/record.url?scp=0346304060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346304060&partnerID=8YFLogxK

U2 - 10.1006/inco.1998.2785

DO - 10.1006/inco.1998.2785

M3 - Article

AN - SCOPUS:0346304060

SN - 0890-5401

VL - 152

SP - 188

EP - 204

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -