This paper introduces a class of graphical independence models that is closed under marginalization and conditioning but that contains all DAG independence models. This class of graphs, called maximal ancestral graphs, has two attractive features: there is at most one edge between each pair of vertices; every missing edge corresponds to an independence relation. These features lead to a simple parameterization of the corresponding set of distributions in the Gaussian case.

We present a system for deciding whether a given sentence can be inferred from text. Each sentence is represented as a directed graph (extracted from a dependency parser) in which the nodes represent words or phrases, and the links represent syntactic and semantic relationships. We develop a learned graph matching model to approximate entailment by the amount of the sentence’s semantic content which is contained in the text. We present results on the Recognizing Textual Entailment dataset (Dagan et (...) al., 2005), and show that our approach outperforms Bag- Of-Words and TF-IDF models. (shrink)

This paper presents a Conceptual Graph (CG) framework to the Generation of Referring Expressions (GRE). Employing Conceptual Graphs as the underlying formalism allows a rigorous, semantically rich, approach to GRE. A number of advantages over existing work are discussed. The new framework is also used to revisit existing complexity results in a fully rigorous way, showing that the expressive power of CGs does not increase the theoretical complexity of GRE.

Previous asymptotically correct algorithms for recovering causal structure from sample probabilities have been limited even in sparse graphs to a few variables. We describe an asymptotically correct algorithm whose complexity for fixed graph connectivity increases polynomially in the number of vertices, and may in practice recover sparse graphs with several hundred variables. From..

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)

A general principle for good pedagogic strategy is this: other things equal, make the essential principles of the subject explicit rather than tacit. We think that this principle is routinely violated in conventional instruction in statistics. Even though most of the early history of probability theory has been driven by causal considerations, the terms “cause” and “causation” have practically disappeared from statistics textbooks. Statistics curricula guide students away from the concept of causality, into remembering perhaps the cliche disclaimer “correlation does (...) not mean causation,” but rarely thinking about what correlation does mean. The treatment of causality is a serious handicap to later studies of such topics as experimental design, where often the main goal is to establish (or disprove) causation. Much of the technical vocabulary of the language used in research design textbooks consists in euphemisms for specific causal relations, e.g, “latent variable,” “intervening variable,” “confounding factor,” etc. The multiplicity of terms used to refer to causation results in confusion and, in effect, may hinder understanding of the basic principles of research design. (shrink)

Since then we have been engaged in the development of such results of greater relevance to mathematical practice. In January, 1997 we presented some new results of this kind involving what we call “jump free” classes of finite functions. This Jump Free Theorem is treated in section 2.

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)

Over a decade ago, John Sowa did the AI community the great service of introducing it to the Existential Graphs of Charles Sanders Peirce. EG is a formalism which lends itself well to the kinds of thing that Conceptual Graphs are aimed at. But it is far more; it is a central element in the mathematical, logical, and philosophical thought of Peirce; this thought is fruitful in ways that are seldom evident when we first encounter it. In one of his (...) major works on Existential Graphs, Peirce remarks that. (shrink)

We describe a pattern acquisition algorithm that learns, in an unsupervised fashion, a streamlined representation of linguistic structures from a plain natural-language corpus. This paper addresses the issues of learning structured knowledge from a large-scale natural language data set, and of generalization to unseen text. The implemented algorithm represents sentences as paths on a graph whose vertices are words. Significant patterns, determined by recursive context-sensitive statistical inference, form new vertices. Linguistic constructions are represented by trees composed of significant patterns (...) and their associated equivalence classes. An input module allows the algorithm to be subjected to a standard test of English as a Second Language profi- ciency. The results are encouraging: the model attains a level of performance considered to be “intermediate” for 9th-grade students, despite having been trained on a corpus containing transcribed speech of parents directed to small children. (shrink)

The most widely used attractive logical account of knowledge uses standard epistemic models, i.e., graphs whose edges are indistinguishability relations for agents. In this paper, we discuss more general topological models for a multi-agent epistemic language, whose main uses so far have been in reasoning about space. We show that this more geometrical perspective affords greater powers of distinction in the study of common knowledge, defining new collective agents, and merging information for groups of agents.

1. A particle moves back and forth along a line, increasing in speed. Graph. 2. How many equivalence classes in Galilean spacetime are there for a particle that is at rest? A particle that is moving at a constant speed? Why are the previous two questions trick questions? 3. In Galilean spacetime, there is no such thing as absolute velocity. Is there such a thing as absolute acceleration? If not, why not? If so, describe a spacetime in which there (...) is no notion of absolute acceleration. Hint: to move from Aristotelian spacetime to Galilean spacetime, we got rid of the notion of absolute velocity by counting two graphs as equivalent if they differed by a shear transformation. Perhaps we can get rid of absolute acceleration with an analogous move? 4. Draw a two-dimensional Cartesian grid. Label the axes x and t, and mark a scale on these axes. Make the x axis the horizontal axis, and the t axis the vertical one. Pick two points that are not on the same vertical line. Name them Ann and Bob. Label each point with its x and t coordinates. (shrink)

