Scalable robust hypothesis tests using graphical models

Traditional binary hypothesis testing relies on the precise knowledge of the probability density of an observed random vector conditioned on each hypothesis. However, for many applications, these densities can only be approximated due to limited training data or dynamic changes affecting the observed signal. A classical approach to handle such scenarios of imprecise knowledge is via minimax robust hypothesis testing (RHT), where a test is designed to minimize the worst case performance for all models in the vicinity of the approximated imprecise density. Despite the promise of RHT for robust classification problems, its applications have remained rather limited because RHT in its native form does not scale gracefully with the dimension of the observed random vector. In this paper, we use approximations via probabilistic graphical models, in particular block-tree graphs, to enable computationally tractable algorithms for realizing RHT on high-dimensional data. We quantify the reductions in computational complexity. Experimental results on simulated data and a target recognition problem show minimal loss over a true RHT.