The Algorithm
n Sample orderings
n Compute ExPLoss for each query
n Choose query that minimizes ExPLoss
n Cost of computing ExPLoss() for fixed ordering:
n Cost of Bayesian network inference for each pair Xi,Xj
n kn pairs where possibly XiXj
n Complexity: O (#orderings kn cost of inference)