# Why do structure learning for Bayesian networks?

Given a very-large data set, if our goal is to do probabilistic inference, what are the main advantages of learning a Bayesian network from data and then, use the Bayesian network to compute conditional probabilities? I see that we could also approximate these probabilities directly from the data set by counting. Further, if the data set is large enough, one could also try to use the CLT/WLLN to compute some confidence intervals. Why would it be better to construct a Bayesian network (hard optimization problem) and do inference (message passing algorithms)? Some kind of over-fitting argument?

Thanks!

• Suppose I have $p = 100$ binary variables. Then there will be $2^{100}$ possible combinations, and effectively $2^{100} - 1$ free parameters. Counting is out of the question because I'm not going to have enough data to estimate all $2^{100}$ possible combinations. An appropriate graphical model, however, will drop the dimensionality down substantially (the amount by which depending on how densely connected the graph is). – guy Aug 23 '14 at 5:22
• @DJohnson, please do not approve these edits spamming the main page w/o proper discussion. – gung - Reinstate Monica May 1 '16 at 20:20

Great question! From what I've seen, folks usually do inference given the structure and assume the structure is a given. I haven't seen folks do structure learning (which is a hard problem as you and others have pointed out) just for doing inference.

Bayesian networks encode conditional independence structure, so learning the structure is useful if you want to understand/explain the dependencies between random variables. For instance, if you have three random variables (smoking, tar in lungs, cancer) it's highly likely you will find that all these variables are associated with one another (i.e., taken pairwise, the variables are not independent of each other). However, if you do structure learning, you might also learn the fact that smoking is independent of cancer given the amount of tar deposits in lungs.

With background and domain knowledge it might also be possible to use the Bayesian network structure to convincingly argue or support causal hypotheses.

• The smoking tar cancer example was used by Pearl to demonstrate how his casual calculus can be used to demonstrate casual conclusions (smoking causes cancer) from observational data and minor casual assumptions (namely that tar can only be caused by smoking) – Neil G Jan 14 '16 at 12:32

In a Bayesian Belief Network (BBN), the joint probability can be decomposed. Assume the following.

• U = {X1, X2, X3, X4 }, U is a set of variables
• P(U) = P(X1, X2, X3, X4), P is the joint probability

Using the chain rule, you can decompose the P as follows

$P(U) = P(X1, X2, X3, X4) = P(X1)P(X2|X1)P(X3|X1,X2)P(X4|X1,X2,X3)$

Because a BBN satisfies the Markov condition, you can decompose P as follows.

$P(U) = \prod_i P(X_i|pa(X_i))$

Let's just say the BBN structure, its directed acyclic graph (DAG), is indeed the following.

X1 -> X2 -> X3 -> X4

Then,

$P(U) = P(X1, X2, X3, X4) = P(X1)P(X2|X1)P(X3|X2)P(X4|X3)$

Do you see any efficiency of computing P by using the the Markov condition versus the Chain Rule?

A more concrete example. Let's say all variables are binary and take on the values yes/no. Let's say you observe

• X1=yes, X2=yes, X3=no,

and you want to predict the states of X4. How would you do this?

If you did not have the structure (DAG), then you can do counts (as you stated in your post) to compute the conditional probabilities.

$P(X4=yes | X1=yes, X2=yes, X3=no)$

and

$P(X4=no | X1=yes, X2=yes, X3=no)$

But, if you do have the DAG, you know you can do the following.

$P(X4=yes | X3=no)$

and

$P(X4=no | X3=no)$

Which is faster to compute, even if you are just counting, with or without the DAG?

• How do you know that your joint distribution factorizes like that? – Vladislavs Dovgalecs Nov 12 '15 at 22:34
• This is all true, bit I don't see how it answers the question. – Neil G Jan 14 '16 at 12:30