Approximating bounded tree-width Bayesian network classifiers with OBDD
Proceedings of the 10th International Conference on Probabilistic Graphical Models, PMLR 138:113-124, 2020.
It is shown that Bayesian network classifiers of tree-width $k$ have an OBDD approximation computable in polynomial time in the parameters, for every fixed $k$. This is shown by approximating a polynomial threshold function representing the classifier. The approximation error can be measured with respect to any distribution which can be approximated by a mixture of bounded width distributions. This includes the input distribution of the classifier.