Tradeoff relation between mutual information and error probability in data classification problem

A data classification model in which the average mutual information between source objects and made decisions is a function of the error probability is investigated. Optimization of the model consists in finding a tradeoff “mutual information–error probability” (MIEP) relation between the minimal average mutual information and the error probability, which is analogous to the well-known rate distortion function for source coding with a given fidelity in the case of a noisy observation channel. A lower bound for the MIEP relation is constructed, which provides a lower bound for the classification error probability on a given set of objects for any fixed value of the average mutual information. The MIEP relation and its lower bound are generalized to ensembles of sources. The obtained bounds are useful for estimating the error probability redundancy for decision algorithms with given sets of discriminant functions.