On the Optimality of the Simple Bayesian Classifier under Zero-One Loss

article1997Machine Learning3,437 citations

Proves that the naive Bayesian classifier remains optimal under zero-one loss even with severe attribute dependencies, showing that minimizing classification error requires only correct relative class rankings rather than accurate probability estimates.

Listen

The simple Bayesian classifier, which assigns an example to the class maximizing the product of the class prior and the conditional probabilities of each attribute value given the class, has long been viewed as theoretically limited because it assumes conditional independence among attributes. In practice, however, it has repeatedly matched or exceeded the accuracy of more flexible learners such as decision-tree, rule-induction, and instance-based methods across dozens of real data sets, many of which exhibit clear attribute dependence.

This paper set out to determine whether the classifier can still minimize misclassification (zero-one loss) when the independence assumption is violated, and, if so, to characterize the conditions under which that occurs. The authors combined a large-scale empirical comparison on 28 UCI data sets with a formal analysis of local and global optimality under zero-one loss, followed by targeted experiments in artificial domains and controlled tests of attribute-joining extensions.

The analysis establishes that the classifier is locally optimal for any example whenever the sign of the difference between the two class scores matches the sign of the difference between the true class probabilities; this region occupies half the volume of the valid probability space, far larger than the infinitesimal slice corresponding to exact independence. The same condition extends directly to global optimality on a data set. As concrete corollaries, the classifier is exactly optimal for conjunctions and disjunctions even though those concepts violate independence, yet it cannot represent certain linearly separable concepts such as some m-of-n functions. On the 28 data sets the classifier produced the highest average accuracy and the best average rank among the four learners tested; attribute-dependence measures correlated only weakly with accuracy differences, confirming that dependence alone does not predict when the classifier will lose. In artificial Boolean domains the classifier also outperformed C4.5 at training-set sizes up to roughly one thousand examples, with the crossover point shifting favorably as the number of attributes grew.

These results imply that the Bayesian classifier’s practical range is substantially broader than its theoretical reputation suggested, that variance reduction can outweigh representational bias on moderate-sized data, and that extensions focused solely on removing the strongest dependence violations are not guaranteed to improve accuracy. Practitioners can therefore consider the classifier as a strong default for classification tasks with hundreds to a few thousand examples, especially when many attributes are present. When further gains are required, accuracy-driven attribute joining or discretization adjustments are more reliable than dependence tests.

The principal limitations are that the derived optimality conditions are not always easy to verify on new domains and that the analysis applies strictly to zero-one loss rather than to full cost matrices or probability estimation. The empirical findings rest on a fixed collection of data sets and on controlled artificial domains whose complexity may not span all real-world distributions; nevertheless, the combination of analytic volume arguments, consistent empirical rankings, and replication across multiple studies supplies high that the central claims will hold under similar conditions.

University of California, Irvine bayesian classifier probability sufficient conditions Simple Bayesian classifier Zero-one loss Attribute dependence

Domingos et al (1997).pdf

Paper: Bayesian Network Classifiers, NIR FRIEDMAN et al. (1997). Reading this foundational work on Bayesian network classifiers first is essential because it investigates whether relaxing the naive independence assumption improves accuracy, directly anticipating the source paper's inquiry into why the simple Bayesian classifier succeeds despite violated assumptions.

Paper: The foundations of cost-sensitive learning, Charles Elkan (2001). This paper extends the source study's focus on probabilistic classification by analyzing how differing misclassification costs interact with Bayes decision thresholds and probability estimates.
Paper: A comparison of event models for naive bayes text classification, Andrew McCallum et al. (1998). This paper builds on the source work by investigating how different event models affect the performance of naive Bayes text classification under the same independence assumptions.

Cover for On the Optimality of the Simple Bayesian Classifier under Zero-One Loss

Abstract

The simple Bayesian classifier is known to be optimal when attributes are independent given the class, but the question of whether other sufficient conditions for its optimality exist has so far not been explored. Empirical results showing that it performs surprisingly well in many domains containing clear attribute dependences suggest that the answer to this question may be positive. This article shows that, although the Bayesian classifier’s probability estimates are only optimal under quadratic loss if the independence assumption holds, the classifier itself can be optimal under zero-one loss (misclassification rate) even when this assumption is violated by a wide margin. The region of quadratic-loss optimality of the Bayesian classifier is in fact a second-order infinitesimal fraction of the region of zero-one optimality. This implies that the Bayesian classifier has a much greater range of applicability than previously thought. For example, in this article it is shown to be optimal for learning conjunctions and disjunctions, even though they violate the independence assumption. Further, studies in artificial domains show that it will often outperform more powerful classifiers for common training set sizes and numbers of attributes, even if its bias is a priori much less appropriate to the domain. This article’s results also imply that detecting attribute dependence is not necessarily the best way to extend the Bayesian classifier, and this is also verified empirically.

