Weak Adaptive Submodularity and Group-Based Active Diagnosis with Applications to State Estimation with Persistent Sensor Faults
In this paper, we consider adaptive decision-making problems for stochastic state estimation with partial observations. First, we introduce the concept of weak adaptive submodularity, a generalization of adaptive submodularity, which has found great success in solving challenging adaptive state estimation problems. Then, for the problem of active diagnosis, i.e., discrete state estimation via active sensing, we show that an adaptive greedy policy has a near-optimal performance guarantee when the reward function possesses this property. We further show that the reward function for group-based active diagnosis, which arises in applications such as medical diagnosis and state estimation with persistent sensor faults, is also weakly adaptive submodular. Finally, in experiments of state estimation for an aircraft electrical system with persistent sensor faults, we observe that an adaptive greedy policy performs equally well as an exhaustive search.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMedical DiagnosisState EstimationSimilar Papers 제목 키워드 기반
Comments on the proof of adaptive submodular function minimization
We point out an issue with Theorem 5 appearing in "Group-based active query selection for rapid diagnosis in time-critical situations". Theorem 5 bounds the expected number of queries for a greedy algorithm to identify t…
Active LearningStochastic OptimizationBudgeted stream-based active learning via adaptive submodular maximization
Active learning enables us to reduce the annotation cost by adaptively selecting unlabeled instances to be labeled. For pool-based active learning, several effective methods with theoretical guarantees have been develope…
Active LearningAdaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this paper, we introduc…
Active LearningMarketingStochastic OptimizationEfficient Online Decision Tree Learning with Active Feature Acquisition
Constructing decision trees online is a classical machine learning problem. Existing works often assume that features are readily available for each incoming data point. However, in many real world applications, both fea…
Medical DiagnosisFast Parallel Algorithms for Statistical Subset Selection Problems
In this paper, we propose a new framework for designing fast parallel algorithms for fundamental statistical subset selection tasks that include feature selection and experimental design. Such tasks are known to be weakl…
Combinatorial OptimizationExperimental Designfeature selection