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)