Heckerthoughts

Let’s put aside the notion of probability for the moment. Rather, let’s focus on the important and frequent need to express one’s uncertainty about the truth of some proposition or, equivalently, the occurrence of some event. For example, I’m fairly sure that I don’t have COVID right now, but I am not certain. How do I tell you just how certain I am? Also, note that I am talking about my uncertainty, not anyone else’s. Uncertainty is subjective. What properties do we want this form of communication to have?

Now let’s think about $b(xyz)$, the degree of belief that three propositions $x$, $y$, and $z$ are true. One way to do this is to decompose $b(xyz)$ in terms of $b(x|yz)$ and $b(yz)$, and then decompose the latter belief in terms of $b(y|z)$ and $b(z)$:

$$b(xyz)=g(b(x|yz),b(yz))=g(b(x|yz),g(b(y|z),b(z))).$$

Another way to do this is to decompose $b(xyz)$ in terms of $b(xy|z)$ and $b(z)$, and then decompose $b(xy|z)$ in terms of $b(x|yz)$ and $b(y|z)$:

$$b(xyz)=g(b(xy|z),b(z))=g(g(b(x|yz),b(y|z)),b(z)).$$

It follows that $g$ is associative:

$$g(b(x|yz),g(b(y|z),b(z)))=g(g(b(x|yz),b(y|z)),b(z)).$$

(1)

Remarkably, it turns out that, if you accept Properties 1 through 3, a degree of belief must satisfy the following rules:

$$b(xy)=b(x|y)\cdot b(y),$$

$$b(\bar{x})=1-b(x).$$

where $b({\rm true})=1$ and $b({\rm false})=0$. These rules are precisely those of probability! Namely,

$$p(xy)=p(x|y)\cdot p(y),\ \ {\rm product\ rule},$$

(2)

$$p(\bar{x})=1-p(x),\ \ {\rm sum\ rule}.$$

(3)

Cox [19] was the first to prove that properties 1 through 3 imply that a degree of belief must satisfy the rules of probability, although he used a slightly stronger technical assumptions for the functions $g$ and $h$. The results here, which assume only continuity and monotonicity, are based on work by Aczel [1], who uses a set of mathematical tools known as functional equations to show that functions satisfying simple properties must have particular forms. Notable is his “Associativity Equation,” where he shows that any continuous, monotonic increasing, and associative function is isomorphic to the addition of numbers (see pages 256-267). This is a remarkable result, as it says that any such function can be implemented on a slide rule. It is a key step in proving the inevitability of probability from Equation 1 and the other properties.

Given these results, the term “probability” gets confusing quickly. Namely, a probability can be a long-run fraction in repeated experiments or a degree of belief, but obey the same syntactic rules. It’s tempting to call them both probabilities, but doing so obscures their very different semantics. To avoid this confusion, when the semantics are unclear from the text, I will refer to degrees of belief as Bayesian or subjective probabilities, and will refer to long-run fractions in repeated experiments as frequentist probabilities. I’ll use $b(\cdot)$, $f(\cdot)$, and $p(\cdot)$, to refer to a degree of belief, frequentist probability, or one of the two, respectively.

One pet peeve of mine is that Bayesian thinking—using the rules of probability to govern degrees of belief—is often confused with Bayes rule, which follows directly from the syntactic product rule of probability (Equation 2). That is, Bayes rule can be applied equally well to Bayesian or frequentist probabilities. In this manuscript, I’ll try to eliminate this confusion by avoiding use of the phrase “Bayes rule” and instead refer to “the rules of probability” or sometimes more precisely “the product rule of probability.”

Thomas Bayes was possibly the first person known to apply the syntactic rules of probability to the semantics of degree of belief [6]. (I say “possibly,” because historical scholars disagree on this point.) Laplace definitively made this observation [55]. Note that Laplace and perhaps Bayes said only that the rules of probability could be applied to degrees of belief. They did not realize that, given Properties 1 through 3, this application was necessary.

One very practical problem is how to put a number on a degree of belief. A simple approach is based on the observation that people find it fairly easy to say that two propositions are equally likely. The approach is as follows. Imagine a simplified wheel of fortune having only two regions (shaded and not shaded), such as the one illustrated in Figure 2. Assuming everything about the wheel is symmetric (except for shading), the degree of belief that the wheel will stop in the shaded region is the fractional area of the wheel that is shaded (in this case, 0.3). (Of course, given that degrees of belief are subjective, a person is not forced to make this judgment about symmetry.) This wheel now provides a reference for measuring your degrees of belief for other events. For example, what is my probability that I currently have COVID? First, I ask myself the question: Is it more likely that I have COVID or that the wheel when spun will stop in the shaded region? If I think that it is more likely that I have COVID, then I imagine another wheel where the shaded region is larger. If I think that it is more likely that the wheel will stop in the shaded region, then I imagine another wheel where the shaded region is smaller. Now I repeat this process until I think that having COVID and the wheel stopping in the shaded region are about equally likely. At this point, my degree of belief that you have COVID is the percent area of the shaded area on the wheel.

In general, the process of measuring a degree of belief is commonly referred to as a belief assessment. The technique for assessment that I have just described is one of many available techniques discussed in the Management Science, Operations Research, and Psychology literature. One problem with belief assessment that is addressed in this literature is that of precision. Can someone really say that their degree of belief is $0.601$ and not $0.599$? In most cases, no. Nonetheless, in most cases, degrees of belief are used to make decisions (I’ll say a lot more about this in Section 3) and these decisions are typically not sensitive to small variations in assessments. Well-established practices of sensitivity analysis help one to know when additional precision is unnecessary (e.g., [47]). Alternatively, a person can reason with upper and lower bounds on degrees of belief [31]. Another problem with probability assessment is that of accuracy. For example, recent experiences or the way a question is phrased can lead to assessments that do not reflect a person’s true beliefs [78]. Methods for improving accuracy can be found in the decision-analysis literature (e.g., [74]).

Finally, let’s consider frequentist probabilities and how they are related to degrees of belief. As we’ve just seen, a similarity is that both semantics are governed by the rules of probability. And, of course, there are differences. For example, assessing a degree of belief does not require repeated trials, whereas estimating a frequentist probability does. Consider an old-fashioned thumbtack—one with a round, flat head (Figure 3). If the thumbtack is thrown up in the air, it will come to rest either on its point and an edge of the head (heads) or lying on its head with point up (tails). In the Bayesian framework, a person can look at the thumbtack and assess their degree of belief that it will land heads on a toss. In the frequentist approach, we assert that there is some unknown frequentist probability of heads, $f$(heads), such that the thumbtack will land heads on any toss with the same degree of belief. (Getting heads is said to be independent and identically distributed.) The connection? This degree of belief must be equal to $f$(heads).

It turns out that the Bayesian and frequentist frameworks are fully compatible. If a person’s beliefs about a series of flips of arbitrary length has the property that any two sequences of the same length and the same number of heads and tails are judged to be equally likely, then the degrees of belief assigned to those outcomes are the same as the degrees of belief assigned to the outcomes in a situation where there exists an unknown frequentist probability that is equal to the degree of belief of heads on every flip. This result was first proven by de Finetti and generalizations of it followed [45]. In short, the frequentist framework can exist within the Bayesian framework. Ironically, despite this compatibility, Bayesians and frequentists—people who work exclusively within the Bayesian and frequentist frameworks, respectively—have been at odds with each other for many decades. The good news is that there is no need to choose—we can embrace both. And the battles seem to be subsiding.

In the AI community, before 1985, a common argument made against the use of probability to reason about uncertainty was that general probabilistic inference was computationally intractable [73, 11]. For example, the number of combinations of $N$ binary variables is $2^{N}$, and no human could assess that many degrees of belief or reason about them when $N$ is more than a dozen or so. The only alternative, it was argued, was to make incorrect assumptions of conditional independence. For example, when building an expert system to diagnose medical diseases, the builder could make the incorrect assumption that all symptoms are mutually independent given the true disease—the so called, “naive Bayes assumption.”

What the community missed was the fact that there were representations of conditional independence that were ideal for the task of representing uncertainty. They were graphical and hence easy to read and write and would accommodate assertions of conditional independence that were tailored to the task at hand.

In this manuscript, I will focus on the most used probabilistic graphical model, the directed acyclic graphical model, or DAG model. The model was first described by Sewell Wright in 1921 [83] and advanced by many researchers including I.J. Good [31].

