I've been trying to learn how belief propagation works. Specifically whether it would work as a SAT solver. Some of my research suggests this is possible. However, I'm really struggling to understand whether it's the right tool for the job or whether my implementations are just incorrect. Unfortunately, most references are heavy on the mathematical formulas and I'm really rusty at reading those, so I feel like maybe I've missed something. And it seems like some references use different terminology or don't even mention things like conditional probability tables.
As a really simple example, I've been trying to solve this formula:
C = A or B
Before doing belief propagation, I wrote out the truth table so I would know what to compare against:
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
From that, I think I can calculate the probabilities of everything which is what I've been using to compare against the results of the belief propagation algorithm. If I understand correctly, the probabilities are:
P(A=true | C=true) = 2/3
P(B=true | C=true) = 2/3
P(A=false | C=true) = 1/3
P(B=false | C=true) = 1/3
P(A=true | C=false) = 0
P(B=true | C=false) = 0
P(A=false | C=false) = 1
P(B=false | C=false) = 1
For purposes of this example, I think choosing to solve for C=true is more interesting, so let's do that.
Here's the logic I've followed to use belief propagation:
Step 1: Set initial likelihoods.
All likelihoods of input variables are set to 1.0 for both false and true states since we don't know anything about their likelihood initially. In the arrays, the first number is for the false state, second is for true state.
Likelihood(A) = [1.0, 1.0]
Likelihood(B) = [1.0, 1.0]
Step 2: Set initial priors.
My understanding is the only initial prior(s) are for the nodes that you know the value of already. In this case, since we want to solve for C=true:
Priors(C) = [0.0 1.0]
Step 3: Define conditional probability tables.
Here I believe both A and B get their own probability tables. They both happen to look the same. I've written P(A|C) and P(B|C) because I've read this is the probability table of the variable given all it's parents.
| A | C | P(A|C) |
|---|---|---|
| 0 | 0 | 1.0 |
| 0 | 1 | 0.5 |
| 1 | 0 | 0.0 |
| 1 | 1 | 0.5 |
| B | C | P(B|C) |
|---|---|---|
| 0 | 0 | 1.0 |
| 0 | 1 | 0.5 |
| 1 | 0 | 0.0 |
| 1 | 1 | 0.5 |
Step 4: Send messages to parents.
Message from A to C:
[
P(A=false|C=false) * Likelihood(A=false) + P(A=true|C=false) * Likelihood(A=true),
P(A=false|C=true) * Likelihood(A=false) + P(A=true|C=true) * Likelihood(A=true),
]
= [1.0 * 1.0 + 0.0 * 1.0, 0.5 * 1.0 + 0.5 * 1.0]
= [1.0, 1.0]
Message from B to C:
[
P(B=false|C=false) * Likelihood(B=false) + P(B=true|C=false) * Likelihood(A=true),
P(B=false|C=true) * Likelihood(B=false) + P(B=true|C=true) * Likelihood(A=true),
]
= [1.0 * 1.0 + 0.0 * 1.0, 0.5 * 1.0 + 0.5 * 1.0]
= [1.0, 1.0]
Step 5: Send messages to children.
Message from C to A:
[
Message from B to C(false) * Prior(C=false),
Message from B to C(true) * Prior(C=true)
]
= [1.0 * 0.0, 1.0 * 1.0]
= [0.0, 1.0]
Message from C to B:
[
Message from A to C(false) * Prior(C=false),
Message from A to C(true) * Prior(C=true)
]
= [1.0 * 0.0, 1.0 * 1.0]
= [0.0, 1.0]
Step 6: Calculate beliefs.
Belief(A) = Likelihood(A) * Message from C to A
= [1.0 * 0.0, 1.0 * 1.0]
= [0.0, 1.0]
Belief(B) = Likelihood(B) * Message from C to B
= [1.0 * 0.0, 1.0 * 1.0]
= [0.0, 1.0]
At this point, my belief propagation algorithm says there's a 100% chance A is true and a 100% chance B is true, which doesn't match what I'm expecting. If I solve for C=false, I do get what I'm expecting.
Is there something wrong with the steps I took, or is this just not going to give me the answer I expect for some reason?
