Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms

Roni Khardon, Dan Roth, Rocco A. ServedioJAIR 2005 · OpenReview

Abstract

In online learning, representing hypotheses as linear threshold elements over Boolean features is a standard approach. To enhance expressiveness, the feature space is often expanded to include conjunctions of basic features. This paper investigates the tradeoff between computational efficiency and generalization ability when using kernel functions to navigate these expanded spaces. Focusing on the Perceptron and Winnow algorithms, we demonstrate a fundamental dichotomy: while the Perceptron can be run efficiently using Boolean kernels, it suffers from an exponential mistake bound. Conversely, while Winnow offers superior convergence properties, simulating its multiplicative updates over exponential feature spaces is #P-hard. These results establish a rigorous "no free lunch" theorem for Boolean kernel methods.

Introduction

Machine learning tasks involving Boolean features ($x_1, x_2, \dots, x_n$) often require models that can capture complex logical relationships, such as Disjunctive Normal Form (DNF) formulas. A common strategy to increase the power of linear classifiers is to map the input into a higher-dimensional space consisting of all possible conjunctions (ANDs) of the original features. However, the number of such conjunctions grows exponentially ($3^n$), making explicit representation computationally prohibitive.

Kernel methods traditionally solve this by allowing algorithms to operate in these massive spaces implicitly. By defining a kernel function $K(x, y)$ that computes the inner product in the expanded space, one can theoretically run online learning algorithms without ever enumerating the features. This research examines whether this approach is viable for the two pillars of online learning: the additive-update Perceptron and the multiplicative-update Winnow.

The Perceptron: Efficient but Ineffective

The authors first define specific Boolean kernels capable of capturing conjunctions. For instance, a kernel such as $K(x, y) = 2^{same(x,y)}$ allows the Perceptron to operate in a space containing all $3^n$ possible conjunctions. This kernel is computationally efficient, requiring only $O(n)$ time to compute.

However, the paper proves that this efficiency comes at a steep price in terms of convergence. In the expanded feature space, the "margin"—the geometric gap between positive and negative examples—becomes exponentially small. Because the Perceptron’s mistake bound is inversely proportional to the square of the margin, the algorithm is forced to make an astronomical number of mistakes ($2^{\Omega(n)}$) even when learning relatively simple monotone DNF functions. Essentially, the additive nature of the Perceptron's updates fails to distinguish relevant features from the overwhelming sea of irrelevant conjunctions.

Winnow: Effective but Incomputable

In contrast to the Perceptron, the Winnow algorithm utilizes multiplicative updates. Theoretically, Winnow is much better suited for high-dimensional Boolean spaces because its mistake bound grows logarithmically with the number of irrelevant features. Known upper bounds suggest that Winnow could learn DNF formulas with only a polynomial number of mistakes in this setting.

This leads to the central question: Can we construct a "Kernel Winnow" to achieve this superior convergence efficiently? The authors provide a negative answer. They demonstrate that simulating Winnow’s behavior over a space of monotone conjunctions is equivalent to counting the satisfying assignments of a Boolean formula. Specifically, they prove that computing the Winnow update is #P-hard (a complexity class even harder than NP). This implies that unless $P = NP$, there is no general construction that can run Winnow with kernels in polynomial time.

The Efficiency-Convergence Tradeoff

The research formalizes a fundamental tension in the design of online learning algorithms for logical domains:

  1. Additive Updates (Perceptron): These are computationally efficient to implement via kernels but exhibit poor convergence (slow learning) because they cannot effectively ignore the exponential noise of the expanded feature space.
  2. Multiplicative Updates (Winnow): These exhibit excellent convergence (fast learning) but are computationally intractable to implement via kernels because the implicit counting required by the update rule is #P-hard.

Conclusion

This study provides a theoretical foundation for the limitations of kernel methods in Boolean domains. It explains why practitioners often find success with low-degree polynomial kernels but encounter diminishing returns or computational explosions when attempting to capture higher-order logical dependencies. While the Perceptron is fast, it is "forgetful" in the face of high dimensionality; while Winnow is "smart," it is too slow to be simulated implicitly. Future work may focus on approximate simulations or restricted concept classes where the #P-hardness might be bypassed, but the general tradeoff remains a cornerstone of Boolean learning theory.

Summary updated

Abstract

The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing the expressiveness of learned hypotheses in this context is to expand the feature set to include conjunctions of basic features. This can be done explicitly or where possible by using a kernel function. Focusing on the well known Perceptron and Winnow algorithms, the paper demonstrates a tradeoff between the computational efficiency with which the algorithm can be run over the expanded feature space and the generalization ability of the corresponding learning algorithm. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over a feature space of exponentially many conjunctions; however we also show that using such kernels, the Perceptron algorithm can provably make an exponential number of mistakes even when learning simple functions. We then consider the question of whether kernel functions can analogously be used to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. Known upper bounds imply that the Winnow algorithm can learn Disjunctive Normal Form (DNF) formulae with a polynomial mistake bound in this setting. However, we prove that it is computationally hard to simulate Winnow's behavior for learning DNF over such a feature set. This implies that the kernel functions which correspond to running Winnow for this problem are not efficiently computable, and that there is no general construction that can run Winnow with kernels.
BibTeX
@article{khardon2005efficiency,
  author = {Roni Khardon and Dan Roth and Rocco A. Servedio},
  title = {{Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms}},
  journal = {J. Artif. Intell. Res.},
  year = {2005},
  url = {https://openreview.net/forum?id=-CuHthMI0B},
}

Loading related content...

Figure