1. Introduction
2. The simple Bayesian classifier in machine learning
3. Empirical evidence
4. An example of optimality without independence
5. Local optimality
6. Global optimality
6.1. Necessary conditions
6.2. Sufficient conditions
7. When will the Bayesian classifier outperform other learners?
9. Conclusions and future work
Acknowledgments
Notes
References

Knowls

Knowl 1 — Necessary and Sufficient Condition for Local Optimality Under Zero-One Loss
theoretical result
For a binary classification task with classes $\{+, -\}$ , let an instance $E$ have true conditional class probability $p = P(+|E)$ , and let the simple (naive) Bayesian classifier discriminant functions be given by $r = P(+) \prod_{j=1}^a P(A_j = v_{jk}|+)$ and $s = P(-) \prod_{j=1}^a P(A_j = v_{jk}|-)$ , where $A_j$ denotes the $j$ th attribute and $v_{jk}$ denotes the value of $A_j$ in $E$ .

Under zero-one loss (misclassification rate), the simple Bayesian classifier assigns $E$ to class $+$ if $r \ge s$ and to class $-$ if $r < s$ . The classifier is locally optimal on $E$ (i.e., its zero-one loss equals the Bayes error rate $\min(p, 1 - p)$ ) if and only if:

$\left(p \ge \frac{1}{2} \land r \ge s\right) \lor \left(p \le \frac{1}{2} \land r \le s\right)$

This condition holds for probability estimates derived from finite samples as well as true distributions. It demonstrates that naive Bayes can achieve zero-one loss optimality even when $r$ and $s$ diverge substantially from the true posterior class probabilities, provided both agree on which class has the majority probability mass.
Knowl 2 — Optimality Region Volume Under Zero-One Loss Versus Squared Error Loss
theoretical result
In the parameter space $(p, r, s) \in [0, 1]^3$ , where $p = P(+|E)$ is the true class posterior probability and $r, s$ are the naive Bayes discriminant products for classes $+$ and $-$ , the region where the classifier achieves zero-one loss optimality occupies exactly half ( $\frac{1}{2}$ ) of the total volume of valid probability combinations.

In contrast, under squared error loss $\text{SE}(E) = [P(C|E) - P_X(C|E)]^2$ , the probability estimates produced by naive Bayes are optimal if and only if the class-conditional independence assumption holds exactly, which corresponds to the one-dimensional line formed by the intersection of $r = p$ and $s = 1 - p$ . Consequently, the region of optimality under squared error loss is a second-order infinitesimal fraction of the region of optimality under zero-one loss.
Knowl 3 — Global Optimality of Naive Bayes on Conjunctions and Disjunctions of Literals
theoretical result
Under a uniform distribution over examples (or any distribution where the prior $P(C) \ge 2^{-n}$ ), the simple Bayesian classifier is globally optimal under zero-one loss for learning conjunctions and disjunctions of $n$ literals, in the presence of any number of irrelevant attributes.

For an $n$ -literal conjunction $C = L_1 \land \dots \land L_n$ , the class-conditional independence assumption holds for class $C=1$ ( $P(L_j|C=1) = 1$ ) but is violated for class $C=0$ , where $P(L_j|C=0) = \frac{2^{n-1}-1}{2^n-1} < \frac{1}{2}$ . For any instance $E$ with $m$ true literals:
- When $m = n$ , $P(C=1|E) > P(C=0|E)$ , and class $1$ wins.
- When $m < n$ , $P(C=1|E) = 0$ while $P(C=0|E) > 0$ , and class $0$ wins.
By symmetry, naive Bayes is also globally optimal for disjunctions of literals, negated conjunctions, and negated disjunctions.
Knowl 4 — Linear Separability and VC Dimension of Naive Bayes in Nominal Domains
theoretical result
When all $a$ attributes are nominal (discrete and unordered) with attribute $A_j$ taking values $v_{jk}$ , the simple Bayesian classifier with discriminant functions $f_i(E) = P(C_i) \prod_{j=1}^a P(A_j = v_{jk}|C_i)$ is equivalent under a logarithmic transform to a linear discriminant machine:

