Optimal value of information in graphical models
From MaRDI portal
Abstract: 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 -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.
Recommendations
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Decision-theoretic optimal sampling in Hidden Markov Random Fields
- Ranking hypotheses to minimize the search cost in probabilistic inference models
- Data association based on optimization in graphical models with application to sensor networks
- Algorithms and Applications for the Same-Decision Probability
Cited in
(28)- Reinforcement learning-based design of sampling policies under cost constraints in Markov random fields: application to weed map reconstruction
- Rough set methods in feature selection via submodular function
- Information gathering in Bayesian networks applied to petroleum prospecting
- Actively learning to infer social ties
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- Sparse optimization in feature selection: application in neuroimaging
- Scheduling networked state estimators based on value of information
- Informed production optimization in hydrocarbon reservoirs
- Informative path planning as a maximum traveling salesman problem with submodular rewards
- A tight analysis of the submodular-supermodular procedure
- Same-decision probability: a confidence measure for threshold-based decisions
- Decision-theoretic optimal sampling in Hidden Markov Random Fields
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Experimental design for nonparametric correction of misspecified dynamical models
- A Hilbert Space Embedding for Distributions
- Submodular functions: learnability, structure, and optimization
- Value of information in probabilistic logic programs
- Constrained submodular maximization via a nonsymmetric technique
- Optimal experimental design for sampling voltage on dendritic trees in the low-SNR regime
- Efficient designs for Bayesian networks with sub-tree bounds
- Sketching valuation functions
- Improved algorithms for non-submodular function maximization problem
- Two-stage non-submodular maximization
- Two-stage BP maximization under \(p\)-matroid constraint
- Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
- Active inference for binary symmetric hidden Markov models
- Soft arc consistency revisited
This page was built for publication: Optimal value of information in graphical models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3651472)
