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 Xi 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 Kp parents and at most Kc 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 Xi be our current target variable, and assume for the moment that we have somehow chosen Ui to be optimal parents of Xi. Consider the case of Kc = 1, where we want to choose the single optimal child for Xi. Candidate children - those that do not introduce a cycle in the graph - are Y1, . . . , Y. Write an argmax expression for finding the optimal child C. Explain your answer.
b. Now consider the case of Kc = 2. How do we find the optimal pair of children? Assuming that our family score for any {Xk, Uk} 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.