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!
 A: 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.
A: 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?
