On a Capacity Control Using Boolean Kernels for the Learning of Boolean Functions Ken Sadohara   View Paper (PDF)   Return to Main-Track Regular Papers Abstract This paper concerns the classification task discrete attribute spaces, but consider the task in a more fundamental framework: the learning of Boolean functions. The purpose of this paper is to present a new learning algorithm for Boolean functions called Boolean Kernel Classifier (BKC) employing capacity control using Boolean kernels. BKC uses Support Vector Machines (SVMs) as learning engines and Boolean kernels are primarily used for running SVMs in feature spaces spanned by conjunctions of Boolean literals. However, another inportant role of Boolean kernels is to appropriately control the size of its hypothesis space to avoid overfitting. After applying a SVM to learn a classifier f in a feature space H induced by a Boolean kernel f k of f onto a subspace Hk of H spanned by conjunctions with length at most k, BKC can determine the smallest k such that f k is as accurate as f and learn another f' in Hk expected to have lower error for unseen data. By an empirical study on learning of randomly generated Boolean functions, it is shown that the capacity control is effective, and BKC outperforms C4.5 and naive Bayes classifiers. DiSC'03 © 2003 Association for Computing Machinery