INFORMATION-THEORETIC BOUNDS TO ACCURACY OF OBJECT CLASSIFICATION IN REPRESENTATION SPACES WITH GIVEN DISTANCES
M. M. Lange, S. V. Paramonov
a:2:{s:4:"TYPE";s:4:"TEXT";s:4:"TEXT";s:105:"Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Moscow, Russia";}
Keywords: classification, object representation, distance, error probability, mutual information, combining representations
Abstract
For spaces of object representations with given distances, the lower bounds to the error probability of object classification subject to the fixed values of the amount of processed information are investigated. The bounds are defined by the strictly decreasing functions of the minimal average mutual information between the submitted objects and the estimations of their classes depending on the error probability. So, the inverse functions yield the minimal error probability for any fixed value of the average mutual information. For spaces of tree-structured and vector-based object representations, numerical realizations of the bounds are calculated. It is shown that the lower bound to the error probability is lower in the space of vector-based representations as against the similar bound in the space of tree-structured representations. Also, a possibility of decreasing the bound to the error probability by combining object representations with various distance functions is demonstrated.
|
