Identifiability of causal effect for a simple causal model

Counterfactual model is put forward to discuss the causal inference in the directed acyclic graph and its corresponding identifiability is thus studied with the ancillary information based on conditional independence. It is shown that the assumption of ignorability can be expanded to the assumption of replaceability,under which the causal efiects are identifiable.     

一类因果模型的可识别性条件

因果问题在近代医学,生物学,社会科学的研究中占有非常重要的地位。通过因果关系预见某些行为或策略对研究对象的影响已经成为一些实际研究的最终目的。Rubin(1978)提出了解决因果问题的虚拟事实模型,建立了因果推断统计分析的基本框架。虚拟事实模型的因果效应是以实际观测数据为研究对象的,但又不完全由数据之间的相关性决定,因此在讨论因果效应时存在可识别性问题。如果因果效应可识别,则有可能利用观测数据直接计算因果效应。但是,众 所周知:在不加任何假设或限制的条件下,虚拟事实模型的因果效应是不可识别的。若要研究变量间的因果效应就必须对虚拟事实模型加入某些必要的限制,使因果效应在这些限制下可识别。郑忠国,张艳艳,童行伟在“因果模型因果效应的可识别性研究”中针对控制变量与协变量相互独立的一类模型的可识别性进行了研究,指出在某些特定的可替换性假设之下,模型的因果效应具有可识别性。该文将针对控制变量作用于协变量的虚拟事实模型进行可识别性研究。作者将指出:控制变量是否作用于协变量并不影响因果效应的可识别性和可替换性假设。并给出:此类模型因果效应可唯一确定的充要条件 。      

Acyclic directed graphs representing independence models

In this paper we study the problem of representing probabilistic independence models, in particular those closed under graphoid properties. We focus on acyclic directed graph (DAG): a new algorithm to build a DAG, given an ordering among random variables, is described and peculiarities and advantages of this approach are discussed. Moreover, we provide a necessary and sufficient condition for the existence of a perfect map representing an independence model and we describe an algorithm based on this characterization.     

The L-separation criterion for description of cs-independence models

Different conditional independence models have been proposed in literature; in this paper we consider models induced by conditional probabilities based on the definition of conditional cs-independence. These models need not comply with the symmetry property, so that they have not the graphoid structure. Hence, the well-known d-separation criterion for directed acyclic graphs may not be able to represent such independence models. Therefore, we introduce a new separation criterion called L-separation. We study its main properties and show how it allows to represent the above-mentioned independence models through directed acyclic graphs.     

On expressiveness of the chain graph interpretations

In this article we study the expressiveness of the different chain graph interpretations. Chain graphs is a class of probabilistic graphical models that can contain two types of edges, representing different types of relationships between the variables in question. Chain graphs is also a superclass of directed acyclic graphs, i.e. Bayesian networks, and can thereby represent systems more accurately than this less expressive class of models. Today there do however exist several different ways of interpreting chain graphs and what conditional independences they encode, giving rise to different so-called chain graph interpretations. Previous research has approximated the number of representable independence models for the Lauritzen–Wermuth–Frydenberg and the multivariate regression chain graph interpretations using an MCMC based approach. In this article we use a similar approach to approximate the number of models representable by the latest chain graph interpretation in research, the Andersson–Madigan–Perlman interpretation. Moreover we summarize and compare the different chain graph interpretations with each other. Our results confirm previous results that directed acyclic graphs only can represent a small fraction of the models representable by chain graphs, even for a low number of nodes. The results also show that the Andersson–Madigan–Perlman and multivariate regression interpretations can represent about the same amount of models and twice the amount of models compared to the Lauritzen–Wermuth–Frydenberg interpretation. However, at the same time almost all models representable by the latter interpretation can only be represented by that interpretation while the former two have a large intersection in terms of representable models.     

Distributions of numbers of runs and scans on directed acyclic graphs with generation

In this paper, we introduce a class of a directed acyclic graph on the assumption that the collection of random variables indexed by the vertices has a Markov property. We present a flexible approach for the study of the exact distributions of runs and scans on the directed acyclic graph by extending the method of conditional probability generating functions. The results presented here provide a wide framework for developing the exact distribution theory of runs and scans on the graphical models. We also show that our theoretical results can easily be carried out through some computer algebra systems and give some numerical examples in order to demonstrate the feasibility of our theoretical results. As applications, two special reliability systems are considered, which are closely related to our general results. Finally, we address the parameter estimation in the distributions of runs and scans.     

