On Error Probability in Recognition Problems with a Random Vocabulary

For recognition problems in which the set of objects to be recognized is not fixed in advance, but only their type is known (e.g., in the handwriting-analysis problem), it is not possible to specify a priori the value of the error probability inherent in the algorithm employed. On the basis of the analogy between such problems and the problem of transmission of information over a noisy channel with random coding, it is shown that it is possible to set up an upper bound for the mean error probability (over the sets) when the maximum-likelihood method of recognition is employed. A working formula for this bound is given for one particular case.