Abstract
This paper provides a formal average-case analysis of the Bayesian classifier, commonly known as Naive Bayes. By developing a mathematical model to predict accuracy based on training instances, attribute relevance, and noise, the authors demonstrate the algorithm's robustness. Despite its simplistic independence assumption, the Bayesian classifier often matches or exceeds the performance of more complex decision tree methods like C4, particularly in the presence of noise and irrelevant features.
Introduction
In the early 1990s, machine learning theory was largely dominated by "worst-case" analysis, such as the PAC learning framework. While mathematically rigorous, these frameworks often failed to capture the practical performance of algorithms on real-world data. Conversely, experimental studies were frequently informal. Langley, Iba, and Thompson (1992) sought to bridge this gap by providing an average-case analysis of the Bayesian classifier.
At the time, the Bayesian classifier was often dismissed due to its core assumption: that attributes are independent given the class. This study investigates why this "naive" algorithm performs so well in practice and how factors like concept complexity, noise, and irrelevant attributes influence its learning curve.
Methodology
The authors developed a mathematical model to predict the expected accuracy of a Bayesian classifier. The model incorporates several key parameters:
- The number of training instances ($n$).
- The number of relevant ($r$) and irrelevant ($i$) Boolean attributes.
- The probability of each attribute occurring.
- The level of class noise ($z$).
To derive these predictions, the authors calculated the probability of inducing specific probabilistic summaries after seeing $n$ instances. They then summed the probability of correct classification over all possible induced descriptions. For tractability, the analysis assumed the target concept was a monotone conjunction and that attributes were Boolean and independent.
Key Insights and Algorithm Behavior
The analysis revealed several critical properties of the Bayesian classifier:
- Graceful Degradation: The algorithm handles class noise remarkably well. As shown in Figure 4(b), increasing noise slows the learning rate but does not prevent the algorithm from eventually reaching high accuracy, provided enough data is available.
- Sensitivity to Attributes: Unlike some algorithms that are only slowed by irrelevant attributes, the Bayesian classifier is sensitive to the number of both relevant and irrelevant attributes. Figure 4(a) shows how the learning curve shifts as the number of relevant attributes increases.
- Representational Power: The authors noted that the Bayesian classifier's data structure is roughly equivalent in representational power to a single-layer perceptron, describing a single decision boundary in instance space.
Experimental Results
The theoretical "learning curves" were validated against experimental results on artificial domains, showing a near-perfect match. Furthermore, the algorithm was tested against a reimplementation of the C4 decision tree algorithm on five natural domains from the UCI repository.
As summarized in the table above, the Bayesian classifier was at least as accurate as C4 in four out of five real-world domains. For instance, it achieved 100% accuracy on the Soybean dataset compared to C4's 93.8%. The only domain where C4 significantly outperformed Bayes was Chess (99.3% vs. 87.5%), likely due to strong attribute dependencies inherent in chess endgames that violate the independence assumption.
Limitations and Future Work
While providing a robust foundation, the current analysis has limitations:
- Concept Complexity: The mathematical analysis is currently restricted to monotone conjunctive concepts, whereas real-world concepts are often disjunctive or non-monotone.
- Attribute Types: The equations are limited to Boolean attributes; multi-valued or continuous data require further modeling.
- Attribute Noise: The paper focuses on class noise (label errors). Modeling attribute noise (feature corruption) is more complex as it affects multiple values simultaneously.
- Independence Assumption: Future work should explore the algorithm's behavior when the independence assumption is explicitly and severely violated.
Summary updated