On Online Learning of Decision Lists

Ziv Nevo, Ran El-YanivJMLR 2002

TL;DR

This paper introduces "Multi-Layered Winnow," a novel online learning algorithm for decision lists that achieves an improved mistake bound of $O(rD \log n)$, outperforming previous methods. This advancement is significant for attribute-efficient learning, a crucial area for feature selection, by offering a more efficient way to learn complex decision structures.

What Problem Does This Paper Address?

The paper tackles the challenge of learning "decision lists" efficiently, particularly in an online setting where the algorithm learns from a stream of data. Decision lists are a fundamental concept class in machine learning, used for hierarchical decision-making and representing various complex functions. A key open problem in the field is whether an "attribute-efficient" learning algorithm exists for decision lists. Attribute-efficient algorithms are desirable because their performance depends logarithmically on the total number of features ($n$) and polynomially on the number of relevant features ($r$), making them ideal for datasets with many irrelevant features. While previous algorithms have made progress, none have fully achieved attribute efficiency for general decision lists. This paper focuses on a restricted but important class: decision lists with a bounded number of "alternations" or "layers" ($D$).

Methods

The core contribution is the "Multi-Layered Winnow" algorithm. It's a generalization of the well-known Winnow algorithm, which is itself an attribute-efficient algorithm for learning monotone disjunctions. Multi-Layered Winnow treats a decision list as a sequence of "layers," where each layer aims to learn a monotone disjunction. It uses multiple independent Winnow instances, one for each layer, and a novel update scheme. When a mistake occurs, it updates the weights of at most two adjacent layers: it "demotes" the layer that made the incorrect prediction and "promotes" the layer above it. This dual update strategy is designed to correct errors by adjusting the "strength" of these layers. The paper also explores a hybrid algorithm combining Multi-Layered Winnow with Rivest's algorithm, which incorporates an "elimination" step to remove irrelevant variables, aiming to further reduce mistakes.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic examples for illustration and empirical evaluation.

Key Insights and Ideas

  • Decision Lists as Layers: The paper frames decision lists as a hierarchy of "layers," each acting as an independent expert. This layered perspective is key to the algorithm's design.
  • Winnow Generalization: Multi-Layered Winnow extends the successful Winnow algorithm to handle the more complex structure of decision lists, demonstrating Winnow's versatility.
  • Dual Update Strategy: The novel approach of simultaneously demoting the incorrect layer and promoting the preceding one is a crucial insight. This strategy aims to correct errors more robustly by addressing potential issues in both the current and previous decision stages.
  • Hybrid Approach Synergy: Combining Multi-Layered Winnow with Rivest's algorithm highlights how different learning strategies can compensate for each other's weaknesses, leading to potentially better overall performance.

Key Results

  • Improved Mistake Bound: The proposed Multi-Layered Winnow algorithm achieves a mistake bound of $O(rD \log n)$, which is an improvement over the $O(r^2D \log n)$ bound of Balanced Winnow for decision lists with $D$ layers.
  • Attribute Efficiency for Restricted Class: For decision lists with a bounded number of layers ($D$), the algorithm is attribute-efficient, with mistake bounds depending logarithmically on the total number of variables ($n$).
  • Empirical Validation: Numerical examples suggest that the Multi-Layered Winnow algorithm, and especially its hybrid version with Rivest's algorithm, performs well empirically, often achieving lower mistake bounds than theoretical predictions and showing robustness across different data distributions.

Limitations and Future Work

  • Open Problem of General Decision Lists: The paper acknowledges that an attribute-efficient learning algorithm for general decision lists (without a bound on $D$) remains an open and challenging problem.
  • Exponential Dependence on D: The mistake bound of Multi-Layered Winnow has an exponential dependence on the number of layers ($D$), which can be problematic if $D$ is large.
  • Hybrid Algorithm Analysis: While the hybrid algorithm shows promising empirical results, a tighter theoretical mistake bound for it is still an open question.
  • Real-Valued Concepts: The current work focuses on boolean-valued concepts. Generalizing Multi-Layered Winnow to real-valued concepts is suggested as future work.
  • Randomization and Loss Functions: Exploring the use of randomization in the algorithm and investigating performance guarantees with different loss functions (beyond 0/1 loss) are also proposed future research directions.

Summary updated

BibTeX
@article{nevo2002online,
  author = {Ziv Nevo and Ran El-Yaniv},
  title = {{On Online Learning of Decision Lists}},
  journal = {J. Mach. Learn. Res.},
  year = {2002},
}
Figure