贝叶斯网边际马尔科夫子图及其应用

范雨, 胡莹莹, 孙毅, 衡佩

数学学报 ›› 2024, Vol. 67 ›› Issue (3) : 565-581.

PDF(986 KB)
中国科学院数学与系统科学研究院期刊网
PDF(986 KB)
数学学报 ›› 2024, Vol. 67 ›› Issue (3) : 565-581. DOI: 10.12386/A20220174
论文

贝叶斯网边际马尔科夫子图及其应用

    范雨1, 胡莹莹1, 孙毅1, 衡佩2
作者信息 +

Marginal Markov Subgraph of Bayesian Network and Its Applications

    Yu FAN1, Ying Ying HU1, Yi SUN1, Pei HENG2
Author information +
文章历史 +

摘要

贝叶斯网络利用有向无圈图对多元联合概率分布中条件独立性进行约束,以实现其在不确定推理中的模块化分解, 降低概率推理的计算复杂度.它在概率推理、机器学习和因果推理中都有广泛的应用. 在实际中,如果采用分而治之或模型压缩的方法对贝叶斯网络进行结构学习或统计推断,那么需要人们寻找边际分布的极小马尔科夫子图(或极小独立图)来建立边际模型.为此,本文基于贝叶斯网的道义图研究贝叶斯网边际模型的极小马尔科夫子图,从统计和图论的观点对其进行了细致的刻画. 针对DAG模型的可压缩性,本文将基于有向导出路径的性质给出更直观的等价条件,同时又给出了若干充分条件, 这为判断模型是否可压缩到局部子模型上提供了更多的理论工具.

Abstract

Bayesian networks utilize directed acyclic graphs (DAGs) to constrain conditional independencies in multivariate joint probability distribution, so as to realize its modular decomposition in uncertainty reasoning and reduce the computational complexity of probabilistic reasoning. They are widely used in probabilistic reasoning, machine learning and causal inference. In practice, if structure learning or statistical inference was performed by adopting the idea of dividing and conquering or model collapsing, we have to establish the marginal models by finding their minimal Markov subgraphs (or minimal independence maps). Therefore, this paper details minimal Markov subgraphs for marginal models of Bayesian networks, and provides the refined characterization on them from the perspectives of statistics and graph theory. For the collapsibility of DAG, this paper gives more intuitive equivalent conditions based on the properties of directed inducing paths, and also proposes some sufficient conditions, which provides more theoretical tools for judging whether the considered models can be collapsible onto local sub-models.

关键词

贝叶斯网络 / 有向无圈图(DAG) / 马尔可夫子图 / 边际模型 / 极小独立图

Key words

Bayesian networks / directed acyclic graph (DAG) / Markov subgraph / marginal model / minimal I-map

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
范雨, 胡莹莹, 孙毅, 衡佩. 贝叶斯网边际马尔科夫子图及其应用. 数学学报, 2024, 67(3): 565-581 https://doi.org/10.12386/A20220174
Yu FAN, Ying Ying HU, Yi SUN, Pei HENG. Marginal Markov Subgraph of Bayesian Network and Its Applications. Acta Mathematica Sinica, Chinese Series, 2024, 67(3): 565-581 https://doi.org/10.12386/A20220174

参考文献

[1] Asmussen S., Edwards D., Collapsibility and response variables in contingency tables, Biometrika, 1983, 70(3): 567-578.
[2] Cai B., Liu Y., Liu Z., et al., Bayesian Networks for Reliability Engineering, Springer Singapore, 2020.
[3] Cowell R. G., Dawid P., Lauritzen S. L., et al., Probabilistic Networks and Expert systems: Exact Computational Methods for Bayesian Networks, Springer Science & Business Media, New York, 2007.
[4] Cox D. R., Wermuth N., Multivariate Dependencies: Models, Analysis and Interpretation, Chapman and Hall/CRC, 2014.
[5] Evans R. J., Graphs for margins of Bayesian networks, Scandinavian Journal of Statistics, 2016, 43(3): 625-648.
[6] Evans R. J., Margins of discrete Bayesian networks, Annals of Statistics, 2018, 46(6A): 2623-2656.
[7] Evans R. J., Richardson T. S., Markovian acyclic directed mixed graphs for discrete data, Annals of Statistics, 2014, 42(4), 1452-1482.
[8] Edwards D., Introduction to Graphical Modelling, Springer Science & Business Media, New York, 2012.
[9] Friedman N., Linial M., Nachman I., et al., Using Bayesian networks to analyze expression data, Journal of Computational Biology, 2000, 7(3-4): 601-620.
[10] Frydenberg M., Marginalization and collapsibility in graphical interaction models, Annals of Statistics, 1990, 18(2): 790-805.
[11] Fenton N., Neil M., Risk Assessment and Decision Analysis with Bayesian Networks, CRC Press, New York, 2018.
[12] Guo J. H., Wang X. F., Graph Decomposition: Theory, Algorithm and Applications (unpublished manuscript in Chinese), KLAS, Northeast Normal University, Changchun, 2015.
[13] Gresele L., Von Kügelgen J., Kübler J., et al., Causal inference through the structural causal marginal problem, In: International Conference on Machine Learning. PMLR, 2022, 7793-7824.
[14] Kim G. H., Kim S. H., Marginal information for structure learning, Statistics and Computing, 2020, 30(2): 331-349.
[15] Kim S. H., Hyper-EM for large recursive models of categorical variables, Computational Statistics & Data Analysis, 2000, 33(4): 401-424.
[16] Kim S., Kim S. H., A note on collapsibility in DAG models of contingency tables, Scandinavian Journal of Statistics, 2006, 33(3), 575-590.
[17] Kim S. H., Kim S. H., A divide-and-conquer approach in applying EM for large recursive models with incomplete categorical data, Computational Statistics & Data Analysis, 2006, 50, 611-641.
[18] Koller D., Friedman N., Probabilistic Graphical Models: Principles and Techniques, MIT Press, Cambridge, Massachusetts.
[19] Koster J. T. A., Marginalizing and conditioning in graphical models, Bernoulli, 2002: 817-840.
[20] Lauritzen S. L., Graphical Models, Clarendon Press, 1996.
[21] Maathuis M., Drton M., Lauritzen S. L., Wainwright M., Handbook of Graphical Models, CRC Press, 2018.
[22] Madigan D., Mosurski K., An extension of the results of Asmussen and Edwards on collapsibility in contingency tables, Biometrika, 1990, 77(2): 315-319.
[23] Meek C., Strong completeness and faithfulness in Bayesian networks, In: Uncertainty in Artificial Intelligence (Montreal, PQ), Morgan Kaufmann, San Francisco, Quebec, Canada, 411-418.
[24] Murphy K. P., Probabilistic Machine Learning: Advanced Topics, MIT Press, 2023.
[25] Neapolitan R. E., Jiang X., Artificial Intelligence: with an Introduction to Machine Learning, CRC Press, 2018.
[26] Ohtsuki T., Cheung L. K., Fujisawa T., Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Journal of Mathematical Analysis and Applications, 1976, 54(3): 622-633.
[27] Parter S., The use of linear graphs in Gauss elimination, Society for Industrial and Applied Mathematics Review, 1961, 3(2): 119-130.
[28] Pearl J., Causality: Models, Reasoning, and Inference, New York: Cambridge University Press, 2009.
[29] Pearl J., Verma T. S., A statistical semantics for causation, Statistics and Computing, 1992, 2(2): 91-95.
[30] Pourret O., Na P., Marcot B., Bayesian Networks: a Practical Guide to Applications, John Wiley & Sons, 2008.
[31] Rose D. J., Tarjan R. E., Lueker G. S., Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 1976, 5(2): 266-283.
[32] Richardson T., Spirtes P., Ancestral graph Markov models, Annals of Statistics, 2002, 30(4): 962-1030.
[33] Richardson T., Markov properties for acyclic directed mixed graphs, Scandinavian Journal of Statistics, 2003, 30(1): 145-157.
[34] Richardson T., A factorization criterion for acyclic directed mixed graphs, In: Proceedings of the TwentyFifth Conference on Uncertainty in Artificial Intelligence, 2009, 462-470.
[35] Richardson T., Evans R., Robins J., et al., Nested Markov properties for acyclic directed mixed graphs, In: UAI’12: Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, Quebec, Canada, 2017.
[36] Sadeghi K., Stable mixed graphs, Bernoulli, 2013, 19(5B): 2330-2358.
[37] Sadeghi K., Marginalization and conditioning for LWF chain graphs, The Annals of Statistics, 2016, 44(4), 1792-1816.
[38] Silva R., Ghahramani Z., The hidden life of latent variables: Bayesian learning with mixed graph models, Journal of Machine Learning Research, 2009, 10: 1187-1238.
[39] Sinoquet C., Probabilistic Graphical Models for Genetics, Genomics, and Postgenomics, OUP, Oxford, 2014.
[40] Spirtes P., Glymour C. N., Scheines R., et al., Causation, Prediction, and Search, MIT Press, Massachusetts, 2000.
[41] Spiegelhalter D. J., Dawid A. P., Lauritzen S. L., et al., Bayesian analysis in expert systems, Statistical Science, 1993: 219-247.
[42] Sun T. R., Sun Y., Marginalization of the Markov property for Bayesian networks, Journal of Systems Science and Mathematical Sciences, 2022, 42(12): 3380-3396.
[43] Trucco P., Cagno E., Ruggeri F., et al., A Bayesian belief network modelling of organisational factors in risk analysis: a case study in maritime transportation, Reliability Engineering and System Safety, 2008, 93(6): 845-856.
[44] Tran K. P., Machine Learning and Probabilistic Graphical Models for Decision Support Systems, CRC Press, New York, 2022.
[45] Xie X., Geng Z., Collapsibility for directed acyclic graphs, Scandinavian Journal of Statistics, 2009, 36(2): 185-203.
[46] Yao C. D., On marginalization and collapsibility of graphical models based on variable elimination (Master thesis), Xinjiang University, Urumqi, 2021.
[47] Yang L., Lee J., Bayesian belief network-based approach for diagnostics and prognostics of semiconductor manufacturing systems, Robotics and Computer-Integrated Manufacturing, 2012, 28(1): 66-74.
[48] Zhang N. L., Poole D., Exploiting causal independence in Bayesian network inference, Journal of Artificial Intelligence Research, 1996, 5: 301-328.

基金

国家自然科学基金 (11726629, 11726630,11701491), 新疆维吾尔自治区自然科学基金(2022D01C406) 和东北师范大学应用统计教育部重点实验室开放课题 (130028906) 资助
PDF(986 KB)

407

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