An efficient algorithm for finding the largest chain graph according to a given chain graph

Chain graph (CG) is a general model of graphical Markov models. Some different chain graphs may describe the same conditional independence structure, then we say that these CGs are Markov equivalent. In 1990 Frydenberg showed that every class of Markov equivalent CGs has a CG which is called the largest chain graph with the greatest number of lines. This paper presents an efficient algorithm for finding the largest chain graph of the corresponding Markov equivalent class of a given CG. The computational complexity of the algorithm is O(n3). It is more efficient than the complexity O(n!) of the present algorithms. Also a more intuitive graphical characterization of the largest chain graph is provided based on the algorithm in this paper.     

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.This research was partially supported by the C.I.C.Y.T. with code tap92-0639.     

Representing Sparse Gaussian DAGs as Sparse R-Vines Allowing for Non-Gaussian Dependence

Modeling dependence in high-dimensional systems has become an increasingly important topic. Most approaches rely on the assumption of a multivariate Gaussian distribution such as statistical models on directed acyclic graphs (DAGs). They are based on modeling conditional independencies and are scalable to high dimensions. In contrast, vine copula models accommodate more elaborate features like tail dependence and asymmetry, as well as independent modeling of the marginals. This flexibility comes however at the cost of exponentially increasing complexity for model selection and estimation. We show a novel connection between DAGs with limited number of parents and truncated vine copulas under sufficient conditions. This motivates a more general procedure exploiting the fast model selection and estimation of sparse DAGs while allowing for non-Gaussian dependence using vine copulas. By numerical examples in hundreds of dimensions, we demonstrate that our approach outperforms the standard method for vine structure selection. Supplementary material for this article is available online.     

Identification of graphical models for nonignorable nonresponse of binary outcomes in longitudinal studies

In this paper, we use directed acyclic graphs (DAGs) with temporal structure to describe models of nonignorable nonresponse mechanisms for binary outcomes in longitudinal studies, and we discuss identification of these models under an assumption that the sequence of variables has the first-order Markov dependence, that is, the future variables are independent of the past variables conditional on the present variables. We give a stepwise approach for checking identifiability of DAG models. For an unidentifiable model, we propose adding completely observed variables such that this model becomes identifiable.     

Identifiability of intermediate variables on causal paths

We discuss the discovery of causal mechanisms and identifiability of intermediate variables on a causal path. Different from variable selection, we try to distinguish intermediate variables on the causal path from other variables. It is also different from ordinary model selection approaches which do not concern the causal relationships and do not contain unobserved variables. We propose an approach for selecting a causal mechanism depicted by a directed acyclic graph (DAG) with an unobserved variable. We consider several causal networks, and discuss their identifiability by observed data. We show that causal mechanisms of linear structural equation models are not identifiable. Furthermore, we present that causal mechanisms of nonlinear models are identifiable, and we demonstrate the identifiability of causal mechanisms of quadratic equation models. Sensitivity analysis is conducted for the identifiability.     

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.     

Decomposition of search for -structures in DAGs

We show that the problem of searching for v-structures in a directed acyclic graph can be decomposed into searches in its decomposed subgraphs. This result simplifies the search for v-structures and the recovery of local causal relationships.     

A logical approach to context-specific independence

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics.     

Pair-Copula Bayesian Networks

Pair-copula Bayesian networks (PCBNs) are a novel class of multivariate statistical models, which combine the distributional flexibility of pair-copula constructions (PCCs) with the parsimony of conditional independence models associated with directed acyclic graphs (DAGs). We are first to provide generic algorithms for random sampling and likelihood inference in arbitrary PCBNs as well as for selecting orderings of the parents of the vertices in the underlying graphs. Model selection of the DAG is facilitated using a version of the well-known PC algorithm that is based on a novel test for conditional independence of random variables tailored to the PCC framework. A simulation study shows the PC algorithm’s high aptitude for structure estimation in non-Gaussian PCBNs. The proposed methods are finally applied to modeling financial return data. Supplementary materials for this article are available online.     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

利用贝叶斯网络分析基因表达数据

利用基因表达数据提出一种新的网络模型—贝叶斯网络,发现基因的互作.一个贝叶斯网络是多变量联合概率分布的有向图模型,表示变量间的条件独立属性.首先我们阐明贝叶斯网络如何表示基因间的互作,然后介绍从基因芯片数据学习贝叶斯网络的方法.     

Volume requirements of 3D upward drawings

This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable.