Reference no: EM131855056

Problem

It is often useful when learning the structure of a Bayesian network to consider more global search operations. In this problem we will consider an operator called reinsertion, which works as follows: For the current structure G, we choose a variable X_i to be our target variable. The first step is to remove the variable from the network by severing all connections to its children and parents. We then select the optimal set of at most K_p parents and at most K_c children for X and reinsert it into the network with edges from the selected parents and to the selected children. Throughout this problem, assume the use of the BIC score for structure evaluation.

a. Let X_i be our current target variable, and assume for the moment that we have somehow chosen U_i to be optimal parents of X_i. Consider the case of K_c = 1, where we want to choose the single optimal child for X_i. Candidate children - those that do not introduce a cycle in the graph - are Y₁, . . . , Y. Write an arg_max expression for finding the optimal child C. Explain your answer.

b. Now consider the case of K_c = 2. How do we find the optimal pair of children? Assuming that our family score for any {X_k, U_k} can be computed in a constant time f, what is the best asymptotic computational complexity of finding the optimal pair of children? Explain. Extend your analysis to larger values of Kc. What is the computational complexity of this task?

c. We now consider the choice of parents for Xi. We now assume that we have already somehow chosen the optimal set of children and will hold them fixed. Can we do the same trick when choosing the parents? If so, show how. If not, argue why not.