Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain

Avrim BlumMachine Learning 1997 · DOI

Introduction

This paper explores the practical application of multiplicative weight-update algorithms—specifically Winnow and Weighted-Majority (WM)—to real-world, non-binary tasks. Using a calendar scheduling assistant as a testbed, the study demonstrates that these "simple" theoretical tools can significantly outperform complex decision-tree systems. The findings show a 10–20% boost in prediction accuracy and superior handling of noisy, high-dimensional, and time-varying data, all while maintaining real-time processing speeds.

The Challenge of Calendar Scheduling

In the mid-90s, the "Calendar APprentice" (CAP) was the state-of-the-art for learning user scheduling preferences, such as meeting locations or durations. CAP relied on decision trees (ID3/C4.5) rebuilt in nightly batch jobs. However, this domain presents three major hurdles for traditional machine learning:

  1. Concept Drift: User behavior is dynamic; a new semester or office move shifts the "target function."
  2. String-Valued Data: Features are often names or locations with values unknown at the start of training.
  3. Irrelevant Features: While dozens of predictors exist, only a few are typically relevant for any specific decision.

The author addresses these challenges by bridging the gap between theoretical algorithms designed for noise tolerance and their practical deployment in messy, multi-class domains.

Incremental Learning Methods

The study focuses on two incremental algorithms that learn from examples one-by-one:

Weighted-Majority (WM)

WM treats pairs of features as "experts." Each expert predicts based on a local memory of the last $k$ occurrences of those features. The global algorithm takes a weighted vote; if the prediction is incorrect, the weights of the erroneous experts are halved.

Winnow (Specialists Variant)

The author introduces a variant of Winnow tailored for string-valued data using "specialists." Unlike standard experts, specialists only "wake up" and vote if specific conditions are met (e.g., "If Event-Type = Seminar").

  • The Update Rule: Weights are only increased if the global algorithm makes a mistake while the specialist was correct. This prevents over-weighting specialists that merely agree with a correct consensus.
  • Pruning: To ensure efficiency, experts with weights below a certain threshold are discarded. The author provides theoretical guarantees that this "timid" pruning does not sacrifice the best-performing experts.

Experimental Setup

The algorithms were tested on real-world data from the CAP project:

  • User 1: 1,685 examples over two years.
  • User 2: 554 examples.
  • Tasks: Predicting Location, Duration, Start Time, and Day of Week.
  • Feature Sets: A "small" set (11–16 features) and a "bigset" (34 features) were used to evaluate robustness against irrelevant data.

Key Results and Insights

The experimental results highlight the superiority of multiplicative algorithms over batch-processed decision trees.

Performance comparison for User 1 across different prediction tasks and algorithms.

As shown in the results for User 1, the Winnow variant achieved 75% accuracy in predicting meeting locations, significantly higher than CAP's 64%. The gains were even more pronounced for User 2, where Winnow outperformed CAP by nearly 20 percentage points on average.

Performance comparison for User 2, showing significant improvements over the baseline CAP system.

Robustness and Efficiency

  • Feature Bloat: While decision trees often struggle with irrelevant features, Winnow and WM remained stable or improved when moving from the small feature set to the "bigset."
  • Handling Concept Drift: By utilizing a small "local memory" for each specialist, the system adapted to behavioral changes much faster than CAP's 180-example window.
  • Real-Time Performance: Winnow processed the entire sequence for User 1 in 30 to 90 seconds on 1990s hardware, enabling true real-time interaction.

Conclusion

The study proves that algorithms designed to "learn simple things really well" are remarkably robust in complex environments. By rewarding specialists only when they correct a global mistake and handling "infinite" attribute spaces on-the-fly, these methods offer a powerful alternative to traditional batch learners. Future work may explore more complex specialist definitions and further bridge the gap between theoretical drift proofs and empirical observations.

Summary updated

BibTeX
@article{blum1997empirical,
  author = {Avrim Blum},
  title = {{Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain}},
  journal = {Machine Learning},
  year = {1997},
  doi = {10.1023/a:1007335615132},
}
Figure