ON AN ERROR PROBABILITY AND COMPUTATIONAL COMPLEXITY FOR PATTERN RECOGNITION IN A METRIC SPACE OF TREE-STRUCTURED REPRESENTATIONS
M.M. Lange, S.V. Paramonov
Federal Research Center "Computer Science and Control", Russian Academy of Sciences, Moscow, Russia
Keywords: classification, error probability, mutual information, discriminant function, redundancy, image, guided search, computational complexity
Abstract
In a space of tree-structured object representations, the accuracy of object classification in terms of an error probability depending on the amount of processed information is studied. For a given set of objects, the lower bound to the average error probability as a function of the average mutual information between the objects and the decisions about their classes is given. Using multilevel discriminant functions in the set of object representations, a guided search algorithm for an object class-label decision is proposed, and a computational profit of the guided search relative to the exhaustive search is shown analytically. In the source datasets of face and signature objects given by the grayscale images as well as in an ensemble of these datasets, we calculate the experimental dependences of the average error probability and the average mutual information on the algorithm parameter which defines the above-mentioned computational profit. Also, for both source datasets and their ensemble, we give numerical values of the lower bounds to the error probability that allow us to estimate the redundancy of the algorithm error probability for different values of the computational profit.
|
