Model Averaging with Bayesian Network Classifiers

Denver Dash, Gregory F. Cooper
Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, PMLR R4:72-79, 2003.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR4-dash03a, title = {Model Averaging with Bayesian Network Classifiers}, author = {Dash, Denver and Cooper, Gregory F.}, booktitle = {Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics}, pages = {72--79}, year = {2003}, editor = {Bishop, Christopher M. and Frey, Brendan J.}, volume = {R4}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r4/dash03a/dash03a.pdf}, url = {https://proceedings.mlr.press/r4/dash03a.html}, 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.}, note = {Reissued by PMLR on 01 April 2021.} }
Endnote
%0 Conference Paper %T Model Averaging with Bayesian Network Classifiers %A Denver Dash %A Gregory F. Cooper %B Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2003 %E Christopher M. Bishop %E Brendan J. Frey %F pmlr-vR4-dash03a %I PMLR %P 72--79 %U https://proceedings.mlr.press/r4/dash03a.html %V R4 %X 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. %Z Reissued by PMLR on 01 April 2021.
APA
Dash, D. & Cooper, G.F.. (2003). Model Averaging with Bayesian Network Classifiers. Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R4:72-79 Available from https://proceedings.mlr.press/r4/dash03a.html. Reissued by PMLR on 01 April 2021.

Related Material