Barry Smith recently discussed the diagraphs of book eight of Jacob Lorhard’s Ogdoas scholastica under the heading “birth of ontology” (Smith, 2022; this issue). Here, I highlight the commonalities between the original usage of diagraphs in the tradition of Ramus for didactic purposes and the the usage of their present-day successors–modern ontologies–for computational purposes. The modern ideas of ontology and of the universal computer were born just two generations apart in the breakthrough century of instrumental reason.

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Chickering provided a transformational characterization of Markov equivalence for DAGs, which is useful in deriving properties shared by Markov equivalent DAGs, and, with certain generalization, is needed to prove the asymptotic correctness of a search procedure over Markov equivalence classes, known as the GES algorithm. For DAG models with latent variables, maximal ancestral graphs (...) provide a neat representation that facilitates model search. However, no transformational characterization -- analogous to Chickering's -- of Markov equivalent MAGs is yet available. This paper establishes such a characterization for directed MAGs, which we expect will have similar uses as it does for DAGs. (shrink)

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional indepen- dence relations among the observed variables. Meek characterizes Markov equiva- lence classes for DAGs by presenting a set of orientation rules that can correctly identify all arrow orienta- tions shared by all DAGs in a Markov equiv- alence class, given a member of that class. For DAG models with latent variables, maxi- mal ancestral graphs provide a neat representation (...) that facilitates model search. Earlier work has identified a set of orientation rules sufficient to con- struct all arrowheads common to a Markov equivalence class of MAGs. In this paper, we provide extra rules sufficient to construct all common tails as well. We end up with a set of orientation rules sound and complete for identifying commonalities across a Markov equivalence class of MAGs, which is partic- ularly useful for causal inference. (shrink)

Peter Spirtes. Calculating TETRAD Constraints Implied by Directed Acyclic Graphs.

It is well known that there may be many causal explanations that are consistent with a given set of data. Recent work has been done to represent the common aspects of these explanations into one representation. In this paper, we address what is less well known: how do the relationships common to every causal explanation among the observed variables of some DAG process change in the presence of latent variables? Ancestral graphs provide a class of graphs that can (...) encode conditional independence relations that arise in DAG models with latent and selection variables. In this paper we present a set of orientation rules that construct the Markov equivalence class representative for ancestral graphs, given a member of the equivalence class. These rules are sound and complete. We also show that when the equivalence class includes a DAG, the equivalence class representative is the essential graph for the said DAG. (shrink)

Christopher Meek. Related Graphical Frameworks: Undircted, Directed Acyclic and Chain Graph Models.

Recursive linear structural equation models can be represented by directed acyclic graphs. When represented in this way, they satisfy the Markov Condition. Hence it is possible to use the graphical d-separation to determine what conditional independence relations are entailed by a given linear structural equation model. I prove in this paper that it is also possible to use the graphical d-separation applied to a cyclic graph to determine what conditional independence relations are entailed to hold by a (...) given non-recursive linear structural equation model. I also give a causal intepretation to the linear coefficients in a non- recursive structural equation models, and explore the relationships between cyclic graphs and undirected graphs, directed acyclic graphs with latent variables, and chain independence graphs. (shrink)

The conditional independence relations present in a data set usually admit multiple causal explanations — typically represented by directed graphs — which are Markov equivalent in that they entail the same conditional independence relations among the observed variables. Markov equivalence between directed acyclic graphs (DAGs) has been characterized in various ways, each of which has been found useful for certain purposes. In particular, Chickering’s transformational characterization is useful in deriving properties shared by Markov equivalent DAGs, (...) and, with certain generalization, is needed to justify a search procedure over Markov equivalence classes, known as the GES algorithm. Markov equivalence between DAGs with latent variables has also been characterized, in the spirit of Verma and Pearl (1990), via maximal ancestral graphs (MAGs). The latter can represent the observable conditional independence relations as well as some causal features of DAG models with latent variables. However, no characterization of Markov equivalent MAGs is yet available that is analogous to the transformational characterization for Markov equivalent DAGs. The main contribution of the current paper is to establish such a characterization for directed MAGs, which we expect will have similar uses as Chickering’s characterization does for DAGs. (shrink)

