10th Recitation Review of Structure Learning for Bayesian Networks and k-Means and a little bit about EM 10-701/15-781 Machine Learning, Fall 2009

This is a set of notes, summarizing what we talked about in the 10th recitation. They are not meant to be rigorous, and are written informally, following what was discussed in class. Structure Learning of Bayesian Networks Up until now we focused on learning how to estimate the conditional probabilities tables (CPTs) of Bayesian networks, given that the structure is fixed. Sometimes the structure can be created (especially for small number of variables) manually, by encoding some prior knowledge about the variables in the form of independence assumptions. However, in the general case, we would like to have a way to learn the structure as well, and not just the CPTs. This is especially important in very big graphical models, where it is very hard to do it manually. The first thing we need to define is a criterion for how well a structure for a Bayesian network fits the data. A natural criterion is the log likelihood. So, let θ encode the CPTs for a given structure G, and let X1 to Xn be the variables in the graphical model. D will be training instances of the form {(x1,j,..., xn,j)} for j between 1 to N. Then, we ca