This paper describes DIVA (Dynamic Imagery for Visual Analogy), a computational model of visual imagery based on the scene graph, a powerful representational structure widely used in computer graphics. Scene graphs make possible the visual display of complex objects, including the motions of individual objects. Our model combines a semantic-network memory system with computational procedures based on scene graphs. The model can account for people’s ability to produce visual images of moving objects, in particular the ability to use dynamic (...) visual analogies that compare two systems of objects in motion. (shrink)

estimated surrogates for biodiversity. Using data setsfrom Quebec and Queensland, zve applied four methods to assess the extent to zvhich environmental surrogates can represent biodiversity components: (1) surrogacy graphs; (2) marginal representation plots; (3) Hamming distance function; and (4) Syj rala statistical test for..

We present an algorithm to infer causal relations between a set of measured variables on the basis of experiments on these variables. The algorithm assumes that the causal relations are linear, but is otherwise completely general: It provides consistent estimates when the true causal structure contains feedback loops and latent variables, while the experiments can involve surgical or ‘soft’ interventions on one or multiple variables at a time. The algorithm is ‘online’ in the sense that it combines the results from (...) any set of available experiments, can incorporate background knowledge and resolves con- flicts that arise from combining results from different experiments. In addition we provide a necessary and sufficient condition that (i) determines when the algorithm can uniquely return the true graph, and (ii) can be used to select the next best experiment until this condition is satisfied. We demonstrate the method by applying it to simulated data and the flow cytometry data of Sachs et al (2005). (shrink)

applied, for instance, to developing a decision support system for the Space Shuttle INogueira et al., 2001] and to graph-theoretic problems arising in..

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..

Numerical simulations of coupled map lattices (CMLs) and other complex model systems show an enormous phenomenological variety that is difficult to classify and understand. It is therefore desirable to establish analytical tools for exploring fundamental features of CMLs, such as their stability properties. Since CMLs can be considered as graphs, we apply methods of spectral graph theory to analyze their stability at locally unstable fixed points for different updating rules, different coupling scenarios, and different types of neighborhoods. Numerical studies (...) are found to be in excellent agreement with our theoretical results. (shrink)

In the last two decades, the World Wide Web has become the universal, and — for many users — main information source. Search engines can efficiently serve daily life information needs due to the enormous redundancy of relevant resources on the web. For educational — and even more so for scientific information needs, the web functions much less efficiently: Scientific publishing is built on a culture of unique reference publications, and moreover abounds with specialized structures, such as technical nomenclature, notational (...) conventions, references, tables, or graphs. Moreover, many of these structures are peculiar to specialized communities determined by nationality, research group membership, or adherence to a special school of thought. To keep the much-lamented “digital divide” from becoming a “cultural divide”, we have to make online material more accessible and adaptable to individual users. In this paper we attack this goal for the field of mathematics where knowledge is abstract, highly structured, and extraordinarily interlinked. Modern, content-based representation formats like OpenMath or content MathML allow us to capture, model, relate, and represent mathematical knowledge objects and thus make them context-aware and machine-adaptable to the respective user contexts. Building on previous work which can make mathematical notations adaptable we employ user modeling techniques to make them adaptive to relieve the reader of configuration tasks. We present a comprehensive framework for adaptive notation management and evaluate it on an implementation integrated in the e-learning platform panta rhei. (shrink)

The integration of reasoning and computation services across system and language boundaries has been mostly treated from an engineering perspective. In this paper we take a foundational point of view. We identify the following form of integration problems: an informal (mathematical; i.e, logically underspecified) specification has multiple concrete formal implementations between which queries and results have to be transported. The integration challenge consists in dealing with the implementation-specific details such as additional constants and properties. We pinpoint their role in safe (...) and unsafe integration schemes and propose a proof-theoretic solution based on modular theory-graphs that include the meta-logical foundations. This also gives a clean conceptual basis for earlier attempts that explain integration via “content/semantic markup”. (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..

We present a novel algorithm for the fast computation of PageRank, a hyperlink-based estimate of the “importance” of Web pages. The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Quadratic Extrapolation, accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method. In Quadratic (...) Extrapolation, we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method. Empirically, we show that using Quadratic Extrapolation speeds up PageRank computation by 50- 300% on a Web graph of 80 million nodes, with minimal overhead. (shrink)

This report details experimental results of using stochastic disambiguation models for parsing sentences from the Redwoods treebank (Oepen et al., 2002). The goals of this paper are two-fold: (i) to report accuracy results on the more highly ambiguous latest version of the treebank, as compared to already published results achieved by the same stochastic models on a previous version of the corpus, and (ii) to present some newly developed models using features from the HPSG signs, as well as the MRS (...) dependency graphs. (shrink)

Method by subtracting off the error along several nonprincipal eigenvectors from the current iterate of the Power Method, making use of known nonprincipal eigenvalues of the Web hyperlink matrix. Empirically, we show that using Power Extrapolation speeds up PageRank computation by 30% on a Web graph of 80 million nodes in realistic scenarios over the standard power method, in a way that is simple to understand and implement.

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)

