Judea Pearl

AAAI Conference 2024 Conference Paper

Probabilities of Causation with Nonbinary Treatment and Effect

• Ang Li
• Judea Pearl

Probabilities of causation are proven to be critical in modern decision-making. This paper deals with the problem of estimating the probabilities of causation when treatment and effect are not binary. Pearl defined the binary probabilities of causation, such as the probability of necessity and sufficiency (PNS), the probability of sufficiency (PS), and the probability of necessity (PN). Tian and Pearl then derived sharp bounds for these probabilities of causation using experimental and observational data. In this paper, we define and provide theoretical bounds for all types of probabilities of causation with multivalued treatments and effects. We further discuss examples where our bounds guide practical decisions and use simulation studies to evaluate how informative the bounds are for various data combinations.

AAAI Conference 2024 Conference Paper

Unit Selection with Nonbinary Treatment and Effect

• Ang Li
• Judea Pearl

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior or to evaluate the percentage of such individuals in a given population, for example, selecting individuals who would respond one way if encouraged and a different way if not encouraged. Using a combination of experimental and observational data, Li and Pearl solved the binary unit selection problem (binary treatment and effect) by deriving tight bounds on the "benefit function," which is the payoff/cost associated with selecting an individual with given characteristics. This paper extends the benefit function to the general form such that the treatment and effect are not restricted to binary. We then propose an algorithm to test the identifiability of the nonbinary benefit function and an algorithm to compute the bounds of the nonbinary benefit function using experimental and observational data.

AAAI Conference 2022 Conference Paper

Bounds on Causal Effects and Application to High Dimensional Data

• Ang Li
• Judea Pearl

This paper addresses the problem of estimating causal effects when adjustment variables in the back-door or front-door criterion are partially observed. For such scenarios, we derive bounds on the causal effects by solving two non-linear optimization problems, and demonstrate that the bounds are sufficient. Using this optimization method, we propose a framework for dimensionality reduction that allows one to trade bias for estimation power, and demonstrate its performance using simulation studies.

NeurIPS Conference 2022 Conference Paper

Causal Inference with Non-IID Data using Linear Graphical Models

• Chi Zhang
• Karthika Mohan
• Judea Pearl

Traditional causal inference techniques assume data are independent and identically distributed (IID) and thus ignores interactions among units. However, a unit’s treatment may affect another unit's outcome (interference), a unit’s treatment may be correlated with another unit’s outcome, or a unit’s treatment and outcome may be spuriously correlated through another unit. To capture such nuances, we model the data generating process using causal graphs and conduct a systematic analysis of the bias caused by different types of interactions when computing causal effects. We derive theorems to detect and quantify the interaction bias, and derive conditions under which it is safe to ignore interactions. Put differently, we present conditions under which causal effects can be computed with negligible bias by assuming that samples are IID. Furthermore, we develop a method to eliminate bias in cases where blindly assuming IID is expected to yield a significantly biased estimate. Finally, we test the coverage and performance of our methods through simulations.

IJCAI Conference 2022 Conference Paper

Causes of Effects: Learning Individual Responses from Population Data

• Scott Mueller
• Ang Li
• Judea Pearl

The problem of individualization is crucial in almost every field of science. Identifying causes of specific observed events is likewise essential for accurate decision making as well as explanation. However, such tasks invoke counterfactual relationships, and are therefore indeterminable from population data. For example, the probability of benefiting from a treatment concerns an individual having a favorable outcome if treated and an unfavorable outcome if untreated; it cannot be estimated from experimental data, even when conditioned on fine-grained features, because we cannot test both possibilities for an individual. Tian and Pearl provided bounds on this and other probabilities of causation using a combination of experimental and observational data. Those bounds, though tight, can be narrowed significantly when structural information is available in the form of a causal model. This added information may provide the power to solve central problems, such as explainable AI, legal responsibility, and personalized medicine, all of which demand counterfactual logic. This paper derives, analyzes, and characterizes these new bounds, and illustrates some of their practical applications.

AAAI Conference 2022 Conference Paper

Unit Selection with Causal Diagram

• Ang Li
• Judea Pearl

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior, for example, selecting individuals who would respond one way if encouraged and a different way if not encouraged. Using a combination of experimental and observational data, Li and Pearl derived tight bounds on the “benefit function” - the payoff/cost associated with selecting an individual with given characteristics. This paper shows that these bounds can be narrowed significantly (enough to change decisions) when structural information is available in the form of a causal model. We address the problem of estimating the benefit function using observational and experimental data when specific graphical criteria are assumed to hold.

AAAI Conference 2020 Conference Paper

A Simultaneous Discover-Identify Approach to Causal Inference in Linear Models

• Chi Zhang
• Bryant Chen
• Judea Pearl

Modern causal analysis involves two major tasks, discovery and identification. The first aims to learn a causal structure compatible with the available data, the second leverages that structure to estimate causal effects. Rather than performing the two tasks in tandem, as is usually done in the literature, we propose a symbiotic approach in which the two are performed simultaneously for mutual benefit; information gained through identification helps causal discovery and vice versa. This approach enables the usage of Verma constraints, which remain dormant in constraint-based methods of discovery, and permit us to learn more complete structures, hence identify a larger set of causal effects than previously achievable with standard methods.

ICML Conference 2019 Conference Paper

Sensitivity Analysis of Linear Structural Causal Models

• Carlos Cinelli
• Daniel Kumor
• Bryant Chen
• Judea Pearl
• Elias Bareinboim

Causal inference requires assumptions about the data generating process, many of which are unverifiable from the data. Given that some causal assumptions might be uncertain or disputed, formal methods are needed to quantify how sensitive research conclusions are to violations of those assumptions. Although an extensive literature exists on the topic, most results are limited to specific model structures, while a general-purpose algorithmic framework for sensitivity analysis is still lacking. In this paper, we develop a formal, systematic approach to sensitivity analysis for arbitrary linear Structural Causal Models (SCMs). We start by formalizing sensitivity analysis as a constrained identification problem. We then develop an efficient, graph-based identification algorithm that exploits non-zero constraints on both directed and bidirected edges. This allows researchers to systematically derive sensitivity curves for a target causal quantity with an arbitrary set of path coefficients and error covariances as sensitivity parameters. These results can be used to display the degree to which violations of causal assumptions affect the target quantity of interest, and to judge, on scientific grounds, whether problematic degrees of violations are plausible.

IJCAI Conference 2019 Conference Paper

Unit Selection Based on Counterfactual Logic

• Ang Li
• Judea Pearl

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior, which is defined in counterfactual terms. A typical example is that of selecting individuals who would respond one way if encouraged and a different way if not encouraged. Unlike previous works on this problem, which rely on ad-hoc heuristics, we approach this problem formally, using counterfactual logic, to properly capture the nature of the desired behavior. This formalism enables us to derive an informative selection criterion which integrates experimental and observational data. We demonstrate the superiority of this criterion over A/B-test-based approaches.

IJCAI Conference 2018 Conference Paper

Estimation with Incomplete Data: The Linear Case

• Karthika Mohan
• Felix Thoemmes
• Judea Pearl

Traditional methods for handling incomplete data, including Multiple Imputation and Maximum Likelihood, require that the data be Missing At Random (MAR). In most cases, however, missingness in a variable depends on the underlying value of that variable. In this work, we devise model-based methods to consistently estimate mean, variance and covariance given data that are Missing Not At Random (MNAR). While previous work on MNAR data require variables to be discrete, we extend the analysis to continuous variables drawn from Gaussian distributions. We demonstrate the merits of our techniques by comparing it empirically to state of the art software packages.

ICML Conference 2017 Conference Paper

Counterfactual Data-Fusion for Online Reinforcement Learners

• Andrew Forney
• Judea Pearl
• Elias Bareinboim

The Multi-Armed Bandit problem with Unobserved Confounders (MABUC) considers decision-making settings where unmeasured variables can influence both the agent’s decisions and received rewards (Bareinboim et al. , 2015). Recent findings showed that unobserved confounders (UCs) pose a unique challenge to algorithms based on standard randomization (i. e. , experimental data); if UCs are naively averaged out, these algorithms behave sub-optimally, possibly incurring infinite regret. In this paper, we show how counterfactual-based decision-making circumvents these problems and leads to a coherent fusion of observational and experimental data. We then demonstrate this new strategy in an enhanced Thompson Sampling bandit player, and support our findings’ efficacy with extensive simulations.