The semantic paradoxes are often associated with self-reference or referential circularity. Yablo (Analysis 53(4):251–252, 1993), however, has shown that there are infinitary versions of the paradoxes that do not involve this form of circularity. It remains an open question what relations of reference between collections of sentences afford the structure necessary for paradoxicality. In this essay, we lay the groundwork for a general investigation into the nature of reference structures that support the semantic paradoxes and the semantic hypodoxes. We develop (...) a functionally complete infinitary propositional language endowed with a denotation assignment and extract the reference structural information in terms of graph-theoretic properties. We introduce the new concepts of dangerous and precarious reference graphs, which allows us to rigorously define the task: classify the dangerous and precarious directed graphs purely in terms of their graph-theoretic properties. Ungroundedness will be shown to fully characterize the precarious reference graphs and fully characterize the dangerous finite graphs. We prove that an undirected graph has a dangerous orientation if and only if it contains a cycle, providing some support for the traditional idea that cyclic structure is required for paradoxicality. This leaves the task of classifying danger for infinite acyclic reference graphs. We provide some compactness results, which give further necessary conditions on danger in infinite graphs, which in conjunction with a notion of self-containment allows us to prove that dangerous acyclic graphs must have infinitely many vertices with infinite out-degree. But a full characterization of danger remains an open question. In the appendices we relate our results to the results given in Cook (J Symb Log 69(3):767–774, 2004) and Yablo (2006) with respect to more restricted sentences systems, which we call $\mathcal{F}$ -systems. (shrink)

In order to make scientific results relevant to practical decision making, it is often necessary to transfer a result obtained in one set of circumstances—an animal model, a computer simulation, an economic experiment—to another that may differ in relevant respects—for example, to humans, the global climate, or an auction. Such inferences, which we can call extrapolations, are a type of argument by analogy. This essay sketches a new approach to analogical inference that utilizes chain graphs, which resemble directed (...) acyclic graphs (DAGs) except in allowing that nodes may be connected by lines as well as arrows. This chain graph approach generalizes the account of extrapolation I provided in my (2008) book and leads to new insights that integrate the contributions of the other participants of this symposium. More specifically, this approach explicates the role of “fingerprints,” or distinctive markers, as a strategy for avoiding an underdetermination problem having to do with spurious analogies. Moreover, it shows how the extrapolator’s circle, one of the central challenges for extrapolation highlighted in my book, is closely tied to distinctive markers and the Markov condition as it applies to chain graphs. Finally, the approach suggests additional ways in which investigations of a model can provide information about a target that are illustrated by examples concerning nanomaterials in sunscreens and Wendy Parker’s discussion of fingerprints in climate science. (shrink)

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. (shrink)

This paper provides a general introduction to the use of causal models in the metaphysics of causation, specifically structural equation models and directed acyclic graphs. It reviews the formal framework, lays out a method of interpretation capable of representing different underlying metaphysical relations, and describes the use of these models in analyzing causation.

Inheritance diagrams are directed acyclic graphs with two types of connections between nodes: x → y and x ↛ y . Given a diagram D, one can ask the formal question of “is there a valid path between node x and node y?” Depending on the existence of a valid path we can answer the question “x is a y” or “x is not a y”. The answer to the above question is determined through a complex inductive (...) algorithm on paths between arbitrary pairs of points in the graph. This paper aims to simplify and interpret such diagrams and their algorithms. We approach the area on two fronts. Suggest reactive arrows to simplify the algorithms for the winning paths. We give a conceptual analysis of inheritance diagrams, and compare our analysis to the “small” and “big sets” of preferential and related reasoning. In our analysis, we consider nodes as information sources and truth values, direct links as information, and valid paths as information channels and comparisons of truth values. This results in an upward chaining, split validity, off-path preclusion inheritance formalism of a particularly simple type. We show that the small and big sets of preferential reasoning have to be relativized if we want them to conform to inheritance theory, resulting in a more cautious approach, perhaps closer to actual human reasoning. We will also interpret inheritance diagrams as theories of prototypical reasoning, based on two distances: set difference, and information difference. We will see that some of the major distinctions between inheritance formalisms are consequences of deeper and more general problems of treating conflicting information. It is easily seen that inheritance diagrams can also be analysed in terms of reactive diagrams - as can all argumentation systems. AMS Classification: 68T27, 68T30. (shrink)

