PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Value of Information in Graphical Models

Andreas Krause, Carlos Guestrin

arXiv:1401.3474v1cs.AI

TL;DR

Expensive observations must be selected to improve expected utility, while common heuristic selection procedures lack general performance guarantees. The paper develops optimal algorithms for observation selection in chain graphical models and proves that value-of-information problems remain computationally hard in polytrees and Naive Bayes models.

  • Problem

    Choosing among costly observations matters in settings such as sensor networks and medical testing, where heuristic selection is commonly used but lacks general performance guarantees.

    Source: §1 · pp. 1–2

  • Method

    The paper uses dynamic programming to optimize value of information on chains, covering fixed observation subsets and conditional plans, and applies the algorithms to sensor scheduling extensions.

    Source: §1 · p. 2, §7 · p. 20

  • Results

    Selecting the best k observations is NPPP-complete for discrete polytrees, and evaluating decision-theoretic value of information is #P-complete for Naive Bayes models.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The algorithms improve on commonly used heuristics for decreasing expected uncertainty and can enhance interactive structured classification tasks.

    Source: §9 · p. 28

    The multi-sensor approximation has no general performance guarantee when sensors are correlated, although independent sensors yield an optimal solution.

    Source: §7.1 · p. 22

Abstract

from arXiv · show

Many real-world decision making tasks require us to choose among several expensive observations. In a sensor network, for example, it is important to select the subset of sensors that is expected to provide the strongest reduction in uncertainty. In medical decision making tasks, one needs to select which tests to administer before deciding on the most effective treatment. It has been general practice to use heuristic-guided procedures for selecting observations. In this paper, we present the first efficient optimal algorithms for selecting observations for a class of probabilistic graphical models. For example, our algorithms allow to optimally label hidden variables in Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan. Furthermore we prove a surprising result: In most graphical models tasks, if one designs an efficient algorithm for chain graphs, such as HMMs, this procedure can be generalized to polytree graphical models. We prove that the optimizing value of information is $NP^{PP}$-hard even for polytrees. It also follows from our results that just computing decision theoretic value of information objective functions, which are commonly used in practice, is a #P-complete problem even on Naive Bayes models (a simple special case of polytrees). In addition, we consider several extensions, such as using our algorithms for scheduling observation selection for multiple sensors. We demonstrate the effectiveness of our approach on several real-world datasets, including a prototype sensor network deployment for energy conservation in buildings.

1. Introduction

The paper develops optimal observation-selection methods for chain graphical models and examines how far those methods extend. It also establishes severe complexity barriers for value-of-information optimization and evaluation in broader graphical models.

1. Introduction

  • The authors present the first efficient optimal algorithms for nonmyopic value-of-information optimization on chains, including subset selection and conditional plans for HMMs.The approach is called VOIDP because it uses dynamic programming to optimize value of information.Source: §1 · p. 2
  • Selecting the best k observations is NPPP-complete for discrete polytrees, while evaluating value-of-information objectives is #P-complete even for Naive Bayes models.The paper notes that Naive Bayes is a frequently used special case of polytrees.Source: §1 · p. 2
  • For multiple correlated sensors, the paper reports that optimal scheduling is wildly intractable and uses single-sensor algorithms to approximately optimize schedules.The approach is demonstrated on a real sensor-network testbed for building management.Source: §1 · p. 2
  • The paper evaluates its algorithms on real-world problems, including sensor scheduling on a testbed and active labeling in bioinformatics and natural-language processing.The introduction also reports evaluation on three real-world datasets and suitability for interactive classification of sequential data.Source: §1 · pp. 2–3

2. Problem Statement

The paper formulates observation selection as maximizing expected reward after observing variables, with choices that can be fixed in advance or adapted to observed outcomes. It describes several reward criteria and allows observation costs to be represented as penalties or budgets.

2. Problem Statement

  • A world state is represented by variables with a prior distribution, and observation selection seeks expected posterior reward through either a fixed subset or a sequential, observation-dependent plan.The paper generally assumes discrete variables, though it notes that some algorithms extend to continuous distributions.Source: §2 · pp. 3–4

2.1 Optimization Criteria

  • Reward criteria include reducing residual entropy and using local rewards to optimize joint entropy through the entropy chain rule.The paper also describes margins for structured classification, weighted mean-squared error for continuous variables, and rewards for detecting critical regions.Source: §2.1 · pp. 5–6

