Finding the Most Probable Explanation using a quantum computer II: An example

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

C    Pr(C)

c     0.5

So I make a clause like (\bar{c})^{-\log 0.5}.

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

(\bar{c} V \bar{r})^{-\log 0.8}.

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!

6 thoughts on “Finding the Most Probable Explanation using a quantum computer II: An example

  1. I’m glad you enjoy Bayesian nets too. If you want to continue learning about them, I’ll give you some pointers.

    (1)I recommend the following very fun and instructive exercise. There are many software programs that implement Bayesian nets. Download one of them and go through its tutorial. For example, you could try Netica, which is free with a limitation of <=15 nodes. Hugin is another famous one.

    (2)You can go back and forth from a directed graph (called a Bayesian network) to an undirected graph (called a Markov random field). This conversion might be useful in D-wave algorithms. You can learn all about this in Koller & Friedman's excellent book.

    (3) The Koller &Friedman book also explains how one can machine learn a Bayesian network from data

    (4)In general, doing inference with a Bayesian network is NP-hard. Software like Netica and Hugin use an exact algorithm invented by Lauritzen and Spiegelhalter in 1988. The L&S algorithm is pretty fast, but still NP-hard. Therefore, for large networks, the L&S algorithm crawls to a halt, and one uses instead an approximate algorithm such as Gibbs sampling. For example, the software WinBUGS is a Gibbs sampler for doing inference with Bayesian nets

  2. Cool, thanks! I found a free matlab toolbox http://code.google.com/p/bnt/ have you tried it? Is it any good? I’ll pick up a copy of the Koller & Friedman book.

    I’m looking for lists of commercial applications of Bayesian approaches, do you know of any good pointers for where I can find such things?

  3. I haven’t tried the matlab tool box but I’m sure it’s pretty good. it was written by Kevin Murphy, about whom I wrote a blog entry

    The Koller & Friedman book is a good “encyclopedic” reference (1200 pages!). I’ve only read parts of it. It’s not the type of book that I would read straight through all at once, but it might be nice to have one copy in your Lab for people to consult when the need arises

    There are numerous commercial Bayesian applications. For example: Google uses it to correct your spelling. Autonomy, UKs largest software company, uses it in its search engines for legal searches and defense related searches. Also, Microsoft is very keen on Bayesian inference and is developing a C# class library called infer.net. And of course, it’s extensively used by statisticians of all stripes (bioinformaticists, astronomers, particle physicists, cosmologists, geologists, economists, hedge fund managers…).

  4. Hi Geordie,

    I have to admit that I only understood 30% of the previous post, but now that you’ve put the picture of the rabid squirrel I now get it!(I’m dead serious) Lol

    The MPE can be used to solve cool problems finance problems, especially those involving correlations between asset classes, and currency pairs – which have been exhibiting weird behaviors off-late (e.g. gold and the USD normally have an inverse relationship, but they have recently been moving in tandem!).

    Now the challenge is a refresher course on Bayes Theory!

    -Craig

    P.S. Have you tried the hardware on quantum random walk models?

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s