Mechanistic philosophy of science views a large part of scientific activity as engaged in modelling mechanisms. While science textbooks tend to offer qualitative models of mechanisms, there is increasing demand for models from which one can draw quantitative predictions and explanations. Casini et al. (Theoria 26(1):5–33, 2011) put forward the Recursive Bayesian Networks (RBN) formalism as well suited to this end. The RBN formalism is an extension of the standard Bayesian net formalism, an extension that allows for modelling the hierarchical (...) nature of mechanisms. Like the standard Bayesian net formalism, it models causal relationships using directed acyclic graphs. Given this appeal to acyclicity, causal cycles pose a prima facie problem for the RBN approach. This paper argues that the problem is a significant one given the ubiquity of causal cycles in mechanisms, but that the problem can be solved by combining two sorts of solution strategy in a judicious way. (shrink)

Recent approaches to causal modelling rely upon the causal Markov condition, which specifies which probability distributions are compatible with a directed acyclic graph. Further principles are required in order to choose among the large number of DAGs compatible with a given probability distribution. Here we present a principle that we call frugality. This principle tells one to choose the DAG with the fewest causal arrows. We argue that frugality has several desirable properties compared to the other principles that (...) have been suggested, including the well-known causal faithfulness condition. _1_ Introduction _2_ The Causal Markov Condition _3_ Faithfulness _4_ Frugality _4.1_ Basic independences and frugality _4.2_ General properties of directed acyclic graphs satisfying frugality _4.3_ Connection to minimality assumptions _5_ Frugality as a Parsimony Principle _6_ Conclusion Appendix. (shrink)

The faithfulness condition (FC) is a useful principle for inferring causal structure from statistical data. The usual motivation for the FC appeals to theorems showing that exceptions to it have probability zero, provided that some apparently reasonable assumptions obtain. However, some have objected that, the theorems notwithstanding, exceptions to the FC are probable in commonly occurring circumstances. I argue that exceptions to the FC are probable in the circumstances specified by this objection only given the presence of a condition that (...) I label homogeneity, and furthermore that this condition typically does not obtain in the FC’s intended domain of application. (shrink)

This paper addresses the existence of Hopf bifurcations in a directed acyclic network of neurons, each of them being modeled by a Hindmarsh–Rose neuronal model. The bifurcation parameter is the small parameter corresponding to the ratio of time scales between the fast and the slow dynamics. We first prove that, under certain hypotheses, the single uncoupled neuron can undergo a Hopf bifurcation. Hopf bifurcation occurrences in a directed acyclic network of HR neurons are then discussed. Numerical (...) simulations are carried out to observe these bifurcations and to illustrate the theoretical results. (shrink)

S There is a long tradition of representing causal relationships by directed acyclic graphs (Wright, 1934 ). Spirtes ( 1994), Spirtes et al. ( 1993) and Pearl & Verma ( 1991) describe procedures for inferring the presence or absence of causal arrows in the graph even if there might be unobserved confounding variables, and/or an unknown time order, and that under weak conditions, for certain combinations of directed acyclic graphs and probability distributions, are asymptotically, (...) in sample size, consistent. These results are surprising since they seem to contradict the standard statistical wisdom that consistent estimators of causal effects do not exist for nonrandomised studies if there are potentially unobserved confounding variables. We resolve the apparent incompatibility of these views by closely examining the asymptotic properties of these causal inference procedures. We show that the asymptotically consistent procedures are ‘pointwise consistent’, but ‘uniformly consistent’ tests do not exist. Thus, no finite sample size can ever be guaranteed to approximate the asymptotic results. We also show the nonexistence of valid, consistent confidence intervals for causal effects and the nonexistence of uniformly consistent point estimators. Our results make no assumption about the form of the tests or estimators. In particular, the tests could be classical independence tests, they could be Bayes tests or they could be tests based on scoring methods such as  or . The implications of our results for observational studies are controversial and are discussed briefly in the last section of the paper. The results hinge on the following fact: it is possible to find, for each sample size n, distributions P and Q such that P and Q are empirically indistinguishable and yet P and Q correspond to different causal effects. (shrink)

Molinists hold that there are contingently true counterfactuals about what agents would do if put in specific circumstances, that God knows these prior to creation, and that God uses this knowledge in choosing how to create. In this essay we critique Molinism, arguing that if these theses were true, agents would not be free. Consider Eve’s sinning upon being tempted by a serpent. We argue that if Molinism is true, then there is some set of facts that fully explains both (...) Eve’s action and everything else Eve does that influences that action; and that if this is the case, Eve does not act freely. The first premise of this argument follows from the explanatory relations the Molinist is committed to, and the second premise follows from libertarian intuitions about free will. (shrink)

