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 Xi®Xj
n    Complexity: O (#orderings · kn · cost of inference)