2.2 Cost of Selecting Observations

  • Observation costs can reduce reward as penalties or constrain selection through a total budget.The paper also allows penalties and costs to depend on the state of the world, such as test risks that vary with a patient's illness.Source: §2.2 · p. 7

3. Decomposing Rewards

The paper’s key insight is that local rewards in chains depend only on nearby observed variables, allowing total rewards to decompose and support efficient nonmyopic optimization. The framework covers both filtering and smoothing, including hidden-state observations in HMMs.

3. Decomposing Rewards

  • The decomposition applies to chain-structured hidden variables in HMMs, where expert labels can be selected in addition to observed emissions.Source: §3 · p. 7
  • For filtering, local rewards condition only on observations up to the current variable, whereas smoothing can use observations on either side.Source: §3 · pp. 7–8
  • In smoothing, observing X4 splits the reward for chain 1:7 into rewards for chains 1:4 and 4:7, plus X4’s immediate reward minus its observation cost.Source: Figure 2 · p. 8, §3 · p. 8
  • Conditional independence means an unobserved variable’s reward depends only on its nearest observed neighbor, or its nearest observed neighbors on both sides for smoothing.This locality enables the chain decomposition used by the optimization algorithms.Source: §3 · p. 8

4. Efficient Algorithms for Optimizing Value of Information

The section develops dynamic programming algorithms that exploit reward decomposition to optimize observation subsets and conditional plans in chains, then extends the approach to trees with few leaves. Its guarantees depend on the problem setting and tree structure.

4.1 Efficient Algorithms for Optimal Subset Selection in Chain Models

  • The chain subset-selection algorithm uses dynamic programming over subchains and budgets to find an optimal subset in (1/6 n^3 + O(n^2))B expected local reward evaluations.Source: §4.1 · pp. 9–10

4.2 Efficient Algorithms for Optimal Conditional Planning in Chain Models

  • Conditional planning selects later observations based on earlier observed values, unlike subset selection, which commits to variables before observing their values.The plan must keep total cost within budget for every possible observation sequence.Source: §4.2 · p. 11, §4.2.1 · p. 11

4.2.1 FROM SUBSET SELECTION TO CONDITIONAL PLANNING

  • The MDP formulation has an exponentially large state space because states correspond to observed evidence, so the chain algorithm avoids applying exact MDP methods directly.Source: §4.2.1 · p. 12

4.2.2 DYNAMIC PROGRAMMING FOR OPTIMAL CONDITIONAL PLANNING IN CHAINS

  • The conditional-planning dynamic program allocates remaining budget across subchains according to observed values, and its computed plan can be executed with a single lookup per next observation.The paper reports polynomial-space plan representation and separate evaluation bounds for smoothing, filtering, and filtering without a budget.Source: §4.2.2 · pp. 13, 15

4.3 Efficient Algorithms for Trees with Few Leaves

  • Reward decomposition extends from chains to trees, but the number of subtrees—and thus the algorithm’s complexity—can grow exponentially with the number of leaves.Source: §4.3 · p. 15
  • For trees with a constant number of leaves, the number of subtrees is polynomial, so optimal observation subsets and conditional plans can be computed in polynomial time.For general trees, the number of subtrees can grow exponentially with the number of leaves.Source: §4.3 · pp. 15–16

5. Theoretical Limits

The section contrasts efficient inference with the difficulty of optimizing value of information on broader graphical structures. It classifies the complexity of computation and optimization, showing strong hardness even for Naive Bayes models and polytrees.

5. Theoretical Limits

  • The chain-to-tree dynamic program can grow exponentially with the number of leaves, and the paper proves this growth cannot be avoided under reasonable complexity assumptions.Source: §5 · p. 16

5.1 Brief Review of Relevant Computational Complexity Classes

  • NPPP consists of nondeterministic polynomial-time problems with access to a majority or counting oracle, and EMAJSAT is complete for this class.Source: §5.1 · p. 16