The exponential growth of social data both in volume and complexity has increasingly exposed many of the shortcomings of the conventional frequentist approach to statistics. The scientific community has called for careful usage of the approach and its inference. Meanwhile, the alternative method, Bayesian statistics, still faces considerable barriers toward a more widespread application. The bayesvl R package is an open program, designed for implementing Bayesian modeling and analysis using the Stan language’s no-U-turn (NUTS) sampler. The package combines the ability (...) to construct Bayesian network models using directed acyclic graphs (DAGs), the Markov chain Monte Carlo (MCMC) simulation technique, and the graphic capability of the ggplot2 package. As a result, it can improve the user experience and intuitive understanding when constructing and analyzing Bayesian network models. A case example is offered to illustrate the usefulness of the package for Big Data analytics and cognitive computing. (shrink)

We propose an efficient algorithm for deciding the reachability between any nodes on XML data represented by connected directed graphs. We develop a technique to reduce the size of the reference table for the reachability test. Using the small table and the standard range labeling method for rooted ordered trees, we show that our algorithm answers almost queries in a constant time preserving the space efficiency and a reasonable preprocessing time.

Time series of macroscopic quantities that are aggregates of microscopic quantities, with unknown one‐many relations between macroscopic and microscopic states, are common in applied sciences, from economics to climate studies. When such time series of macroscopic quantities are claimed to be causal, the causal relations postulated are representable by a directed acyclic graph and associated probability distribution—sometimes called a dynamical Bayes net. Causal interpretations of such series imply claims that hypothetical manipulations of macroscopic variables have unambiguous effects on (...) variables “downstream” in the graph, and such macroscopic variables may be predictably produced or altered even while particular microstates are not. This paper argues that such causal time series of macroscopic aggregates of microscopic processes are the appropriate model for mental causation. (shrink)

There are simple mechanical systems that elude causal representation. We describe one that cannot be represented in a single directed acyclic graph. Our case suggests limitations on the use of causal graphs for causal inference and makes salient the point that causal relations among variables depend upon details of causal setups, including values of variables.

We develop a mathematical and interpretative foundation for the enterprise of decision-theoretic (DT) statistical causality, which is a straightforward way of representing and addressing causal questions. DT reframes causal inference as “assisted decision-making” and aims to understand when, and how, I can make use of external data, typically observational, to help me solve a decision problem by taking advantage of assumed relationships between the data and my problem. The relationships embodied in any representation of a causal problem require deeper justification, (...) which is necessarily context-dependent. Here we clarify the considerations needed to support applications of the DT methodology. Exchangeability considerations are used to structure the required relationships, and a distinction drawn between intention to treat and intervention to treat forms the basis for the enabling condition of “ignorability.” We also show how the DT perspective unifies and sheds light on other popular formalisations of statistical causality, including potential responses and directed acyclic graphs. (shrink)

The introduction of statistical models represented by directed acyclic graphs (DAGs) has proved fruitful in the construction of expert systems, in allowing efficient updating algorithms that take advantage of conditional independence relations (Pearl, 1988, Lauritzen et al. 1993), and in inferring causal structure from conditional independence relations (Spirtes and Glymour, 1991, Spirtes, Glymour and Scheines, 1993, Pearl and Verma, 1991, Cooper, 1992). As a framework for representing the combination of causal and statistical hypotheses, DAG models have shed (...) light on a number of issues in statistics ranging from Simpson’s Paradox to experimental design (Spirtes, Glymour and Scheines, 1993). The relations of DAGs with statistical constraints, and the equivalence and distinguishability properties of DAG models, are now well understood, and their characterization and computation involves three properties connecting graphical structure and probability distributions: (i) a local directed Markov property, (ii) a global directed Markov property, (iii) and factorizations of joint densities according to the structure of a graph (Lauritizen, et al., 1990). (shrink)

independence facts implied by a particular directed acyclic graph; an alternative equivalent rule has been proposed by Lauritzen et al. (1990). Geiger et al. (1990) have shown that d-separation is atomic-complete for independence statements..

