Optimal sequential multiclass diagnosis
From MaRDI portal
Abstract: Sequential multi-class diagnosis, also known as multi-hypothesis testing, is a classical sequential decision problem with broad applications. However, the optimal solution remains, in general, unknown as the dynamic program suffers from the curse of dimensionality in the posterior belief space. We consider a class of practical problems in which the observation distributions associated with different classes are related through exponential tilting, and show that the reachable beliefs could be restricted on, or near, a set of low-dimensional, time-dependent manifolds with closed-form expressions. This sparsity is driven by the low dimensionality of the observation distributions (which is intuitive) as well as by specific structural interrelations among them (which is less intuitive). We use a matrix factorization approach to uncover the potential low dimensionality hidden in high-dimensional beliefs and reconstruct the beliefs using a diagnostic statistic in lower dimension. For common univariate distributions, e.g., normal, binomial, and Poisson, the belief reconstruction is exact, and the optimal policies can be efficiently computed for a large number of classes. We also characterize the structure of the optimal policy in the reduced dimension. For multivariate distributions, we propose a low-rank matrix approximation scheme that works well when the beliefs are near the low-dimensional manifolds. The optimal policy significantly outperforms the state-of-the-art heuristic policy in quick diagnosis with noisy data. (forthcoming in Operations Research)
Recommendations
Cites work
- scientific article; zbMATH DE number 3906232 (Why is no real title available?)
- scientific article; zbMATH DE number 3766893 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 2243378 (Why is no real title available?)
- scientific article; zbMATH DE number 3057677 (Why is no real title available?)
- A Sequential Decision Procedure for Choosing One of k Hypotheses Concerning the Unknown Mean of a Normal Distribution
- A Sequential Decision Procedure for Choosing One of Three Hypotheses Concerning the Unknown Mean of a Normal Distribution
- A Sequential Three Hypothesis Test for Determining the Mean of a Normal Population with Known Variance
- A sequential procedure for multihypothesis testing
- Active sequential hypothesis testing
- Asymptotic efficiency of a sequential multihypothesis test
- Bayesian sequential change diagnosis
- Controlled Sensing for Multihypothesis Testing
- Design and analysis of diagnostic service centers
- Dynamic programming and stochastic control
- Empirical likelihood ratio based confidence intervals for mixture proportions
- From the zonotope construction to the Minkowski addition of convex polytopes
- Multivariate logistic compounds
- Nearly-optimal sequential tests for finitely many parameter values
- Optimal learning before choice
- Partially observed Markov decision processes. From filtering to controlled sensing
- Repetitive Testing in the Presence of Inspection Errors
- Repetitive testing strategies when the testing process is imperfect
- Sequential Anomaly Detection Under a Nonlinear System Cost
- Sequential Design of Experiments
- Sequential Tests of Statistical Hypotheses
- Some Reliability Fault-Testing Models
- Spectral density ratio models for multivariate extremes
- The quickhull algorithm for convex hulls
- Using specially designed exponential families for density estimation
Cited in
(3)
This page was built for publication: Optimal sequential multiclass diagnosis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031008)
