Here is a simple example, which I found here, modified somewhat to be in line with my previous example related to rain.
What we want to know is this: when I wake up tomorrow morning, what is the probability that I will hear a rain-like tapping sound on my roof? One of the things we might think is important is the weather forecast. Is it projected to be cloudy? If so, it’s more likely to rain, which increases my chances. Another important item to consider is that where I live, there is a horde of rabid squirrels who often run on the roof in preparation for attack, yet strangely they don’t come out much if it’s cloudy.
So we make a model with a total of 4 boolean (TRUE/FALSE) variables: Is it cloudy (C)? Is it raining (R)? Are there rabid squirrels out (S)? And is there a Tapping Sound (TS) on my roof? The relationships between these are stored in a set of Conditional Probability Tables (CPTs) shown in the picture below.
The first of these tables says that there is a 50% chance of being cloudy or not cloudy (I can change this as desired). The CPT on the right shows the conditional probability of variable Rain being true or false, depending on the value of the variable Cloudy (more likely Rain is True if Cloudy is True). The CPT on the left shows that if Cloudy is True, Squirrel is likely to be False (as squirrels don’t like the clouds), but if Cloudy is False, Squirrel is equally likely to be True or False. The bottom CPT shows the probability of Tapping Sound being True given the values of Squirrel and Rain.
Alright now that we’ve got our Bayesian net set up, we want to use it. Here we’ll use it as follows: we present evidence, which are known fixed values of one or more of our boolean variables, and we want to compute the Most Probable Explanation consistent with that evidence. For example, if I provide the evidence that Tapping Sound is True, the Most Probable Explanation is that Rain and Squirrel are both True, and Cloudy is False (note this may not be completely obvious, and depends on the numerical values we assign to the CPTs).
Let’s convert this problem to Weighted MAX-SAT. Using the prescription in the paper cited in the previous post. The idea is very simple. For every row in every CPT, create a clause formed of the negation of all the variables OR’ed together, and raise this clause to – log of the probability associated with that row. For example, I have my Cloudy CPT, whose first row is
So I make a clause like .
When I have more variables influencing the probability I get more variables in the clause. For example If I have a CPT entry, for Rain,
C R Pr(R|C)
c r 0.8
ie if C is True, the probability of R being true also is 0.8, then I create a clause
After I’m done creating all of these clauses, I AND them all together, and that’s my Weighted MAX-SAT problem, which we can then run directly on the hardware!
I coded all this up in Matlab and ran it on the hardware. It works! See Bayesian networks are exciting!