My Ph.D. dissertation written under the supervision of Prof. Tomasz Placek at the Institute of Philosophy of the Jagiellonian University in Kraków. In one of its most basic and informal shapes, the principle of the common cause states that any surprising correlation between two factors which are believed not to directly influence one another is due to their common cause. Here we will be concerned with a version od this idea which possesses a purely probabilistic formulation. It was introduced, in (...) the form of a general principle, by Hans Reichenbach in his posthumously published book "The Direction of Time". The central notion of the principle in Reichenbach's formulation, and of the current essay, is that of screening off: two correlated events are screened off by a third event if conditioning on the third event makes them probabilistically independent. Reichenbach's principle marks also the beginning of a new field of philosophy: namely, that of ``probabilistic causality''. For the most part, the current essay can be seen as an effort at checking how far one can go with the purely statistical notions revolving around Reichenbach's idea of common cause. In short, the answer is ``surprisingly far''; in some classes of probability spaces all correlations between ``interesting'' events possess explanations of such sort. However, this fact lends itself to opposing interpretations; more on that in the conclusion. Chapters 6 and 7 contain mathematical results concerning these issues. The screening-off condition requires an equality of a probabilistic nature to hold; chapter 8 is a short discussion of slightly weakened versions of the condition, which hold if the sides of the above mentioned equality differ to a small degree. In chapter 2, after some mathematical preliminaries, we study the various formulations of the principle which might be said to stem from the original idea of Reichenbach. We also examine a few of the most salient counterarguments, which undermine at least some of the formulations. Chapter 3 is of a formal nature, dealing with various probabilistic notions which can be thought of as generalizations of Reichenbach's concept of common cause. The next chapter concerns the relationship between the idea of common causal explanation and the Bell inequalities. In chapter 5 we briefly present the form of Reichenbach's principle which can be found in the field of representing causal structures by means of directed acyclic graphs. (shrink)

We describe anytime search procedures that (1) find disjoint subsets of recorded variables for which the members of each subset are d-separated by a single common unrecorded cause, if such exists; (2) return information about the causal relations among the latent factors so identified. We prove the procedure is point-wise consistent assuming (a) the causal relations can be represented by a directed acyclic graph (DAG) satisfying the Markov Assumption and the Faithfulness Assumption; (b) unrecorded variables are not caused (...) by recorded variables; and (c) dependencies are linear. We compare the procedure with standard approaches over a variety of simulated structures and sample sizes, and illustrate its practical value with brief studies of social science data sets. Finally, we consider generalizations for non-linear systems. Keywords: latent variable models, causality, graphical models.. (shrink)

We define an applicative theory of truth TPTTPT which proves totality exactly for the polynomial time computable functions. TPTTPT has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. (...) Truth induction can be allowed without any constraints. For these reasons the system TPTTPT has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.The proof that the theory TPTTPT is feasible is not easy. It is not possible to apply a standard realisation approach. For this reason we develop a new realisation approach whose realisation functions work on directed acyclic graphs. In this way, we can express and manipulate realisation information more efficiently. (shrink)