IJCAI Conference 2016 Conference Paper

Incorporating Knowledge into Structural Equation Models Using Auxiliary Variables

• Bryant Chen
• Judea Pearl
• Elias Bareinboim

In this paper, we extend graph-based identification methods by allowing background knowledge in the form of non-zero parameter values. Such information could be obtained, for example, from a previously conducted randomized experiment, from substantive understanding of the domain, or even an identification technique. To incorporate such information systematically, we propose the addition of auxiliary variables to the model, which are constructed so that certain paths will be conveniently cancelled. This cancellation allows the auxiliary variables to help conventional methods of identification (e. g. , single-door criterion, instrumental variables, half-trek criterion), as well as model testing (e. g. , d-separation, over-identification). Moreover, by iteratively alternating steps of identification and adding auxiliary variables, we can improve the power of existing identification methods via a bootstrapping approach that does not require external knowledge. We operationalize this method for simple instrumental sets (a generalization of instrumental variables) and show that the resulting method is able to identify at least as many models as the most general identification method for linear systems known to date. We further discuss the application of auxiliary variables to the tasks of model testing and z-identification.

TIST Journal 2016 Journal Article

Preface to the ACM TIST Special Issue on Causal Discovery and Inference

• Kun Zhang
• Jiuyong Li
• Elias Bareinboim
• Bernhard Schölkopf
• Judea Pearl

NeurIPS Conference 2015 Conference Paper

Bandits with Unobserved Confounders: A Causal Approach

• Elias Bareinboim
• Andrew Forney
• Judea Pearl

The Multi-Armed Bandit problem constitutes an archetypal setting for sequential decision-making, permeating multiple domains including engineering, business, and medicine. One of the hallmarks of a bandit setting is the agent's capacity to explore its environment through active intervention, which contrasts with the ability to collect passive data by estimating associational relationships between actions and payouts. The existence of unobserved confounders, namely unmeasured variables affecting both the action and the outcome variables, implies that these two data-collection modes will in general not coincide. In this paper, we show that formalizing this distinction has conceptual and algorithmic implications to the bandit setting. The current generation of bandit algorithms implicitly try to maximize rewards based on estimation of the experimental distribution, which we show is not always the best strategy to pursue. Indeed, to achieve low regret in certain realistic classes of bandit problems (namely, in the face of unobserved confounders), both experimental and observational quantities are required by the rational agent. After this realization, we propose an optimization metric (employing both experimental and observational distributions) that bandit agents should pursue, and illustrate its benefits over traditional algorithms.

UAI Conference 2015 Conference Paper

Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data

• Guy Van den Broeck
• Karthika Mohan
• Arthur Choi
• Adnan Darwiche
• Judea Pearl

We propose a family of efficient algorithms for learning the parameters of a Bayesian network from incomplete data. Our approach is based on recent theoretical analyses of missing data problems, which utilize a graphical representation, called the missingness graph. In the case of MCAR and MAR data, this graph need not be explicit, and yet we can still obtain closedform, asymptotically consistent parameter estimates, without the need for inference. When this missingness graph is explicated (based on background knowledge), even partially, we can obtain even more accurate estimates with less data. Empirically, we illustrate how we can learn the parameters of large networks from large datasets, which are beyond the scope of algorithms like EM (which require inference).

UAI Conference 2015 Conference Paper

Missing Data as a Causal and Probabilistic Problem

• Ilya Shpitser
• Karthika Mohan
• Judea Pearl

Causal inference is often phrased as a missing data problem – for every unit, only the response to observed treatment assignment is known, the response to other treatment assignments is not. In this paper, we extend the converse approach of [7] of representing missing data problems to causal models where only interventions on missingness indicators are allowed. We further use this representation to leverage techniques developed for the problem of identification of causal effects to give a general criterion for cases where a joint distribution containing missing variables can be recovered from data actually observed, given assumptions on missingness mechanisms. This criterion is significantly more general than the commonly used “missing at random” (MAR) criterion, and generalizes past work which also exploits a graphical representation of missingness. In fact, the relationship of our criterion to MAR is not unlike the relationship between the ID algorithm for identification of causal effects [22, 18], and conditional ignorability [13].

NeurIPS Conference 2014 Conference Paper

Graphical Models for Recovering Probabilistic and Causal Queries from Missing Data

• Karthika Mohan
• Judea Pearl

We address the problem of deciding whether a causal or probabilistic query is estimable from data corrupted by missing entries, given a model of missingness process. We extend the results of Mohan et al, 2013 by presenting more general conditions for recovering probabilistic queries of the form P(y|x) and P(y, x) as well as causal queries of the form P(y|do(x)). We show that causal queries may be recoverable even when the factors in their identifying estimands are not recoverable. Specifically, we derive graphical conditions for recovering causal effects of the form P(y|do(x)) when Y and its missingness mechanism are not d-separable. Finally, we apply our results to problems of attrition and characterize the recovery of causal effects from data corrupted by attrition.

AAAI Conference 2014 Conference Paper

Recovering from Selection Bias in Causal and Statistical Inference

• Elias Bareinboim
• Jin Tian
• Judea Pearl

Selection bias is caused by preferential exclusion of units from the samples and represents a major obstacle to valid causal and statistical inferences; it cannot be removed by randomized experiments and can rarely be detected in either experimental or observational studies. In this paper, we provide complete graphical and algorithmic conditions for recovering conditional probabilities from selection biased data. We also provide graphical conditions for recoverability when unbiased data is available over a subset of the variables. Finally, we provide a graphical condition that generalizes the backdoor criterion and serves to recover causal effects when the data is collected under preferential selection.

AAAI Conference 2014 Conference Paper

Testable Implications of Linear Structural Equation Models

• Bryant Chen
• Jin Tian
• Judea Pearl

In causal inference, all methods of model learning rely on testable implications, namely, properties of the joint distribution that are dictated by the model structure. These constraints, if not satisfied in the data, allow us to reject or modify the model. Most common methods of testing a linear structural equation model (SEM) rely on the likelihood ratio or chi-square test which simultaneously tests all of the restrictions implied by the model. Local constraints, on the other hand, offer increased power (Bollen and Pearl 2013; McDonald 2002) and, in the case of failure, provide the modeler with insight for revising the model specification. One strategy of uncovering local constraints in linear SEMs is to search for overidentified path coefficients. While these overidentifying constraints are well known, no method has been given for systematically discovering them. In this paper, we extend the half-trek criterion of (Foygel, Draisma, and Drton 2012) to identify a larger set of structural coefficients and use it to systematically discover overidentifying constraints. Still open is the question of whether our algorithm is complete.

NeurIPS Conference 2014 Conference Paper

Transportability from Multiple Environments with Limited Experiments: Completeness Results

• Elias Bareinboim
• Judea Pearl

This paper addresses the problem of $mz$-transportability, that is, transferring causal knowledge collected in several heterogeneous domains to a target domain in which only passive observations and limited experimental data can be collected. The paper first establishes a necessary and sufficient condition for deciding the feasibility of $mz$-transportability, i. e. , whether causal effects in the target domain are estimable from the information available. It further proves that a previously established algorithm for computing transport formula is in fact complete, that is, failure of the algorithm implies non-existence of a transport formula. Finally, the paper shows that the do-calculus is complete for the $mz$-transportability class.

AAAI Conference 2013 Conference Paper

Causal Transportability with Limited Experiments

• Elias Bareinboim
• Judea Pearl

We address the problem of transferring causal knowledge learned in one environment to another, potentially different environment, when only limited experiments may be conducted at the source. This generalizes the treatment of transportability introduced in [Pearl and Bareinboim, 2011; Bareinboim and Pearl, 2012b], which deals with transferring causal information when any experiment can be conducted at the source. Given that it is not always feasible to conduct certain controlled experiments, we consider the decision problem whether experiments on a selected subset Z of variables together with qualitative assumptions encoded in a diagram may render causal effects in the target environment computable from the available data. This problem, which we call z-transportability, reduces to ordinary transportability when Z is all-inclusive, and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. This paper establishes a necessary and sufficient condition for causal effects in the target domain to be estimable from both the non-experimental information available and the limited experimental information transferred from the source. We further provides a complete algorithm for computing the transport formula, that is, a way of fusing experimental and observational information to synthesize an unbiased estimate of the desired causal relation.