This paper examines the contemporary philosophical and cognitive relevance of Charles Peirce's diagrammatic logic of existential graphs (EGs), the ‘moving pictures of thought’. The first part brings to the fore some hitherto unknown details about the reception of EGs in the early 1900s that took place amidst the emergence of modern conceptions of symbolic logic. In the second part, philosophical aspects of EGs and their contributions to contemporary logical theory are pointed out, including the relationship between iconic logic and (...) images, the problem of the meaning of logical constants, the cognitive economy of iconic logic, the failure of the Frege–Russell thesis, and the failure of the Language of Thought hypothesis. (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* PCFG parsing can dramatically reduce the time required to find the exact Viterbi parse by conservatively estimating outside Viterbi probabilities. We discuss various estimates and give efficient algorithms for computing them. On Penn treebank sentences, our most detailed estimate reduces the total number of edges processed to less than 3% of that required by exhaustive parsing, and even a simpler estimate which can be pre-computed in under a minute still reduces the work by a factor of 5. The algorithm (...) extends the classic A* graph search procedure to a certain hypergraph associated with parsing. Unlike bestfirst and finite-beam methods for achieving this kind of speed-up, the A* parser is guaranteed to return the most likely parse, not just an approximation. The algorithm is also correct for a wide range of parser control strategies and maintains a worst-case cubic time bound. (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)

It has been shown in Spirtes(1995) that X and Y are d-separated given Z in a directed graph associated with a recursive or non-recursive linear model without correlated errors if and only if the model entails that ρXY.Z = 0. This result cannot be directly applied to a linear model with correlated errors, however, because the standard graphical representation of a linear model with correlated errors is not a directed graph. The main result of this paper is to (...) show how to associate a directed graph with a linear model L with correlated errors, and then use d-separation in the associated directed graph to determine whether L entails that a particular partial correlation is zero. (shrink)

Wilfred Sieg and John Byrnes. K-Graph Machines: Generalizing Turing's Machines and Arguments.

This paper presents our work on textual inference and situates it within the context of the larger goals of machine reading. The textual inference task is to determine if the meaning of one text can be inferred from the meaning of another and from background knowledge. Our system generates semantic graphs as a representation of the meaning of a text. This paper presents new results for aligning pairs of semantic graphs, and proposes the application of natural logic to derive inference (...) decisions from those aligned pairs. We consider this work as first steps toward a system able to demonstrate broad-coverage text understanding and learning abilities. (shrink)

Peter Spirtes. Building Causal Graphs from Statistical Data in the Presence of Latent Variables.

Thomas Richardson and Peter Spirtes. Scoring Ancestral Graph Models.

Wilfried Sieg and John Byrnes. Gödel, Turing, and K-Graph Machines.

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)

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)

Given any finite graph, which transitive graphs approximate it most closely and how fast can we find them? The answer to this question depends on the concept of “closest approximation” involved. In [8,9] a qualitative concept of best approximation is formulated. Roughly, a qualitatively best transitive approximation of a graph is a transitive graph which cannot be “improved” without also going against the original graph. A quantitative concept of best approximation goes back at least to [10]. (...) A quantitatively best transitive approximation is a transitive graph that makes the minimal number of mistakes against the original graph. In other words, the sum of the edges that are removed from and are added to the original graph is minimal. (shrink)

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)

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

I examine the adequacy of the causal graph-structural equations approach to causation for modeling biological mechanisms. I focus in particular on mechanisms with complex dynamics such as the PER biological clock mechanism in Drosophila. I show that a quantitative model of this mechanism that uses coupled differential equations – the well-known Goldbeter model – cannot be adequately represented in the standard causal graph framework, even though this framework does permit causal cycles. The reason is that the model contains (...) dynamical information about the mechanism that concerns causal properties but that does not correspond to variables that could be subject to independent interventions. Thus, a representation of the mechanisms as a causal structural model necessarily suppresses causally relevant information. (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)

Thomas Richardson and Peter Spirtes. Parameterizing and Scoring Mixed Ancestral Graphs.

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

In Recursivity and Contingency, Yuk Hui prompts a rigorous historical and philosophical analysis of today’s algorithmic culture. As evidenced by highspeed AI trading, predictive processing algorithms, elastic graph-bunching biometrics, Hebbian machine learning and thermographic drone warfare, we are privy to an epochal technological transition. As these technologies, stilted on inductive learning, demonstrate, we no longer occupy the moment of the ‘storage-and-retrieval’ static database but are increasingly engaged with technologies that are involved in the ‘manipulable arrangement’ (p204) of the indeterminable. (...) It is, in fact, extricating the indeterminable or the Inhuman and its cosmic anti-capitalist imperative that concerns the core of Hui’s project of technodiversity. (shrink)

Criminal intelligence data poses problems for conventional database technology. It has little structure or homogeneity and queries may involve looking for unknown associations between entities; such open-ended queries cannot be made in current systems. Finally, the data must be presented in an intuitively simple fashion for both investigative and evidential purposes. We discuss a database system which uses a labelled graph as its data model. This approach obviates the need for schema design, allows queries which look for associations (...) between entities to be implemented and provides the basis for a natural visual representation of the data. (shrink)