In this paper, we compare several cut-free sequent systems for propositional intuitionistic logic Intwith respect to polynomial simulations. Such calculi can be divided into two classes, namely single-succedent calculi (like Gentzen's LJ) and multi-succedent calculi. We show that the latter allow for more compact proofs than the former. Moreover, for some classes of formulae, the same is true if proofs in single-succedent calculi are directed acyclic graphs (dags) instead of trees. Additionally, we investigate the effect of weakening (...) rules on the structure and length of dag proofs.The second topic of this paper is the effect of different embeddings from Int to S4. We select two different embeddings from the literature and show that translated (propositional) intuitionistic formulae have sometimes exponentially shorter minimal proofs in a cut-free Gentzen system for S4than the original formula in a cut-free single-succedent Gentzen system for Int. Moreover, the length and the structure of proofs of translated formulae crucially depend on the chosen embedding. (shrink)

Facial expression recognition plays a significant part in artificial intelligence and computer vision. However, most of facial expression recognition methods have not obtained satisfactory results based on low-level features. The existed methods used in facial expression recognition encountered the major issues of linear inseparability, large computational burden, and data redundancy. To obtain satisfactory results, we propose an innovative deep learning model using the kernel entropy component analysis network and directed acyclic graph support vector machine. We use the KECANet (...) in the feature extraction stage. In the stage of output, binary hashing and blockwise histograms are adopted. We sent the final output features to the DAGSVM classifier for expression recognition. We test the performance of our proposed method on three databases of CK+, JAFFE, and CMU Multi-PIE. According to the experiment results, the proposed method can learn high-level features and provide more recognition information in the stage of training, obtaining a higher recognition rate. (shrink)

Spirtes, Glymour and Scheines [Causation, Prediction, and Search Springer] described a pointwise consistent estimator of the Markov equivalence class of any causal structure that can be represented by a directed acyclic graph for any parametric family with a uniformly consistent test of conditional independence, under the Causal Markov and Causal Faithfulness assumptions. Robins et al. [Biometrika 90 491–515], however, proved that there are no uniformly consistent estimators of Markov equivalence classes of causal structures under those assumptions. Subsequently, Kalisch (...) and B¨uhlmann [J. Mach. Learn. Res. 8 613–636] described a uniformly consistent estimator of the Markov equivalence class of a linear Gaussian causal structure under the Causal Markov and Strong Causal Faithfulness assumptions. However, the Strong Faithfulness assumption may be false with high probability in many domains. We describe a uniformly consistent estimator of both the Markov equivalence class of a linear Gaussian causal structure and the identifiable structural coefficients in the Markov equivalence class under the Causal Markov assumption and the considerably weaker k-Triangle-Faithfulness assumption. (shrink)

Resolution and cut-free LK are the most popular propositional systems used for logical automated reasoning. The question whether or not resolution and cut-free LK have the same efficiency on the system of CNF formulas has been asked and studied since 1960 425–467). It was shown in Cook and Reckhow, J. Symbolic Logic 44 36–50 that tree resolution has super-polynomial speed-up over cut-free LK. Naturally, the current issue is whether or not resolution and cut-free LK expressed as directed acyclic (...) graphs have the same efficiency. In this paper, we introduce a new algorithm to eliminate atomic cuts and show that cut-free LK polynomially simulates resolution when the input formula is expressed as a k-CNF formula. As a corollary, we show that regular resolution does not polynomially simulate cut-free LK . We also show that cut-free LK polynomially simulates regular resolution. (shrink)

Causal reasoning is primarily concerned with what would happen to a system under external interventions. In particular, we are often interested in predicting the probability distribution of some random variables that would result if some other variables were forced to take certain values. One prominent approach to tackling this problem is based on causal Bayesian networks, using directed acyclic graphs as causal diagrams to relate post-intervention probabilities to pre-intervention probabilities that are estimable from observational data. However, such (...) causal diagrams are seldom fully testable given observational data. In consequence, many causal discovery algorithms based on data-mining can only output an equivalence class of causal diagrams. This paper is concerned with causal reasoning given an equivalence class of causal diagrams, represented by a ancestral graph. We present two main results. The first result extends Pearl 's celebrated do-calculus to the context of ancestral graphs. In the second result, we focus on a key component of Pearl's calculus---the property of invariance under interventions, and give stronger graphical conditions for this property than those implied by the first result. The second result also improves the earlier, similar results due to Spirtes et al. (shrink)

I thank Judea Pearl for his discussion of my paper and respond to the points he raises. In particular, his attachment to unaugmented directed acyclic graphs has led to a misapprehension of my own proposals. I also discuss the possibilities for developing a non-manipulative understanding of causality.

Methods for performing complex probabilistic reasoning tasks, often based on masses of different forms of evidence obtained from a variety of different sources, are being sought by, and developed for, persons in many important contexts including law, medical diagnosis, and intelligence analysis. The complexity of these tasks can often be captured and represented by graphical structures now called inference networks. These networks are directed acyclic graphs, consisting of nodes, representing relevant hypotheses, items of evidence, and unobserved variables, (...) and arcs joining some of the nodes, representing dependency relations among them. This chapter describes and comments on two different approaches to inference network construction. In the first approach, a DAG network structure is explicitly constructed as a vehicle for probabilistic analyses. Since the associated computations can be regarded as generalising the use of Bayes' rule, such networks are commonly called Bayesian networks. The second approach stems from the work of the American jurist John H. Wigmore who was the very first person to attempt a systematic study of inference networks. (shrink)

Yarkoni argues that one solution is to abandon quantitative methods for qualitative ones. While we agree that qualitative methods are undervalued, we argue that both are necessary for thoroughgoing psychological research, complementing one another through the use of causal analysis. We illustrate how directed acyclic graphs can bridge qualitative and quantitative methods, thereby fostering understanding between different psychological methodologies.

