Observation Subset Selection as Local Compilation of Performance Profiles
This work addresses the challenge of efficient measurement selection in decision-making under uncertainty, which is incremental as it builds on existing performance profile and local compilation methods.
The paper tackles the problem of selecting an optimal subset of measurements under dependencies modeled by tree-shaped Bayesian networks, developing approximation algorithms that generalize anytime algorithm composition by relaxing monotonicity assumptions and extending local compilation techniques. The result includes applications to maximizing expectation in binary-valued BNs and minimizing worst variance in Gaussian BNs, though no concrete numerical results are provided.
Deciding what to sense is a crucial task, made harder by dependencies and by a nonadditive utility function. We develop approximation algorithms for selecting an optimal set of measurements, under a dependency structure modeled by a tree-shaped Bayesian network (BN). Our approach is a generalization of composing anytime algorithm represented by conditional performance profiles. This is done by relaxing the input monotonicity assumption, and extending the local compilation technique to more general classes of performance profiles (PPs). We apply the extended scheme to selecting a subset of measurements for choosing a maximum expectation variable in a binary valued BN, and for minimizing the worst variance in a Gaussian BN.