Hierarchical testing designs for pattern recognition

Gilles Blanchard (1, 2, 3) , Donald Geman (4, 5, 6, 7)

1 CNRS - Centre National de la Recherche Scientifique
2 LMO - Laboratoire de Mathématiques d'Orsay
3 DMA - Département de Mathématiques et Applications - ENS Paris
4 IMEDIA - Image and multimedia indexing, browsing and retrieval
5 JHU - Johns Hopkins University
6 UMass Amherst - University of Massachusetts [Amherst]
7 Département de mathématiques, ENS Cachan

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 $\mathcal{Y}$ of possible patterns or explanations, narrow down the true one $Y$ to a small (random) subset $\widehat{Y} \subset \mathcal{Y}$ 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 \not\in A^c$. Each test has null type I error and the candidate sets $A \subset \mathcal{Y}$ 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 $\widehat{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 $|Y|$) and the corresponding optimization problem is analyzed. As might be expected, under mild assumptions good designs for sequential testing strategies exhibit a steady progression from broad scope coupled with low power to high power coupled with dedication to specific explanations. In the assumptions ensuring this property a key role is played by the ratio cost/power. These ideas are illustrated in the context of detecting rectangles amidst clutter.

Mots clés: AMS 2000 subject classifications. Primary 62H30; 62L05; 68T10; secondary 62H15; 68T45; 90B40 Classification; sequential hypothesis testing; hierarchical designs; coarse-to-fine search; pattern recognition; scene interpretation

Domaines: Statistiques [math.ST]; Apprentissage [cs.LG]; Intelligence artificielle [cs.AI]

Gilles Blanchard, Donald Geman. Hierarchical testing designs for pattern recognition. Annals of Statistics, 2005, 33 (3), pp.1155-1202. ⟨10.1214/009053605000000174⟩. ⟨hal-03337848⟩