SOURCE-LINKED INTELLIGENCE

Fitting and Learning Basis-Restricted Propositional Formulas

arXiv · AI, language, vision and robotics · article · Sep 8, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global