Online Learning of k-CNF Boolean Functions

Joel Veness, Marcus Hutter

Abstract

This paper presents a computationally efficient framework for the online learning of $k$-CNF Boolean functions, bridging the gap between classical "Probably Approximately Correct" (PAC) learning and modern online probabilistic prediction. By transforming Leslie Valiant’s foundational PAC learning algorithm into a Bayesian framework, the authors derive two novel algorithms that achieve low cumulative log-loss while maintaining polynomial time and space complexity. This work effectively bypasses the #P-complete complexity typically associated with full Bayesian inference for Boolean logic, providing a robust path for sequential prediction in logical domains.

Introduction

In 1984, Leslie Valiant introduced the PAC learning framework, showing that certain classes of logic—specifically $k$-Conjunctive Normal Form ($k$-CNF) formulas—could be learned efficiently from examples. However, PAC learning is traditionally batch-oriented and relies on the assumption that data is Independent and Identically Distributed (IID).

In contrast, many modern applications, such as real-time data compression or streaming classification, require online learning. In this setting, a model must predict the next label, observe the true value, and update its internal state immediately. While the Bayesian mixture is the theoretical gold standard for online prediction, the authors demonstrate that calculating this mixture for $k$-CNF functions is #P-complete. This computational intractability necessitates new algorithms that mimic Bayesian behavior without the exponential overhead.

Methodology

The authors focus their derivation on monotone conjunctions (simple "AND" logic, such as $x_1 \wedge x_3 \wedge x_6$), because $k$-CNF problems can be mathematically reduced to this form by expanding the input space to include all possible $k$-literal clauses.

Algorithm 1: Hybrid Bayesian + Memorization

The authors discovered that while general Bayesian inference is hard, it becomes tractable if the model only encounters "positive" examples (where the output is 1). Algorithm 1 uses exact Bayesian updates for positive instances and a simple memorization strategy for negative instances. This hybrid approach ensures a cumulative loss bounded by $O(d^2)$, where $d$ is the number of variables, though it requires $O(nd)$ space to store negative examples.

Algorithm 2: The Smoothed Practical Approach

To improve memory efficiency, the authors proposed a "smoothed" version that tracks which variables remain consistent with the data using only $O(d)$ space. While its loss bound is slightly higher—$O(d \log n)$, growing logarithmically with the number of examples $n$—it is significantly more viable for high-speed data streams and embedded systems.

Theoretical Insights

Two key insights underpin the success of these algorithms:

  1. The Positive Example Shortcut: Using the Generalized Distributive Law, the authors prove that the sum over $2^d$ possible hypotheses collapses into a simple product of $d$ terms when only positive labels are considered. This "aha moment" allows the math to remain tractable.
  2. Valiant as a Bayesian: The research shows that Valiant’s original 1984 algorithm can be reinterpreted as a "Maximum A Posteriori" (MAP) model selection procedure under a specific family of priors, providing a new probabilistic foundation for classical learning theory.

Empirical Results

The algorithms were evaluated using synthetic data to verify theoretical bounds, as well as real-world datasets from the UCI repository:

  • UCI Mushroom Dataset: In this classification task (edible vs. poisonous), the $k$-CNF approach (with $k=3$) achieved 98.58% accuracy. This significantly outperformed the "Model Averaging Discriminative Naive Bayes" (MADNB) baseline, which reached 93.17%.
  • UCI King-Rook vs. King-Pawn: This chess endgame dataset was used to test the limits of the Boolean logic approach, confirming the model's ability to capture complex logical dependencies.
  • Efficiency: Algorithm 2 demonstrated that it could achieve high accuracy with very low memory overhead, making it a practical choice for real-time applications.

Limitations and Future Work

Despite the strong performance on Boolean datasets, the authors note that many real-world problems involve continuous data (e.g., temperature or financial metrics). The current algorithms are best suited as components within larger "predictive ensembles" rather than standalone solutions for non-Boolean data.

Additionally, Algorithm 1 can suffer from "infinite loss" if the data is not strictly generated by a monotone conjunction (the "model mismatch" problem). While Algorithm 2 mitigates this through smoothing, further research is required to increase robustness against noise. The authors envision integrating these logic-based predictors into universal source coding architectures to better exploit logical structures in general data compression.

Summary updated

BibTeX
@inproceedings{veness2015online,
  author = {Joel Veness and Marcus Hutter},
  title = {{Online Learning of k-CNF Boolean Functions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=S1V91NfuZr},
}
Figure