NeurIPS Conference 2013 Conference Paper

Graphical Models for Inference with Missing Data

• Karthika Mohan
• Judea Pearl
• Jin Tian

We address the problem of deciding whether there exists a consistent estimator of a given relation Q, when data are missing not at random. We employ a formal representation called `Missingness Graphs' to explicitly portray the causal mechanisms responsible for missingness and to encode dependencies between these mechanisms and the variables being measured. Using this representation, we define the notion of \textit{recoverability} which ensures that, for a given missingness-graph $G$ and a given query $Q$ an algorithm exists such that in the limit of large samples, it produces an estimate of $Q$ \textit{as if} no data were missing. We further present conditions that the graph should satisfy in order for recoverability to hold and devise algorithms to detect the presence of these conditions.

NeurIPS Conference 2013 Conference Paper

Transportability from Multiple Environments with Limited Experiments

• Elias Bareinboim
• Sanghack Lee
• Vasant Honavar
• Judea Pearl

This paper considers the problem of transferring experimental findings learned from multiple heterogeneous domains to a target environment, in which only limited experiments can be performed. We reduce questions of transportability from multiple domains and with limited scope to symbolic derivations in the do-calculus, thus extending the treatment of transportability from full experiments introduced in Pearl and Bareinboim (2011). We further provide different graphical and algorithmic conditions for computing the transport formula for this setting, that is, a way of fusing the observational and experimental information scattered throughout different domains to synthesize a consistent estimate of the desired effects.

UAI Conference 2012 Conference Paper

Causal Inference by Surrogate Experiments: z-Identifiability

• Elias Bareinboim
• Judea Pearl

We address the problem of estimating the effect of intervening on a set of variables X from experiments on a different set, Z, that is more accessible to manipulation. This problem, which we call z-identifiability, reduces to ordinary identifiability when Z = ∅ and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. We provide a graphical necessary and sufficient condition for zidentifiability for arbitrary sets X, Z, and Y (the outcomes). We further develop a complete algorithm for computing the causal effect of X on Y using information provided by experiments on Z. Finally, we use our results to prove completeness of do-calculus relative to z-identifiability, a result that does not follow from completeness relative to ordinary identifiability.

UAI Conference 2012 Conference Paper

The Do-Calculus Revisited

• Judea Pearl

The do-calculus was developed in 1995 to facilitate the identification of causal effects in non-parametric models. The completeness proofs of [Huang and Valtorta, 2006] and [Shpitser and Pearl, 2006] and the graphical criteria of [Tian and Shpitser, 2010] have laid this identification problem to rest. Recent explorations unveil the usefulness of the do-calculus in three additional areas: mediation analysis [Pearl, 2012], transportability [Pearl and Bareinboim, 2011] and metasynthesis. Meta-synthesis (freshly coined) is the task of fusing empirical results from several diverse studies, conducted on heterogeneous populations and under different conditions, so as to synthesize an estimate of a causal relation in some target environment, potentially different from those under study. The talk surveys these results with emphasis on the challenges posed by meta-synthesis. For background material, see hhttp://bayes.cs.ucla.edu/csl papers.htmli.

AAAI Conference 2012 Conference Paper

Transportability of Causal Effects: Completeness Results

• Elias Bareinboim
• Judea Pearl

AAAI Conference 2011 Conference Paper

Controlling Selection Bias in Causal Inference

• Elias Bareinboim
• Judea Pearl

Selection bias, caused by preferential exclusion of units (or samples) from the data, is a major obstacle to valid causal inferences, for it cannot be removed or even detected by randomized experiments. This paper highlights several graphical and algebraic methods capable of mitigating and sometimes eliminating this bias. These nonparametric methods generalize and improve previously reported results, and identify the type of knowledge that need to be available for reasoning in the presence of selection bias.

YNIMG Journal 2011 Journal Article

Graphical models, potential outcomes and causal inference: Comment on Linquist and Sobel

• Judea Pearl

AAAI Conference 2011 Conference Paper

Transportability of Causal and Statistical Relations: A Formal Approach

• Judea Pearl
• Elias Bareinboim

We address the problem of transferring information learned from experiments to a different environment, in which only passive observations can be collected. We introduce a formal representation called “selection diagrams” for expressing knowledge about differences and commonalities between environments and, using this representation, we derive procedures for deciding whether effects in the target environment can be inferred from experiments conducted elsewhere. When the answer is affirmative, the procedures identify the set of experiments and observations that need be conducted to license the transport. We further discuss how transportability analysis can guide the transfer of knowledge in non-experimental learning to minimize re-measurement cost and improve prediction power.

UAI Conference 2010 Conference Paper

Confounding Equivalence in Causal Inference

• Judea Pearl
• Azaria Paz

The paper provides a simple test for deciding, from a given causal diagram, whether two sets of variables have the same bias-reducing potential under adjustment. The test requires that one of the following two conditions holds: either (1) both sets are admissible (i.e., satisfy the back-door criterion) or (2) the Markov boundaries surrounding the manipulated variable(s) are identical in both sets. Applications to covariate selection and model testing are discussed.

UAI Conference 2010 Conference Paper

On a Class of Bias-Amplifying Variables that Endanger Effect Estimates

• Judea Pearl

This note deals with a class of variables that, if conditioned on, tends to amplify confounding bias in the analysis of causal effects. This class, independently discovered by Bhattacharya and Vogt (2007) and Wooldridge (2009), includes instrumental variables and variables that have greater influence on treatment selection than on the outcome. We offer a simple derivation and an intuitive explanation of this phenomenon and then extend the analysis to non linear models. We show that: 1. the bias-amplifying potential of instrumental variables extends over to nonlinear models, though not as sweepingly as in linear models; 2. in non-linear models, conditioning on instrumental variables may introduce new bias where none existed before; 3. in both linear and non-linear models, instrumental variables have no effect on selection-induced bias.

UAI Conference 2010 Conference Paper

On Measurement Bias in Causal Inference

• Judea Pearl

This paper addresses the problem of measurement errors in causal inference and highlights several algebraic and graphical methods for eliminating systematic bias induced by such errors. In particulars, the paper discusses the control of partially observable confounders in parametric and non parametric models and the computational problem of obtaining biasfree effect estimates in such models.

UAI Conference 2009 Conference Paper

Effects of Treatment on the Treated: Identification and Generalization

• Ilya Shpitser
• Judea Pearl

differently to a reduced dosage x than a randomly selected patient would. Many applications of causal analysis call for assessing, retrospectively, the effect of withholding an action that has in fact been implemented. This counterfactual quantity, sometimes called “effect of treatment on the treated, ” (ETT) have been used to to evaluate educational programs, critic public policies, and justify individual decision making. In this paper we explore the conditions under which ETT can be estimated from (i. e. , identified in) experimental and/or observational studies. We show that, when the action invokes a singleton variable, the conditions for ETT identification have simple characterizations in terms of causal diagrams. We further give a graphical characterization of the conditions under which the effects of multiple treatments on the treated can be identified, as well as ways in which the ETT estimand can be constructed from both interventional and observational distributions. The second problem involves a policy maker considering the termination of an ongoing job-training program, seeking to estimate the anticipated reduction in future earning of those enrolled in the program. This calls for comparing the future earning of the program’s graduates to their hypothetical earning had they not been trained. Again, because those who enroll in the program have special needs and qualities, comparison to the population at large will not be adequate.

JMLR Journal 2008 Journal Article

Complete Identification Methods for the Causal Hierarchy

• Ilya Shpitser
• Judea Pearl

We consider a hierarchy of queries about causal relationships in graphical models, where each level in the hierarchy requires more detailed information than the one below. The hierarchy consists of three levels: associative relationships, derived from a joint distribution over the observable variables; cause-effect relationships, derived from distributions resulting from external interventions; and counterfactuals, derived from distributions that span multiple "parallel worlds" and resulting from simultaneous, possibly conflicting observations and interventions. We completely characterize cases where a given causal query can be computed from information lower in the hierarchy, and provide algorithms that accomplish this computation. Specifically, we show when effects of interventions can be computed from observational studies, and when probabilities of counterfactuals can be computed from experimental studies. We also provide a graphical characterization of those queries which cannot be computed (by any method) from queries at a lower layer of the hierarchy. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

UAI Conference 2007 Conference Paper

What Counterfactuals Can Be Tested

• Ilya Shpitser
• Judea Pearl

Counterfactual statements, e.g., "my headache would be gone had I taken an aspirin" are central to scientific discourse, and are formally interpreted as statements derived from "alternative worlds". However, since they invoke hypothetical states of affairs, often incompatible with what is actually known or observed, testing counterfactuals is fraught with conceptual and practical difficulties. In this paper, we provide a complete characterization of "testable counterfactuals," namely, counterfactual statements whose probabilities can be inferred from physical experiments. We provide complete procedures for discerning whether a given counterfactual is testable and, if so, expressing its probability in terms of experimental data.

UAI Conference 2006 Conference Paper

Graphical Condition for Identification in recursive SEM

• Carlos Brito 0001
• Judea Pearl

The paper concerns the problem of predicting the effect of actions or interventions on a system from a combination of (i) statistical data on a set of observed variables, and (ii) qualitative causal knowledge encoded in the form of a directed acyclic graph (DAG). The DAG represents a set of linear equations called Structural Equations Model (SEM), whose coefficients are parameters representing direct causal effects. Reliable quantitative conclusions can only be obtained from the model if the causal effects are uniquely determined by the data. That is, if there exists a unique parametrization for the model that makes it compatible with the data. If this is the case, the model is called identified. The main result of the paper is a general sufficient condition for identification of recursive SEM models.

UAI Conference 2006 Conference Paper

Identification of Conditional Interventional Distributions

• Ilya Shpitser
• Judea Pearl

The subject of this paper is the elucidation of effects of actions from causal assumptions represented as a directed graph, and statistical knowledge given as a probability distribution. In particular, we are interested in predicting conditional distributions resulting from performing an action on a set of variables and, subsequently, taking measurements of another set. We provide a necessary and sufficient graphical condition for the cases where such distributions can be uniquely computed from the available information, as well as an algorithm which performs this computation whenever the condition holds. Furthermore, we use our results to prove completeness of do-calculus [Pearl, 1995] for the same identification problem.

AIJ Journal 2005 Journal Article

Response to review by Kyburg

• Judea Pearl

UAI Conference 2004 Conference Paper

Robustness of Causal Claims

• Judea Pearl

A causal claim is any assertion that invokes causal relationships between variables, for example that a drug has a certain effect on preventing a disease. Causal claims are established through a combination of data and a set of causal assumptions called a causal model. A claim is robust when it is insensitive to violations of some of the causal assumptions embodied in the model. This paper gives a formal definition of this notion of robustness and establishes a graphical condition for quantifying the degree of robustness of a given causal claim. Algorithms for computing the degree of robustness are also presented.

UAI Conference 2002 Conference Paper

Generalized Instrumental Variables

• Carlos Brito 0001
• Judea Pearl

This paper concerns the assessment of direct causal effects from a combination of: (i) non-experimental data, and (ii) qualitative domain knowledge. Domain knowledge is encoded in the form of a directed acyclic graph (DAG), in which all interactions are assumed linear, and some variables are presumed to be unobserved. We provide a generalization of the well-known method of Instrumental Variables, which allows its application to models with few conditional independeces.

UAI Conference 2002 Conference Paper

On the Testable Implications of Causal Models with Hidden Variables

• Jin Tian 0001
• Judea Pearl

The validity OF a causal model can be tested ONLY IF the model imposes constraints ON the probability distribution that governs the generated data. IN the presence OF unmeasured variables, causal models may impose two types OF constraints : conditional independencies, AS READ through the d - separation criterion, AND functional constraints, FOR which no general criterion IS available.This paper offers a systematic way OF identifying functional constraints AND, thus, facilitates the task OF testing causal models AS well AS inferring such models FROM data.

UAI Conference 2002 Conference Paper

Qualitative MDPs and POMDPs: An Order-Of-Magnitude Approximation

• Blai Bonet
• Judea Pearl

We develop a qualitative theory of Markov Decision Processes (MDPs) and Partially Observable MDPs that can be used to model sequential decision making tasks when only qualitative information is available. Our approach is based upon an order-of-magnitude approximation of both probabilities and utilities, similar to epsilon-semantics. The result is a qualitative theory that has close ties with the standard maximum-expected-utility theory and is amenable to general planning techniques.

UAI Conference 2001 Conference Paper

Causal Discovery from Changes

• Jin Tian 0001
• Judea Pearl

We propose a new method of discovering causal structures, based on the detection of local, spontaneous changes in the underlying data-generating model. We analyze the classes of structures that are equivalent relative to a stream of distributions produced by local changes, and devise algorithms that output graphical representations of these equivalence classes. We present experimental results, using simulated data, and examine the errors associated with detection of changes and recovery of structures.

UAI Conference 2001 Conference Paper

Causes and Explanations: A Structural-Model Approach: Part 1: Causes

• Joseph Y. Halpern
• Judea Pearl

We propose a new definition of actual causes, using structural equations to model counterfactuals.We show that the definitions yield a plausible and elegant account ofcausation that handles well examples which have caused problems forother definitions and resolves major difficulties in the traditionalaccount. In a companion paper, we show how the definition of causality can beused to give an elegant definition of (causal) explanation.

UAI Conference 2001 Conference Paper

Direct and Indirect Effects

• Judea Pearl

The direct effect of one eventon another can be defined and measured byholding constant all intermediate variables between the two.Indirect effects present conceptual andpractical difficulties (in nonlinear models), because they cannot be isolated by holding certain variablesconstant. This paper shows a way of defining any path-specific effectthat does not invoke blocking the remainingpaths.This permits the assessment of a more naturaltype of direct and indirect effects, one thatis applicable in both linear and nonlinear models. The paper establishesconditions under which such assessments can be estimated consistentlyfrom experimental and nonexperimental data,and thus extends path-analytic techniques tononlinear and nonparametric models.

UAI Conference 2000 Conference Paper

Probabilities of Causation: Bounds and Identification

• Jin Tian 0001
• Judea Pearl

This paper deals with the problem of estimating the probability that one event was a cause of another in a given scenario. Using structural-semantical definitions of the probabilities of necessary or sufficient causation (or both), we show how to optimally bound these quantities from data obtained in experimental and observational studies, making minimal assumptions concerning the data-generating process. In particular, we strengthen the results of Pearl (1999) by weakening the data-generation assumptions and deriving theoretically sharp bounds on the probabilities of causation. These results delineate precisely how empirical data can be used both in settling questions of attribution and in solving attribution-related problems of decision making.

IJCAI Conference 1999 Conference Paper

Reasoning with Cause and Effect

• Judea Pearl

This paper summarizes concepts, principles, and tools that were found useful in applications involving causal modeling. 1 The principles are based on structural-model semantics, in which functional (or counterfactual) relationships, representing autonomous physical processes are the fundamental building blocks. The paper presents the formal basis of this semantics, illustrates its application in simple problems and discusses its ramifications to computational and cognitive problems concerning causation.

AIJ Journal 1997 Journal Article

Axioms of causal relevance

• David Galles
• Judea Pearl

This paper develops axioms and formal semantics for statements of the form “X is causally irrelevant to Y in context Z”, which we interpret to mean “Changing X will not affect Y once Z is held constant”. The axiomization of causal irrelevance is contrasted with the axiomization of informational irrelevance, as in “Finding X will not alter our belief in Y, once we know Z”. Two versions of causal irrelevance are analyzed: probabilistic and deterministic. We show that, unless stability is assumed, the probabilistic definition yields a very loose structure that is governed by just two trivial axioms. Under the stability assumption, probabilistic causal irrelevance is isomorphic to path interception in cyclic graphs. Under the deterministic definition, causal irrelevance complies with all of the axioms of path interception in cyclic graphs except transitivity. We compare our formalism to that of Lewis (1973) and offer a graphical method of proving theorems about causal relevance.

AIJ Journal 1997 Journal Article

On the logic of iterated belief revision

• Adnan Darwiche
• Judea Pearl

We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of observations. We remedy this weakness by proposing four additional postulates, which are sound relative to a qualitative version of probabilistic conditioning. Contrary to the AGM framework, the proposed postulates characterize belief revision as a process which may depend on elements of an epistemic state that are not necessarily captured by a belief set. We also show that a simple modification to the AGM framework can allow belief revision to be a function of epistemic states. We establish a model-based representation theorem which characterizes the proposed postulates and constrains, in turn, the way in which entrenchment orderings may be transformed under iterated belief revision.

AIJ Journal 1997 Journal Article

The relevance of relevance

• Devika Subramanian
• Russell Greiner
• Judea Pearl

TARK Conference 1996 Conference Paper

Causation, Action and Counterfactuals

• Judea Pearl

UAI Conference 1996 Conference Paper

Identifying Independencies in Causal Graphs with Feedback

• Judea Pearl
• Rina Dechter

We show that the d -separation criterion constitutes a valid test for conditional independence relationships that are induced by feedback systems involving discrete variables.

AIJ Journal 1996 Journal Article

Qualitative probabilities for default reasoning, belief revision, and causal modeling

• Moisés Goldszmidt
• Judea Pearl

This paper presents a formalism that combines useful properties of both logic and probabilities. Like logic, the formalism admits qualitative sentences and provides symbolic machinery for deriving deductively closed beliefs and, like probability, it permits us to express if-then rules with different levels of firmness and to retract beliefs in response to changing observations. Rules are interpreted as order-of-magnitude approximations of conditional probabilities which impose constraints over the rankings of worlds. Inferences are supported by a unique priority ordering on rules which is syntactically derived from the knowledge base. This ordering accounts for rule interactions, respects specificity considerations and facilitates the construction of coherent states of beliefs. Practical algorithms are developed and analyzed for testing consistency, computing rule ordering, and answering queries. Imprecise observations are incorporated using qualitative versions of Jeffrey's rule and Bayesian updating, with the result that coherent belief revision is embodied naturally and tractably. Finally, causal rules are interpreted as imposing Markovian conditions that further constrain world rankings to reflect the modularity of causal organizations. These constraints are shown to facilitate reasoning about causal projections, explanations, actions and change.

AIJ Journal 1996 Journal Article

Uncovering trees in constraint networks

• Itay Meiri
• Rina Dechter
• Judea Pearl

This paper examines the possibility of removing redundant information from a given knowledge base and restructuring it in the form of a tree to enable efficient problem-solving routines. We offer a novel approach that guarantees removal of all redandancies that hide a tree structure. We develop a polynomial-time algorithm that, given an arbitrary binary constraint network, either extracts (by edge removal) a precise tree representation from the path-consistent version of the network or acknowledges that no such tree can be extracted. In the latter case, a tree is generated that may serve as an approximation to the original network.

AIIM Journal 1995 Journal Article

Causal inference from indirect experiments

• Judea Pearl

An indirect experiment is a study in which randomized control is replaced by randomized encouragement, that is, subjects are encouraged, rather than forced, to receive a given treatment program. The purpose of this paper is to bring to the attention of experimental researchers simple mathematical results that enable us to assess, from indirect experiments, the strength with which causal influences operate among variables of interest. The results reveal that despite the laxity of the encouraging instrument, data from indirect experimentation can yield significant and sometimes accurate information on the impact of a program on the population as a whole, as well as on the particular individuals who participated in the program.

UAI Conference 1995 Conference Paper

Counterfactuals and Policy Analysis in Structural Models

• Alexander Balke
• Judea Pearl

Evaluation of counterfactual queries (e.g., "If A were true, would C have been true?") is important to fault diagnosis, planning, determination of liability, and policy analysis. We present a method of revaluating counterfactuals when the underlying causal model is represented by structural models - a nonlinear generalization of the simultaneous equations models commonly used in econometrics and social sciences. This new method provides a coherent means for evaluating policies involving the control of variables which, prior to enacting the policy were influenced by other variables in the system.

UAI Conference 1995 Conference Paper

Logarithmic-Time Updates and Queries in Probabilistic Networks

• Arthur L. Delcher
• Adam J. Grove
• Simon Kasif
• Judea Pearl

In this paper we propose a dynamic data structure that supports efficient algorithms for updating and querying singly connected Bayesian networks (causal trees and polytrees). In the conventional algorithms, new evidence in absorbed in time O(1) and queries are processed in time O(N), where N is the size of the network. We propose a practical algorithm which, after a preprocessing phase, allows us to answer queries in time O(log N) at the expense of O(logn N) time per evidence absorption. The usefulness of sub-linear processing time manifests itself in applications requiring (near) real-time response over large probabilistic databases.

UAI Conference 1995 Conference Paper

On the Testability of Causal Models With Latent and Instrumental Variables

• Judea Pearl

Certain causal models involving unmeasured variables induce no independence constraints among the observed variables but imply, nevertheless, inequality contraints on the observed distribution. This paper derives a general formula for such instrumental variables, that is, exogenous variables that directly affect some variables but not all. With the help of this formula, it is possible to test whether a model involving instrumental variables may account for the data, or, conversely, whether a given variables can be deemed instrumental.

UAI Conference 1995 Conference Paper

Probabilistic evaluation of sequential plans from causal models with hidden variables

• Judea Pearl
• James M. Robins

The paper concerns the probabilistic evaluation of plans in the presence of unmeasured variables, each plan consisting of several concurrent or sequential actions. We establish a graphical criterion for recognizing when the effects of a given plan can be predicted from passive observations on measured variables only. When the criterion is satisfied, a closed-form expression is provided for the probability that the plan will achieve a specified goal.

UAI Conference 1995 Conference Paper

Testing Identifiability of Causal Effects

• David Galles
• Judea Pearl

This paper concerns the probabilistic evaluation of the effects of actions in the presence of unmeasured variables. We show that the identification of causal effect between a singleton variable X and a set of variables Y can be accomplished systematically, in time polynomial in the number of variables in the graph. When the causal effect is identifiable, a closed-form expression can be obtained for the probability that the action will achieve a specified goal, or a set of goals.

UAI Conference 1994 Conference Paper

A Probabilistic Calculus of Actions

• Judea Pearl

We present a symbolic machinery that admits both probabilistic and causal information about a given domain and produces probabilistic statements about the effect of actions and the impact of observations. The calculus admits two types of conditioning operators: ordinary Bayes conditioning, P(y|X = x), which represents the observation X = x, and causal conditioning, P(y|do(X = x)), read the probability of Y = y conditioned on holding X constant (at x ) by deliberate action. Given a mixture of such observational and causal sentences, together with the topology of the causal graph, the calculus derives new conditional probabilities of both types, thus enabling one to quantify the effects of actions (and policies) from partially specified knowledge bases, such as Bayesian networks in which some conditional probabilities may not be available.

ECAI Conference 1994 Conference Paper

Causation, Action and Counterfactuals

• Judea Pearl

UAI Conference 1994 Conference Paper

Counterfactual Probabilities: Computational Methods, Bounds and Applications

• Alexander Balke
• Judea Pearl

Evaluation of counterfactual queries (e.g., "If A were true, would C have been true?") is important to fault diagnosis, planning, and determination of liability. In this paper we present methods for computing the probabilities of such queries using the formulation proposed in [Balke and Pearl, 1994], where the antecedent of the query is interpreted as an external action that forces the proposition A to be true. When a prior probability is available on the causal mechanisms governing the domain, counterfactual probabilities can be evaluated precisely. However, when causal knowledge is specified as conditional probabilities on the observables, only bounds can computed. This paper develops techniques for evaluating these bounds, and demonstrates their use in two applications: (1) the determination of treatment efficacy from studies in which subjects may choose their own treatment, and (2) the determination of liability in product-safety litigation.

UAI Conference 1994 Conference Paper

On Testing Whether an Embedded Bayesian Network Represents a Probability Model

• Dan Geiger
• Azaria Paz
• Judea Pearl

Testing the validity of probabilistic models containing unmeasured (hidden) variables is shown to be a hard task. We show that the task of testing whether models are structurally incompatible with the data at hand, requires an exponential number of independence evaluations, each of the form: "X is conditionally independent of Y, given Z." In contrast, a linear number of such evaluations is required to test a standard Bayesian network (one per vertex). On the positive side, we show that if a network with hidden variables G has a tree skeleton, checking whether G represents a given probability model P requires the polynomial number of such independence evaluations. Moreover, we provide an algorithm that efficiently constructs a tree-structured Bayesian network (with hidden variables) that represents P if such a network exists, and further recognizes when such a network does not exist.

TARK Conference 1994 Conference Paper

On the Logic of iterated Belief Revision

• Adnan Darwiche
• Judea Pearl

We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of obserwtions. We remedy this weakness by augmenting the AGM system with four additional postulates, which are sound relative to a qualitative version of probabilistic conditioning. Finally, we establish a model-based representation theorem which characterizes the augmented system of postulates and constrains, in turns, the way in which entrenchment orderings may be transformed under iterated belief revisions.

AIJ Journal 1993 Journal Article

Belief networks revisited

• Judea Pearl

UAI Conference 1993 Conference Paper

Deciding Morality of Graphs is NP-complete

• Thomas Verma
• Judea Pearl

In order to find a causal explanation for data presented in the form of covariance and concentration matrices it is necessary to decide if the graph formed by such associations is a projection of a directed acyclic graph (dag). We show that the general problem of deciding whether such a dag exists is NP-complete.

UAI Conference 1993 Conference Paper

From Conditional Oughts to Qualitative Decision Theory

• Judea Pearl

The primary theme of this investigation is a decision theoretic account of conditional ought statements (e.g., "You ought to do A, if C") that rectifies glaring deficiencies in classical deontic logic. The resulting account forms a sound basis for qualitative decision theory, thus providing a framework for qualitative planning under uncertainty. In particular, we show that adding causal relationships (in the form of a single graph) as part of an epistemic state is sufficient to facilitate the analysis of action sequences, their consequences, their interaction with observations, their expected utilities and, hence, the synthesis of plans and strategies under uncertainty.

UAI Conference 1992 Conference Paper

An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

• Thomas Verma
• Judea Pearl

In a previous paper [Pearl and Verma, 1991] we presented an algorithm for extracting causal influences from independence information, where a causal influence was defined as the existence of a directed arc in all minimal causal models consistent with the data. In this paper we address the question of deciding whether there exists a causal model that explains ALL the observed dependencies and independencies. Formally, given a list M of conditional independence statements, it is required to decide whether there exists a directed acyclic graph (dag) D that is perfectly consistent with M, namely, every statement in M, and no other, is reflected via dseparation in D. We present and analyze an effective algorithm that tests for the existence of such a day, and produces one, if it exists.

AIJ Journal 1992 Journal Article

Conditional entailment: Bridging two approaches to default reasoning

• Hector Geffner
• Judea Pearl

In recent years, two conceptually different interpretations of default expressions have been advanced: extensional interpretations, in which defaults are regarded as prescriptions for extending one's set of beliefs, and conditional interpretations, in which defaults are regarded as beliefs whose validity is bound to a particular context. The two interpretations possess virtues and limitations that are practically orthogonal to each other. The conditional interpretations successfully resolve arguments of different “specificity” (e. g. , “penguins don't fly in spite of being birds”) but fail to capture arguments of “irrelevance” (e. g. , concluding “red birds fly” from “birds fly”). The opposite is true for the extensional interpretations. This paper develops a new account of defaults, called conditional entailment, which combines the benefits of the two interpretations. Like prioritized circumscriptions, conditional entailment resolves arguments by enforcing priorities among defaults. However, instead of having to be specified by the user, these priorities are extracted automatically from the knowledge base. Similarly, conditional entailment possesses a sound and complete proof theory, based on interacting arguments and amenable to implementation in conventional ATMSs.

UAI Conference 1992 Conference Paper

Reasoning with Qualitative Probabilities Can Be Tractable

• Moisés Goldszmidt
• Judea Pearl

We recently described a formalism for reasoning with if-then rules that re expressed with different levels of firmness [18]. The formalism interprets these rules as extreme conditional probability statements, specifying orders of magnitude of disbelief, which impose constraints over possible rankings of worlds. It was shown that, once we compute a priority function Z+ on the rules, the degree to which a given query is confirmed or denied can be computed in O(log n`) propositional satisfiability tests, where n is the number of rules in the knowledge base. In this paper, we show that computing Z+ requires O(n2 X log n) satisfiability tests, not an exponential number as was conjectured in [18], which reduces to polynomial complexity in the case of Horn expressions. We also show how reasoning with imprecise observations can be incorporated in our formalism and how the popular notions of belief revision and epistemic entrenchment are embodied naturally and tractably.

