QQ客服 官方微博 反馈留言

	Counting and Exploring Sizes of Markov Equivalence Classes of Directed Acyclic Graphs
	He, Yangbo ; Jia, Jinzhu ; Yu, Bin
	2015
关键词	directed acyclic graphs Markov equivalence class size distribution causality NETWORKS MODELS
英文摘要	When learning a directed acyclic graph (DAG) model via observational data, one generally cannot identify the underlying DAG, but can potentially obtain a Markov equivalence class. The size (the number of DAGs) of a Markov equivalence class is crucial to infer causal effects or to learn the exact causal DAG via further interventions. Given a set of Markov equivalence classes, the distribution of their sizes is a key consideration in developing learning methods. However, counting the size of an equivalence class with many vertices is usually computationally infeasible, and the existing literature reports the size distributions only for equivalence classes with ten or fewer vertices. In this paper, we develop a method to compute the size of a Markov equivalence class. We first show that there are five types of Markov equivalence classes whose sizes can be formulated as five functions of the number of vertices respectively. Then we introduce a new concept of a rooted sub-class. The graph representations of rooted subclasses of a Markov equivalence class are used to partition this class recursively until the sizes of all rooted subclasses can be computed via the five functions. The proposed size counting is efficient for Markov equivalence classes of sparse DAGs with hundreds of vertices. Finally, we explore the size and edge distributions of Markov equivalence classes and find experimentally that, in general, (1) most Markov equivalence classes are half completed and their average sizes are small, and (2) the sizes of sparse classes grow approximately exponentially with the numbers of vertices.; NSFC [11101008, 11101005, 71271211]; US NSF [DMS-1107000, CDSE-MSS 1228246]; ARO [W911NF-11-1-0114]; AFOSR Grant [FA 9550-14-0016]; Center for Science of Information (CSoI, a US NSF Science and Technology Center) [CCF-0939370]; [DPHEC-20110001120113]; SCI(E); EI; ARTICLE; HEYB@PKU.EDU.CN; JZJIA@MATH.PKU.EDU.CN; BINYU@STAT.BERKELEY.EDU; 2589-2609; 16
语种	英语
出处	EI ; SCI
出版者	JOURNAL OF MACHINE LEARNING RESEARCH
内容类型	其他
源URL	[http://hdl.handle.net/20.500.11897/435634]
专题	数学科学学院
推荐引用方式 GB/T 7714	He, Yangbo,Jia, Jinzhu,Yu, Bin. Counting and Exploring Sizes of Markov Equivalence Classes of Directed Acyclic Graphs. 2015-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。