A Quantitative Study of Small Disjuncts

AAAI 2000

TL;DR

This paper tackles the "problem of small disjuncts" in machine learning, where small, specific rules (disjuncts) that cover few training examples disproportionately contribute to errors. By introducing a quantitative measure called "Error Concentration" (EC) and analyzing 30 datasets, the authors reveal that this problem is widespread and influenced by factors like pruning, training set size, and noise.

What Problem Does This Paper Address?

Machine learning models that learn from examples often build complex concepts by combining simpler rules, known as disjuncts. Some of these disjuncts are "small," meaning they only correctly classify a handful of training examples. While these small disjuncts collectively cover a significant portion of the data, they tend to have much higher error rates than larger disjuncts. This phenomenon, dubbed "the problem with small disjuncts," leads to a disproportionate number of errors in the overall model. Previous research has explored this problem, but often with limited datasets, leading to weak conclusions. This paper aims to provide a more robust, quantitative understanding of the prevalence and impact of small disjuncts across a wider range of datasets and learning scenarios.

Methods

The core of this paper's contribution lies in its quantitative approach. The authors introduce Error Concentration (EC), a metric designed to measure how heavily errors are skewed towards small disjuncts. EC is derived from an "error concentration curve," which plots the percentage of total errors against the percentage of correctly classified examples covered by disjuncts of increasing size. A high EC value indicates that errors are indeed concentrated in small disjuncts.

To analyze this, the researchers modified the C4.5 decision tree algorithm to track disjunct sizes and their associated correct and incorrect classifications. They also used RIPPER, a rule learner, to ensure their findings weren't specific to C4.5. Experiments were conducted with varying pruning strategies, training set sizes, and noise levels to understand their impact on small disjuncts.

Datasets

The study utilized a total of 30 datasets:

  • 19 datasets were sourced from the UCI repository.
  • 11 datasets were provided by researchers at AT&T.

The paper does not introduce new benchmark datasets but rather applies its analysis to a broad collection of existing ones to ensure generalizability.

Key Insights and Ideas

  • The "Problem of Small Disjuncts" is Pervasive: The study confirms that small disjuncts are a significant source of errors across a wide range of datasets, not just isolated cases.
  • Error Concentration (EC) as a Diagnostic Tool: EC provides a clear, quantitative way to assess the severity of the small disjunct problem for a given concept.
  • Pruning Helps, But Doesn't Solve: While pruning reduces the overall error rate and the concentration of errors in small disjuncts, the problem persists. Even after pruning, a substantial portion of errors can still be attributed to smaller disjuncts.
  • Training Set Size Matters: Smaller training sets tend to exacerbate the small disjunct problem, leading to higher EC values. This suggests that the definition of "small" might need to be relative to the training data size.
  • Noise Amplifies the Problem: Datasets with higher EC values are more sensitive to noise, experiencing a greater increase in error rate when noise is introduced. Conversely, low-EC datasets are often more tolerant of noise.
  • Pruning's Trade-offs: While pruning improves overall accuracy, it can negatively impact precision for certain recall levels, suggesting that the choice of pruning strategy should align with the specific performance metric desired.

Key Results

  • Widespread High EC: Out of 30 datasets analyzed with C4.5 (without pruning), 10 datasets exhibited high EC values (above 55.8), indicating a severe problem with small disjuncts.
  • Pruning's Impact: Pruning reduced the average EC across the 30 datasets from 47.1% to 33.5%. It also decreased the overall error rate from 18.4% to 17.5% on average.
  • Training Set Size Effect: For 27 out of 30 datasets, EC decreased as the training set size decreased, highlighting the importance of data quantity.
  • Noise Sensitivity: Datasets with high EC values showed a greater increase in error rate when class noise was introduced.
  • RIPPER vs. C4.5: The study found a strong correlation between the EC values produced by C4.5 and RIPPER, suggesting that the problem of small disjuncts is a fundamental characteristic of the datasets rather than an artifact of a specific algorithm.

Limitations and Future Work

  • Defining "Small": The paper suggests that the current definition of small disjuncts (based solely on the number of training examples) might be insufficient. Future work could explore thresholds for "smallness" that are more dynamically determined by the relationship between disjunct size and error rate, potentially using EC.
  • Improving Learning Algorithms: The authors believe their findings can motivate the development of new learning strategies that more effectively address the problem of small disjuncts, potentially by employing variable bias systems or more nuanced pruning strategies.
  • Performance Metrics: The paper highlights that the effectiveness of pruning depends on the performance metric. Future work could explore how different learning tasks and their associated metrics (e.g., precision vs. recall) should influence the use of pruning and other strategies for handling small disjuncts.
  • Idealized Strategy: While an "idealized" strategy (where small disjunct errors match larger disjunct errors) significantly outperforms C4.5's pruning, it's not achievable. This motivates research into practical methods that can approach this ideal.

Summary updated

BibTeX
@inproceedings{2000quantitative,
  title = {{A Quantitative Study of Small Disjuncts}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}
Figure