期刊
ANNALS OF STATISTICS
卷 41, 期 4, 页码 1742-1779出版社
INST MATHEMATICAL STATISTICS
DOI: 10.1214/13-AOS1125
关键词
Sparse graphical model; reversible Markov chain; Markov equivalence class; Causal inference
资金
- NSFC [11101008, 11101005, 71271211]
- 973 Program [2007CB814905, DPHEC-20110001120113]
- US NSF [DMS-11-07000, DMS-09-07632, DMS-06-05165, DMS-12-28246 3424, SES-0835531]
- US ARO [W911NF-11-1-0114]
- Center for Science of Information (CSoI), a US NSF Science and Technology Center [CCF-0939370]
- School of Mathematical Science
- Center of Statistical Sciences
- Key Lab of Mathematical Economics and Quantitative Finance (Ministry of Education)
- Key lab of Mathematics and Applied Mathematics (Ministry od Education)
- Microsoft Joint Lab on Statistics and information technology at Peking University
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1107000] Funding Source: National Science Foundation
Graphical models are popular statistical tools which are used to represent dependent or causal complex systems. Statistically equivalent causal or directed graphical models are said to belong to a Markov equivalent class. It is of great interest to describe and understand the space of such classes. However, with currently known algorithms, sampling over such classes is only feasible for graphs with fewer than approximately 20 vertices. In this paper, we design reversible irreducible Markov chains on the space of Markov equivalent classes by proposing a perfect set of operators that determine the transitions of the Markov chain. The stationary distribution of a proposed Markov chain has a closed form and can be computed easily. Specifically, we construct a concrete perfect set of operators on sparse Markov equivalence classes by introducing appropriate conditions on each possible operator. Algorithms and their accelerated versions are provided to efficiently generate Markov chains and to explore properties of Markov equivalence classes of sparse directed acyclic graphs (DAGs) with thousands of vertices. We find experimentally that in most Markov equivalence classes of sparse DAGs, (1) most edges are directed, (2) most undirected subgraphs are small and (3) the number of these undirected subgraphs grows approximately linearly with the number of vertices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据