Bayesian networks are computer programs which represent probabilitistic relationships graphically as directed acyclic graphs, and which can use those graphs to reason probabilistically , often at relatively low computational cost. Almost every expert system in the past tried to support probabilistic reasoning, but because of the computational difficulties they took approximating short-cuts, such as those afforded by MYCIN's certainty factors. That all changed with the publication of Judea Pearl's Probabilistic Reasoning in Intelligent Systems, in 1988, which (...) synthesized a decade of research making accurate graphical probabilistic reasoning computationally achievable.Bayesian network technology is now one of the fastest growing fields of research in artificial intelligence. That it has become a publication industry in its own right is shown by a search on Google scholar :This development, together with a parallel related growth in the use of causal discovery algorithms which automate the learning of Bayesian networks from sample data, has generated considerable interest, and controversy, within the philosophy-of-science community.Three central questions bringing together AI researchers and philosophers of science are: Are Bayesian networks Bayesian? What is the relation between probability and causality? Are the assumptions behind causal discovery of Bayesian networks realistic or fantastical?Jon Williamson, as a philosopher of science with a keen interest in the technology, asks and answers these questions in his new book. Although it is self-contained, his book is not very likely as an introduction to the technology , nor is it optimal even as an introduction to the philosophical problems in interpreting Bayesian networks . Rather Williamson's book is an attempt to move the debate forward by solving the central problems of the …. (shrink)

The Fast Casual Inference (FCI) algorithm searches for features common to observationally equivalent sets of causal directed acyclic graphs. It is correct in the large sample limit with probability one even if there is a possibility of hidden variables and selection bias. In the worst case, the number of conditional independence tests performed by the algorithm grows exponentially with the number of variables in the data set. This affects both the speed of the algorithm and the accuracy (...) of the algorithm on small samples, because tests of independence conditional on large numbers of variables have very low power. In this paper, I prove that the FCI algorithm can be interrupted at any stage and asked for output. The output from the interrupted algorithm is still correct with probability one in the large sample limit, although possibly less informative (in the sense that it answers “Can’t tell” for a larger number of questions) than if the FCI algorithm had been allowed to continue uninterrupted. (shrink)

if and only if for every W in V, W is independent of the set of all its non-descendants conditional on the set of its parents. One natural question that arises with respect to DAGs is when two DAGs are “statistically equivalent”. One interesting sense of “statistical equivalence” is “d-separation equivalence” (explained in more detail below.) In the case of DAGs, d-separation equivalence is also corresponds to a variety of other natural senses of statistical equivalence (such as representing the same (...) set of distributions). Theorems characterizing d-separation equivalence for directed acyclic graphs and that can be used as the basis for polynomial time algorithms for checking d-separation equivalence were provided by Verma and Pearl (1990), and Frydenberg (1990). The question we will examine is how to extend these results to cases where a DAG may have latent (unmeasured) variables or selection bias (i.e. some of the variables in the DAG have been conditioned on.) D-separation equivalence is of interest in part because there are algorithms for constructing DAGs with latent variables and selection bias that are based on observed conditional independence relations. For this class of algorithms, it is impossible to determine which of two d-separation equivalent causal structures generated a given probability distribution, given only the set of conditional independence and dependence relations true of the observed distribution. We will describe a polynomial (in the number of vertices) time algorithm for determining when two DAGs which may have latent variables or selection bias are d-separation equivalent. (shrink)

A primary object of causal reasoning concerns what would happen to a system under certain interventions. Specifically, we are often interested in estimating the probability distribution of some random variables that would result from forcing some other variables to take certain values. The renowned do-calculus gives a set of rules that govern the identification of such post-intervention probabilities in terms of pre-intervention probabilities, assuming available a directed acyclic graph that represents the underlying causal structure. However, a DAG causal (...) structure is seldom fully testable given preintervention, observational data, since many competing DAG structures are equally compatible with the data. In this paper we extend the do-calculus to cover cases where the available causal information is summarized in a so-called partial ancestral graph that represents an equivalence class of DAG structures. The causal assumptions encoded by a PAG are significantly weaker than those encoded by a full-blown DAG causal structure, and are in principle fully testable by observed conditional independence relations. (shrink)

