Gary M. Weiss's Research on Small Disjuncts

My earliest research in machine learning involved trying to gain a better understanding of the role that rarity plays in classification tasks and how it impacts classification algorithms. This work was motivated by research by Holte, Acker, and Porter from 1989 that showed that rare/exceptional cases manifest themselves in classifiers that form disjunctive concepts as "small" disjuncts (i.e., disjuncts that cover relatively few training examples) and that these small disjuncts are very error prone. I investigated this phenomenon in a series of papers in order to better understand how rare cases impact classifier learning and to quantify the effect that these rare cases have on learning. The first two papers, both published in ICML, investigated the reasons why small disjuncts are more error prone than large disjuncts as how rare cases impacts learning overall. The first paper used artificial data sets so that I could precisely control the prevalence of rare cases within the domain (Weiss, 1995) whereas the second paper used two "real" data sets (Weiss & Hirsh, 1998). Together these papers demonstrated that when there are rare/exceptional cases within a domain, then factors such as attribute noise, missing attributes, class noise and training set size can result in small disjuncts being more error prone than large disjuncts and in rare cases being more error prone than common cases. Thus, these papers established the mechanisms by which rare cases lead to error prone small disjuncts. These papers also both came to the conclusion that when there is attribute noise then it is the rare cases within the domain that are primarily responsible for degrading classification performance.

These two papers also began to quantify the relationship between rare cases and small disjuncts and classification performance. But because these papers relied only on synthetic data sets or a few realistic data sets, reliable empirical conclusions were not possible. Other papers on the area had similar limitations. What was needed was a comprehensive empirical analysis of a large number of data sets and I provided this as a AAAI paper (Weiss & Hirsh, 2000) that was subsequently followed up by a more detailed journal version (Weiss, 2010). This work analyzed 30 datasets and used a measure that I created called error concentration to summarize, in a single number, the degree to which errors are concentrated in the smaller disjuncts. This work confirmed that fact that errors are usually highly concentrated toward the smaller disjuncts and quantified the impact that small disjuncts and rare cases have on learning. This paper also investigated the relationship between small disjuncts and pruning, training set size, and noise. One notable conclusion was that pruning is not particularly effective when the errors are not originally concentrated toward the small disjuncts (which happens for some data sets) and that pruning tends to distribute the errors more uniformly throughout the disjuncts. While pruning does generally reduce overall error rate, this spreading out of the errors can actually lead to poorer results when one can act selectively (i.e., only act on the most confident classifications).

These papers have materially contributed to the literature on small disjuncts and, more generally, on rarity in learning and have been relatively well cited. These papers led to a better understanding of rarity and thus laid the groundwork for much of the material in my general paper on the problems associated with learning from rare data and potential cures (Weiss, 2004). This work on rare/exceptional cases also established a connection to rare classes. Specifically, my research showed that part of the reason why small disjuncts have a higher error rate than the large disjuncts is that minority-class predictions are more likely to be erroneous than majority-class predictions and small disjuncts are disproportionately associated with the minority class. This was the first empirical evidence that class imbalance is partly responsible for the problem with small disjuncts and also suggests that if one artificially balances the class distribution of the training data then the small disjuncts will become less of a problem. This observation links this work on small disjuncts with my work on class distribution (Weiss & Provost, 2003), described in the next section, and also explains why classifiers built using a balanced class distributions tend to be quite robust.

 
   
top | Home | CIS Dept. | Fordham