Prolog Trick

My misunderstanding about the nature of the prolog trick has been cleared up a bit, and it is time for an analysis of just what the idea is.

Previously, I thought that the basic idea was simply to construct Bayesian Networks incrementally with a backward-chaining type search inspired by Prolog. However, this is just a part of the idea. The more important thing is the way the probabilities are calculated incrementally as the search progresses. Here's how it works if we support only deduction, not abduction (ie, we only follow baye's net arrows in one direction):

We have a query node, call it A. We might find B&C->A, making new query nodes B and C. We then might find X&Y->C, and find X, and find Y. At this point we have enough information to propagate forward from X and Y to C. We check whether we have enough to propagate even further, but we do not, so we continue the network construction. We could then find B, which would give us enough to propagate again; when we do so, we get A, so we are done.

"Finding X" here means finding a stored probability for the statement X, and propagating along X&Y->C means using the conditional table stored in that BN link to compute a probability distribution for  C.

Now, the interesting thing is, what we're doing here is a single pass of the belief propagation algorithm. A single pass like this is what you do if you only want to marginalize one variable, and of the network you've got is a tree. If you want to marginalize all the variables in a tree, all you need is a second pass, going in the opposite direction; this finishes off the computation for all the other variables with just twice the work. But, no need for twice the work if we only want the one!

If the network isn't a tree, then belief propagation is no longer guaranteed to be correct, but it's been shown that multiple passes (keep doing passes until the numbers appear to converge) can generate good approximations of the correct probabilities in practice. (The exact conditions in which this happens are not well-understood). The prolog trick still just does a single pass for non-tree-like situations, so (in a not-well-understood subset of cases) we should expect worse approximations than we'd get with a bunch of passes. However, one pass will obviously be quicker than a bunch, and it seems reasonable (to me) to expect somewhat graceful degradation.

In any case, here is how you do it. Suppose that node C is connected to rules C&D->A, C&E->B, and F&G->C. We know E, B, F, and G, and from that want to compute C. Suppose also that A is the node which C was invoked in order to estimate, so (via the rules of belief propagation) we ignore it in coming up with our estimate of C. So, then, how do we calculate C?

The basic idea is that we regard the messages coming down as priors and the messages coming up as likelihoods, so (applying Baye's rule) we just multiply them together to get the posterior. That is: the link F&G->C combined with the probabilities F and G will generate a probability for C, call it the "prior" (but keep in mind we're just temporarily treating it as a prior; it's not the prior of C in any long-term sense; indeed, it's an estimate given some evidence). This is a list of C's values and probabilities for each. Using the link C&E->B plus our knowledge of E and B, we can generate a likelihood function: a list of C's values with a probability of the evidence we have concerning B for each. I am going to grind in basic Baye's Law stuff for a sec, in case any readers don't "get it" yet: this is not a probability function. It does not necessarily sum to 1. It is a likelihood function, which means it measures how well different possible values of C would explain the evidence. We multiply it component-wise by the prior on C and normalize the vector to obtain the updated estimate on C (the posterior).

An example. Let's just suppose all these variables have just two states, true and false. Suppose F&G->C stores the following table of probabilities for C being true, given combinations of F and G:

F and G:.1
F and not G: .2
not F, but G: .3
neither F nor G: .4

Then, suppose that we find G and F both have probability .5. We calculate the "prior" for C being true as .025 + .05 + .075 + .1 = .25, with the value for C being false coming to .75 similarly (or by just taking 1-.25).

Now, suppose C&E->B stores the following probabilities for B:

C and E: .6
C but not E: .7
not C, but E: .8
neither C nor E: .9

Further suppose we know that B and E have probability 1. We calculate the likelihood for C being true as .6, and the likelihood for C being false as .8. [The likelihood of C being true will be: ((the probability of B being true supposing C is true and using our probability for E being true or false) times (the probability we had for B being true to start with)) plus ((the probability of B being false supposing C is true and using our probability for E being true or false) times (the probability we had for B being false to start with)). The likelihood for C being false will be the same replacing "supposing C is false" with "supposing C is true".]

Now, we multiply the two vectors together and normalize! The prior is [.25, .75] and the likelihood is [.6, .8]. Multiplying, we get [.15, .6]. Normalizing, we get [.2, .8], which is our final message for C which we'd pass along to help construct a probability for A.

To sum up: adding abduction to the prolog trick calculations can be accomplished via the belief prop rule, which says to multiply the deductive value (what I called the "prior" value) by a likelihood vector, and then normalize the resulting vector.