极大祖先图的马尔可夫性质研究
|
摘要
极大祖先图可编码为含有潜变量的有向无圈图模型的条件独立性关系。不同的极大祖先图可表示相同的条件独立集,称之为马尔可夫等价。基于有向无圈图模型,给出了构造极大祖先图的算法,研究了极大祖先图的马尔可夫性质,并给出了构造极大祖先图马尔可夫等价类的方向准则。
Maximal ancestral graphs can encode conditional independence relations of directed acyclic graphs with latent variables.Different maximal ancestral graphs may be Markov equivalent in the sense that they entail the same conditional independent relations.Based on the model of directed acyclic graphs,an algorithm for constructing maximal ancestral graphs is given,and the Markov properties of maximal ancestral graphs are discussed.Finally,a set of orientation rules is presented that construct the Markov equivalence class representative given a member of the equivalence class.
Maximal ancestral graphs can encode conditional independence relations of directed acyclic graphs with latent variables.Different maximal ancestral graphs may be Markov equivalent in the sense that they entail the same conditional independent relations.Based on the model of directed acyclic graphs,an algorithm for constructing maximal ancestral graphs is given,and the Markov properties of maximal ancestral graphs are discussed.Finally,a set of orientation rules is presented that construct the Markov equivalence class representative given a member of the equivalence class.
引文
[1] Lauritzen S L.Graphical Model[M].Clarendon:Oxford University Press,1996.
[2] Neapolitan R E.Learning Bayesian Netwokes[M].Upper Saddle River:Prentice Hall,2004.
[3] Richardson T,Spirtes P.Ancestral graph Markov models[J].Annals of Statistics,2002,30(4):962-1030.
[4] Ali R A.Markov equivalence for ancestral graphs[J].Annals of Statistics,2009,37(5B):2808-2837.
[5] Tian J.Generating Markov Equivalent Maximal Ancestral Graphs by Single Edge Replacement[C]//Conference on Uncertainty in Artificial Intelligence.Edinburgh,Scotland,July 26-29,2005:591-598.
[6] Sadeghi K.Stable mixed graphs[J].Bernoulli Official Journal of the Bernoulli Society for Mathematical Statistics&Probability,2013,19(5B):2330-2358.
[7] Borboudakis G,Tsamardinos I.Incorporating Causal Prior Knowledge as Path-Constraints in Bayesian Networks and Maximal Ancestral Graphs[C]//Appearing in Proceedings of the 29th International Conference on Machine Learning.Edinburgh,Scotland,UK,June 27-July 3,2012.
[8] Perkovi E,Textor J,Kalisch M,et al.Complete graphical characterization and construction of adjustment sets in Markov equivalence classes of ancestral graphs[J].Journal of Machine Learning Research,2018,18(220):1-62.
[9] Zhang J.Causal Reasoning with Ancestral Graphs[J].Journal of Machine Learning Research,2008,9(3):1437-1474.
[10]Javidian M A,Valtorta M.Decomposition of structural learning about directed acyclic graphs[J].Artificial Intelligence,2006,170(4-5):422-439.
[11]Sadeghi K,Lauritzen S L.Markov Properties for Loopless Mixed Graphs[J].Bernoulli,2014,20(2):676-696.
[12]Evans R J.Graphs for Margins of Bayesian Networks[J].Scandinavian Journal of Statistics,2016,43(3):625-648.
[13]Ali R A,Thomas S R.Markov Equivalence Classes for Maximal Ancestral Graphs[C]//Uncertainty in Artificial Intelligence.Edmonton,January 1-2,2002:1-9.
[14]Ali R A,Thomas S R,Spirtes,P L,et al.Towards Characterizing Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variables[C]//Twenty-First Conference on Uncertainty in Artificial Intelligence(UAI 2005).Edinburgh,Scotland,UK,January 1-2,2005:10-17.
[15]Zhang J,Spirtes P.A Transformational Characterization of Markov Equivalence between DAGs with Latent Variables[J].Journal of the American Chemical Society,2005,133(39):15324-15327.
[2] Neapolitan R E.Learning Bayesian Netwokes[M].Upper Saddle River:Prentice Hall,2004.
[3] Richardson T,Spirtes P.Ancestral graph Markov models[J].Annals of Statistics,2002,30(4):962-1030.
[4] Ali R A.Markov equivalence for ancestral graphs[J].Annals of Statistics,2009,37(5B):2808-2837.
[5] Tian J.Generating Markov Equivalent Maximal Ancestral Graphs by Single Edge Replacement[C]//Conference on Uncertainty in Artificial Intelligence.Edinburgh,Scotland,July 26-29,2005:591-598.
[6] Sadeghi K.Stable mixed graphs[J].Bernoulli Official Journal of the Bernoulli Society for Mathematical Statistics&Probability,2013,19(5B):2330-2358.
[7] Borboudakis G,Tsamardinos I.Incorporating Causal Prior Knowledge as Path-Constraints in Bayesian Networks and Maximal Ancestral Graphs[C]//Appearing in Proceedings of the 29th International Conference on Machine Learning.Edinburgh,Scotland,UK,June 27-July 3,2012.
[8] Perkovi E,Textor J,Kalisch M,et al.Complete graphical characterization and construction of adjustment sets in Markov equivalence classes of ancestral graphs[J].Journal of Machine Learning Research,2018,18(220):1-62.
[9] Zhang J.Causal Reasoning with Ancestral Graphs[J].Journal of Machine Learning Research,2008,9(3):1437-1474.
[10]Javidian M A,Valtorta M.Decomposition of structural learning about directed acyclic graphs[J].Artificial Intelligence,2006,170(4-5):422-439.
[11]Sadeghi K,Lauritzen S L.Markov Properties for Loopless Mixed Graphs[J].Bernoulli,2014,20(2):676-696.
[12]Evans R J.Graphs for Margins of Bayesian Networks[J].Scandinavian Journal of Statistics,2016,43(3):625-648.
[13]Ali R A,Thomas S R.Markov Equivalence Classes for Maximal Ancestral Graphs[C]//Uncertainty in Artificial Intelligence.Edmonton,January 1-2,2002:1-9.
[14]Ali R A,Thomas S R,Spirtes,P L,et al.Towards Characterizing Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variables[C]//Twenty-First Conference on Uncertainty in Artificial Intelligence(UAI 2005).Edinburgh,Scotland,UK,January 1-2,2005:10-17.
[15]Zhang J,Spirtes P.A Transformational Characterization of Markov Equivalence between DAGs with Latent Variables[J].Journal of the American Chemical Society,2005,133(39):15324-15327.