Eliminating Variable Order Instability in Greedy Score-Based Structure Learning

Neville K Kitson, Anthony C Constantinou
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:147-163, 2024.

Abstract

Many Bayesian Network structure learning algorithms are unstable in that the learnt graph is sensitive to arbitrary artefacts of the dataset, such as the ordering of columns (i.e., variable order). PC-Stable, developed by \cite{colombo2014order}, attempts to address this issue for the widely-used PC algorithm, prompting researchers to use the ‘stable’ version instead. However, this problem seems to have been overlooked for score-based algorithms. In this study, we show that some widely-used score-based algorithms suffer from the same issue and that PC-Stable, although less sensitive than most of the score-based algorithms tested, is not completely stable. We also present a solution to score-based greedy hill-climbing that completely eliminates this instability, and provide two implementations: the HC-Stable and Tabu-Stable algorithms, the latter of which learns more accurate graphs than all the well-known algorithms we compared it to.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-kitson24a, title = {Eliminating Variable Order Instability in Greedy Score-Based Structure Learning}, author = {Kitson, Neville K and Constantinou, Anthony C}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {147--163}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/kitson24a/kitson24a.pdf}, url = {https://proceedings.mlr.press/v246/kitson24a.html}, abstract = {Many Bayesian Network structure learning algorithms are unstable in that the learnt graph is sensitive to arbitrary artefacts of the dataset, such as the ordering of columns (i.e., variable order). PC-Stable, developed by \cite{colombo2014order}, attempts to address this issue for the widely-used PC algorithm, prompting researchers to use the ‘stable’ version instead. However, this problem seems to have been overlooked for score-based algorithms. In this study, we show that some widely-used score-based algorithms suffer from the same issue and that PC-Stable, although less sensitive than most of the score-based algorithms tested, is not completely stable. We also present a solution to score-based greedy hill-climbing that completely eliminates this instability, and provide two implementations: the HC-Stable and Tabu-Stable algorithms, the latter of which learns more accurate graphs than all the well-known algorithms we compared it to.} }
Endnote
%0 Conference Paper %T Eliminating Variable Order Instability in Greedy Score-Based Structure Learning %A Neville K Kitson %A Anthony C Constantinou %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-kitson24a %I PMLR %P 147--163 %U https://proceedings.mlr.press/v246/kitson24a.html %V 246 %X Many Bayesian Network structure learning algorithms are unstable in that the learnt graph is sensitive to arbitrary artefacts of the dataset, such as the ordering of columns (i.e., variable order). PC-Stable, developed by \cite{colombo2014order}, attempts to address this issue for the widely-used PC algorithm, prompting researchers to use the ‘stable’ version instead. However, this problem seems to have been overlooked for score-based algorithms. In this study, we show that some widely-used score-based algorithms suffer from the same issue and that PC-Stable, although less sensitive than most of the score-based algorithms tested, is not completely stable. We also present a solution to score-based greedy hill-climbing that completely eliminates this instability, and provide two implementations: the HC-Stable and Tabu-Stable algorithms, the latter of which learns more accurate graphs than all the well-known algorithms we compared it to.
APA
Kitson, N.K. & Constantinou, A.C.. (2024). Eliminating Variable Order Instability in Greedy Score-Based Structure Learning. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:147-163 Available from https://proceedings.mlr.press/v246/kitson24a.html.

Related Material