nature of modern data collection and storage techniques, and the increases in the speed and storage capacities of computers. Statistics books from 30 years ago often presented examples with fewer than 10 variables, in domains where some background knowledge was plausible. In contrast, in new domains, such as climate research where satellite data now provide daily quantities of data unthinkable a few decades ago, fMRI brain imaging, and microarray measurements of gene expression, the number of variables can range into the (...) tens of thousands, and there is often limited background knowledge to reduce the space of alternative causal hypotheses. In such domains, non-automated causal discovery techniques appear to be hopeless, while the availability of faster computers with larger memories and disc space allow for the practical implementation of computationally intensive automated search algorithms over large search spaces. Contemporary science is not your grandfather’s science, or Karl Popper’s. Causal inference without experimental controls has long seemed as if it must somehow be capable of being cast as a kind of statistical inference involving estimators with some kind of convergence and accuracy properties under some kind of assumptions. Until recently, the statistical literature said not. While parameter estimation and experimental design for the effective use of data developed throughout the 20th century, as recently as 20 years ago the methodology of causal inference without experimental controls remained relatively primitive. Besides a cessation of hostilities from the majority of the statistical and philosophical communities (which has still only partially happened), several things were needed for theories of causal estimation to appear and to flower: well defined mathematical objects to represent causal relations; well defined connections between aspects of these objects and sample data; and a way to compute those connections. A sequence of studies beginning with Dempster’s work on the factorization of probability distributions [Dempster 1972] and culminating with Kiiveri and Speed’s [Kiiveri & Speed 1982] study of linear structural equation models, provided the first, in the form of directed acyclic graphs, and the second, in the form of the “local” Markov condition.. (shrink)

Through their transcript products genes regulate the rates at which an immense variety of transcripts and subsequent proteins occur. Understanding the mechanisms that determine which genes are expressed, and when they are expressed, is one of the keys to genetic manipulation for many purposes, including the development of new treatments for disease. Viewing each gene in a genome as a distinct variable that is either on or off, or more realistically as a continuous variable, the values of some of these (...) variables influence the values of others through the regulatory proteins they express, including, of course, the possibility that the rate of expression of a gene at one time may, in various circumstances, influence the rate of expression of that same gene at a later time. If we imagine an arrow drawn from each gene expression variable at a given time to a gene variable whose expression it influences a short while after, the result is a network, technically a directed acyclic graph. For example, the DAG in Figure 1 is a representation of a system in which the expression level of gene G1 at time 1 ) causes the expression level of G2, which in turn causes the expression level of G3. The arrows in Figure 1 which do not have a variable at their tails are “error terms” which represent all of the causes of a variable other than the ones explicitly represented in the DAG. The DAG describes more than associations—it describes causal connections among gene expression rates. A shock to a cell—by mutation, heating, chemical treatment, etc. may alter the DAG describing the relations among gene expressions, for example by activating a gene that was otherwise not expressed, producing a cascade of new expression effects. Although “knockout” experiments can reveal some of the underlying causal network of gene expression levels, unless guided by information from other sources, such experiments are limited in how much of the network structure they can reveal, due to the sheer number of possible combinations of experimental manipulations of genes necessary to reveal the complete causal network. Recent developments have made it possible to compare quantitatively the expression of tens of thousands of genes in cells from different sources in a single experiment, and to trace gene expression over time in thousands of genes simultaneously. cDNA microarrays are already producing extensive data, much of it available on the web. Thus there are calls for analytic software that can be applied to microarray and other data to help infer regulatory networks. In this paper we will review current techniques that are available for searching for the causal relations between variables, describe algorithmic and data gathering obstacles to applying these techniques to gene expression levels, and describe the prospects for overcoming these obstacles. (shrink)

A Bayesian network consists of two distinct parts: a directed acyclic graph (DAG or belief-network structure) and a set of parameters for the DAG. The DAG in a Bayesian network can be used to represent both causal hypotheses and sets of probability distributions. Under the causal interpretation, a DAG represents the causal relations in a given population with a set of vertices V when there is an edge from A to B if and only if A is a (...) direct cause of B relative to V. (We adopt the convention that sets of variables are capitalized and boldfaced, and individual variables are capitalized and italicized.) Under the statistical interpretation a DAG G can be taken to represent a set of all distributions all of which share a set of conditional independence relations that are entailed by satisfying a local directed Markov property (defined below). (shrink)

In recent papers we have described a framework for inferring causal structure from relations of statistical independence among a set of measured variables. Using Pearl's notion of the perfect representation of a set of independence relations by a directed acyclic graph we proved..