5.2 Complexity of Computing and Optimizing Value of Information

  • Computing decision-theoretic value-of-information functions is #P-complete for Naive Bayes models and cannot be approximated to any factor unless P = NP.Source: §5.2 · p. 17
  • Subset selection is PP-hard for Naive Bayes models and NPPP-complete for discrete polytrees, even though inference remains tractable on polytrees.Source: §5.2 · p. 17
  • Selecting sensors from a network of correlated sensors is therefore likely intractable without heuristics, according to the paper’s hardness result.Source: §5.2 · p. 17
  • Conditional-plan computation is PP-hard for Naive Bayes models and NPPP-hard for discrete polytrees.Source: §5.2 · p. 17

6. Experiments

Experiments compare optimal observation selection with greedy and uniform-spacing heuristics across temperature sensing, CpG-island detection, and interactive POS tagging. The optimal methods reduce uncertainty or improve classification in the reported tasks.

6.1 Temperature Time Series

  • For temperature sensing, optimal selection reduced expected uncertainty by several percent over both heuristics when fewer than about half of the 24 daily time points were selected.At larger k, the optimal plan's improvement over subset selection became more pronounced, while the optimal subset and greedy subset were almost identical.Source: §6.1 · p. 18

6.2 CpG-Island Detection

  • With six observations, the optimal algorithm's mean classification error was 25% lower than the greedy heuristic's on CpG-island detection.Expected margin scores were similar for the two methods, despite the difference in classification performance.Source: §6.2 · p. 19

6.3 Part-of-Speech Tagging

  • In POS tagging, requesting three of 50 labels increased mean F1 by more than five percent, and the optimal conditional plan improved classification by incorporating expert labels.The experiment used ten 50-word sequences and a conditional random field, with sum of margins as the reward and F1 as the performance measure.Source: §6.3 · p. 19

7. Applying Chain Algorithms for More General Graphical Models

The paper extends single-chain observation scheduling to correlated sensors, where interactions make exact joint optimization intractable. It develops a lower-bound coordinate-ascent approximation and evaluates it in a building testbed.

7. Applying Chain Algorithms for More General Graphical Models

  • For correlated sensors, reward decomposition across individual chains fails, and joint observation selection is NPPP-complete even for two dependent chains.The model treats a spatiotemporal process over locations and time under a Markov assumption; single-sensor scheduling remains solvable by the chain algorithm.Source: §7 · p. 20, §7.1 · p. 20

7.1 Approximate Sensor Scheduling by Lower Bound Maximization

  • The multi-sensor approximation keeps only each sensor's most recent observation when evaluating local rewards, yielding a lower bound on the true objective.The authors justify this lower bound by monotonicity of value of information in the observation set.Source: §7.1 · p. 21
  • Naively computing expected utility takes time exponential in the number of chains, while sampling can approximate value of information with polynomial sample bounds for any additive error ε.Approximate inference is also suggested as a way around the increasing inference difficulty as sensor counts grow.Source: §7.1 · p. 22
  • Coordinate ascent repeatedly optimizes one sensor's schedule while holding the others fixed, monotonically increasing the shared objective and converging to a local optimum.These guarantees ignore possible sampling or approximate-inference errors; without general performance guarantees, the procedure is optimal when sensors are independent and at least as good as independent scheduling when correlated.Source: §7.1 · pp. 21–22

7.2 Proof of Concept Study on Real Deployment

  • In the building testbed, scheduling three sensors with one observation per sensor brought user utility close to continuous sensing, while sensor lifetime increased by a factor of 3 without significant utility reduction or increased energy cost.The study varied each sensor's schedule over ten daytime time steps; single-observation sensing also came close to continuous sensing's power savings.Source: §7.2 · pp. 23–24, Figure 5 · p. 24

8. Related Work

Related work connects value-of-information selection to experimental design, planning, sensing, and learning, while distinguishing this paper's structured optimal algorithms from heuristic or differently scoped approaches.

8.1 Optimal Experimental Design

  • For Bayesian experimental design, the paper's chain algorithms solve non-fractional design problems optimally, including continuous distributions when inference is tractable.The paper frames value-of-information problems as instances of Bayesian experimental design with graphical-model structure.Source: §8.1 · pp. 24–25

8.2 Value of Information in Graphical Models

  • Prior graphical-model approaches include greedy methods without theoretical guarantees, large-sample evaluation for fixed observations, and branch-and-bound methods with worst-case exponential runtime.The paper contrasts these with its algorithms for chain models and general local reward functions.Source: §8.2 · p. 25