AIJ Journal 1992 Journal Article

Structure identification in relational data

• Rina Dechter
• Judea Pearl

This paper presents several investigations into the prospects for identifying meaningful structures in empirical data, namely, structures permitting effective organization of the data to meet requirements of future queries. We propose a general framework whereby the notion of identifiability is given a precise formal definition similar to that of learnability. Using this framework, we then explore if a tractable procedure exists for deciding whether a given relation is decomposable into a constraint network or a CNF theory with desirable topology and, if the answer is positive, identifying the desired decomposition. Finally, we address the problem of expressing a given relation as a Horn theory and, if this is impossible, finding the best k-Horn approximation to the given relation. We show that both problems can be solved in time polynomial in the length of the data.

I&C Journal 1991 Journal Article

Axioms and algorithms for inferences involving probabilistic independence

• Dan Geiger
• Azaria Paz
• Judea Pearl

This paper offers an axiomatic characterization of the probabilistic relation “X is independent of Y (written (X, Y))”, where X and Y are two disjoint sets of variables. Four axioms for (X, Y) are presented and shown to be complete. Based on these axioms, a polynomial membership algorithm is developed to decide whether any given independence statement (X, Y) logically follows from a set Σ of such statements, i. e. , whether (X, Y) holds in every probability distribution that satisfies Σ. The complexity of the algorithm is O(|Σ| · k 2 + |Σ| · n), where |Σ| is the number of given statements, n is the number of variables in Σ ∪ {(X, Y)}, and k is the number of variables in (X, Y).

