Compiling Bayesian Network Classifiers into Decision Graphs

  • Andy Shih University of California, Los Angeles
  • Arthur Choi University of California, Los Angeles
  • Adnan Darwiche University of California, Los Angeles


We propose an algorithm for compiling Bayesian network classifiers into decision graphs that mimic the input and output behavior of the classifiers. In particular, we compile Bayesian network classifiers into ordered decision graphs, which are tractable and can be exponentially smaller in size than decision trees. This tractability facilitates reasoning about the behavior of Bayesian network classifiers, including the explanation of decisions they make. Our compilation algorithm comes with guarantees on the time of compilation and the size of compiled decision graphs. We apply our compilation algorithm to classifiers from the literature and discuss some case studies in which we show how to automatically explain their decisions and verify properties of their behavior.

AAAI Technical Track: Reasoning under Uncertainty