To better understand DAG models, we should now move beyond the simple notion of a proposition to talk about a variable—a collection of mutually exclusive and exhaustive values (sometimes called “states”). I will typically denote a variable by an upper-case, potentially indexed letter (e.g., $X,Y,X_{i}$, and a value of a corresponding variable by that same letter in lower case (e.g., $x,y,x_{i}$). To denote a set of variables, I will use a bold-face upper-case letter (e.g., ${\bf X},{\bf Y},{\bf X}_{i}$), and will use a corresponding bold-face lower-case letter (e.g., ${\bf x},{\bf y},{\bf x}_{i}$) to denote a value for each variable in a given set. When showing specific examples, I will sometimes give variables understandable names and denote them in typewriter font—for example, Age. To denote a probability distribution over $X$, where $X$ has a finite number of values, I will use $p(x)$. In addition, I will use this same term to denote a probability for a value of $X$. Whether the mention is a distribution or a single probability should be clear from context. Similarly, if $X$ is a continuous variable, then I will use $p(x)$ to refer to $X$’s probability density function or the density at a given point.

DAG models can represent either Bayesian or frequentist probabilities. So, to start, let’s talk about them generically. Suppose we have a problem domain consisting of a set of variables ${\bf X}=\{X_{1},\ldots,X_{n}\}$. A DAG model for ${\bf X}$ consists of (1) a DAG structure that encodes a set of conditional independence assertions about variables in ${\bf X}$, and (2) a set of local probability distributions, one associated with each variable. Together, these components define a probability distribution for ${\bf X}$, sometimes called a joint probability distribution. The nodes in the graph are in one-to-one correspondence with the variables ${\bf X}$. I use $X_{i}$ to denote both the variable and its corresponding node, and ${\bf Pa}_{i}$ to denote the parents of node $X_{i}$ in the graph as well as the variables corresponding to those parents. The lack of possible arcs in the graph encode conditional independencies. To understand these independencies, let’s fix the ordering of nodes in the graph to be $X_{1},\ldots,X_{n}$. This ordering is not necessary, but it keeps things simple. Because the graph is acyclic, it is possible to describe the parents of $X_{i}$ as a subset of the nodes $X_{1},\ldots,X_{i-1}$. Given this description, the graph states the following conditional independencies:

$$p(X_{i}|X_{1},\ldots,X_{i-1})=p(X_{i}|{\bf Pa}_{i}).$$

(4)

Note that other conditional independencies can be derived from these assertions. Now, from (a generalization of) the product rule of probability, we can write

$$p({\bf X})=\prod_{i=1}^{n}p(X_{i}|X_{1},\ldots,X_{i-1}).$$

(5)

Combining Equations 4 and 5, we obtain

$$p({\bf X})=\prod_{i=1}^{n}p(X_{i}|{\bf Pa}_{i}).$$

(6)

Consequently, the conditional independencies implied by the graph combined with the local probability distributions $p(X_{i}|{\bf Pa}_{i}),i=1,\ldots,N$, determine the joint probability distribution for ${\bf X}$.

One other note about the acyclicity of these graphs: Such acyclicity has been criticized due to its lack of applicability in many situations, such as when there is bi-directional cause and effect. That said, if a model is built that includes the representation of time, where the observation of a quantity over time is represented with multiple variables, then most criticism disappears. Also, notably, Sewall Wright and others have considered atemporal graph models with cycles.

In Section 4, we will see how DAG models can be constructed for frequentist probabilities. Here, let’s return to the state of AI in the 1980s and consider how to create a DAG model for degrees of belief. Such models became known as Bayesian networks. After that, we’ll look at how these models can make reasoning with uncertainty computationally efficient.

To be concrete, let us build a simple Bayesian network for the task of detecting credit-card fraud. (Of course, in practice, there is an individual, typically an expert, who provides the knowledge that goes into the Bayesian network. Here, I’ll simply use “us” and “we”.) We begin by determining the variables to include in the model. One possible choice of variables for our problem is whether or not there is fraud (Fraud or $F$), whether or not there was a gas purchase in the last 24 hours (Gas or $G$), whether or not there was a jewelry purchase in the last hour (Jewelry or $J$), the age of the cardholder (Age or $A$), and the sex (at birth) of the cardholder (Sex or $S$). The values of these variables are shown in Figure 4.

This initial task is not always straightforward. As part of this task we should (1) correctly identify the goals of modeling (e.g., prediction versus decision making), (2) identify many possible findings that may be relevant to the problem, (3) determine what subset of those findings is worthwhile to model, and (4) organize the findings into variables having mutually exclusive and collectively exhaustive values. Difficulties here are not unique to modeling with Bayesian networks, but rather are common to most tasks. Although solutions are not always simple, some guidance is offered by decision analysts (e.g., citeBlueBook).

In the next phase of Bayesian-network construction, we build a directed acyclic graph that encodes our assertions of conditional independence. One approach for doing so is to choose an ordering on the variables, $X_{1},\ldots,X_{n}$, and, for each $X_{i}$, determine the subset of $X_{1},\dots,X_{i-1}$ such that Equation 4 holds. In our example, using the ordering $(F,A,S,G,J)$, let’s assert the following:

	$\displaystyle p(a|f)$	$\displaystyle=$	$\displaystyle p(a),$		(7)
	$\displaystyle p(s|f,a)$	$\displaystyle=$	$\displaystyle p(s),$		(8)
	$\displaystyle p(g|f,a,s)$	$\displaystyle=$	$\displaystyle p(g|f),$		(9)
	$\displaystyle p(j|f,a,s,g)$	$\displaystyle=$	$\displaystyle p(j|f,a,s).$		(10)

These assertions yield the structure shown in Figure 4.

This approach has a serious drawback. If we choose the variable order carelessly, the resulting network structure may fail to reveal many conditional independencies among the variables. For example, if we construct a Bayesian network for the fraud problem using the ordering $(J,G,S,A,F)$, we obtain a fully connected network structure. In the worst case, we must explore $n!$ variable orderings to find the best one.

Fortunately, there is another technique for constructing Bayesian networks that does not require an ordering. The approach is based on two observations: (1) people can often readily assert causal relationships among variables, and (2) causal relationships typically reveal a full set of conditional independence assertions. So, to construct the graph structure of Bayesian network for a given set of variables, we can simply draw arcs from cause variables to their immediate effects. In almost all cases, doing so results in a network structure that satisfies the definition of Equation 6. For example, given the assertion that Fraud is a direct cause of Gas, the assertion that Fraud, Age, and Sex are direct causes of Jewelry, and the assertion that there are no other causes among these variables, we obtain the network structure in Figure 4.

In the next section, we will explore causality in detail. Here, it suffices to say that the human ability to naturally think in terms of cause and effect is in large part responsible for the success of the DAG model as a representation in AI systems (see Section 3).

In the final step of constructing a Bayesian network, we assess the local probability distributions $p(X_{i}|{\bf Pa}_{i})$. In our fraud example, where all variables are discrete, we assess one distribution for $X_{i}$ for every set of values for ${\bf Pa}_{i}$. Example distributions are shown in Figure 4. Although we have described these construction steps as a simple sequence, they are often intermingled in practice. For example, judgments of conditional independence and/or cause and effect can influence problem formulation. Also, assessments of probability can lead to changes in the network structure.

One final note: In some situations, a child can be a deterministic function of its parents. We can still be uncertain about the value of such a node, because we can be uncertain about the values of its parents. Given the values of its parents, however, the value of the child is determined with certainty. In those situations, I will draw the child node with a double oval. We will see an example of this situation when we consider influence diagrams.

Let’s now turn to how we can use this model to reason under uncertainty. In this case, we may want to infer the Bayesian probability of fraud, given observations of the other variables. This probability is not stored directly in the model and hence needs to be computed using the rules of probability. In general, the computation of a probability of interest given a model is known as probabilistic inference. This discussion on inference applies equally well to frequentist probabilities, so we can talk about both at the same time.

Because a DAG model for ${\bf X}$ determines a joint probability distribution for ${\bf X}$, we can—in principle—use the model to compute any probability over the its variables. As an example, let’s compute the probability of fraud given observations of the other variables. Using the rules of probability, we have

$$p(f|a,s,g,j)=\frac{p(f,a,s,g,j)}{p(a,s,g,j)}=\frac{p(f,a,s,g,j)}{\sum_{f^{\prime}}p(f^{\prime},a,s,g,j)}.$$

(11)

For problems with many variables, however, this direct approach is computationally slow. Fortunately, we can use the conditional independencies encoded in the DAG, Equation 7, to make this computation more efficient. Equation 11 becomes

	$\displaystyle p(f|a,s,g,j)$	$\displaystyle=$	$\displaystyle\frac{p(f)\ p(a)\ p(s)\ p(g|f)\ p(j|f,a,s)}{\sum_{f^{\prime}}p(f^{\prime})\ p(a)\ p(s)\ p(g|f^{\prime})\ p(j|f^{\prime},a,s)}$
		$\displaystyle=$	$\displaystyle\frac{p(f)\ p(g|f)\ p(j|f,a,s)}{\sum_{f^{\prime}}p(f^{\prime})\ p(g|f^{\prime})\ p(j|f^{\prime},a,s)}.$

Many algorithms that exploit conditional independence in DAG models to speed up inference have been developed (see the annual proceedings of The Conference on Uncertainty in Artificial Intelligence—UAI). In some cases, however, inference in a domain remains intractable. In such cases, techniques have been developed that approximate results efficiently—for example, [27, 50].

The representation and use of conditional independence makes reasoning under uncertainty practical for a wide variety of tasks and, in hindsight, is largely responsible for AI’s transition to the use of probability for representing uncertainty. In this section, I highlight some key steps in the actual transition and the role I think I played in it.

In the late 1970s and early 1980s, multiple alternatives to probability were described, including Dempster–Shafer Theory and Fuzzy Logic. As my PhD advisor was Ted Shortliffe, my greatest exposure was to the Certainty Factor model, which he had developed for use in expert systems for medical diagnosis such as MYCIN and EMYCIN [73, 11]. The expert systems consisted of IF–THEN rules, which could be combined together in parallel or series, effectively forming a directed graph. Figure 5 shows a simple made-up example for diagnosing infection. An arc from node $e$ to $h$ corresponds to the rule IF $E=e$ THEN $H=h$, where $e$ and $h$ are propositions that typically correspond to evidence and a hypothesis, respectively. An example of series combination is Sore throat $\rightarrow$ Throat inflamed $\rightarrow$ Infection. An example of parallel combination is Sore throat $\rightarrow$ Throat inflamed $\leftarrow$ Hoarse. Importantly, the semantics of the graph associated with a Certainty Factor model is different from that of the DAG model we have been considering. I use dashed lines for the former graph to highlight this difference. In the Certainty Factor model, arc direction goes from evidence (typically observed) to hypothesis (typically unobserved). In contrast, in a DAG model, arc direction typically goes from cause to effect. For some problems, each hypothesis in the model is a cause of the corresponding evidence, so that every arc in the Certainty Factor model and DAG model will point in the opposite direction. There are many instances, however, where this relationship does not hold.

Associated with each rule $e\rightarrow h$ is a certainty factor $CF(h,e)$, which was intended to quantify the degree to which $e$ changes the belief in $h$. CFs range from -1 to 1. A CF of 1 corresponds to complete confirmation of $h$; a CF of -1 corresponds to complete disconfirmation of $H$; and a CF of 0 leaves the degree of belief of $H$ unchanged. In particular, a CF was not intended to represent an absolute degree of belief in $H$ given $E$. The Certainty Factor model offers functions that combine these CFs when used in series and parallel. As a result, the model can infer a net increase or decrease in the degree of belief for a target hypothesis (Infection in this example), given multiple pieces of evidence. A list of properties or “desiderata” that these functions should obey were described.

One day in early 1985, as a teaching assistant for one of Ted’s medical informatics courses, I was listening to his explanation of the model. It occurred to me that CFs may simply be a transformation of probabilistic quantities. A simple candidate in my mind was the likelihood ratio $\lambda(h,e)=p(e|h)/p(e|\bar{h})$. From the rules of probability, we have

	$\displaystyle\frac{p(h|e)}{p(\bar{h}|e)}$	$\displaystyle=$	$\displaystyle\frac{p(e|h)}{p(e|\bar{h})}\ \frac{p(h)}{p(\bar{h})}$		(12)
	$\displaystyle O(h|e)$	$\displaystyle=$	$\displaystyle\lambda(h,e)\ O(h),$

where $O(h|e)$ and $O(h)$ are the prior and posterior odds of $h$, respectively. That is, the posterior odds of $h$ are just the product of the likelihood ratio and the prior odds of $h$. (I.J. Good [31] wrote extensively about the logarithm of the likelihood ratio, known as the weight of evidence.) One catch was that the likelihood ratio ranges from 0 to infinity, but that was easy to fix: simply use a monotonic transformation to map the likelihood ratio to $[-1,1]$.

That night, I went home and gave the mapping $CF(h,e)=(\lambda(h,e)-1)/(\lambda(h,e)+1)$ a try. It satisfied the desiderata and closely matched the series and parallel combination functions in the Certainty Factor model. Even more important, the correspondence revealed that the Certainty Factor model facilitated the expression of conditional independence assertions that were less extreme than the naive-Bayes assumption. (In the example in Figure 5, the resulting conditional independencies can be identified by reversing the arcs in the figure and interpreting the result as a DAG model.) Given my proclivity for probability, I was excited and wrote up the result [33] [arXiv:1304.3419].

The work got an interesting mix of reactions. I was particularly nervous about what Ted would say about it, but he was very gracious. When he saw the result, he was very interested and gave me a set of papers to read to help me structure my thinking and prepare a publication. When I presented the work at the first UAI meeting that summer, it got a surprisingly good reception. At the time, the debate about probability as a measure of uncertainty was in full swing, having been ignited by Judea Pearl and Peter Cheeseman at the previous year’s AAAI Conference. Those in the probability camp welcomed the work. Ross Shachter and Jack Breese were perhaps the most surprised that someone from Stanford, the home of the Certainty Factor model, would be presenting such a result. We met for the first time there and have been friends and collaborators ever since.

I should note that there is an interesting connection between the Certainty Factor model and the modern reincarnation of the DAG model. In 1978, Dick Duda and Peter Hart created a variant of the Certainty Factor model for PROSPECTOR, a computer-based consultation system for mineral exploration [21]. Peter Hart went on to work at Stanford Research Institute, where he met Ron Howard and Jim Matheson. Ron and Jim saw this model and were inspired to create influence diagrams, an extension of DAG models that we discuss in the next section. After that, Judea Pearl heard Ron Howard talk about influence diagrams and began work his on DAG models [63].

For me, the next question to answer in AI’s transition to probability was the following: Is a monotonic transform of the likelihood ratio the only measure of a belief update? Over the next year, I took Ted’s desiderata, converted them to a series of functional equations (after learning about what Cox did with degrees of belief), and answered the question: a monotonic transform of the likelihood ratio is the only quantity satisfying these desiderata [34] [arXiv:1304.3091]. The support for probability was increasing. That said, critics were still in the majority.

The key remaining criticism of probability was that no one had built a successful probabilistic expert system. In 1984, that was about to change. Bharat Nathwani, a successful surgical pathologist from USC, visited Ted Shortliffe and several of students with the idea of building an expert system to aid surgical pathologists in the diagnosis of disease. The idea was straightforward: a surgical pathologist would look at one or more slides of tissue from a patient under the microscope, identify values for features such as the color or size of cells, report them to an expert system, and get back a list of possible diseases ordered by how likely they were given what was seen. Eric Horvitz and I were in that group of students and jumped at the chance. Over the next year, we built the first version of a probabilistic expert system for the diagnosis of lymph-node pathology, called Pathfinder. Even though we knowingly made the inaccurate assumption that features were mutually independent given disease, the system worked well—so well, that Bharat, Eric, and I started Intellipath, a company that would build expert systems for the diagnosis of all tissue types.

By now it was mid-1985, and fully appreciating Bayesian networks, I wanted to use the representation to incorporate important conditional dependencies among features. But there was a big catch: Bharat and I wanted to extend Pathfinder to include over 60 diseases and over 100 features. Even if we assumed features were mutually independent given disease, Bharat would have to assess almost ten thousand probabilities. So, over the next year I developed two techniques that made the construction of Bayesian networks for medical diagnosis in large domains easier and more efficient. This work became the focus of my PhD dissertation [44] [arXiv:1911.06263].

Before describing these techniques, I should note that diagnosis of disease in surgical pathology is well suited to the assumption that diseases are mutually exclusive. In particular, it is certainly possible for a patient to have two or more diseases, but these diseases are almost always spatially separated and easily identified as separate diseases. Both techniques make strong use of this assumption. In addition, both techniques make use of the following point. Let $d_{1}$ and $d_{2}$ denote two diseases, let $X$ denote some feature (e.g., cell size), and suppose that $p(x|d_{1})=p(x|d_{2})$ for each value of $X$. From the rules of probability, we see that the ratio of disease priors and posteriors is the same:

$$\frac{p(d_{1}|x)}{p(d_{2}|x)}=\frac{p(x|d_{1})}{p(x|d_{2})}\ \frac{p(d_{1})}{p(d_{2})}=\frac{p(d_{1})}{p(d_{2})}.$$

(13)

In words, $X$ does not differentiate between the two diseases. It turns out that surgical pathologists (and experts in other fields) find it easier to think about whether $X$ differentiates diseases $d_{1}$ and $d_{2}$, than think about whether $p(x|d_{1})=p(x|d_{2})$. Comparing Equations 12 and 13, another way to think about this situation is that the observation $X=x$, for any value $x$, is a null belief update for $d_{i}$, under the assumption that only $d_{1}$ and $d_{2}$ are possible.

The first technique was inspired by my discussions with Bharat about how he related findings to disease. He found it difficult to think about how a finding differentiated among all diseases. Rather, he liked to think about pairs of diseases and, for each pair, which of the many findings differentiated them. So, I developed the similarity graph, both an abstract concept and a graphical user interface, to allow him to do just that. An example for the simpler task of diagnosing five diseases that cause sore throat is shown in Figure 6. Each of the five diseases, which we assume to be mutually exclusive for purposes of presentation, correspond to a node in the similarity graph. An undirected edge between two diseases denotes that the expert is comfortable thinking about what features differentiate them. Note that every disease in the graph must border at least one edge, because otherwise some diseases could not be differentiated. After drawing the similarity graph, the expert can then click on one of the edges (in the small oval on the edge) and draw a local Bayesian network structure, a Bayesian network structure that includes the findings useful for differentiating the two diseases and the conditional independencies among these findings. Local structures for different disease pairs need not contain the same findings nor the same assertions of independence. So, unlike an ordinary Bayesian network structure, the technique allows for the specification of asymmetric conditional independencies. In my dissertation, I showed how the collection of local structures can be combined automatically to form a coherent (ordinary) Bayesian network structure for the entire domain. In addition, I showed how probability assessments for the local networks can automatically populate the distributions for this whole-domain structure [44] [arXiv:1911.06263]. The mathematics is interesting (see Chapter 3 and [24] [arXiv:1611.02126]). I called the similarity graph combined with the collection of local Bayesian networks a Probabilistic Similarity Network.

The second technique I developed made probability assessment even easier and more efficient than assessment within local structures. The technique uses a visual structure known as a partition. An example, again for the task of diagnosing sore throat, is shown in Figure 8. The box on the left shows a finding to be assessed (Palatal spots) along with the values for that finding. Each of the other boxes (in this example, there are two of them) contain diseases that are not differentiated by the finding. To construct this partition, the expert first groups diseases into boxes, and then, for each box, assesses a single probability distribution for the finding given any disease in the box. By Equation 13, there is only one distribution for each box. This technique generalizes easily to the case where the probabilities depend on other findings.

Using these techniques, Bharat and I built the extended version of Pathfinder in a relatively short amount of time and showed that its probabilistic diagnoses were accurate. Bharat, Eric, and I then used these same techniques to build many more expert systems for Intellipath. Then, on one sunny day in 1986 at Stanford, while Eric and I were riding our bikes from one class to the next, he said, “Let’s start a company to build expert systems for any diagnostic problem.” We agreed that Jack Breese should join the venture, and the company Knowledge Industries was born. Over the next several years, both Intellipath and Knowledge Industries continued to produce successful probabilistic expert systems based on Bayesian networks. With these results and the successful work of many others mostly in the UAI community, AI was fully embracing probability.

As luck would have it, these efforts brought Eric, Jack, and me to Microsoft. While finishing my Ph.D. and M.D., I got accepted as an assistant professor at UCLA—my dream job. Two weeks after finishing, I got a call from Nathan Myhrvold, a friend of mine from high school. He asked that we meet, ostensibly to catch up, and invited me to join him at Spago, a fancy restaurant in Beverly Hills (which seemed a bit odd). When I arrived, he told me about his work at Yale with Steven Hawking and his rise to vice-president at Microsoft having overseen version 2 of Windows. He then popped the question: “I read your dissertation and want you to come to Microsoft to apply your work to problems there.” Having just landed my dream job, I said, “No way, but you can buy Knowledge Industries.” Several months later, he did just that—an acqui-hire of Jack, Eric, and me.

Using probabilities to be precise about one’s uncertainties is important. It allows us to be precise in communicating our uncertainties to others. It also helps us make good decisions. To the second point, decision theory, developed in the middle of the twentieth century, provides a formal recipe for how to use subjective probability to make decisions. By the way, please don’t let the phrase “decision theory” scare you. As you will see, it is an extremely simple and intuitive theory—in essence, it is just common sense made precise.

Let’s start with an example to introduce the basics. Suppose we are the decision maker (so I don’t have to keep saying “decision maker”) and are deciding whether to have a party outdoors or indoors on a given day where the weather can be sunny or rainy. We can depict this decision problem using a graphical model known as an influence diagram, introduced by Ron Howard, my PhD advisor, and Jim Matheson [48]. The influence diagram for this party problem is shown in Figure 9.

In general, an influence diagram always contains three types of nodes, corresponding to three types of variables. Each type of variable, like any other variable, has a set of mutually exclusive values. In our example, there is one node/variable of each type. The square node Location corresponds to a decision variable. Each value of a decision variable corresponds to a possible action or alternative—in this example, indoors and outdoors. Other names that have been used for the value of a decision variable include “act” and “intervention.” The oval node Weather corresponds to an uncertainty variable (the type of variable seen in DAG models). In this example, let’s suppose this variable has only two relevant values: sunny or rainy. Finally, every influence diagram contains exactly one deterministic outcome node corresponding to the outcome variable. The values of the outcome variable correspond to all possible outcomes—that is, all combinations of alternatives and possible values of the uncertainty variables. In this example, the possible outcomes are (1) an outdoor sunny party, (2) an outdoor rainy party, (3) an indoor sunny party, and (4) an indoor rainy party.

An influence diagram can include multiple decision nodes, and can represent observations of uncertainty nodes interleaved with the making of individual decisions. The latter capability is important to the process of making real-world decisions, but is not central to the connection between decision making and causal reasoning. Consequently, to keep this presentation simple, I will assume that all decisions are made up front, before any uncertainty nodes are observed. For details on interleaving observations with decisions, see the discussion of “informational arcs” in [48].

As in a DAG model, the lack of arcs pointing to uncertainty variables encode assertions of conditional independence. In particular, given an ordering over decision and uncertainty variables, Equation 4 holds for each uncertainty variable, but now parent variables can include decision variables. Also, based on our assumption that decisions are made up front, the decision variables appear first in the variable ordering. In our party problem, the lack of an arc from Location to Weather corresponds to the assertion that the weather does not depend on our decision about the location of the party. Also as in a DAG model, an uncertainty variable in an influence diagram is associated with a local (subjective) probability distribution for each set of values of the variable’s parents. In our example, Weather has no parents, so this variable has only one distribution that encodes our prior beliefs that it will be rainy or sunny. Together, the assertions of independence and the local probability distributions define a joint distribution for the uncertainty variables conditioned on all possible alternatives.

The single outcome variable in an influence diagram encodes our preferences for the various outcomes. In particular, associated with each possible outcome is a number known as a utility. The larger the number, the more desirable the outcome. Utilities range between 0 and 1 (we will see why in a moment). That said, if the utilities are transformed linearly, the choice of the best alternative remains the same.

Decision theory says the decision maker should choose the alternative with the highest expected utility, where expectation is taken with respect to the decision maker’s joint distribution over uncertainty variables given each of the possible alternatives. In the party problem, expectation is taken with respect to $W$ (weather), which we assert does not depend on party location. Based on the utilities in Figure 9, the expected utility of the outdoor location is 0.7; the expected utility of the indoor location is 0.8; so, we should choose the indoor alternative. This principle is generally known as the principle of maximum expected utility or MEU principle.

Decision problems can also be represented with another type of graphical model known as a decision tree. This graphical model should not be confused with the “decision tree” used in the machine-learning community. Unfortunately, the two communities chose the same name for these rather different representations. When I use the term “decision tree,” I will make it clear which one I am talking about. Figure 10a shows the party problem depicted as a decision tree.

As in the influence diagram, a square node represents a decision variable, but now the variable’s values are drawn as edges emerging from the node. To the right of the decision variable come the uncertainty variables and possibly additional decision variables. In this case, there is just one uncertainty variable and no additional decision variables. Finally, utilities of the various outcomes are shown at the far right of the decision tree. Note that, in this case, the decision tree can be simplified, because the utility of the indoor location does not depend on the weather. The simplified decision tree is shown in Figure 10b.

When I first learned of influence diagrams (and decision trees) and the MEU principle, two questions immediately came up in my mind: What are these mysterious utilities? And what justifies the use of the MEU principle to choose the best alternative? In 1948, von Neumann and Morgenstern provided a very elegant answer to both questions. In a manner similar to Cox, von Neumann and Morgenstern introduced several properties that, if followed by a decision maker, define utilities and imply the MEU principle. Here, I’ll present a slightly different version of their argument given by my PhD advisor, Ron Howard [46]. I’ll use decision trees to present his argument and assume the rules of probability are in force.

Now consider the rather general decision problem shown in Figure 12a. Here, there are two alternatives and, for each alternative, a set of possible outcomes that will occur with the probabilities shown. As we will see, this decision problem is sufficiently general to make the argument. Given this decision problem, the first task of the decision maker is to identify the best and worst outcome, again denoted $best$ and $worst$, respectively. Then, for each possible outcome, the decision maker uses the continuity property to construct an equally preferred chance at getting the best versus worst outcome. The following property says that the decision maker can substitute this chance for the original outcome in the original decision problem, yielding the equivalent decision problem in Figure 12b.

The resulting decision problem is simply a set of chances at the best versus worst outcome. The next property says that the decision maker can collapse these chances into one chance at the best versus worst outcome using the rules or probability.

Given this property, the decision maker now has the equivalent decision problem shown in Figure 12c. The final property describes how the decision maker should make this decision.

Applying this property to the decision problem in Figure 12c yields the MEU principle, where the utility of an outcome is the probability of the chance at outcome $best$ versus $worst$. In addition, given the substitutability and decomposability properties, the decision problem in Figure 12a is sufficiently general to address any decision problem with two alternatives. Finally, there is a straightforward generalization of this argument to a decision problem with any number of alternatives.

In essence, these properties allow a decision maker to boil down any decision problem into a series of simple decision problems like the one in Figure 11. Note that this simple decision problem has the same form as the party problem. In the party problem, the decision maker is asked to assess utilities and apply the MEU principle to choose. The clever trick from von Neumann and Morgenstern is to recast this problem into one of choosing a probability of sunny that makes the alternatives outdoors and indoors equally preferable.

When I first saw this argument, I thought to myself, “This is the most elegant and practical application of math I have ever seen.” Both the assumptions and the proof of the MEU principle are simple, and the result is a tool that just about anyone can use to improve their decision making. This realization came to mind because my father was a high school math teacher and was always looking for practical applications of math to show his students. By the time I saw this proof, he had already retired, but nevertheless, we were both excited to discuss it.

To close this section, it’s worthwhile to comment on the two rather different graphical models for decision problems. The decision tree more naturally depicts the flow of time and the display of probabilities and utilities. Also, it allows the explicit depiction of any asymmetries in a decision problem, as we see in our example. In contrast, an influence diagram is typically more compact and, as mentioned, enables the explicit representation of probabilistic independencies. We will see examples of this benefit later. Given these tradeoffs, both representations are still in use.

There is a special class of utility that is worth mentioning—namely, proper scoring rules. To motivate this class of utility, imagine you operate a company that invests is new and upcoming businesses. You are constantly making high-stakes decisions and sometimes need probabilities (or probability densities) from experts that various possible outcomes will occur, such as whether a particular piece of legislation in Washington is going to pass. You have access to experts, and want to be sure that the probabilities you get from them are “honest.” One way to do this is to frame the expert as a decision maker who is deciding what distribution to report over some variable $X$, and then receiving a utility for that report based on the value of $X$ that is eventually observed. The utility they receive should be a function of (1) every possible observed value of $X=x$ and (2) the expert’s reported distribution $q(x^{\prime})$ for every possible value of $X=x^{\prime}$. Let’s denote this utility function as $u(x,q(x^{\prime}))$. For the reported probability distribution $q$ to be honest, we want the expert’s expected utility to be a maximum when $q$ is equal to the expert’s actual probability distribution $p$. That is, we want $\int_{x}p(x)\ u(x,q(x^{\prime}))$ to be a maximum when $q=p$. (Here, I am using $\int_{x}$ generally—it can be a sum when $X$ is discrete.) When this condition holds, $u$ is said to be a proper scoring rule.

One proper scoring rule is the log scoring rule: $u(x,q(x^{\prime}))=\log q(x)$—that is, $u(x,q(x^{\prime}))$ is the logarithm of $q(x)$ where $x$ is the value of $X$ that is actually observed. It is easy to check that utility is maximized when $p=q$. What is rather remarkable, however, is that the log scoring rule is the only proper scoring rule (up to linear transformation) when (1) $X$ takes on three or more states, (2) $u(x,q(x^{\prime}))$ is local in the sense that it only depends on $q$ at the observed value of $X$, and (3) certain regularity conditions hold [7, 8]. The concept of a proper scoring rule will come in handy in Section 4.1, where we consider learning graphical models from data.

It’s tempting to sum up the difference between a purely probabilistic DAG model and an influence diagram by viewing the latter as merely the former with decisions and utilities “tacked on.” Nonetheless, there is something fundamentally different about them. In particular, an influence diagram can express causal relationships among its variables, whereas a probabilistic graphical model strictly represents correlational or acausal relationships among its variables.

Ironically, Howard and Matheson, have been reluctant to associate their elegant representation for decision problems with any notion of causality. Note the label “influence diagrams” rather than “causal diagrams.” This reluctance had also been prominent in the statistics community until pioneers including Peter Spirtes, Clark Glymour, Richard Scheines, Jamie Robbins, and Judea Pearl began their relentless work to change that.

Perhaps one source of reluctance was the lack of a clear definition of cause and effect. Even in his recent work [65], Judea describes the notion of cause and effect as a primitive, like points and lines in geometry. Personally, I think causality can and should not be left as a primitive, but should be defined in more basic terms. Before I go any further, allow me to take a crack at this.

Let’s start with a simple example: colliding billiard balls. When a moving ball strikes another, we naturally say that the collision “caused” the subsequent motion. (At a party in the mid-1980s for Ted Shortliffe’s research group, I was playing Pictionary. Eric Horvitz, my game partner, drew a picture of a billiard table with a pool cue about to strike a ball. I immediately guessed the answer: “causality.” The other players were astounded. Eric and I think a lot alike.) This easily generalizes. When we say, “event x causes event y,” we mean that there are physical interactions, via the forces of nature, that relate event x to event y. Note that this definition may extend to quantum interactions. Current experimental results involving quantum entanglement, perhaps the oddest of quantum interactions, suggest two possibilities. One is that special relativity holds and thus there is correlation without causation, which is extremely strange [29, 28]. The other is that special relativity does not hold and a quantum signal that governs the entanglement is propagating faster than the speed of light. Under this second possibility, my definition still applies. Unfortunately, it is quite possible that we may never know which possibility holds. That said, to me, the concepts in Newtonian physics and classical chemistry are adequate to describe almost all causal relationships that have practical relevance.

With this definition, it becomes clear that reasoning about actions and their consequences is tantamount to causal reasoning. For example, my decision to hold the party outdoors leads to me writing invitations, which in turn are read by my guests, who then follow those instructions and show up at my house—all happening via forces of nature. Note that, although there are many definitions of cause and effect, there is general agreement on how to test for the existence of a causal effect and to quantify its strength: the randomized trial. We examine this test in Section 4.5.

An influence diagram can represent both causal and acasual relationships. In the party problem, suppose that the decision maker can check a weather forecast before making the location decision. The updated influence diagram (structure only) is shown in Figure 13. Here, the relationship from Location and Weather to Outcome is causal, whereas the relationship between Weather and Forecast need only be considered in terms of probabilities. Of course, we could model a causal relationship between Weather and Forecast by introducing other variables such as the current weather and its time derivatives at nearby locations, but doing so is not needed to decide on the location of the party. To make the decision, only the probabilistic relationship between Weather and Weather forecast matters. For a detailed discussion of the flexibility of influence diagrams to represent both causal and acausal relationships, see [43] [10.1613/jair.202].

In contrast, many researchers working on the theory of causal inference focus on models where every arc is causal. In addition, they don’t represent explicit decisions, but rather reason about decisions that are implicitly defined by the domain variables. In particular, for every domain variable, they imagine a decision with alternatives that either force the variable to take on a particular value, or take no action and simply observe the variable. I call this framework a fully causal framework and a model therein a fully causal model.

The fully causal framework lies strictly within the decision-theoretic framework. In particular, a fully causal model within this framework can be represented by an influence diagram in a straightforward manner. As an example, consider the fully causal model for the assertions “$X$ causes $Y$” and “$Y$ causes $Z$”. The model structure can be drawn in simple form as a DAG on the domain variables as shown in Figure 14a. It can also be represented by the influence-diagram structure shown in Figure 14b.

First, let’s look at the decision variables in this influence diagram. To be concrete, consider the decision variable force$(Z)$; similar remarks apply to force$(X)$ and force$(Y)$. One value of the decision variable force$(Z)$ is “do nothing”, whereby $Z$ is observed rather than manipulated. Other values of force$(Z)$ corresponding to $Z$ taking on one of its possible values, regardless of the values of $Z$’s parents in the graph. Pratt and Schlaifer [49] describe this action as “forcing” $X$ to take on some value. Note the connection between the verb “force” and the noun “force” in my definition of causality. Spirtes, Glymour, Scheines also describe this type of action, calling it a “manipulation” in [75] and “set$(X)$” in various other writings. Pearl calls it a “do operator” and uses the notation “do$(X)$.” In addition, he sometimes talks about $Z$ ignoring its parents as graph surgery [64, 65].

Now let’s look at the remaining variables. Each observed variable ($X$, $Y$, and $Z$) is a deterministic function of its corresponding force/set/do decision and its corresponding uncertainty variables ($U_{x}$, $U_{y}$, and $U_{z}$) that encode the uncertainties in the problem. When force$(Z)$ takes on the value “do nothing,” then $Z=U_{z}$. When, for example, force$(Z)$ takes on the value “force $Z$ to value $z$,” then $Z=z$, as described in the previous paragraph. Typically, as depicted in the figure, we assume these uncertainty variables are mutually independent, reflecting the modularity of causal interactions (which I will discuss shortly). As for the outcome variable, I’ve omitted it, because here we are not concerned with making the actual decisions, but rather representing the relationships among the variables.

The influence diagram for a fully causal model not only represents causal interactions, it also represents assertions of conditional independence. For example, given the fully causal model in Figure 14b, when we set all force/set/do decisions to “do nothing” and absorb the uncertainties into the observable variables, we end up with a probabilistic DAG model with the same independence semantics as the model in simple form (Figure 14a) interpreted as a probabilistic model. In general, a fully causal model implies the same assertions of conditional independence as those implied by its simple form interpreted as an acausal model. This statement is sometimes called the causal Markov assumption [75] and, as we shall see, is important for learning causal models from observational data.

The fully causal framework makes certain forms of causal reasoning accessible to simple mathematical treatment (see, e.g., the section in [65] starting on p.231). In addition, when creating a model within this framework, a person need not specify up front whether a variable is manipulated or observed. That said, it’s important to note that force/set/do decisions are not the norm in real life. A classic example where a decision is intended to be a force/set/do decision, but isn’t, is making a wish to a magic genie:

Me: “Genie, I wish to be rich.”
Genie: “Your wish is granted. I killed your aunt, and you will now inherit her fortune.”
Me: “No, that’s not what I meant!”

The genie acts to increase the value of my bank account, but his actions cause other changes that I did not intend. (When I was a very young, I watched The Twilight Zone television series, which left a deep impression on me. Season 2, episode 2 has a variation on the magic-genie theme. The protagonist wishes to be all-powerful, and the genie turns him into Hitler in his final moments in the bunker—very disturbing. When I first heard of the force/set/do decision, I couldn’t help but think of this episode.) Nonetheless, there are occasional situations where force/set/do decisions can be realized in practice (see Sections 4.4 and 4.5).

A useful property of cause–effect relationships is that they tend to be modular. To illustrate this point, consider a clinical trial to test the efficacy of drugs in lowering cholesterol. A reasonable causal model structure is as follows:

$$\texttt{Drug offered}\rightarrow\texttt{Drug taken}\rightarrow\texttt{Cholesterol level}$$

It is interesting to speculate that the modularity of causal reasoning has a potential survival advantage for humans. Humans excel above all other creatures in large part because they can make good decisions. As we’ve just discussed, causal reasoning is a key component of decision making, and the modularity of causal relationships allows this reasoning to be more easily executed in the human brain. Furthermore, the high-level process of decision making is itself modular—we decompose the process into selecting alternatives, specifying uncertainty in the face of interventions, and specifying preferences for the possible outcomes. This additional modularity further facilitates the execution of decision making in the brain. Furthermore, the ability to imagine possible alternatives necessarily requires at least the perception of free will. Whether we actually have free will is a matter of debate. Sadly, experimental evidence suggests it is an illusion [32]. Ross Shachter and I discuss these points in more detail in [72] [10.1145/3501714.3501756].

One final note: individual decision making is better than group decision making. Specifically, a single decision maker has a set of beliefs and a set preferences that prescribe an optimal decision. This is not the case for groups. One merely needs to experience a group trying to decide where to go out to eat or witness the decision paralysis of political bodies to appreciate this point. (Also, see Arrow’s impossibility theorem [3].) Going down the rabbit hole one step further, scientific investigations suggest that the human thought proceeds as a collection of subconscious processes that feed into a sense of a single, conscious “I” (e.g., [32]). If these processes did not feed into a single “I,” then decision making would suffer in a manner similar to that of group decision making, leading to a survival disadvantage. Thus, it is not too surprising that the sense of a single, conscious “I” would emerge through evolution. I’m not suggesting that a single “I” must be conscious to have this advantage, but it seems clear that if evolution were to produce such a conscious “I,” then it would have a survival advantage.

To begin a discussion of learning acausal DAG models, let’s look at the simplest possible problem: learning a DAG model for a single binary variable $X$ with observational data only. To be concrete, let’s return to the problem of flipping a thumbtack, which can come up heads (denoted $x$) or tails (denoted $\bar{x}$). We flip the thumbtack $N$ times, under the assumption that the physical properties of the thumbtack and the conditions under which it is flipped remain stable over time, yielding data $D={X_{1},\ldots,X_{N}}$. From these $N$ observations, we want to determine the probability of (say) heads on the $N+1$th toss. As we have discussed, there is some unknown frequency of heads. We could use $f$(heads) to denote this frequency, but to avoid the accumulation of parentheses, let’s use $\theta_{x}$ instead (and similarly $\theta_{\bar{x}}$). In the context of learning graphical models from data, $\theta_{x}$ and $\theta_{\bar{x}}$ are often referred to as parameters for the variable $X$. In addition, I will use $\theta_{X}$ to apply to the case where $X$ is either $x$ or $\bar{x}$.

As we are uncertain about $\theta_{x}$, we can express this uncertainty with a (Bayesian) probability distribution (in this case, a probability density function) $p(\theta_{x})$. The independence relationships among the variables $\theta_{x}$ and $X_{1},\ldots,X_{N}$ can be described by the Bayesian network, shown on the left-hand side of Figure 15. Namely, as we discussed at the end of Section 2.1, given $\theta_{x}$, the values for the observations $X_{1},\ldots,X_{N}$ are mutually independent. The right-hand side of Figure 15 is the same model depicted in plate notation, first described by [12]. Plates depict repetition in shorthand form. Anything inside the plate (i.e., the box) is repeated over the index noted inside the plate.

Learning the parameter for the one-node Bayesian network now boils down to determining the posterior distribution $p(\theta_{x}|D)$ from $D$ and the prior distribution $p(\theta_{x})$. From the rules of probability, we have

$$p(\theta_{x}|D)=\frac{p(\theta_{x})\ p(D|\theta_{x})}{p(D)}.$$

(14)

where

$$p(D)=\int p(D|\theta_{x})\ p(\theta_{x})\ d\theta_{x}.$$

The quantity $p(D)$ is sometimes called the marginal likelihood of the data. As we will see, this quantity is important for inferring posterior probabilities of model structures. From the independencies in Figure 15, we have

$$p(D|\theta_{x})=\prod_{i=1}^{N}p(x_{i}|\theta_{x}),$$

where each term in the product is $\theta_{x}$ when $X_{i}$ is heads and ($1-\theta_{x}$) when $X_{i}$ is tails. Both Bayesians and frequentists agree on this term: it is the likelihood function for Bernoulli sampling. Equation 14 becomes

$$p(\theta_{x}|D)=\frac{p(\theta_{x})\ \theta_{x}^{N_{x}}\ (1-\theta_{x})^{N_{\bar{x}}}}{p(D)},$$

(15)

where $N_{x}$ and $N_{\bar{x}}$ are the number of heads and tails observed in $D$, respectively. The quantities $N_{x}$ and $N_{\bar{x}}$ are sometimes called sufficient statistics, because they provide a summarization of the data that is sufficient to describe the data under the assumptions of their generation.

Now that we have the posterior distribution for $\theta_{x}$, we can determine the probability that the $N+1$th toss of the thumbtack will come up heads (denoted $x_{N+1}$) heads:

	$\displaystyle p(x_{N+1}|D)$	$\displaystyle=$	$\displaystyle\int p(x_{N+1}|\theta_{x})\ p(\theta_{x}|D)\ d\theta_{x}$
		$\displaystyle=$	$\displaystyle\int\theta_{x}\ p(\theta_{x}|D)\ d\theta_{x}\equiv{\rm E}_{p(\theta_{x}|D)}(\theta_{x}).$

where ${\rm E}_{p(\theta_{x}|D)}(\theta_{x})$ denotes the expectation of $\theta_{x}$ with respect to the distribution $p(\theta_{x}|D)$. The probability that the $N+1$th toss comes up tails is simply

$$p(\bar{x}_{N+1}|D)=1-p(x_{N+1}|D).$$

To complete the Bayesian story for this example, we need a method to assess the prior distribution over $\theta_{x}$. A common approach, often adopted for convenience, is to assume that this distribution is a beta distribution:

$$p(\theta_{x})={\rm Beta}(\theta_{x}|\alpha_{x},\alpha_{\bar{x}})\equiv\frac{\Gamma(\alpha_{x})}{\Gamma(\alpha_{x})\Gamma(\alpha_{\bar{x}})}\theta_{x}^{\alpha_{x}-1}(1-\theta_{x})^{\alpha_{\bar{x}}-1},$$

where $\alpha_{x}>0$ and $\alpha_{\bar{x}}>0$ are the parameters of the beta distribution, $\alpha_{X}=\alpha_{x}+\alpha_{\bar{x}}$, and $\Gamma(\cdot)$ is the Gamma function which satisfies $\Gamma(x+1)=x\Gamma(x)$ and $\Gamma(1)=1$. The quantities $\alpha_{x}$ and $\alpha_{\bar{x}}$ are often referred to as hyperparameters to distinguish them from the parameter $\theta_{x}$. For the beta distribution, the hyperparameters $\alpha_{x}$ and $\alpha_{\bar{x}}$ must be greater than zero so that the distribution can be normalized. Examples of beta distributions are shown in Figure 16.

The beta prior is convenient for several reasons. By Equation 15, the posterior distribution will also be a beta distribution:

$$p(\theta_{x}|D)={\rm Beta}(\theta_{x}|\alpha_{x}+N_{x},\alpha_{\bar{x}}+N_{\bar{x}}).$$

(16)

We say that the set of beta distributions is a conjugate family of distributions for binomial sampling. In general, when both the prior and posterior live in the same distribution family for a particular type of sampling, we say that distribution family is conjugate for that type of sampling. Also, the expectation of $\theta_{x}$ with respect to this distribution has a simple form:

$$\int\theta_{x}\ {\rm Beta}(\theta_{x}|\alpha_{x},\alpha_{\bar{x}})\ d\theta_{x}=\frac{\alpha_{x}}{\alpha_{X}}.$$

So, given a beta prior, we have a simple expression for the probability of heads in the $N+1$th toss:

$$p(x_{N+1}|D)=\frac{\alpha_{x}+N_{x}}{\alpha_{X}+N}.$$

(17)

Note that, for very large $N$ with $\theta_{x}>0$, the posterior distribution over $\theta_{x}$ is sharply peaked around $N_{x}/N$, the fraction of heads observed. Finally, the marginal likelihood becomes

$$p(D)=\frac{\Gamma(\alpha_{X})}{\Gamma(\alpha_{X}+N)}\ \frac{\Gamma(\alpha_{x})}{\Gamma(\alpha_{x}+N_{x})}\ \frac{\Gamma(\alpha_{\bar{x}})}{\Gamma(\alpha_{\bar{x}}+N_{\bar{x}})}.$$

Assuming $p(\theta_{x})$ is a beta distribution, it can be assessed in a number of ways. For example, we can assess our probability for heads in the first toss of the thumbtack (e.g., using a probability wheel). Next, we can imagine having seen the outcomes of $k$ flips and reassess our probability for heads in the next toss. From Equation 17, we have (for $k=1$):

$$p(x_{1})=\frac{\alpha_{x}}{\alpha_{x}+\alpha_{\bar{x}}},\ \ \ \ \ p(x_{2}|x_{1})=\frac{\alpha_{x}+1}{\alpha_{x}+\alpha_{\bar{x}}+1}.$$

Given these probabilities, we can solve for $\alpha_{x}$ and $\alpha_{\bar{x}}$. This assessment technique is known as the method of imagined future data.

Another assessment method is based on Equation 16. This equation says that, if we start with a Beta$(0,0)$ prior and observe $\alpha_{x}$ heads and $\alpha_{\bar{x}}$ tails, then our posterior (i.e., new prior) will be a Beta$(\alpha_{x},\alpha_{\bar{x}})$ distribution. (Technically, the hyperparameters of this prior should be small positive numbers so that $p(\theta)$ can be normalized.) If we suppose that a Beta$(0,0)$ prior encodes a state of minimum information (a supposition that remains debated), we can assess $\alpha_{x}$ and $\alpha_{\bar{x}}$ by determining the (possibly fractional) number of observations of heads and tails that is equivalent to our actual knowledge about flipping thumbtacks. Alternatively, we can assess $p(x_{1})$, the probability of heads on the first toss, and $\alpha_{X}$, the latter of which can be regarded as an effective sample size for our current knowledge. This technique is known as the method of effective samples. Other techniques for assessing beta distributions are discussed in [82] and [15].

Although the beta prior is convenient, it is not accurate for some problems. For example, suppose we think that the thumbtack may have been purchased at a magic shop. In this case, a more appropriate prior may be a mixture of beta distributions—for example,

$$p(\theta_{x})=0.4\ {\rm Beta}(20,1)+0.4\ {\rm Beta}(1,20)+0.2\ {\rm Beta}(2,2),$$

where 0.4 is our probability that the thumbtack is heavily weighted toward heads (tails). In effect, we have introduced an additional unobserved or “hidden” variable $H$, whose values correspond to the three possibilities: (1) thumbtack is biased toward heads, (2) thumbtack is biased toward tails, and (3) thumbtack is normal; and we have asserted that $\theta$ conditioned on each value of $H$ is a beta distribution. In general, there are simple methods (e.g., the method of imagined future data) for determining whether or not a beta prior is an accurate reflection of one’s beliefs. In those cases where the beta prior is inaccurate, an accurate prior can often be assessed by introducing additional hidden variables, as in this example.

Finally, I note that this approach generalizes to the case where $X$ has $k>2$ values with parameters $\theta_{1},\ldots,\theta_{k}$. In this case, the conjugate distribution for these parameters is the Dirichlet distribution, the generalization of the Beta distribution, given by

$$p(\theta_{1},\ldots,\theta_{k})=c\ \prod_{i=1}^{k}\theta_{i}^{\alpha_{i}-1},$$

where hyperparameters $\alpha_{1},\ldots,\alpha_{k}>0$, and $c$ is the normalization constant.

Next, let’s consider the problem of learning DAG models having only two binary variables, which I will denote $X$ and $Y$. In this case, there are only two possible model structures to consider—the one where $X$ and $Y$ are independent, and one where there is no claim of independence. Note that there are two graph structures that express no claim of independence: $X\rightarrow Y$ and $X\leftarrow Y$. (When depicting DAG models inline, I will draw them without ovals around node names.) As acausal networks, they are equivalent, so we only need consider one of them. To be concrete, let’s use the graph structure $X\rightarrow Y$.

I denote the model structures representing independence and no claim of independence $s_{XY}$ and $s_{X\rightarrow Y}$, respectively. Using a Bayesian approach, we can reason about the posterior probability of either of the graph structures (generically denoted $s$) given their prior probabilities and marginal likelihoods for data $D=X_{1},Y_{1},\ldots,X_{N},Y_{N}$:

$$p(s|D)=\frac{p(s)\ p(D|s)}{p(s_{XY})\ p(D|s_{XY})+p(s_{X\rightarrow Y})\ p(D|s_{X\rightarrow Y})}.$$

(18)

For a historical perspective on this sort of reasoning, see [53].

Interestingly, there is a relationship between the marginal likelihood and cross validation. Using the product rule of probability, the logarithm of the marginal likelihood given a model $s$ can be written as follows:

$$\log p(D|s)=\log p(X_{1})+\log p(X_{2}|X_{1})+\ldots+\log p(X_{N}|X_{1},\ldots,X_{N-1}).$$

Each term in the sum is a proper score (i.e., utility) for the prediction of one data sample. In words, first we see how well we predict the first observation. Then we train our model with the first observation and see how well we predict the second observation. We continue in this fashion until we predict and score each observation in sequence. By the rules of probability, the total score will be the same, regardless of how the data samples are ordered. This perspective was first noticed by Phil Dawid [20]. In this form, the marginal likelihood resembles cross validation, except that there is no crossing—that is, there is never a case where $X_{i}$ is used in the training data to predict $X_{j}$ and vice versa. As crossing can lead to over fitting [20], the marginal likelihood appears to be an ideal validation approach. In practice, however, I have seen many instances where cross validation yields a result that seems to be more reasonable.

Now let’s examine the Bayesian approach to learning models in detail. First, let’s consider the simpler graph structure $s_{XY}$. As both $X$ and $Y$ are binary, let’s use $\theta_{x}$ and $\theta_{y}$ to denote the frequency of $X$ and $Y$ coming up heads, respectively. When determining the marginal likelihood for the data given this graph structure, the assumption that these two parameters are independent greatly simplifies the computation. In particular,

	$\displaystyle p(D|s_{xy})$	$\displaystyle=$	$\displaystyle\int p(\theta_{x},\theta_{y}|s_{xy})\ p(D|\theta_{x},\theta_{y},s_{xy})\ d\theta_{x}d\theta_{y}$
		$\displaystyle=$	$\displaystyle\int p(\theta_{x}|s_{xy})\ p(\theta_{y}|s_{xy})\ p(D|\theta_{x},\theta_{y},s_{xy})\ d\theta_{x}d\theta_{y}$
		$\displaystyle=$	$\displaystyle\int p(\theta_{x}|s_{xy})\ p(X_{1},\ldots,X_{n}|\theta_{x},s_{xy})\ d\theta_{x}\ \int p(\theta_{y}|x_{xy})\ p(X_{1},\ldots,X_{n}|\theta_{y},s_{xy})\ d\theta_{y}$

In effect, with this assumption of parameter independence, the determination of the marginal likelihood decomposes into the determination of the marginal likelihood for flips of two separate thumbtacks. The marginal likelihood becomes

	$\displaystyle p(D|s_{xy})$	$\displaystyle=$	$\displaystyle\frac{\Gamma(\alpha_{X})}{\Gamma(\alpha_{X}+N)}\ \frac{\Gamma(\alpha_{x})}{\Gamma(\alpha_{x}+N_{X})}\ \frac{\Gamma(\alpha_{\bar{x}})}{\Gamma(\alpha_{\bar{x}}+N_{\bar{x}})}\times$
			$\displaystyle\frac{\Gamma(\alpha_{Y})}{\Gamma(\alpha_{Y}+N)}\ \frac{\Gamma(\alpha_{y})}{\Gamma(\alpha_{y}+N_{y})}\ \frac{\Gamma(\alpha_{\bar{y}})}{\Gamma(\alpha_{\bar{y}}+N_{\bar{y}})},$

where the hyperparameters and sufficient statistics for $Y$ have definitions analogous to those for $X$ described in the previous section.

Now consider $s_{X\rightarrow Y}$, the graph structure that does not assume independence. We now have parameter $\theta_{x}$ as before, and two parameters: $\theta_{y|x}$, which denotes the frequency of $Y$ when $X$ comes up heads, and $\theta_{y|\bar{x}}$, which denotes the frequency of $Y$ when $X$ comes up tails. If we make two assumptions, the marginal likelihood decomposes into three terms, and we can think of there being flips for three separate thumbtacks: one for $X$ and two for $Y$. When $X$ comes up heads on a toss, we flip one of the thumbtacks for $Y$. When $X$ comes up tails on a toss, we flip the other thumbtack for $Y$. The first assumption is that the three parameters are mutually independent. The second assumption is that for every observation of $Y$, we see an observation for $X$. If this assumption did not hold, the parameters would not remain mutually independent after observing the data. The independence assumptions for this case are depicted in Figure 17.

Tracing through the argument for the single-thumbtack case for these three thumbtacks, we obtain the marginal likelihood for the graph structure $s_{x\rightarrow y}$:

	$\displaystyle p(D|s_{x\rightarrow y})$	$\displaystyle=$	$\displaystyle\frac{\Gamma(\alpha_{X})}{\Gamma(\alpha_{X}+N)}\ \frac{\Gamma(\alpha_{x})}{\Gamma(\alpha_{x}+N_{x})}\ \frac{\Gamma(\alpha_{\bar{x}})}{\Gamma(\alpha_{\bar{x}}+N_{\bar{x}})}\times$
			$\displaystyle\frac{\Gamma(\alpha_{x\cdot})}{\Gamma(\alpha_{x\cdot}+N_{x})}\ \frac{\Gamma(\alpha_{xy})}{\Gamma(\alpha_{xy}+N_{xy})}\frac{\Gamma(\alpha_{x\bar{y}})}{\Gamma(\alpha_{x\bar{y}}+N_{x\bar{y}})}\times$
			$\displaystyle\frac{\Gamma(\alpha_{\bar{x}\cdot})}{\Gamma(\alpha_{\bar{x}\cdot}+N_{\bar{x}})}\ \frac{\Gamma(\alpha_{\bar{x}y})}{\Gamma(\alpha_{\bar{x}y}+N_{\bar{x}y)}}\frac{\Gamma(\alpha_{\bar{x}\bar{y}})}{\Gamma(\alpha_{\bar{x}\bar{y}}+N_{\bar{x}\bar{y}})},$

where $\alpha_{x\cdot}=\alpha_{xy}+\alpha_{x\bar{y}}$ are the hyperparameters for the Beta distribution for $Y$ when $X$ is heads, and $N_{xy}$ and $N_{x\bar{y}}$ are the corresponding sufficient statistics, and similarly for the terms for $Y$ when $X$ is tails.

Technically, these arguments complete the story. We start with priors on the two graph structures and their parameters, observe data, and compute posteriors on the graph structures using Equation 18. The catch, however, is that for a domain with $n$ variables, the number of possible graph structures—assuming none are eliminated by prior knowledge—is super exponential in $n$. So, it would be extremely desirable to identify additional techniques, which are reasonable in many situations, that lead to a reduction in the number of priors that need to be assessed.

One technique follows from the semantics of the acausal DAG model—namely, that such models encode only assumptions of conditional independence. Given these semantics, if two models encode the same independencies, their parameters should be equivalent. For example, the parameters of the two-variable model $s_{X\rightarrow Y}$ and those of the model $s_{X\leftarrow Y}$, which are frequencies, show be related according to the rules of probability as follows:

$$\theta_{X}\ \theta_{Y|X}=\theta_{Y}\ \theta_{X|Y}.$$

(Transforming a distribution for one set of parameters to an equivalent set is sometimes call a change of variable.) Unfortunately, however, unless the hyperparameters for the parameters of $s_{X\rightarrow Y}$ are specified carefully, the computed parameters for $s_{X\leftarrow Y}$ will be neither independent nor distributed according to the Beta distribution, which, as we will see shortly, leads to a complication. One day in 1993, I was sitting in my office in Building 9, one of the original Microsoft buildings, and started to fiddle with the hyperparameters to try to create independence for both graphs. I discovered that, if I (1) defined parameters $\theta_{xy}$, $\theta_{x\bar{y}}$, $\theta_{\bar{x}y}$, and $\theta_{\bar{x}\bar{y}}$ to be the parameters of a single, four-value variable $XY$, (2) assumed these parameters were distributed according to the Dirichlet distribution (with arbitrary hyperparameters), and (3) computed the parameters for the two graph structures using

$$\theta_{XY}=\theta_{X}\ \theta_{Y|X}=\theta_{Y}\ \theta_{X|Y},$$

then the parameters for both graph structures were mutually independent and distributed according to the Beta distribution. At this point, I tried to find generalizations of the Dirichlet distribution that satisfied this property. I couldn’t and wondered whether the only distribution on $XY$ that yielded parameter independence for both graph structures was the Dirichlet. After about a year of hard work, Dan Geiger and I showed that my guess was correct. Our theorem states that, if $X$ are finite distributions, and if the parameters for the two graph structures $s_{X\rightarrow Y}$ and $s_{X\leftarrow Y}$ are mutually independent, then the parameters for $XY$ have a Dirichlet distribution, and each of the parameters for the two structures are also Dirichlet [25]. [10.1214/aos/1069362752]. The theorem is rather remarkable, as qualitative assertions about independence provide a characterization of the Dirichlet distribution. To prove the theorem, we used the tools of functional equations discussed previously.

Based on this theorem, in order to have the mutually independent parameters for the equivalent graph structures $s_{X\rightarrow Y}$ and $s_{X\leftarrow Y}$, there must exist a probability distribution for the variable $XY$ and an effective sample size $\alpha>0$ such that the hyperparameter $\alpha_{XY}=\alpha\ p(XY)$ for each of the four values of $XY$. Under these conditions, our prior knowledge about the parameters for both graph structures is, in effect, the situation where we started from complete ignorance and saw complete data on both variables. Furthermore, this theorem and its consequences for two variables generalize to domains with more than two variables. Namely, in a domain with $n$ variables, there are $n!$ graph structures (one for each ordering of the variables) that have no missing arcs and thus equivalently avoid the assumption of conditional independence among any of the variables. From the theorem, it follows that all Dirichlet hyperparameters for the parameters of all complete graph structures can be derived from a single joint distribution over the $n$ variables and a single effective sample size $\alpha>0$. And, to assess this joint distribution, we can assess a single Bayesian network for it. Thus, all parameter priors are defined from a single prior Bayesian network for the domain and the effective sample size $\alpha$.

A second technique that reduces the number of assessments needed has to do with copying parameter priors from one graph structure to another. The assumption, called parameter modularity says that, if variable $X$ in two different graph structures have the same parents, then the prior distribution over the parameters for $X$ are equal. Note that missing data can destroy parameter modularity as well as parameter independence [35] [arXiv:1302.4958]. Thus, to determine the prior for any parameter $X$ in a graph $s$ with parents ${\bf Pa}(X)$, we first find a complete graph that has an ordering where $X$ also has parents ${\bf Pa}(X)$ and then copy the prior for the parameters of $X$ from this complete graph structure to the prior for the parameters of $X$ in $s$. This procedure is illustrated for $n=2$ in Figure 18. The procedure only makes sense when the parameters for both complete graph structures satisfy parameter independence. For the case where $n=2$ and for the case with arbitrary $n$, the assumption of parameter independence for all complete graphs is essential for tractable assessment.

Finally, we need to assign a prior, $p(s)$, to every possible DAG model structure $s$. A uniform distribution is one possibility, and is often used. Another approach is to assess a prior Bayesian network as we have just discussed, and specify a distance metric between an arbitrary $s$ and the structure of this prior network to define the prior for $s$ [39].

Putting it altogether, the above description realizes the vision that Ross and I had years before: We can start with a prior Bayesian network and improve it with data. Dan and I extended this approach to include continuous variables with parameters described by a multivariate-Normal distribution. The conjugate distribution for these parameters is the Normal-Wishart and, like the finite-variable case, Dan and I developed a characterization of this distribution from an analogous assumption of parameter independence [26] [arXiv:2105.03248]. In addition, we showed that it is possible to derive parameter priors for all possible graph structures from a single Bayesian network and the assessment of two sample sizes, one for the Normal distribution and one for the Wishart distribution.

Now let’s consider learning fully causal models. To be concrete, I will describe learning fully causal models in simple form (where a model structure is depicted as a DAG over the domain variables). That said, the model in simple form can always be converted to an influence diagram as described in Section 3.4.

In [75] (second edition) [https://10.1007/978-1-4612-2748-9], Chris Meek, Greg Cooper, and I show how fully causal models can be learned from observational data only using essentially the same approach as that used to learn acausl models. The key takeaway is that learning takes place via the probabilistic semantics of the causal graph, not the causal semantics. In particular, the learning derives from the causal Markov assumption (Section 3.4), which states that arcs missing in the graph imply specific conditional independencies. Technically, learning also derives from the converse assumption that arcs present in the graph imply specific conditional dependencies. That said, this assumption, sometimes called the faithfulness assumption, is built into the parameter priors typically used for learning.

When learning causal and acausal DAG models, are the assumptions of parameter independence, parameter modularity, and parameter equivalence among graph structures with the same independence assertions reasonable? When learning causal DAG models, the assumptions of parameter independence and parameter modularity are often reasonable, due to the modularity often seen among causal relationships. Nonetheless, the assumption of parameter equivalence among graph structures that encode equivalent conditional independencies is not mandated. For example, the causal graphs $X\rightarrow Y$ and $X\leftarrow Y$ are not equivalent. In contrast, when learning acausal DAG models, the assumption of parameter equivalence follows from the semantics of acausal graph structures, whereas the assumptions of parameter independence and parameter modularity are less likely to apply than in the case of learning causal models. In general, applications of the assumptions need to be considered carefully.

Another key issue to consider when learning causal DAG models is the possible presence of confounders. We look at this issue in detail in Section 4.5.

Next, let’s consider the case of learning influence diagrams from data containing a mix of observations and interventions. The approach is similar to what we have just described for acausal DAG models with two exceptions. One, because utilities represent preferences, they are not learned—they are specified by the decision maker. Two, decision variables, by their nature, have no parameters to update and are root nodes in any possible influence-diagram structure. So, the task of learning influence diagrams from data boils down to learning causal structures for the domain’s uncertainty variables conditioned on its decision variables. If we assume that all decisions are made in each data sample and all uncertainty variables are observed in each data sample, make the assumptions of parameter independence and parameter modularity, and use conjugate priors, then we can learn influence diagrams using the the same techniques we have discussed for learning acausal DAG models.

The task of learning a fully causal model from a mix of observations and interventions is a simple special case. Here, only those observations of uncertainty variables whose corresponding force/set/do decisions have the value “no nothing” participate in the marginal likelihood. When a variable is forced to be a particular value, its observation provides no information about the relationship between the variable and its possible direct causes.

I seem to have been the first to describe learning in these two situations. For details, see [35] [arXiv:1302.4958].

As mentioned, one issue with fully causal models is that the force/set/do decision is typically not realized in practice. A notable exception is the learning of causal models relating the expression of various genes from a combination of observations and gene manipulations. In this case, the gene manipulations can be made in such a way as to directly affect only one gene and thus reflect a force/set/do decision. In collaboration with Amgen, I used this approach to learn causal models relating the expression of thousands of genes under various conditions related to drug design. Amgen has told me that the resulting models have been very useful to them [37].

In the 1990s, a strong negative correlation between consuming $\beta$-carotene and lung cancer was noted. This correlation prompted cereal companies to start adding $\beta$-carotene to their cereals and promoting that addition right on the box. A randomized trial published in 1996, however, produced strong evidence that $\beta$-carotene actually caused cancer [62]. Similarly, There was a well-known negative correlation between levels of HDL in the blood and heart attacks. So, over the last two decades, several companies developed drugs to raise HDL levels. Many of the drugs successfully increased HDL, but failed to suppress heart attacks (e.g., [70]). The drug companies lost billions of dollars.

What was going on? The answer lies in the fully causal models shown in Figure 19. In the case of $\beta$-carotene, an unobserved or hidden health lifestyle was causing $\beta$-carotene in the body to increase and also causing a reduction in cancer. In the HDL case, a hidden health lifestyle was causing an increase in HDL and a decrease in heart attacks. In each case, there was a hidden variable—a confounder—that was a common cause of two variables, thus inducing a correlation between them. When there were interventions on the supposed cause, the effect was not as anticipated. As the saying goes: “correlation is not causation.”

Of course, this issue has been known for almost a century, and the ideal solution for teasing out possible causation from correlation is to perform a randomized trial. An influence diagram (in plate notation) for a generic randomized trial that measures the causal effect of $X$ on $Y$ is shown in Figure 20. Here, a coin is flipped for each of $N$ subjects. Depending on the outcome of the flip, an intervention is performed that forces $X$ to be one of two values, and $Y$ is then observed. The randomized trial accurately assesses the causal effect of $X$ on $Y$, because the coin flip breaks the causal influence of the confounders on $X$. In effect, the coin flip is a force/set/do decision without the alternative of “do nothing.” Unfortunately, the randomized trial is often an unattainable ideal. Such trials can be extremely expensive. Sometimes, ethical considerations preclude a randomized trial (e.g., when attempting to determine the effects of smoking on cancer). Also, study subjects often fail to comply with the intervention.

All attempts to solve this problem involve making assumptions. Basically, the goal is for the analyst to construct an argument that people will accept. The more reasonable the assumptions, the greater the number of individuals who will accept the argument.

One solution is to replace the coin flip with a natural intervention. As shown in Figure 21, this variable is called an instrumental variable. In order for the instrumental variable to accurately uncover the causal effect of $X$ on $Y$, it must obey the independence assumptions shown in the figure. In particular, the instrumental variable must be independent of the confounder(s), and the instrumental variable must be independent of $Y$, given $X$ and the confounder(s). In addition, the instrumental variable must have a direct effect on $X$. One interesting point here is that, if there is no causal effect, and if the instrumental variable and $Y$ are independent, then the two independence assumptions are satisfied. So, in this case, the assumptions don’t need to be left to debate—they can be demonstrated with data.

Voight et al. [79] used genetic markers as instrumental variables to investigate the effects of HDL increasing drugs on the incidence of heart attack. (In general, when the instrumental variable is a genetic marker, this process is called Mendelian randomization.) He found genetic markers that had a direct effect on HDL but were independent of incidence, and thus concluded that raising HDL had no effect on incidence. If only this work had been done before the drug companies spent billions on drugs development.

Another common approach for dealing with confounders is to use observational data only, avoiding interventions, and assume that a complete set of relevant confounders are observed. ([75] second edition, p.209, and [64] second edition, p.79, provide an algorithm for identifying such a set.) In this approach, the causal effect of $X$ and $Y$ is estimated by weighting each observation with one over the probability of $X$ given the confounder(s). This approach, known as propensity score weighting, was first introduced by Robins and others in 2000 [68]. This approach has been typically applied to problems where $X$ is finite and has a relatively small number of values. Recently, however, Taha Bahadori, Eric Tchetgen, and I used deep learning to create an approach that can provide an accurate estimate when $X$ is continuous [5] [arXiv:2107.13068].

Another approach is to use DAG model learning that includes a deliberate search for confounders. Let’s consider an example taken from [36] [arXiv:2002.00269]. Sewell and Shah [71] measured the following variables for 10,318 Wisconsin high school seniors: Sex ($Sex$): male, female; Socioeconomic Status ($SES$): low, lower middle, upper middle, high; Intelligence Quotient ($IQ$): low, lower middle, upper middle, high; Parental Encouragement ($PE$): low, high; and College Plans ($CP$): yes, no. The data are described by the sufficient statistics in Table 1. Each entry denotes the number of cases in which the five variables take on some particular configuration. The first entry corresponds to the configuration SEX$=$male, SES$=$low, IQ$=$low, PE$=$low, and $CP$=yes. The remaining entries correspond to configurations obtained by cycling through the values of each variable such that the last variable (CP) varies most quickly. Thus, for example, the upper (lower) half of the table corresponds to male (female) students.