$\log f_i(E) = \log P(C_i) + \sum_{j,k} \log P(A_j = v_{jk}|C_i) \, b_{jk}$

where $b_{jk} \in \{0, 1\}$ is a Boolean indicator feature indicating whether attribute $A_j$ equals value $v_{jk}$ .

Consequently:
1. The simple Bayesian classifier cannot be globally optimal for concept classes that are not linearly separable in the space of Boolean indicator features $b_{jk}$ .
2. The Vapnik-Chervonenkis (VC) dimension of the simple Bayesian classifier over $a$ nominal attributes is $O(a)$ , implying that under PAC learning guarantees, the sample complexity required to learn within error $\epsilon$ with confidence $1 - \delta$ is linear in the number of attributes $a$ .
Knowl 5 — Suboptimality of Simple Bayesian Classifier for m-of-n Concepts
theoretical result
An $m$ -of- $n$ concept is a Boolean concept over $n$ attributes that is positive if and only if at least $m$ attributes are true. Although $m$ -of- $n$ concepts are linearly separable, the simple Bayesian classifier is not globally optimal for this concept class in general.

When trained on all $2^n$ examples with equal instance probabilities, the classification of an instance with $j$ true attributes depends on the sign of:

$\text{Diff}(m, n, j) = P(C) P(A|C)^j [1 - P(A|C)]^{n-j} - P(\bar{C}) P(A|\bar{C})^j [1 - P(A|\bar{C})]^{n-j}$

where $P(C) = \sum_{i=m}^n \binom{n}{i} 2^{-n}$ , $P(\bar{C}) = \sum_{i=0}^{m-1} \binom{n}{i} 2^{-n}$ , $P(A|C) = \frac{\sum_{i=m-1}^{n-1}\binom{n-1}{i}}{\sum_{i=m}^n\binom{n}{i}}$ , and $P(A|\bar{C}) = \frac{\sum_{i=0}^{m-2}\binom{n-1}{i}}{\sum_{i=0}^{m-1}\binom{n}{i}}$ .

For example, in an $8$ -of- $25$ concept, $\text{Diff}(8, 25, j) > 0$ for all $j \ge 6$ , resulting in false positive errors when $j \in \{6, 7\}$ .
Knowl 6 — Concept Capacity Bound of the Simple Bayesian Classifier
theoretical result
Let $a$ be the number of attributes, $c$ the number of classes, $v$ the maximum number of values per attribute, and $d$ the number of distinct numeric values representable in machine arithmetic (e.g., $d = 2^{16}$ for 16-bit representation).

Because the state of the simple Bayesian classifier is fully specified by $c(av + 1)$ probability values, the learner can enter at most $d^{c(av+1)}$ distinct states. Consequently, the simple Bayesian classifier cannot be globally optimal for more than $d^{c(av+1)}$ distinct concepts. This $O(a)$ parameter capacity restricts naive Bayes from distinguishing arbitrary concept classes whose size grows doubly exponential in $a$ (such as arbitrary DNF formulas).
Knowl 7 — Measure of Class-Conditional Pairwise Attribute Dependence
equation
The degree of pairwise dependence between attributes $A_m$ and $A_n$ given a discrete class variable $C$ , denoted $D(A_m, A_n|C)$ , is defined as:

$D(A_m, A_n|C) = H(A_m|C) + H(A_n|C) - H(A_m A_n|C)$

where $A_m A_n$ is the Cartesian product attribute formed by all pairs of values of $A_m$ and $A_n$ , and the conditional entropy $H(A_j|C)$ for attribute $A_j$ with values $v_{jk}$ across classes $C_i$ is computed as:

$H(A_j|C) = \sum_i P(C_i) \sum_k -P(C_i \land A_j = v_{jk}) \log_2 P(C_i \land A_j = v_{jk})$

$D(A_m, A_n|C) = 0$ when $A_m$ and $A_n$ are conditionally independent given $C$ , and achieves its maximum when $C$ and one attribute fully determine the other.
Knowl 8 — Lack of Empirical Correlation Between Attribute Dependence and Naive Bayes Performance
empirical result
In an empirical comparison across 28 UCI benchmark datasets comparing discretized naive Bayes against C4.5 (decision trees), PEBLS (instance-based), and CN2 (rule induction), naive Bayes achieved the highest mean accuracy (79.1% vs. 77.2% for C4.5, 77.6% for PEBLS, and 76.2% for CN2) and the best average rank (2.43).

Measuring pairwise class-conditional attribute dependence $D(A_m, A_n|C)$ demonstrated that naive Bayes often ranked first in domains with high attribute dependence (e.g., Labor and Sonar, where 100% of attributes had $D \ge 0.2$ ). Furthermore, the linear correlation between mean attribute dependence and the performance difference between naive Bayes and other algorithms was negligible ( $R^2 = 0.04$ for C4.5, $R^2 = 0.0004$ for PEBLS, and $R^2 = 0.002$ for CN2), confirming that attribute dependence is not a valid predictor of naive Bayes accuracy degradation.
Knowl 9 — Bias-Variance Trade-Off and Small-Sample Superiority in DNF Concepts
empirical result
Under zero-one loss, classification accuracy is largely insensitive to probability estimation bias (as long as class rankings remain correct) but remains sensitive to variance. In experiments on synthetic random DNF target concepts across varying numbers of attributes $a \in \{16, 32, 64\}$ and sample sizes $n \in [10, 10000]$ :
1. The simple Bayesian classifier outperforms C4.5RULES at small to medium sample sizes ( $n \le 1000$ ), despite C4.5RULES possessing an appropriate inductive bias with zero asymptotic bias on DNF concepts.
2. C4.5 suffers from extreme estimation variance on small samples (approaching 50% error), dominating total loss.
3. As the number of attributes $a$ grows, the sample size crossover threshold where C4.5 overtakes naive Bayes increases, broadening the sample size regime where naive Bayes is superior due to its low VC dimension ( $O(a)$ ).
Knowl 10 — Superiority of Accuracy Estimation Over Dependence Measures for Feature Joining
empirical result
When extending the simple Bayesian classifier by semi-naive attribute joining (replacing two attributes with their Cartesian product), selecting attribute pairs based on leave-one-out cross-validation accuracy on the training set consistently outperforms selecting pairs with the highest class-conditional dependence $D(A_m, A_n|C)$ .

Joining the pair with the highest dependence often harms accuracy on non-linearly separable sub-structures (e.g., in a 6-variable synthetic concept with strong $A_1, A_2$ dependence, entropy-based joining picked $A_1, A_2$ reducing accuracy to 90.1%, while accuracy-based joining picked the least dependent pair $A_5, A_6$ , raising accuracy to 96.9% over the 92.8% baseline). Cross-validation accuracy is a substantially better predictor of test set improvement from attribute joining ( $R^2 = 0.497$ vs. $R^2 = 0.006$ on Chess endgames; $R^2 = 0.907$ vs. $R^2 = 0.019$ on Mushroom).

Coverage note — No substantial contributed theoretical or empirical material was omitted; all primary theorems (local and global optimality, concept bounds, conjunction/disjunction optimality, $m$-of-$n$ suboptimality), representations, and empirical analyses are included.

References

1.Ben-Bassat, M., Klove, K. L., & Weil, M. H. (1980). Sensitivity analysis in Bayesian classification models: Multiplicative deviations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2, 261–266.
2.Breiman, L. (1996). Bias, variance and arcing classifiers (Technical Report 460). Statistics Department, University of California at Berkeley, Berkeley, CA. ftp://ftp.stat.berkeley.edu/users/breiman/arcall.ps.Z.
3.Cestnik, B. (1990). Estimating probabilities: A crucial task in machine learning. Proceedings of the Ninth European Conference on Artificial Intelligence. Stockholm, Sweden: Pitman.
4.Clark, P., & Boswell, R. (1991). Rule induction with CN2: Some recent improvements. Proceedings of the Sixth European Working Session on Learning (pp. 151–163). Porto, Portugal: Springer-Verlag.
5.Clark, P., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning, 3, 261–283.
6.Cost, S., & Salzberg, S. (1993). A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10, 57–78.
7.DeGroot, M. H. (1986). Probability and statistics (2nd ed.). Reading, MA: Addison-Wesley.
8.Dietterich, T. (1996). Statistical tests for comparing supervised classification learning algorithms (technical report). Department of Computer Science, Oregon State University, Corvallis, OR. ftp://ftp.cs.orst.edu/pub/tgd/papers/stats.ps.gz.
9.Dougherty, J., Kohavi, R., & Sahami, M. (1995). Supervised and unsupervised discretization of continuous features. Proceedings of the Twelfth International Conference on Machine Learning (pp. 194–202). Tahoe City, CA: Morgan Kaufmann.
10.Duda, R. O., & Hart, P. E. (1973). Pattern classification and scene analysis. New York, NY: Wiley.
11.Flury, B., Schmid, M. J., & Narayanan, A. (1994). Error rates in quadratic discrimination with constraints on the covariance matrices. Journal of Classification, 11, 101–120.
12.Friedman, J. H. (1996). On bias, variance, 0/1 - loss, and the curse-of-dimensionality (technical report). Department of Statistics, Stanford University, Stanford, CA. ftp://playfair.stanford.edu/pub/friedman/kdd.ps.Z.
13.Friedman, N., Geiger, D., & Goldszmidt, M. (1997). Bayesian network classifiers. Machine Learning (this volume).
14.Haussler, D. (1988). Quantifying inductive bias: AI learning algorithms and Valiant’s learning framework. Artificial Intelligence, 36, 177–221.
15.John, G., & Langley, P. (1995). Estimating continuous distributions in Bayesian classifiers. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (pp. 338–345). Montr´eal, Canada: Morgan Kaufmann.
16.Kohavi, R. (1995). Wrappers for performance enhancement and oblivious decision graphs. PhD thesis, Department of Computer Science, Stanford University, Stanford, CA.
17.Kohavi, R. (1996). Scaling up the accuracy of naive-Bayes classifiers: A decision-tree hybrid. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (pp. 202–207). Portland, OR: AAAI Press.
18.Kohavi, R., Becker, B., & Sommerfield, D. (1997). Improving simple Bayes (technical report). Data Mining and Visualization Group, Silicon Graphics Inc., Mountain View, CA. ftp://starry.stanford.edu/pub/ronnyk/impSBC.ps.Z.
19.Kohavi, R., & Wolpert, D. H. (1996). Bias plus variance decomposition for zero-one loss functions. Proceedings of the Thirteenth International Conference on Machine Learning (pp. 275–283). Bari, Italy: Morgan Kaufmann.
20.Kong, E. B., & Dietterich, T. G. (1995). Error-correcting output coding corrects bias and variance. Proceedings of the Twelfth International Conference on Machine Learning (pp. 313–321). Tahoe City, CA: Morgan Kaufmann.
21.Kononenko, I. (1990). Comparison of inductive and naive Bayesian learning approaches to automatic knowledge acquisition. In B. Wielinga (Ed.), Current Trends in Knowledge Acquisition. Amsterdam, The Netherlands: IOS Press.
22.Kononenko, I. (1991). Semi-naive Bayesian classifier. Proceedings of the Sixth European Working Session on Learning (pp. 206–219). Porto, Portugal: Springer-Verlag.
23.Kubat, M., Flotzinger, D., & Pfurtscheller, G. (1993). Discovering patterns in EEG-Signals: Comparative study of a few methods. Proceedings of the Eighth European Conference on Machine Learning (pp. 366–371). Vienna, Austria: Springer-Verlag.
24.Langley, P. (1993). Induction of recursive Bayesian classifiers. Proceedings of the Eighth European Conference on Machine Learning (pp. 153–164). Vienna, Austria: Springer-Verlag.
25.Langley, P., Iba, W., & Thompson, K. (1992). An analysis of Bayesian classifiers. Proceedings of the Tenth National Conference on Artificial Intelligence (pp. 223–228). San Jose, CA: AAAI Press.
26.Langley, P., & Sage, S. (1994). Induction of selective Bayesian classifiers. In Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (pp. 399–406). Seattle, WA: Morgan Kaufmann.
27.Merz, C. J., Murphy, P. M., & Aha, D. W. (1997). UCI repository of machine learning databases. Department of Information and Computer Science, University of California, Irvine, CA. http://www.ics.uci.edu/ mlearn/MLRepository.html.
28.Niblett, T. (1987). Constructing decision trees in noisy domains. Proceedings of the Second European Working Session on Learning (pp. 67–78). Bled, Yugoslavia: Sigma.
29.Pazzani, M. J. (1996). Searching for dependencies in Bayesian classifiers. In D. Fisher & H.-J. Lenz (Eds.), Learning from data: Artificial intelligence and statistics V (pp. 239–248). New York, NY: Springer-Verlag.
30.Pazzani, M., Muramatsu, J., & Billsus, D. (1996). Syskill & Webert: Identifying interesting web sites. Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 54–61). Portland, OR: AAAI Press.
31.Pazzani, M., & Sarrett, W. (1990). A framework for average case analysis of conjunctive learning algorithms. Machine Learning, 9, 349–372.
32.Quinlan, J. R. (1993). C4.5: Programs for machine learning. San Mateo, CA: Morgan Kaufmann.
33.Russek, E., Kronmal, R. A., & Fisher, L. D. (1983). The effect of assuming independence in applying Bayes’ theorem to risk estimation and classification in diagnosis. Computers and Biomedical Research, 16, 537–552.
34.Sahami, M. (1996). Learning limited dependence Bayesian classifiers. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (pp. 335–338). Portland, OR: AAAI Press.
35.Singh, M., & Provan, G. M. (1995). A comparison of induction algorithms for selective and non-selective Bayesian classifiers. Proceedings of the Twelfth International Conference on Machine Learning (pp. 497–505). Tahoe City, CA: Morgan Kaufmann.
36.Singh, M., & Provan, G. M. (1996). Efficient learning of selective Bayesian network classifiers. Proceedings of the Thirteenth International Conference on Machine Learning (pp. 453–461). Bari, Italy: Morgan Kaufmann.
37.Tibshirani, R. (1996). Bias, variance and prediction error for classification rules (technical report). Department of Preventive Medicine and Biostatistics, University of Toronto, Toronto, Ontario. http://utstat.toronto.edu/reports/tibs/biasvar.ps.
38.Wan, S. J., & Wong, S. K. M. (1989). A measure for concept dissimilarity and its applications in machine learning. Proceedings of the International Conference on Computing and Information (pp. 267–273). Toronto, Ontario: North-Holland.

