Model Averaging with Bayesian Network Classifiers

Abstract

This paper considers the problem of performing classification by model-averaging over a class of discrete Bayesian network structures consistent with a partial ordering and with bounded in-degree $k .$ We show that for $N$ nodes this class contains in the worst-case at least $\Omega\left(\left(\begin{array}{c}N/2 \\{k}\end{array}\right)^{N / 2} \right)$ distinct network structures, but we show that this summation can be performed in $O\left(\left(\begin{array}{c}N \\{k}\end{array}\right) \cdot N\right)$ time. We use this fact to show that it is possible to efficiently construct a single directed acyclic graph (DAG) whose predictions approximate those of exact model-averaging over this class, allowing approximate model-averaged predictions to be performed in $O(N)$ time. We evaluate the procedure in a supervised classification context, and show empirically that this technique can be beneficial for classification even when the generating distribution is not a member of the class being averaged over, and we characterize the performance over several parameters on simulated and real-world data.