IJCAI Conference 1991 Conference Paper

Directed Constraint Networks: A Relational Framework for Causal Modeling

• Rina Dechter
• Judea Pearl

AIJ Journal 1991 Journal Article

On the consistency of defeasible databases

• Moisés Goldszmidt
• Judea Pearl

We propose a norm of consistency for a mixed set of defeasible and strict sentences which, guided by a probabilistic interpretation of these sentences, establishes a clear distinction between exceptions, ambiguities and outright contradictions. A notion of entailment is then defined which represents a minimal core of beliefs that must follow from the database if one is committed to avoid inconsistencies. The paper establishes necessary and sufficient conditions for consistency, and provides a simple decision procedure for testing the consistency of a database or whether a given sentence is entailed by the database. It is also shown that if all sentences are of Horn type, consistency and entailment can be tested in polynomial time. Finally, we discuss procedures for reasoning with inconsistent databases and identifying sentences directly responsible for the inconsistency.

AIJ Journal 1991 Journal Article

Temporal constraint networks

• Rina Dechter
• Itay Meiri
• Judea Pearl

This paper extends network-based methods of constraint satisfaction to include continuous variables, thus providing a framework for processing temporal constraints. In this framework, called temporal constraint satisfaction problem (TCSP), variables represent time points and temporal information is represented by a set of unary and binary constraints, each specifying a set of permitted intervals. The unique feature of this framework lies in permitting the processing of metric information, namely, assessments of time differences between events. We present algorithms for performing the following reasoning tasks: finding all feasible times that a given event can occur, finding all possible relationships between two given events, and generating one or more scenarios consistent with the information provided. We distinguish between simple temporal problems (STPs) and general temporal problems, the former admitting at most one interval constraint on any pair of time points. We show that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time. For general TCSPs, we present a decomposition scheme that performs the three reasoning tasks considered, and introduce a variety of techniques for improving its efficiency. We also study the applicability of path consistency algorithms as preprocessing of temporal problems, demonstrate their termination and bound their complexities.

