Problem

This problem considers the performance of various types of structure search algorithms. Suppose we have a general network structure search algorithm, A, that takes a set of basic operators on network structures as a parameter. This set of operators defines the search space for A, since it defines the candidate network structures that are the "immediate successors" of any current candidate network structure-that is, the successor states of any state reached in the search. Thus, for example, if the set of operators is {add an edge not currently in the network}, then the successor states of any candidate network G is the set of structures obtained by adding a single edge anywhere in G (so long as acyclicity is maintained). Given a set of operators, A does a simple greedy search over the set of network structures, starting from the empty network (no edges), using the BIC scoring function. Now, consider two sets of operators we can use in A. Let A[add] be A using the set of operations {add an edge not currently in the network}, and let A_[add,delete] be A using the set of operations {add an edge not currently in the network, delete an edge currently in the network}.

a. Show a distribution where, regardless of the amount of data in our training set (that is, even with infinitely many samples), the answer produced by A[add] is worse (that is, has a lower BIC score) than the answer produced by A_[add,delete] . (It is easiest to represent your true distribution in the form of a Bayesian network; that is, a network from which the sample data are generated.)

b. Show a distribution where, regardless of the amount of data in our training set, A_[add,delete] will converge to a local maximum. In other words, the answer returned by the algorithm has a lower score than the optimal (highest-scoring) network. What can we conclude about the ability of our algorithm to find the optimal structure?