Improving Performance in Neural Networks Using a Boosting Algorithm

Harris Drucker, Robert E. Schapire, Patrice Y. SimardNeurIPS 1992 · OpenReview

TL;DR

This paper presents a practical implementation of Schapire’s theoretical "boosting" algorithm, demonstrating how to combine multiple neural networks to achieve significantly lower error rates in optical character recognition (OCR). By using a novel "deformation model" to generate a virtually infinite supply of synthetic training data, the authors reduced error rates by up to a factor of three on standard handwritten digit and letter datasets.

The Challenge of Finite Data

In the early 1990s, neural networks were already showing promise in OCR, but researchers hit a plateau: how do you push performance further without simply building massive, unmanageable models?

Robert Schapire had previously proven a "boosting" theorem showing that a collection of "weak" learners (those performing just slightly better than a coin flip) could be combined into a single "strong" learner with arbitrarily low error. However, the theory relied on a major assumption: access to an "oracle" that could provide an inexhaustible supply of independent training samples. In the real world, datasets like the USPS handwritten digits were finite and relatively small. This paper bridges the gap between that theoretical ideal and practical engineering.

The Boosting Pipeline and Methods

The authors implemented a three-stage boosting pipeline to create an ensemble of networks:

  1. Network 1: Trained on the original available data.
  2. Network 2: Trained on a "filtered" dataset. To build this, images are passed through Network 1; the training set for Network 2 is composed of 50% images Network 1 got wrong and 50% it got right.
  3. Network 3: Trained on images where Network 1 and Network 2 disagree.

The "Secret Sauce": Image Deformations

To solve the data scarcity problem and simulate the "oracle" required by boosting theory, the authors used a Deformation Model. Instead of needing new real-world images, they took existing ones and applied small mathematical transformations: translations, rotations, scaling, and "thickness" changes (using derivatives of Gaussian kernels). This generated hundreds of thousands of "new" difficult patterns to challenge the subsequent networks.

Soft Decision Making

While the original theory suggested a simple majority vote among the networks, the authors found that summing the raw outputs (a "soft-decision" rule) worked better. This incorporates the "confidence" of each network into the final result, rather than treating every vote as equal regardless of the output margin.

Key Insights

  • Synthetic Data as a Proxy for Theory: The most important insight is that local deformations of images can act as a valid proxy for the independent samples required by boosting theory. This turned a theoretical curiosity into a functional tool for computer vision.
  • Confidence Matters: Moving from "hard" voting to "soft" summing reduced error rates by an additional 0.5%. This highlights that the degree of a network's certainty is a valuable signal when ensemble modeling.
  • Boosting "Strong" Learners: While the theory focuses on "weak" learners (50% error), this paper shows boosting is highly effective even when the base learners are already quite good (e.g., 5% error).
  • The Reject Rate Metric: The authors emphasize the "reject rate"—the percentage of images a system refuses to classify to maintain a 1% error rate on the accepted images. In industrial applications like mail sorting, it is often better to ask a human for help than to guess incorrectly.

Key Results

The study evaluated the algorithm on four major handwritten databases: USPS Digits (12,000 samples), NIST Digits (220,000 samples), NIST Upper Case Alphas (45,000 samples), and NIST Lower Case Alphas (45,000 samples).

The boosting approach consistently outperformed single-network architectures across all benchmarks.

Performance comparison of single networks versus boosting across four databases.

As shown in the results, boosting improved performance dramatically. On the USPS dataset, the reject rate dropped from 9.6% to 6.6% when using the three-network ensemble, significantly improving the efficiency of the automated system.

Limitations and Future Work

  • Computational Cost: The primary drawback is the "penalty" of evaluation time. Running three networks instead of one triples the computation required for every image. The authors suggest a "sieving" procedure (only running the later networks if the first is uncertain) could reduce this overhead to a factor of 1.75.
  • Deformation Limits: The success of the method depends on the quality of the deformation model. If the transformations are too extreme, the images become distorted and non-representative of real data; if too subtle, they don't provide enough "new" information for the boosting algorithm to learn from.
  • Recursive Iteration: While the process could theoretically be iterated to 9 or 27 networks, the authors found diminishing returns after the first three.

Summary updated

Abstract

A boosting algorithm converts a learning machine with error rate less than 50% to one with an arbitrarily low error rate. However, the algorithm discussed here depends on having a large supply of independent training samples. We show how to circumvent this problem and generate an ensemble of learning machines whose performance in optical character recognition problems is dramatically improved over that of a single network. We report the effect of boosting on four databases (all handwritten) consisting of 12,000 digits from segmented ZIP codes from the United State Postal Service (USPS) and the following from the National Institute of Standards and Testing (NIST): 220,000 digits, 45,000 upper case alphas, and 45,000 lower case alphas. We use two performance measures: the raw error rate (no rejects) and the reject rate required to achieve a 1% error rate on the patterns not rejected. Boosting improved performance in some cases by a factor of three.
BibTeX
@inproceedings{drucker1992improving,
  author = {Harris Drucker and Robert E. Schapire and Patrice Y. Simard},
  title = {{Improving Performance in Neural Networks Using a Boosting Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1992},
  url = {https://openreview.net/forum?id=rkbsSdbuWH},
}
Figure