UAI Conference 1990 Conference Paper

Equivalence and synthesis of causal models

• Thomas Verma
• Judea Pearl

Scientists often use directed acyclic graphs (days) to model the qualitative structure of causal theories, allowing the parameters to be estimated from observational data. Two causal models are equivalent if there is no experiment which could distinguish one from the other. A canonical representation for causal models is presented which yields an efficient graphical criterion for deciding equivalence, and provides a theoretical basis for extracting causal structures from empirical data. This representation is then extended to the more general case of an embedded causal model, that is, a dag in which only a subset of the variables are observable. The canonical representation presented here yields an efficient algorithm for determining when two embedded causal models reflect the same dependency information. This algorithm leads to a model theoretic definition of causation in terms of statistical dependencies.

TARK Conference 1990 Conference Paper

System Z: A Natural Ordering of Defaults with Tractable Applications to Nonmonotonic Reasoning

• Judea Pearl

UAI Conference 1989 Conference Paper

d-Separation: From Theorems to Algorithms

• Dan Geiger
• Thomas Verma
• Judea Pearl

An efficient algorithm is developed that identifies all independencies implied by the topology of a Bayesian network. Its correctness and maximality stems from the soundness and completeness of d-separation with respect to probability theory. The algorithm runs in time O ( l E l ) where E is the number of edges in the network.

