2012/10/19 by Hei Chan, Adnan Darwiche, Chan, Hei +1 · 4 citations
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Quality and Management #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.1212.2470
openalex publication_date 2012/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Bayesian network classifiers are used in many fields, and one common class of classifiers are naive Bayes classifiers. In this paper, we introduce an approach for reasoning about Bayesian network classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDs), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size even given an intractable number of instances. Since ODDs are tractable representations of classifiers, our algorithm allows us to efficiently test the equivalence of two naive Bayes classifiers and characterize discrepancies between them. We also show a number of additional results including a count of distinct classifiers that can be induced by changing some CPT in a naive Bayes classifier, and the range of allowable changes to a CPT which keeps the current classifier unchanged.