Hierarchical testing designs for pattern recognition

Abstract

We explore the theoretical foundations of a ``twenty questions'' approach to pattern recognition. The object of the analysis is the computational process itself rather than probability distributions (Bayesian inference) or decision boundaries (statistical learning). Our formulation is motivated by applications to scene interpretation in which there are a great many possible explanations for the data, one (``background'') is statistically dominant, and it is imperative to restrict intensive computation to genuinely ambiguous regions. The focus here is then on pattern filtering: Given a large set Y of possible patterns or explanations, narrow down the true one Y to a small (random) subset \hat Y\subsetY of ``detected'' patterns to be subjected to further, more intense, processing. To this end, we consider a family of hypothesis tests for Y\in A versus the nonspecific alternatives Y\in A^c. Each test has null type I error and the candidate sets A\subsetY are arranged in a hierarchy of nested partitions. These tests are then characterized by scope (|A|), power (or type II error) and algorithmic cost. We consider sequential testing strategies in which decisions are made iteratively, based on past outcomes, about which test to perform next and when to stop testing. The set \hat Y is then taken to be the set of patterns that have not been ruled out by the tests performed. The total cost of a strategy is the sum of the ``testing cost'' and the ``postprocessing cost'' (proportional to |\hat Y|) and the corresponding optimization problem is analyzed.

Published at http://dx.doi.org/10.1214/009053605000000174 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Hierarchical testing designs for pattern recognition

Cited by in corpus (9)

• Hierarchical testing designs for pattern recognition
• Multi-study Integration of Brain Cancer Transcriptomes Reveals Organ-Level Molecular Signatures
• False discovery rate control with multivariate $p$-values
• Efficient blind search: Optimal power of detection under computational cost constraints
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Adaptive Sensing for Estimation of Structured Sparse Signals
• Complexity of Representation and Inference in Compositional Models with Part Sharing
• Genomic Prediction of Quantitative Traits using Sparse and Locally Epistatic Models
• Sparse Recovery With Multiple Data Streams: A Sequential Adaptive Testing Approach