Learning Bayesian network classifiers with completed partially directed acyclic graphs

Bojan Mihaljević, Concha Bielza, Pedro Larrañaga
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:272-283, 2018.

Abstract

Most search and score algorithms for learning Bayesian network classifiers from data traverse the space of directed acyclic graphs (DAGs), making arbitrary yet possibly suboptimal arc directionality decisions. This can be remedied by learning in the space of DAG equivalence classes. We provide a number of contributions to existing work along this line. First, we identify the smallest subspace of DAGs that covers all possible class-posterior distributions when data is complete. All the DAGs in this space, which we call \textit{minimal class-focused} DAGs (MC-DAGs), are such that their every arc is directed towards a child of the class variable. Second, in order to traverse the equivalence classes of MC-DAGs, we adapt the greedy equivalence search (GES) by adding operator validity criteria which ensure GES only visits states within our space. Third, we specify how to efficiently evaluate the discriminative score of a GES operator for MC-DAG in time independent of the number of variables and without converting the completed partially DAG, which represents an equivalence class, into a DAG. The adapted GES perfomed well on real-world data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-mihaljevic18a, title = {Learning Bayesian network classifiers with completed partially directed acyclic graphs}, author = {Mihaljevi\'{c}, Bojan and Bielza, Concha and Larra\~{n}aga, Pedro}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {272--283}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/mihaljevic18a/mihaljevic18a.pdf}, url = {https://proceedings.mlr.press/v72/mihaljevic18a.html}, abstract = {Most search and score algorithms for learning Bayesian network classifiers from data traverse the space of directed acyclic graphs (DAGs), making arbitrary yet possibly suboptimal arc directionality decisions. This can be remedied by learning in the space of DAG equivalence classes. We provide a number of contributions to existing work along this line. First, we identify the smallest subspace of DAGs that covers all possible class-posterior distributions when data is complete. All the DAGs in this space, which we call \textit{minimal class-focused} DAGs (MC-DAGs), are such that their every arc is directed towards a child of the class variable. Second, in order to traverse the equivalence classes of MC-DAGs, we adapt the greedy equivalence search (GES) by adding operator validity criteria which ensure GES only visits states within our space. Third, we specify how to efficiently evaluate the discriminative score of a GES operator for MC-DAG in time independent of the number of variables and without converting the completed partially DAG, which represents an equivalence class, into a DAG. The adapted GES perfomed well on real-world data sets.} }
Endnote
%0 Conference Paper %T Learning Bayesian network classifiers with completed partially directed acyclic graphs %A Bojan Mihaljević %A Concha Bielza %A Pedro Larrañaga %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-mihaljevic18a %I PMLR %P 272--283 %U https://proceedings.mlr.press/v72/mihaljevic18a.html %V 72 %X Most search and score algorithms for learning Bayesian network classifiers from data traverse the space of directed acyclic graphs (DAGs), making arbitrary yet possibly suboptimal arc directionality decisions. This can be remedied by learning in the space of DAG equivalence classes. We provide a number of contributions to existing work along this line. First, we identify the smallest subspace of DAGs that covers all possible class-posterior distributions when data is complete. All the DAGs in this space, which we call \textit{minimal class-focused} DAGs (MC-DAGs), are such that their every arc is directed towards a child of the class variable. Second, in order to traverse the equivalence classes of MC-DAGs, we adapt the greedy equivalence search (GES) by adding operator validity criteria which ensure GES only visits states within our space. Third, we specify how to efficiently evaluate the discriminative score of a GES operator for MC-DAG in time independent of the number of variables and without converting the completed partially DAG, which represents an equivalence class, into a DAG. The adapted GES perfomed well on real-world data sets.
APA
Mihaljević, B., Bielza, C. & Larrañaga, P.. (2018). Learning Bayesian network classifiers with completed partially directed acyclic graphs. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:272-283 Available from https://proceedings.mlr.press/v72/mihaljevic18a.html.

Related Material