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 X
_{i}
,X
_{j}
n
kn pairs where possibly X
_{i}
®
X
_{j}
n
Complexity:
O
(#orderings
·
kn
·
cost of inference)