TAN Classifiers Based on Decomposable Distributions
Machine LearningPublished 20 May 2005Open access
Jesús Cerquides, Ramón López de Mántaras
Citations33
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
This paper extends the results in Meila & Jaakkola (2000a) to TANs by proving that accepting a prior decomposable distribution over TAN’s, the exact Bayesian model averagingover TAN structures and parameters in polynomial time is computed.
Abstract
In this paper we present several Bayesian algorithms for learning Tree Augmented Naive Bayes (TAN) models. We extend the results in Meila & Jaakkola (2000a) to TANs by proving that accepting a prior decomposable distribution over TAN's, we can compute the exact Bayesian model averaging over TAN structures and parameters in polynomial time. Furthermore, we prove that the k-maximum a posteriori (MAP) TAN structures can also be computed in polynomial time. We use these results to correct minor errors in Meila & Jaakkola (2000a) and to construct several TAN based classifiers. We show that these classifiers provide consistently better predictions over Irvine datasets and artificially generated data than TAN based classifiers proposed in the literature.
Keywords
Computer Science
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.
Machine LearningLearning Bayesian Networks: The Combination of Knowledge and Statistical Data
3,242 Citations1995David Heckerman, Dan Geiger +1 more
A methodology for assessing informative priors needed for learning Bayesian networks from a combination of prior knowledge and statistical data is developed and how to compute the relative posterior probabilities of network structures given data is shown.
Machine LearningOn the Optimality of the Simple Bayesian Classifier under Zero-One Loss
3,072 Citations1997Pedro Domingos, Michael J. Pazzani
The Bayesian classifier is shown to be optimal for learning conjunctions and disjunctions, even though they violate the independence assumption, and 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.
IEEE Transactions on Information TheoryApproximating discrete probability distributions with dependence trees
2,640 Citations1968Chee Lap Chow, C. Liu
It is shown that the procedure derived in this paper yields an approximation of a minimum difference in information when applied to empirical observations from an unknown distribution of tree dependence, and the procedure is the maximum-likelihood estimate of the distribution.
Machine LearningA Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems
2,264 Citations2001David J. Hand, Robert John Till
This work extends the definition of the area under the ROC curve to the case of more than two classes by averaging pairwise comparisons and proposes an alternative definition of proportion correct based on pairwise comparison of classes for a simple artificial case.
Machine LearningLearning Bayesian networks: The combination of knowledge and statistical data
2,043 Citations1995David Heckerman, Dan Geiger +1 more
It is shown that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—aprior network—and a single measure of confidence for that network.
An analysis of Bayesian classifiers
1,145 Citations1992Pat Langley, and Wayne Iba +1 more
An average-case analysis of the Bayesian classifier, a simple induction algorithm that fares remarkably well on many learning tasks, and explores the behavioral implications of the analysis by presenting predicted learning curves for artificial domains.
ROC Graphs: Notes and Practical Considerations for Data Mining Researchers
635 Citations2003Tom Fawcett
Journal of the ACMAn optimal minimum spanning tree algorithm
296 Citations2002Seth Pettie, Vijaya Ramachandran
It is established that the algorithmic complexity of the minimumspanning tree problem is equal to its decision-tree complexity and a deterministic algorithm to find aminimum spanning tree of a graph with vertices and edges that runs in time is presented.
SIAM Journal on ComputingAn Algorithm for Finding <i>K</i> Minimum Spanning Trees
86 Citations1981Naoki Katoh, Toshihide Ibaraki +1 more
This paper presents an algorithm for finding K minimum spanning trees in an undirected graph based on three subroutines which obtains the kth minimum spanning tree in $O(m)$ steps when the jthminimum spanning trees for $j = 1,2, \cdots ,k - 1$ are given.
Statistics and ComputingTractable Bayesian learning of tree belief networks
82 Citations2006Marina Meilă, Tommi Jaakkola
Applying general Bayesian techniques to improve TAN induction
12 Citations1999Jesús Cerquides
Two ideas to overcome shortcomings in the Free Augmented Naive Bayes induction algorithm are introduced: the multinomial sampling approach to learning bayesian networks and local bayesian model averaging.
Lecture notes in computer scienceBayes optimal instance-based learning
12 Citations1998Petri Kontkanen, Petri Myllymdki +2 more
The results suggest that the Bayesian instancebased learning approach yields better results than the traditional Naive Bayes classifier, especially in cases where the amount of the training data is small.