Boolean regression

The authors take a regression-based approach to the problem of induction, which is the problem of inferring general rules from specific instances. Whereas traditional regression analysis fits a numerical formula to data, they fit a logical formula to boolean data. For instance, an expert system can be constructed for fitting rules to an expert’s observed behavior. A regression-based approach has the advantage of providing tests of statistical significance as well as other tools of regression analysis. The present approach can be extended to nonboolean discrete data, and the authors argue that it is better suited to rule construction than logit and other types of categorical data analysis. They find maximum likelihood and bayesian estimates of a best-fitting boolean function or formula and show that bayesian estimates are more appropriate. The authors also derive confidence and significance levels. They show that finding the best-fitting logical formula is a pseudo-boolean optimization problem, and finding the best-fitting monotone function is a network flow problem.