"Metric Entropy and
Minimax Risk in Classification" (with Manfred Opper), Lecture Notes in Computer Science: Studies in Logic
and Computer Science Vol. 1261, 212-235 (1997)
Eds. J. Mycielski, G. Rozenberg and A. Salomaa
[245k postscript]
Abstract:
We apply recent results on the minimax risk in density estimation to the
related problem of pattern classification.
The notion of loss we seek to minimize is an information theoretic
measure of how well we can predict the classification of future examples,
given the classification of previously seen examples. We give an asymptotic
characterization of the minimax risk
in terms of the metric entropy
properties of the class of distributions that might be generating
the examples. We then use these results to characterize the minimax
risk in the special
case of noisy two-valued classification problems in terms
of the Assouad density and the Vapnik-Chervonenkis dimension.