Complexity of learning Boolean formulas from examples explained
Fitting and Learning Basis-Restricted Propositional Formulas
Logic in Computer ScienceMachine Learning
Summary
This paper looks at how hard it is to find or learn logical formulas made from certain basic building blocks, called Boolean functions, that match given example data. It studies different tasks like finding any formula that fits the data, finding the simplest formula, or handling mistakes when the data doesn’t perfectly match any formula. The authors figure out the computational difficulty of these tasks depending on which building blocks are allowed. They also consider both formulas shaped like trees and more general logical circuits.
Boolean functionpropositional formulalearning theorycomputational complexityempirical risk minimizationOccam algorithmPAC learninglogical circuitfitting sample
Authors
Balder ten Cate
Abstract
For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.