8.3 Bandit Problems and Exploration / Exploitation

  • The approach can solve a bandit instance with dependent arms, but unlike classical bandits, arms cannot be chosen repeatedly.The cited classical bandit result computes an optimal strategy in polynomial time for a fixed number of draws, using a different dynamic-programming structure.Source: §8.3 · p. 26

8.4 Probabilistic Planning

  • POMDP planning can formalize value-of-information optimization, but its state-space growth makes black-box solvers infeasible for these selection problems.Prior sensor-scheduling use of approximate POMDP planning reported empirical results without theoretical guarantees.Source: §8.4 · p. 26

8.5 Sensor Selection and Scheduling

  • Existing sensor-selection methods target coverage, specified prediction accuracy, or entropy reduction, rather than the more complex utility functions considered here.Some alternatives offer approximation guarantees, while the cited entropy-reduction heuristics do not.Source: §8.5 · pp. 26–27

8.6 Relationship to Machine Learning

  • The paper relates observation selection to feature selection and active learning, noting that it knows of no provably optimal active-learning algorithms even for restricted instances.It also notes that the decision-theoretic value of information is not submodular, precluding the cited greedy guarantee for submodular objectives.Source: §8.6 · p. 27, §8.7 · pp. 27–28

8.7 Previous Work by the Authors

  • This version extends earlier work with new algorithmic and hardness results, and value of information can be non-submodular even in Naive Bayes models.The paper intuitively attributes non-submodularity to cases where several observations are needed before changing an action.Source: §8.7 · pp. 27–28

9. Conclusions

The paper concludes that optimal subset selection and conditional observation plans are efficient for chains and certain trees, but broader graphical-model classes face sharp complexity limits. Its experiments also report gains for uncertainty reduction and interactive classification.

9. Conclusions

  • The paper presents efficient optimal algorithms for subset selection and conditional plans in chain graphical models and trees with few leaves, including HMMs.Its empirical evaluation reports improvements over common heuristics for uncertainty reduction and gains in interactive structured classification.Source: §9 · p. 28
  • Value-of-information optimization becomes intractable beyond chains: the paper identifies NPPP-completeness for polytrees and computation hardness even for Naive Bayes models.These are presented as theoretical limits on extending the optimal methods to more complex models.Source: §9 · p. 28
  • The authors point to approximation algorithms with non-trivial guarantees for interesting value-of-information problems as a direction in light of these theoretical limits.They cite Krause and Guestrin (2005a), Radovilsky et al. (2006), and Krause et al. (2007).Source: §9 · p. 28

Appendix A

Appendix reductions connect observation-selection rewards to satisfiability counting and majority thresholds, and extend hardness results to conditional plans and chain-structured models.

Appendix A

  • Theorem 3’s construction makes expected reward equal the number of satisfying assignments and can be converted to a Naive Bayes model by marginalizing U.Its reward is positive only when the observations establish Y > 0 with certainty.Source: Appendix A · p. 29
  • Any-factor approximation of the constructed reward would decide whether the formula is satisfiable, implying P = NP.The reduction distinguishes zero from positive reward.Source: Appendix A · p. 30
  • L(V) counts satisfying assignments, so L(V) > 2^(n−1) exactly when a majority of assignments satisfies the formula.The proof uses this threshold to connect a Naive Bayes model to majority satisfiability.Source: Appendix A · p. 30
  • The EMAJSAT reduction proves subset selection is NPPP-complete: for ˆR = R(Y2n | ˆO), φ ∈ EMAJSAT exactly when ˆR > 0.5.A reward above 0.5 implies that the majority of all provably consistent assignments satisfy φ.Source: Appendix A · p. 31
  • The conditional-plan constructions establish PP-hardness and NPPP-hardness because positive-reward plans reduce to subset selection when observation order is irrelevant.The cited cases require observations corresponding to valid instantiations.Source: Appendix A · p. 32
  • The polytree hardness construction can be arranged into two dependent chains through an arc reversal and triplicated variables.The transformed variables are distributed across successive timesteps.Source: Appendix A · p. 32
  • For the utility function L, maximization over actions is convex, and Jensen’s inequality supports the stated bound L(A) ≥ L(∅).The proof proceeds by induction.Source: Appendix A · p. 32
  • Under the stated binary-classification example with asymmetric costs, the utility objective is not submodular: adding X2 after X1 increases utility more than adding X2 to the empty set.Source: Appendix A · p. 32
Loading 1401.3474v1…