A Simple Bayesian Network

Figure 14: (a) An example Bayesian network. (b) A factor graph representation of the Bayesian network.

Judea Pearl's classic example of a Bayesian network is a burglar alarm that can be triggered by either an earthquake or a burglar [17]. The network has three binary random variables: one for the burglar marked ``b," one for the earthquake marked ``e," and one for the alarm marked ``a." This network and its factor graph representation are shown in figure 14. Frey has extended this example to include the following conditional probability relationships, which I have further modified [2]:

$$p(b = 1) = 0.5$$

$$p(e = 1) = 0.1$$

$$p(a = 1 \vert b = 0, e = 0) = 0.15$$

$$p(a = 1 \vert b = 0, e = 1) = 0.15$$

$$p(a = 1 \vert b = 1, e = 0) = 0.368$$

$$p(a = 1 \vert b = 1, e = 1) = 0.607$$

To build this network as a circuit, we map the two types of circuits described in the previous section onto the factor graph shown in figure 14b. If we first look at the downwards path of the sum-product algorithm marked 1 - 3, we see that messages are passed through all six nodes. Three are of them are function nodes and three are variable nodes. Recall from section 4 that function nodes send messages to variables and variable nodes send messages to functions. The algorithm dictates that messages are sent once down the network until they reach a node with only one neighbor, and then back up to the top of the network where they are absorbed at their origin.

In the burglar alarm example, message passing starts with the function nodes marked ``E" and ``B." Each message is shown with a numbered arrow indicating its direction and order in which it is sent. We start with the circuits that implement the first two messages sent. Because these circuits do not need to have any inputs, they may be built in several different ways. One way is to build them in form of the function-to-variable circuits described previously, but with one input rather than two. The input can then be the apriori knowledge that $p(b = 1) = 0.5$ or $p(e = 1) = 0.1$ generated by some reference current source, and its output is the same. These nodes only contain four current mirrors as no multiplication or scaling is needed. This circuit is shown in figure 15.

Figure 15: Schematic for a one-input, one-output variable-to-function of function-to-variable circuit for the sum-product algorithm.

A second option is to build them with no inputs as they are represented in the factor graph. This type of circuit could take a reference current and divide it with some form of scaling to generate a message. A final option is to omit these two nodes from the graph as they do not perform any calculation. In this case, a message can be generated by some type of current source and fed directly into the next node. This is the best choice because it makes the network smaller, faster, and more accurate.

The next pair of messages from the ``b" and ``e" variables to the ``A" function are essentially the same. No marginalization is required in either node as they only have one input. Any of the three options described for the generation of the first messages also apply to these messages.

The generation of the third message, which occurs within the ``A" function, requires the type of sum-product marginalization described previously. A two-input, one-output function-to-variable circuit for the generation of this message is shown in figure 12. The inputs to the circuit are connected to the outputs from the variable-to-function circuits for ``b" and ``e." The inputs marked $p(x = 0)$ and $p(x = 1)$ correspond to the message from ``b," and $p(y = 0)$ and $p(y = 1)$ correspond to the message from ``e." A mirror image of these currents is created so that they may be multiplied. These mirror-image currents are marked $I_{1}$ and $I_{2}$ in figure 12. The first level of multiplication, $p(b) \cdot p(e)$, is performed by the partial Gilbert multiplier circuits. These products are the currents marked $I_{3}$ - $I_{6}$, where:

$$I_{3} = p(b = 0)p(e = 0) = (0.5)(0.9) = 0.45$$

$$I_{4} = p(b = 0)p(e = 1) = (0.5)(0.1) = 0.05$$

$$I_{5} = p(b = 1)p(e = 0) = (0.5)(0.9) = 0.45$$

$$I_{6} = p(b = 1)p(e = 1) = (0.5)(0.1) = 0.05.$$

The second level of multiplication, $p(b)p(e) \cdot f(a,b,e)$, is accomplished by scaling in the current mirrors. This scaling appears in the currents marked $I_{7}$ - $I_{14}$ where:

$$I_{7} = p(b = 0)p(e = 0)f(a = 0, b = 0, e = 0) = (0.5)(0.9)(0.85) = 0.3825$$

$$I_{8} = p(b = 0)p(e = 0)f(a = 1, b = 0, e = 0) = (0.5)(0.9)(0.15) = 0.0675$$

$$I_{9} = p(b = 1)p(e = 1)f(a = 0, b = 1, e = 1) = (0.5)(0.1)(0.395) = 0.0198$$

$$I_{10} = p(b = 1)p(e = 1)f(a = 1, b = 1, e = 1) = (0.5)(0.1)(0.607) = 0.0304$$

$$I_{11} = p(b = 0)p(e = 1)f(a = 0, b = 0, e = 1) = (0.5)(0.1)(0.85) = 0.0425$$

$$I_{12} = p(b = 0)p(e = 1)f(a = 1, b = 0, e = 1) = (0.5)(0.1)(0.15) = 0.0075$$

$$I_{13} = p(b = 1)p(e = 0)f(a = 0, b = 1, e = 0) = (0.5)(0.9)(0.632) = 0.2844$$

$$I_{14} = p(b = 1)p(e = 0)f(a = 1, b = 1, e = 0) = (0.5)(0.9)(0.368) = 0.1656$$

The summing of the terms occurs through the shorting of the wires. The results at the outputs are these sums, marked $p(z = 0)$ and $p(z = 1)$, comprise the message that is sent to the variable ``a." Their values are:

$$p(z = 0) = I_{7} + I_{9} + I_{11} + I_{13} = 0.7291$$

$$p(z = 1) = I_{8} + I_{10} + I_{12} + I_{14} = 0.2710$$

This brings us to the message marked 4 in figure 14, which is just a reflection of the message sent from the function ``A." Returning to ``A", we break from the strict factor graph representation. Rather than having each node be a complex circuit that can generate all of the messages that it sends during the sum-product algorithm, we have several simple circuits that generate only one type of message. For ``A", we actually build three separate circuits because it sends three messages during the course of the algorithm. The first of these messages has been covered explicitly, and the other two are generated in exactly the same way, but with different inputs and outputs.

The final messages, marked 6, are copies of the inputs to the ``b" and ``e" variables. These can be implemented with the identity circuit or omitted to create a simpler circuit with greater accuracy.