Efficient Learning With Virtual Threshold Gates

Wolfgang Maass, Manfred K. WarmuthInf. Comput 1998 · DOI

TL;DR

This paper introduces a novel technique to efficiently learn complex geometric concepts by reducing them to simpler problems involving exponentially many "virtual" variables. This allows them to leverage the efficient Winnow algorithm, achieving near-optimal mistake bounds and polynomial time complexity for learning axis-parallel boxes and their unions, even in the presence of noise.

What Problem Does This Paper Address?

The paper tackles the challenge of designing efficient online learning algorithms for geometric concept classes, such as axis-parallel boxes. Traditional online learning algorithms often struggle with concept classes that have a large number of variables or complex structures, leading to either poor mistake bounds or prohibitive computational costs. Specifically, learning axis-parallel boxes in $d$ dimensions can require a number of mistakes that grows polynomially with $d$, and the computational cost can be exponential in the number of bits used to represent the boundaries. The authors aim to develop algorithms that are efficient (polynomial in $d$ and $\log n$, where $n$ is the range of coordinates) and achieve optimal or near-optimal mistake bounds for these geometric concepts.

Methods

The core of the paper's contribution lies in a reduction technique that transforms complex geometric learning problems into learning disjunctions over exponentially many "virtual" variables. This allows them to apply the Winnow algorithm, an online learning algorithm known for its logarithmic mistake bound growth with respect to the number of variables.

Here's a breakdown of the key methods:

  • Virtual Variables: For geometric concepts like axis-parallel boxes, the authors define a set of "virtual" binary variables. These variables correspond to halfspaces (e.g., $x_i < c$ or $x_i > c$). A geometric concept (or its complement) can then be represented as a disjunction of these virtual variables.
  • Winnow Algorithm: The paper utilizes two versions of Littlestone's Winnow algorithm: Winnow1 (for noise-free settings) and Winnow2 (which tolerates attribute noise). Winnow is chosen because its mistake bound grows logarithmically with the number of variables, making it suitable for the exponentially large number of virtual variables.
  • Implicit Weight Maintenance: A crucial innovation is the ability to simulate Winnow without explicitly storing and updating the weights for all exponentially many virtual variables. Instead, they use data structures (like balanced trees) to efficiently track dynamically changing blocks of variables that share the same weight. This allows for polynomial-time predictions and updates.
  • Reduction to Disjunctions: The paper demonstrates how various geometric concept classes (boxes, unions of boxes, etc.) can be expressed as disjunctions of these virtual variables. This reduction is the key to applying Winnow effectively.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for abstract concept classes rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of "Virtual" Variables: The most significant insight is that complex geometric problems can be elegantly mapped to simpler disjunctive learning problems by introducing a large number of auxiliary "virtual" variables. This abstraction is key to leveraging existing efficient learning algorithms.
  • Winnow's Suitability for High Dimensions: Winnow's logarithmic dependence on the number of variables is a critical property. It allows the authors to handle exponentially many virtual variables without incurring an exponential mistake bound, which would be the case for algorithms with linear dependence.
  • Efficient Simulation of Winnow: The development of data structures to implicitly manage Winnow's weights is a major technical contribution. This avoids the computational blow-up of explicitly maintaining exponentially many weights, making the algorithms practical.
  • Noise Robustness Inheritance: By using Winnow2, the developed algorithms inherit its ability to handle attribute noise, which is a valuable practical feature for real-world learning scenarios.
  • Optimal Bounds for Geometric Concepts: The paper achieves mistake bounds that are optimal or near-optimal (within a constant factor) for several geometric concept classes, including axis-parallel boxes and their unions, which are fundamental in computational geometry and machine learning.

Key Results

The paper presents several theoretical results, primarily in the form of mistake bounds and computational complexity for online learning algorithms:

  • Learning Axis-Parallel Boxes (BOX): An algorithm is presented that makes at most $O(d \log n)$ mistakes and requires $O(d(\log d + \log \log n))$ time per prediction/update. This is shown to be optimal.
  • Learning Noisy Axis-Parallel Boxes: A noise-robust algorithm achieves $O(z + d \log n)$ mistakes, where $z$ is the number of attribute errors.
  • Learning Unions of Boxes (U≤k BOX): For a fixed dimension $d$, algorithms are provided with mistake bounds polynomial in $k$ and $\log n$, and time bounds that are also polynomial. For constant $k$, the bounds are $O(dk \log n + z)$ mistakes and $O((dk \log n + z)^2d)$ time.
  • Learning Lower-Dimensional Boxes: Algorithms are developed for boxes that depend on only $u$ out of $d$ dimensions, achieving $O(z + u \log(dn/u))$ mistakes.
  • Generalization to LINk,v: The method is extended to learn generalized monotone disjunctions with non-boolean base variables.

Limitations and Future Work

  • Computational Complexity for Unions of Boxes: While the mistake bounds for unions of boxes are good, the time complexity for learning $U_{\le k} BOX^d$ can still be exponential in $k$ (specifically, $O((dk \log n + z)^k)$). The authors note that improving this to be polynomial in $k$ and $d$ would solve a major open problem in learning $k$-term DNF formulas.
  • Continuous Domains: The current work focuses on discretized domains. Extending the methods to continuously valued domains is mentioned as an interesting future direction.
  • Other Learning Models: The paper primarily focuses on the online learning model. While connections to PAC learning are discussed, further exploration of these connections and other learning models could be beneficial.
  • General Geometric Concepts: The paper hints at the possibility of applying the method to more general geometric objects defined by arbitrary sets of directions, which could be a fruitful area for future research.

Summary updated

BibTeX
@article{maass1998efficient,
  author = {Wolfgang Maass and Manfred K. Warmuth},
  title = {{Efficient Learning With Virtual Threshold Gates}},
  journal = {Inf. Comput.},
  year = {1998},
  doi = {10.1006/inco.1997.2686},
}
Figure