UAI Conference 1989 Conference Paper

Deciding Consistency of Databases Containing Defeasible and Strict Information

• Moisés Goldszmidt
• Judea Pearl

We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.

AIJ Journal 1989 Journal Article

Tree clustering for constraint networks

• Rina Dechter
• Judea Pearl

The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting search without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.

UAI Conference 1988 Conference Paper

Causal networks: semantics and expressiveness

• Thomas Verma
• Judea Pearl

AIJ Journal 1988 Journal Article

Embracing causality in default reasoning

• Judea Pearl

The purpose of this note is to draw attention to certain aspects of causal reasoning which are pervasive in ordinary discourse yet, based on the author's scan of the literature, have not received due treatment by logical formalisms of common-sense reasoning. In a nutshell, it appears that almost every default rule falls into one of two categories: expectation-evoking or explanation-evoking. The former describes association among events in the outside world (e. g. , fire is typically accompanied by smoke); the latter describes how we reason about the world (e. g. , smoke normally suggests fire). This distinction is consistently recognized by people and serves as a tool for controlling the invocation of new default rules. This note questions the ability of formal systems to reflect common-sense inferences without acknowledging such distinction and outlines a way in which the flow of causation can be summoned within the formal framework of default logic.

UAI Conference 1988 Conference Paper

On the logic of causal models

• Dan Geiger
• Judea Pearl

IJCAI Conference 1987 Conference Paper

An Improved Constraint-Propagation Algorithm for Diagnosis

• Hector Geffner
• Judea Pearl

Diagnosing a system requires the identification of a set of components whose abnormal behavior could explain the faulty sys­ tem behavior. Previously, model-based diagnosis schemes have pro­ ceeded through a cycle of assumptions -* predictions observations assumptions-adjustment, where the basic assumptions entail the proper functioning of those components whose failure is not esta­ blished. Here we propose a scheme in which every component's status is treated as a variable; therefore, predictions covering all pos­ sible behavior of the system can be generated. Remarkably, the algo­ rithm exhibits a drastic reduction in complexity for a large family of system-models. Additionally, the intermediate computations pro­ vide useful guidance for selecting new tests. The proposed scheme may be considered as either an enhancement of the scheme proposed in [de Kleer, 1986] or an adap­ tation of the probabilistic propagation scheme proposed in [Pearl, 1986] for the diagnosis of deterministic systems.

AIJ Journal 1987 Journal Article

Distributed revision of composite beliefs

• Judea Pearl

This paper extends the applications of belief network models to include the revision of belief “commitments, ” i. e. , the categorical acceptance of a subset of hypotheses which, together, constitute the most satisfactory explanation of the evidence at hand. A coherent model of nonmonotonic reasoning is introduced, and distributed algorithms for belief revision are presented. We show that, in singly connected networks, the most satisfactory explanation can be found in linear time by a message-passing algorithm similar to the one used in belief updating. In multiply connected networks, the problem may be exponentially hard but, if the network is sparse, topological considerations can be used to render the interpretation task tractable. In general, finding the most probable combination of hypotheses is no more complex than computing the degree of belief for any individual hypothesis. Applications to circuit and medical diagnosis are illustrated.

AAAI Conference 1987 Conference Paper

Embracing Causality in Formal Reasoning

• Judea Pearl

The purpose of this note is to draw attention to certain aspects of causal reasoning which are pervasive in ordinary discourse yet, based on the author’s scan of the literature, have not received due treatment by logical formalisms of common-sense reasoning. In a nutshell, it appears that almost every default rule falls into one of two categories: expectation-evoking or explanation-evoking. The former describes association among events in the outside world (e.g., Fire is typically accompanied by smoke.); the latter describes how we reason about the world (e.g., Smoke normally suggests fire.). This distinction is consistently recognized by people and serves as a tool for controlling the invocation of new default rules. This note questions the ability of formal systems to reflect common-sense inferences without acknowledging such distinction and outlines a way in which the flow of causation can be summoned within the formal framework of default logic.

AIJ Journal 1987 Journal Article

Evidential reasoning using stochastic simulation of causal models

• Judea Pearl

Stochastic simulation is a method of computing probabilities by recording the fraction of time that events occur in a random series of scenarios generated from some causal model. This paper presents an efficient, concurrent method of conducting the simulation which guarantees that all generated scenarios will be consistent with the observed data. It is shown that the simulation can be performed by purely local computations, involving products of parameters given with the initial specification of the model. Thus, the method proposed renders stochastic simulation a powerful technique of coherent inferencing, especially suited for tasks involving complex, nondecomposable models where “ballpark” estimates of probabilities will suffice.

ECAI Conference 1987 Conference Paper

Graphoids: Graph-Based Logic for Reasoning about Relevance Relations or When would x tell you more about y if you already know z?

• Judea Pearl
• Azaria Paz

AIJ Journal 1987 Journal Article

Network-based heuristics for constraint-satisfaction problems

• Rina Dechter
• Judea Pearl

Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i. e. , the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

UAI Conference 1987 Conference Paper

Structuring Causal Tree Models with Continuous Variables

• Lei Xu 0001
• Judea Pearl

This paper considers the problem of invoking auxiliary, unobservable variables to facilitate the structuring of causal tree models for a given set of continuous variables. Paralleling the treatment of bi-valued variables in [Pearl 1986], we show that if a collection of coupled variables are governed by a joint normal distribution and a tree-structured representation exists, then both the topology and all internal relationships of the tree can be uncovered by observing pairwise dependencies among the observed variables (i.e., the leaves of the tree). Furthermore, the conditions for normally distributed variables are less restrictive than those governing bi-valued variables. The result extends the applications of causal tree models which were found useful in evidential reasoning tasks.

AAAI Conference 1987 Conference Paper

The Logic of Representing Dependencies by Directed Graphs

• Judea Pearl

Data-dependencies of the type "x can tell us more about y given that we already know z" can be represented in various formalisms: Probabilistic Dependencies, Embedded-Multi-Valued Dependencies, Undirected Graphs and Directed-Acyclic Graphs (DAGs). This paper provides an axiomatic basis, called a semi-graphoid which captures the structure common to all four types of dependencies and explores the expressive power of DAGs in representing various types of data dependencies. It is shown that DAGs can represent a richer set of dependencies than undirected graphs, that DAGs completely represent the closure of their specification bases, and that they offer an effective computational device for testing membership in that closure as well as inferring new dependencies from given inputs. These properties might explain the prevailing use of DAGs in causal reasoning and semantic nets.

UAI Conference 1987 Conference Paper

The Recovery of Causal Poly-Trees from Statistical Data

• George Rebane
• Judea Pearl

Poly-trees are singly connected causal networks in which variables may arise from multiple causes. This paper develops a method of recovering poly-trees from empirically measured probability distributions of pairs of variables. The method guarantees that, if the measured distributions are generated by a causal process structured as a poly-tree then the topological structure of such tree cam be recovered precisely and, in addition, the causal directionality of the branches can be determined up to the maximum extent possible. The method also pinpoints the minimum (if any) external semantics required to determine the causal relationships among the variables considered.

