On Boosting Sparse Parities

Lev ReyzinAAAI 2014 · DOI

Abstract

Boosting algorithms like AdaBoost typically rely on simple weak learners such as decision stumps. This paper explores the use of sparse parities—low-degree XOR functions—as an alternative. By leveraging the theoretical properties of Fourier analysis on Boolean functions, sparse parities offer a principled middle ground between overly simple stumps and complex decision trees. Experimental results across several UCI datasets demonstrate that sparse parities consistently outperform decision stumps and remain competitive with pruned decision trees, providing a robust and theoretically grounded choice for boosting.

Introduction

Boosting is a cornerstone of machine learning, exemplified by the AdaBoost algorithm. The core idea is to iteratively combine "weak learners"—algorithms that perform only slightly better than random guessing—into a "strong learner." Historically, research has focused on the mechanics of the boosting process, such as reweighting schemes and aggregation methods. However, the choice of the weak learner itself is often limited to standard defaults like decision stumps (single-feature tests) or pruned decision trees.

Decision stumps are often too simple to capture complex feature interactions, such as the XOR problem. Conversely, decision trees can become overly complex and prone to overfitting. This paper proposes a "principled" weak learner: sparse parities. These low-degree XOR-like functions balance simplicity, diversity, and richness, offering a more powerful alternative to stumps without the overhead of deep trees.

Methods: The Power of Sparse Parities

A "parity" function in the context of Boolean inputs is the XOR of a subset of features. A "sparse" parity of degree $d$ considers only a small number of features.

  • Degree $d=1$: Equivalent to a standard decision stump.
  • Degree $d > 1$: Captures interactions between $d$ features that single-feature tests cannot detect.

The theoretical foundation for this approach lies in the Fourier analysis of Boolean functions. Any Boolean function can be represented as a weighted sum of parity functions. By using sparse parities in boosting, we are essentially performing a greedy search for the most significant Fourier coefficients of the target data.

While finding the optimal parity function is computationally challenging (related to the "Learning Parities with Noise" problem), the author employs a brute-force search for small degrees ($d=2, 3$). For higher degrees, the paper suggests sub-quadratic algorithms from theoretical computer science.

Experimental Results

The approach was evaluated on several datasets from the UCI Machine Learning Repository, including OCR tasks (oct17, ocr49), biological data (splice, ecoli), and clinical data (census, heart, cancer). All datasets were pre-processed to ensure binary features and labels.

Performance Comparison

Experimental results demonstrate that sparse parities are highly competitive. As shown in the comparison below, 3-parities consistently outperformed decision stumps. For instance, on the ocr49 dataset, the error rate dropped from 6.08% with stumps to 2.77% with 3-parities.

Comparison of error rates for decision stumps, 3-parities, and CART-16 trees across various datasets.

Furthermore, sparse parities held their own against more complex models like CART trees pruned to 16 nodes. On the ecoli dataset, 3-parities significantly outperformed these trees, achieving a 5.87% error rate compared to 8.98% for CART-16.

Impact of Parity Degree

Increasing the degree of the parity function generally leads to better performance, as it allows the model to capture more complex interactions. The following table illustrates the progression from decision stumps (degree 1) to 2-parities and 3-parities.

Error rate comparison between decision stumps, 2-parities, and 3-parities, showing the impact of increasing parity degree.

In almost every test case, the error rate decreased as the degree increased. Notably, sparse parities were never the worst-performing classifier across all datasets, consistently providing top-tier or middle-ground performance.

Discussion and Conclusion

Sparse parities offer several advantages:

  1. Diversity: Parity functions are naturally orthogonal under uniform distributions, ensuring that each new weak hypothesis in the boosting process is distinct.
  2. Simplicity vs. Power: They have a smaller hypothesis space than full decision trees, leading to better generalization bounds while still solving problems like XOR that stumps cannot.
  3. Robustness: They provide a reliable middle ground between the simplicity of stumps and the complexity of trees.

However, limitations remain. The current framework is restricted to binary features and classification. Additionally, the computational cost of brute-forcing parities scales as $O(n^d)$, necessitating more advanced algorithms for higher degrees on high-dimensional data. Future work could explore multi-class extensions and the application of sub-quadratic search algorithms.

In summary, this research encourages a shift in focus toward the weak learner, demonstrating that sparse parities are a theoretically grounded and empirically effective tool for boosting.

Summary updated

BibTeX
@inproceedings{reyzin2014boosting,
  author = {Lev Reyzin},
  title = {{On Boosting Sparse Parities}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9020},
}
Figure