Surrogate Cost Techniques in Countable Classification

We study the problem of classification when the set of classes is a sigma-compact metric space, by means of surrogate cost minimization. We give a natural sufficient condition for the optimal classifier to be of the form Tf when the function f minimizes a surrogate for the actual loss defined on pairs of classes. Sequences of functions whose expectations converge to the infimum of the expectations of all such functions can then be found by minimizing the sample averages of training sets. In particular, we show how to use surrogate cost minimization when the set of classes is countable and give an example.