### Progic VI

#### Posted by David Corfield

I talked about Bayesian networks back here as a prelude to the shift from propositional to first-order relational structures. But before we take that step, it’s worth mentioning that there are other graphical models used in probabilistic reasoning. (If you prefer videos try this or this.)

In particular, there’s a class of models called Markov networks, which unlike Bayesian networks involve undirected edges. Given an undirected graph, a distribution is given by assigning non-negative real functions, $\phi_k$, to cliques, $k$, in the graph. These are called *potential functions*.

Then the probability of the node variables being in a given state is given by the product of the potential functions evaluated at the corresponding clique states, divided by a normalizing factor. All of which should put you in mind of certain models from statistical physics.

What Markov networks can’t represent is the classic Bayesian network converging arrows situation, where a variable, $C$, has two independent causes, $A$ and $B$. Whereas $P(A, B) = P(A) \cdot P(B),$ it is not the case that $P(A, B | C) = P(A | C) \cdot P(B | C).$ The best a Markov network can do is form a complete graph on $A$, $B$ and $C$.

On the other hand, where Markov networks can surpass Bayesian networks is in situations of cyclic dependency. The most natural illustration of this structure involves four heterosexual people, but as this is a family blog, let’s do this with infected computers. So we have personal computers $A$ and $B$, and servers, $C$ and $D$. Each computer is connected to the two servers, and *vice versa*, but the computers aren’t directly connected, nor are the servers.

Then we have independencies such as $P(A is infected| B, C, D are infected) = P(A is infected| C, D are infected),$ which are not representable by Bayesian networks.

So, neither Bayesian networks nor Markov networks capture all the independencies you might wish to represent. But graphical modellers haven’t stopped there. There are also factor graphs and their cousins *directed* factor graphs. Then there are chain graphs, which allow directed *and* undirected edges in the same graph. I’d like a clearer picture of how these models related to each other.

## Re: Progic VI

Markov Nets and Bayesian nets are very closely related and one can easily move from one to another.

Lauritzen and Spiegelhalter’s Junction Tree Algorithm for computing probabilities in a Bayesian net first converts the Bayesian net to a Markov net. Going the other way round, a maximum entropy probability distribution is most naturally represented by a Markov net, but one can straightforwardly convert that to a Bayesian net representation, called an Objective Bayesian Net.

For probability logic it is often important to use another kind of network representation. If one is given premiss sentences and their probabilities, then these constrain a closed convex set of probability functions (a *credal set*). This set is most naturally represented by a *credal net*, which looks like a Bayesian net but contains probability intervals rather than probabilities in the probability tables. See here.

Some colleagues and I are currently working out how to use credal nets for inference in probability logic, in our progicnet project.