Contributor: Judea Pearl<\/p>\n
In comparing the tradeoffs between the structural\u00a0and potential outcome frameworks, I often state that the\u00a0two are logically equivalent yet poles apart in terms\u00a0of transparency and computational efficiency.\u00a0(See Slide #34 of the JSM tutorial). Indeed,\u00a0anyone who examines how the two frameworks\u00a0solve a specific problem from begining to end\u00a0(See, e.g., Slides #35-36 )\u00a0would find the differences astonishing.<\/p>\n
The question naturally arises:\u00a0How can two equivalent frameworks differ so\u00a0substantially in actual use.<\/p>\n
The answer is that epistemic equivalence does not\u00a0mean representational equivalence.\u00a0Two representations of the same information may\u00a0highlight different aspects of the problem and\u00a0thus differ substantially in how easy it is to solve a given\u00a0problem.\u00a0 This is a recurrent theme in complexity analysis,\u00a0but is not generally appreciated outside computer science.\u00a0We saw it in our discussions with\u00a0Guido Imbens who could not accept the fact that\u00a0the use of graphical models is a mathematical necessity\u00a0not just a matter of taste.\u00a0(http:\/\/causality.cs. The examples usually cited in complexity analysis are\u00a0combinatorial problems whose solution times depend\u00a0critically on the initial representation. I hesitated from\u00a0bringing up these examples, fearing that they will not be\u00a0compelling to readers on this blog who are more\u00a0familiar with classical mathematics.<\/p>\n Last week I stumbled upon a very simple example\u00a0that demonstrates representational differences\u00a0in no ambiguous terms;\u00a0I would like to share it with readers.<\/p>\n Consider the age-old problem of finding a solution to an\u00a0algebraic equation, say This is a tough problem for those of us who do not\u00a0remember Tartalia\u2019s solution of the cubic.\u00a0 (It can\u00a0be made much tougher once we go to quintic equation.)<\/p>\n But there are many syntactic ways of representing the same\u00a0function y(x)\u00a0. Here is one equivalent representation: The last representation permits an immediate solution,\u00a0which is: The example may appear trivial, and some may even\u00a0call it cheating, saying that finding x1<\/sub>, x2<\/sub>, and x3<\/sub>\u00a0is as hard as solving the original problem.\u00a0This is true, but the purpose of\u00a0the example was not to produce an easy solution to\u00a0the cubic. The purpose was to demonstrate that\u00a0different syntactic ways of representing the\u00a0same information (i.e., the same polynomial)\u00a0may lead to substantial differences in the complexity\u00a0of computing an answer to a query (i.e., find a root).<\/p>\n A preferred representation is one that makes\u00a0certain desirable aspects of the problem explicit, thus\u00a0facilitating a speedy solution.\u00a0Complexity theory is full of such examples.<\/p>\n Note that the complexity is query-dependent.\u00a0Had our goal been to find a value x that makes the polynomial y(x) equal 4, not zero, the representation above y(x) = (x-x1)(x-x2)(x-x3) would offer no help at all. For this query, the representation This simple example demonstrates\u00a0nicely the principle that makes graphical models\u00a0more efficient than alternative representations\u00a0of the same causal information, say a set of\u00a0ignorability assumptions.\u00a0What makes graphical models efficient is the fact that\u00a0they make explicit the logical ramifications of\u00a0the conditional-independencies conveyed\u00a0by the model. Deriving those ramifications by algebraic\u00a0or logical means takes substantially more work.\u00a0(See\u00a0http:\/\/ftp.cs.ucla. A typical\u00a0example of how nasty such derivations\u00a0can get is given in Heckman and Pinto\u2019s paper\u00a0on \u201cCausal Inference after Haavelmo\u201d (Econometric Theory, 2015).\u00a0Determined to avoid graphs at all cost,\u00a0Heckman and Pinto derived conditional independence\u00a0relations directly from Dawid\u2019s axioms and the Markov\u00a0condition (See\u00a0https:\/\/en.wikipedia.org\/
\n<\/span>y(x) = x3<\/sup>\u00a0+ ax2<\/sup>\u00a0+ bx + c = 0<\/p>\n
\ny(x) = x(x2<\/sup>+ax) + b(x+c\/b) = 0
\nand here is another:
\ny(x) = (x-x1<\/sub>)(x-x2<\/sub>)(x-x3<\/sub>) = 0,
\nwhere x1<\/sub>, x2<\/sub>, and x3<\/sub>\u00a0are some functions of a, b, c.<\/span><\/p>\n
\nx=x1<\/sub>, x=x2<\/sub>, x=x3<\/sub>.<\/p>\n
\ny(x) = (x-z1<\/sub>)(x-z2<\/sub>)(x-z3<\/sub>) + 4 \u00a0
\nwould yield an immediate solution
\nx=z1<\/sub>, x=z2<\/sub>, x=z3,<\/sub>
\nwhere z1<\/sub>, z2<\/sub>, and z3<\/sub>\u00a0are the roots of\u00a0another polynomial:
\nx3<\/sup>\u00a0+ ax2<\/sup>\u00a0+ bx\u00a0+ (c-4) = 0<\/span><\/p>\n