Induction of Selective Bayesian Classifiers

Pat Langley, Stephanie SageUAI 1994

TL;DR

This paper introduces the "selective Bayesian classifier," a modification of the standard naive Bayesian classifier that addresses its sensitivity to correlated features. By greedily selecting a subset of attributes, this new approach improves classification accuracy in domains with redundant features without sacrificing performance in others, offering a more robust probabilistic induction method.

What Problem Does This Paper Address?

The paper tackles a known limitation of the naive Bayesian classifier: its assumption of feature independence within each class. While this assumption simplifies learning and computation, it can lead to degraded accuracy when features are actually correlated. This is because correlated features can disproportionately influence the classification decision, leading to biased predictions. The authors aim to develop a method that retains the benefits of Bayesian classification while mitigating the negative effects of feature dependencies, particularly in real-world domains where such correlations are common.

Methods

The core innovation is the "selective Bayesian classifier." This method augments the standard naive Bayesian classifier with a feature selection mechanism. Specifically, it employs a greedy forward selection strategy. The algorithm starts with an empty set of attributes and iteratively adds the attribute that most improves (or at least maintains) the classifier's accuracy on the training data. This process continues until adding any further attribute results in a decrease in accuracy. The final classifier then uses only this selected subset of attributes for prediction, applying the independence assumption only to this reduced set. This approach is designed to be efficient, with a worst-case time complexity of O(n²), where n is the number of attributes.

Datasets

The authors evaluated their selective Bayesian classifier on six natural domains from the UCI repository of machine learning databases. These domains were chosen because previous studies indicated that the naive Bayesian classifier performs well on some and poorly on others, providing a good testbed for their hypotheses. The specific domains mentioned are:

  • Congressional voting records
  • Mushroom domain
  • Chess endgames
  • Breast cancer domain
  • Soybean disease domain
  • DNA promoter domain

Key Insights and Ideas

  • Correlated features are a real problem: Despite the naive Bayesian classifier's surprising robustness in many domains, the paper strongly suggests that correlated features do negatively impact its accuracy, especially in certain types of domains.
  • Feature selection is a viable solution: The greedy forward selection approach effectively identifies and utilizes a subset of attributes that avoids the pitfalls of correlated features, leading to improved performance.
  • Selective Bayes offers a "best of both worlds" scenario: The selective Bayesian classifier appears to achieve improved asymptotic accuracy in domains where the naive Bayes struggles (likely due to correlations) while performing comparably to the naive Bayes in domains where it already excels. This suggests it's a more generally applicable probabilistic learner.
  • The independence assumption is a double-edged sword: While simplifying learning, it's the source of the problem. By selectively choosing attributes, the paper shows how to retain the convenience of the assumption without suffering its full detrimental effects.

Key Results

The experimental results generally supported the authors' hypotheses:

  • In domains where the naive Bayesian classifier had low asymptotic accuracy (e.g., Congressional voting, mushroom, chess endgames), the selective Bayesian classifier showed marked improvement. For instance, in the Congressional voting domain, its accuracy approached that of the C4.5 decision-tree algorithm.
  • In domains where the naive Bayesian classifier already outperformed decision-tree methods (e.g., breast cancer, soybean, DNA promoter), the selective Bayesian classifier performed comparably to the naive Bayes, indicating it did not harm performance.
  • The paper presents learning curves showing the selective Bayesian classifier's accuracy increasing with more training data, often surpassing the naive Bayesian classifier's performance, especially in the challenging domains.

Limitations and Future Work

  • Preliminary nature of results: The authors acknowledge that their experimental results are preliminary and suggest the need for additional comparative studies.
  • Comparison with other sophisticated methods: They propose comparing their technique to other methods for inducing Bayesian networks and probabilistic concept hierarchies to determine if these more complex approaches offer benefits beyond simple attribute selection.
  • Design choices: Further studies are recommended to explore the impact of different design decisions made in implementing the selective Bayesian classifier, such as the stopping criteria for the search.
  • Alternative selection techniques: The paper suggests investigating other selection techniques, like those used by Kubat et al., and comparing them to their greedy approach.
  • Theoretical analysis: The authors believe their method's simplicity lends itself to average-case analyses, which could allow for theoretical comparisons with experimental results, particularly in synthetic domains.
  • Irrelevant features: While the primary motivation was correlated features, the authors also suggest the approach should prove useful in domains with irrelevant features.

Summary updated

BibTeX
@inproceedings{langley1994induction,
  author = {Pat Langley and Stephanie Sage},
  title = {{Induction of Selective Bayesian Classifiers}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure