Not So Naive Bayes: Aggregating One-Dependence Estimators
Machine LearningPublished 1 January 2005Open access
Geoffrey I. Webb, Janice R. Boughton, Zhihai Wang
Citations714
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new approach to weakening the attribute independence assumption by averaging all of a constrained class of classifiers is presented, which delivers comparable prediction accuracy to LBR and Super-Parent TAN with substantially improved computational efficiency at test timerelative to the former and at training time relative to the latter.
Abstract
Of numerous proposals to improve the accuracy of naive Bayes by weakening its attribute independence assumption, both LBR and Super-Parent TAN have demonstrated remarkable error performance. However, both techniques obtain this outcome at a considerable computational cost. We present a new approach to weakening the attribute independence assumption by averaging all of a constrained class of classifiers. In extensive experiments this technique delivers comparable prediction accuracy to LBR and Super-Parent TAN with substantially improved computational efficiency at test time relative to the former and at training time relative to the latter. The new algorithm is shown to have low variance and is suited to incremental learning.
Keywords
Computer Science
Springer series in statisticsThe Elements of Statistical Learning
24,344 Citations2001Trevor Hastie, J. Friedman +1 more
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
The Elements of Statistical Learning: Data Mining, Inference, and Prediction
19,345 Citations2013Trevor Hastie, Robert Tibshirani +1 more
Neural NetworksStacked generalization
7,478 Citations1992David H. Wolpert
The conclusion is that for almost any real-world generalization problem one should use some version of stacked generalization to minimize the generalization error rate.
Machine LearningBayesian Network Classifiers
4,738 Citations1997Nir Friedman, Dan Geiger +1 more
Tree Augmented Naive Bayes (TAN) is single out, which outperforms naive Bayes, yet at the same time maintains the computational simplicity and robustness that characterize naive Baye.
International Joint Conference on Artificial IntelligenceMulti-Interval Discretization of Continuous-Valued Attributes for Classification Learning
2,832 Citations1993Usama M. Fayyad, Keki B. Irani
This paper addresses the use of the entropy minimization heuristic for discretizing the range of a continuous-valued attribute into multiple intervals.
Scaling up the accuracy of Naive-Bayes classifiers: a decision-tree hybrid
1,363 Citations1996Ron Kohavi
A new algorithm, NBTree, is proposed, which induces a hybrid of decision-tree classifiers and Naive-Bayes classifiers: the decision-Tree nodes contain univariate splits as regular decision-trees, but the leaves contain Naïve-Bayesian classifiers.
Beyond Independence: Conditions for the Optimality of the Simple Bayesian Classifier.
683 Citations1996Pedro Domingos, Michael J. Pazzani
It is shown that the simple Bayesian classi er (SBC) does not in fact assume attribute independence, and can be optimal even when this assumption is violated by a wide margin, and the previously-assumed region of optimality is a second-order in nitesimal fraction of the actual one.
Elsevier eBooksInduction of Selective Bayesian Classifiers
659 Citations1994Pat Langley, Stephanie Sage
This paper embeds the naive Bayesian induction scheme within an algorithm that carries out a greedy search through the space of features, hypothesize that this approach will improve asymptotic accuracy in domains that involve correlated features without reducing the rate of learning in ones that do not.
Bias plus variance decomposition for zero-one loss functions
627 Citations1996Ron Kohavi, David H. Wolpert
It is shown that in practice the naive frequency based estimation of the decompo sition terms is by itself biased and how to correct for this bias is correct.
Data Mining - Practical Machine Learning Tools and Techniques with JAVA Implementations
396 Citations2000I.H. Witten, E. Frank
Wiley Encyclopedia of Operations Research and Management ScienceBayesian Network Classifiers
363 Citations2011Moisés Goldszmidt
The main concepts behind statistical pattern classifiers and Bayesian networks, including the main methods for the automated induction of these models are reviewed, including the main methods for the automated induction of these models.
Learning limited dependence Bayesian classifiers
363 Citations1996Mehran Sahami
A framework for characterizing Bayesian classification methods is presented and a general induction algorithm is presented that allows for traversal of this spectrum depending on the available computational power for carrying out induction and its application in a number of domains with different properties.
Lecture notes in computer scienceSemi-naive bayesian classifier
333 Citations1991Igor Kononenko
The algorithm of the 'naive' Bayesian classifier (that assumes the independence of attributes) is extended to detect the dependencies between attributes to optimize the tradeoff between the 'non-naivety' and the reliability of approximations of probabilities.
Machine LearningDiscretization for naive-Bayes learning: managing discretization bias and variance
255 Citations2008Ying Yang, Geoffrey I. Webb
Properly managing discretization bias and variance can effectively reduce naive-Bayes classification error by adjusting the number of intervals and theNumber of training instances contained in each interval is supplied.
Machine LearningLazy Learning of Bayesian Rules
249 Citations2000Zijian Zheng, Geoffrey I. Webb
This paper proposes the application of lazy learning techniques to Bayesian tree induction and presents the resulting lazy Bayesian rule learning algorithm, called LBR, which can be justified by a variant of Bayes theorem which supports a weaker conditional attribute independence assumption than is required by naive Bayes.
Learning augmented Bayesian classifiers: A comparison of distribution-based and classification-based approaches.
207 Citations1999Eamonn Keogh, Michael J. Pazzani
This work examines an approach where na ve Bayes is augmented by the addition of correlation arcs between attributes, and explores two methods for finding the set of augmenting arcs, a greedy hillclimbing search, and a novel, more computationally efficient algorithm that is called SuperParent.
Constructive Induction of Cartesian Product Attributes
96 Citations1998Michael J. Pazzani
This work describes the construction of new attributes that are the Cartesian product of existing attributes and considers the effects of this operator on three learning algorithms and compares two different methods for determining when to construct new attributes with this operator.
Lecture notes in computer scienceInduction of recursive Bayesian classifiers
93 Citations1993Pat Langley
A recursive algorithm is described that should outperform the simpler scheme in domains that involve disjunctive concepts, since they violate the independence assumption on which the latter relies.
International Conference on Machine LearningEfficient learning of selective Bayesian network classifiers
84 Citations1996Moninder Singh, Gregory Provan
Experimental results show the resulting classifiers are competitive with (or superior to) the best classifiers, based on both Bayesian networks and other formalisms, and that the computational time for learning and using these classifiers is relatively small.
Lecture notes in computer scienceSNNB: A Selective Neighborhood Based Naïve Bayes for Lazy Learning
78 Citations2002Zhipeng Xie, Wynne Hsu +2 more
The results of the experiments show that the proposed SNNB algorithm is efficient and it outperforms Naive Bayes, and state-of-the-art classification methods NBTree, CBA, and C4.5 in terms of accuracy.
Lecture notes in computer scienceAdjusted probability Naive Bayesian induction
75 Citations1998Geoffrey I. Webb, Michael J. Pazzani
The use of this adjusted value in place of the naive Bayesian probability is shown to significantly improve predictive accuracy.
Lecture notes in computer scienceThe Need for Low Bias Algorithms in Classification Learning from Large Data Sets
61 Citations2002Damien Brain, Geoffrey I. Webb
Experiments show that learning from large data sets may be more effective when using an algorithm that places greater emphasis on bias management, rather than variance management, as well as a different type of algorithm to optimal learning from small data sets.
Elsevier eBooksOn Pruning and Averaging Decision Trees
58 Citations1995Jonathan Oliver, David J. Hand
This work performs an empirical comparison of pruning with the approach of averaging over decision trees, using a computationally efficient method of averaging, namely averaging over the extended, fanned set of a tree.
Lazy Bayesian Rules: A Lazy Semi-Naive Bayesian Learning Technique Competitive to Boosting Decision Trees
35 Citations1999Zijian Zheng, Geoffrey I. Webb +1 more
A bias and variance analysis of Lbr reveals that it signiicantly reduces the bias of naive Bayesian classiication at a cost of a slight increase in variance.
Elsevier eBooksOn learning Decision Committees
22 Citations1995Richard Nock, Olivier Gascuel
It is shown that for every constant k, the subclass of decision committees whose elements have monomial of length ≤ k is pac-learnable and that it properly contains k-DL, however, it is also shown that the problem of inducing the shortest consistent decision committee is NP-Hard.
Comparison of lazy Bayesian rule, and tree-augmented Bayesian learning
18 Citations2003Zhihai Wang, Geoffrey I. Webb
The lazy Bayesian rule (LBR) and the tree-augmented naive Bayes (TAN) have demonstrated strong prediction accuracy, but their relative performance has never been evaluated, so these two techniques should be selected according to computational profile.
On learning multiple descriptions of a concept
17 Citations2002Kamal Ali, Cliff Brunk +1 more
The primary result of this paper is that multiple concept descriptions are particularly helpful in "flat" hypothesis spaces in which there are many equally good ways to grow a rule, each having similar gain.
Lecture notes in computer scienceCandidate Elimination Criteria for Lazy Bayesian Rules
10 Citations2001Geoffrey I. Webb
This paper explores alternatives to the candidate elimination criterion employed within Lazy Bayesian Rules, demonstrated to provide better overall error reduction than the use of a minimum data subset size criterion.