UAI Conference 1986 Conference Paper

Distributedrevision of belief commitment in composite explanations

• Judea Pearl

AIJ Journal 1986 Journal Article

Fusion, propagation, and structuring in belief networks

• Judea Pearl

Belief networks are directed acyclic graphs in which the nodes represent propositions (or variables), the arcs signify direct dependencies between the linked propositions, and the strengths of these dependencies are quantified by conditional probabilities. A network of this sort can be used to represent the generic knowledge of a domain expert, and it turns into a computational architecture if the links are used not merely for storing factual knowledge but also for directing and activating the data flow in the computations which manipulate this knowledge. The first part of the paper deals with the task of fusing and propagating the impacts of new information through the networks in such a way that, when equilibrium is reached, each proposition will be assigned a measure of belief consistent with the axioms of probability theory. It is shown that if the network is singly connected (e. g. tree-structured), then probabilities can be updated by local propagation in an isomorphic network of parallel and autonomous processors and that the impact of new information can be imparted to all propositions in time proportional to the longest path in the network. The second part of the paper deals with the problem of finding a tree-structured representation for a collection of probabilistically coupled propositions using auxiliary (dummy) variables, colloquially called “hidden causes. ” It is shown that if such a tree-structured representation exists, then it is possible to uniquely uncover the topology of the tree by observing pairwise dependencies among the available propositions (i. e. , the leaves of the tree). The entire tree structure, including the strengths of all internal relationships, can be reconstructed in time proportional to n log n, where n is the number of leaves.

AIJ Journal 1986 Journal Article

On evidential reasoning in a hierarchy of hypotheses

• Judea Pearl

AAAI Conference 1986 Conference Paper

On the Logic of Probabilistic Dependencies

• Judea Pearl

This paper uncovers the axiomatic basis for the probabilistic relation "x is independent of y, given z" and offers it as a formal definition of informational dependency. Given an initial set of such independence relationships, the axioms established permits us to infer new independencies by non-numeric, logical manipulations. Additionally, the paper legitimizes the use of inference networks to represent probabilistic dependencies by establishing a clear correspondence between the two relational structures. Given an arbitrary probabilistic model, P, we demonstrate a construction of a unique edge-minimum graph G such that each time we observe a vertex x separated from y by a subset S of vertices, we can be guaranteed that variables x and y are independent in P, given the values of the variables in S.

UAI Conference 1985 Conference Paper

A Constraint-Propagation Approach to Probabilistic Reasoning

• Judea Pearl

The paper demonstrates that strict adherence to probability theory does not preclude the use of concurrent, self-activated constraint-propagation mechanisms for managing uncertainty. Maintaining local records of sources-of-belief allows both predictive and diagnostic inferences to be activated simultaneously and propagate harmoniously towards a stable equilibrium.

IJCAI Conference 1985 Conference Paper

Learning Hidden Causes from Empirical Data

• Judea Pearl

IJCAI Conference 1985 Conference Paper

The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation

• Rina Dechter
• Judea Pearl

IJCAI Conference 1983 Conference Paper

A Computational Model for Causal and Diagnostic Reasoning in Inference Systems

• Jin H. Kim
• Judea Pearl

AIJ Journal 1983 Journal Article

A minimax algorithm better than alpha-beta? Yes and No

• Igor Roizen
• Judea Pearl

This paper contains a probabilistic analysis of the performance of the game-searching SSS * algorithm which has been shown to be superior to α-β. Necessary and sufficient conditions for node expansion are established, and an expression for the average number of nodes expanded is derived. The branching factor of SSS * is shown to coincide with that of α-β, thus rendering the two algorithms asymptotically equivalent. Numerical comparison of the expected complexities of the two algorithms is finally carried out over a wide spectrum of search depths and branching degrees. The latter shows that the savings in the number of positions evaluated by SSS * relative to that of α-β is rather limited and is not enough to offset the increase in other computational resources.

AIJ Journal 1983 Journal Article

Knowledge versus search

• Judea Pearl

This paper analyzes the average number of nodes expanded by A∗ as a function of the accuracy of its heuristic estimates, by treating the errors h∗ - h as random variables whose distribution may vary over the nodes in the graph. The search model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root. The main result states that if the typical error grows like φ(h∗) then the mean complexity of A∗ grows approximately like G(N)exp[cφ(N)], where c is a positive constant and G(N) is O(N2). Thus, a necessary and sufficient condition for maintaining polynomial search complexity is that A∗ be guided by heuristics with logarithmic precision, e. g. φ(N) = (log N) k. A∗ is shown to make much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.

AIJ Journal 1983 Journal Article

On the nature of pathology in game searching

• Judea Pearl

Game-playing programs usually process the estimates attached to game positions through repeated minimax operations, as if these were true terminal payoffs. This process introduces a spurious noise which degrades the quality of the decisions and, in the extreme case, may cause a pathological phenomenon: the deeper we search the worse we play. Using a probabilistic game model, this paper examines the nature of this distortion, quantifies its magnitude, determines the conditions when its damage is curtailed and explains why search-depth pathology (the extreme manifestation of minimax distortion) is rarely observed in common games.

AIJ Journal 1983 Journal Article

Preface

• Judea Pearl

AIJ Journal 1983 Journal Article

Searching for an optimal path in a tree with random costs

• Richard M. Karp
• Judea Pearl

We consider the problem of finding an optimal path leading from the root of a tree to any of its leaves. The tree is known to be uniform, binary, and of height N, and each branch independently may have a cost of 1 or 0 with probability p and 1−p, respectively. We show that for p<1/2 the uniform cost algorithm can find a cheapest path in linear expected time. By contrast, when p>1/2, every algorithm which guarantees finding an exact cheapest path, or even a path within a fixed cost ratio of the cheapest, must run in exponential average time. If, however, we are willing to accept a near optimal solution almost always, then a pruning algorithm exists which finds such a solution in linear expected time. The algorithm employs a depth-first strategy which stops at regular intervals to appraise its progress and, if the progress does not meet a criterion based on domain-specific knowledge, the current node is irrevocably pruned.

AAAI Conference 1982 Conference Paper

Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach

• Judea Pearl

This paper presents generalizations of Bayes likelihood-ratio updating rule which facilitate an asynchronous propagation of the impacts of new beliefs and/or new evidence in hierarchically organized inference structures with multi-hypotheses variables. The computational scheme proposed specifies a set of belief parameters, communication messages and updating rules which guarantee that the diffusion of updated beliefs is accomplished in a single pass and complies with the tenets of Bayes calculus.

ECAI Conference 1982 Conference Paper

The Utility of Precision in Search Heuristics

• Judea Pearl

MFCS Conference 1980 Conference Paper

Asymptotic Complexity of Game-Searching Procedures

• Judea Pearl

AIJ Journal 1980 Journal Article

Asymptotic properties of minimax trees and game-searching procedures

• Judea Pearl

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods. If the terminal positions are assigned a WIN-LOSS status with the probabilities P 0 and 1 − P 0, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P 0 is higher or lower than some fixed-point probability P∗(d). When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value v∗, which is the (1 − P∗)-fractile of the terminal distribution. Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, O[(d) h 2 ] terminal positions if positions if P0 ≠ P∗ and O[( P∗ (1 − P∗) )h] positions if P0 = P∗, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of O[( P∗ (1 − P∗) )h] positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of O[(d) h 2 ] terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.

AIJ Journal 1980 Journal Article

Probabilistic analysis of the complexity of A∗

• Nam Huyn
• Rina Dechter
• Judea Pearl

This paper analyzes the number of nodes expanded by A∗ as a function of the accuracy of its heuristic estimates by treating the errors h∗ - h as random variables whose distributions may vary over the nodes in the graph. Our model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root. Two results are established: 1. (1) for any error distribution, if A∗1 is stochastically more informed than A∗2, then A∗1 is stochastically more efficient than A∗2, and 2. (2) if the probability that the relative error be bounded away from zero is greater than 1/m, then the average complexity of A∗ is exponential with N, where as if the probability of zero error is greater than 1–1/m, the average complexity is O(N).

AAAI Conference 1980 Conference Paper

SCOUT: A Simple Game-Searching Algorithm with Proven Optimal Properties

• Judea Pearl