Introduction
This paper investigates the "small disjuncts problem"—the tendency for machine learning rules that cover very few examples to be highly error-prone. The author demonstrates that this phenomenon isn't an inherent flaw of learning algorithms. Instead, it is the result of how rare cases in a dataset interact with noise and training set size to "overwhelm" specific subconcepts.
In inductive learning (like building decision trees), a "disjunct" is a rule or a leaf node that defines a portion of a concept. "Small disjuncts" are those that cover only a few training examples. Historically, researchers noticed that these small disjuncts have much higher error rates than "large" ones. However, they couldn't simply be ignored because, collectively, they often account for a significant portion of the total data (e.g., 20%).
The author seeks to answer why these small disjuncts are so error-prone. Is it just a bias of the learning algorithm, or is it something fundamental about the data? Specifically, the paper explores the relationship between rare cases (infrequent occurrences in the underlying population) and the small disjuncts created during the learning process.
Methodology
To isolate the causes of error, the author used artificial domains where every variable could be strictly controlled. The study relied entirely on synthetic 5-bit binary domains (32 distinct possible cases) to maintain experimental control, typically using 1,000 training examples and 2,000 test examples.
- Concepts: Two functions were used to determine the class: Parity (is the sum of bits even or odd?) and Voting (majority rule).
- Distributions: The author compared "Uniform" distributions (all cases equally likely) against "Skewed" distributions (where cases were divided into 5 "bands," with Band 1 containing common cases duplicated 16x, and Band 5 containing rare cases with no duplication).
- Learning Algorithm: A modified version of C4.5 (a classic decision tree inducer) was used. Crucially, the author disabled "pruning" to ensure small disjuncts were preserved and could be studied.
- Noise Models: The study introduced varying levels of attribute noise (flipping bits), class noise (flipping the label), and missing attributes to see how they disproportionately affected rare cases.
- Metrics: The author introduced the Error Factor, a ratio of the cumulative percentage of errors to the cumulative percentage of cases. An error factor > 1 indicates that a specific disjunct size is more error-prone than average.
Key Insights and Results
Rare Cases Lead to Small Disjuncts
Rare cases in the population are the primary reason small disjuncts form. Because they are rare, the learner has fewer examples to generalize from, making the resulting rules fragile.
In the Parity domain with 5% attribute noise, the rarest cases (Band 5) had an error rate of 36.01%, compared to only 15.53% for the most common cases (Band 1).
Crucially, the "Error Factor" for small disjuncts (low coverage) in skewed domains was significantly higher than 1, while in uniform domains, it stayed near 1. This proves that small disjuncts aren't inherently bad—they only become "error-prone" when they are forced to represent rare cases in a noisy environment.
The "Overwhelming" Effect of Noise
Attribute noise is identified as the biggest villain. If a common case has a 2% chance of being corrupted, those corrupted examples might look exactly like a rare case. Because the common case is so much more frequent, these "noisy" examples can outnumber the actual rare examples, causing the learner to "learn the noise" instead of the rare subconcept.
Interestingly, class noise (errors in labeling) doesn't hurt rare cases as much as attribute noise does, until the noise level becomes extremely high (>30%). Furthermore, removing just one attribute caused the error rate for rare cases in the Parity domain to skyrocket to 85%, while common cases remained at 0% error.
The Training Set Size Paradox
In small training sets, skewed distributions actually help because the learner quickly masters the common cases. However, as the training set grows, the rare cases become the primary bottleneck for accuracy, whereas a uniform distribution eventually allows the learner to master everything equally.
Limitations and Future Work
- Artificial vs. Real World: The study uses very small, 5-bit artificial domains. While this allows for perfect control, real-world datasets have much higher dimensionality and complex feature interactions that might behave differently.
- Noise Model Specificity: The results are highly dependent on the specific noise models used (random vs. systematic). Different noise models might yield different conclusions.
- Pruning Strategies: Since the author disabled pruning to study the disjuncts, the paper doesn't deeply explore how modern pruning techniques might mitigate these issues without losing the valuable information contained in rare cases.
The author suggests a future direction where "small disjuncts" should perhaps be redefined not just by their size, but by their Error Factor, to better identify which rules are truly unreliable.
Summary updated