Citation

MLA

Domingos, P., and M. Pazzani. “On the Optimality of the Simple Bayesian Classifier Under Zero-One Loss”. Machine Learning, vol. 29, nos. 2-3, 1997, pp. 103–30, https://doi.org/10.1023/A:1007413511361.

APA

Domingos, P., & Pazzani, M. (1997). On the Optimality of the Simple Bayesian Classifier under Zero-One Loss. Machine Learning, 29(2-3), 103–130. https://doi.org/10.1023/A:1007413511361

Chicago

Domingos, P., and M. Pazzani. 1997. “On the Optimality of the Simple Bayesian Classifier Under Zero-One Loss”. Machine Learning 29 (2-3): 103–30. https://doi.org/10.1023/A:1007413511361.

Harvard

Domingos, P. and Pazzani, M. (1997) “On the Optimality of the Simple Bayesian Classifier under Zero-One Loss”, Machine Learning, 29(2-3), pp. 103–130. Available at: https://doi.org/10.1023/A:1007413511361.

Vancouver

1. Domingos P, Pazzani M (1997) On the Optimality of the Simple Bayesian Classifier under Zero-One Loss. Machine Learning 29:103–130

BibTeX

@article{Domingos_1997, title={On the Optimality of the Simple Bayesian Classifier under Zero-One Loss}, volume={29}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1007413511361}, DOI={10.1023/a:1007413511361}, number={2-3}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Domingos, Pedro and Pazzani, Michael}, year={1997}, month=Nov, pages={103–130} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

On the Optimality of the Simple Bayesian Classifier under Zero-One Loss

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Necessary and Sufficient Condition for Local Optimality Under Zero-One Loss

Knowl 2 — Optimality Region Volume Under Zero-One Loss Versus Squared Error Loss

Knowl 3 — Global Optimality of Naive Bayes on Conjunctions and Disjunctions of Literals

Knowl 4 — Linear Separability and VC Dimension of Naive Bayes in Nominal Domains

Knowl 5 — Suboptimality of Simple Bayesian Classifier for m-of-n Concepts

Knowl 6 — Concept Capacity Bound of the Simple Bayesian Classifier

Knowl 7 — Measure of Class-Conditional Pairwise Attribute Dependence

Knowl 8 — Lack of Empirical Correlation Between Attribute Dependence and Naive Bayes Performance

Knowl 9 — Bias-Variance Trade-Off and Small-Sample Superiority in DNF Concepts

Knowl 10 — Superiority of Accuracy Estimation Over Dependence Measures for Feature Joining

References

Citation

BibTeX

Access the Paper