Probabilistic Tools for Optimization of Classifiers on Large Data Sets

Abstrakt

The number of classification tasks on a finite domain (representing a set of vectors of features, measurements, or observations) grows exponentially with its size. However, for a given application area relevance of many such tasks might be very low or negligible. A probabilistic framework is introduced, modeling prior knowledge about probabilities that a presence of some features implies a property described by one of the classes. Impact of increasing sizes of domains on correlations between input-output mappings of computational models and randomly-chosen classifiers is analyzed. It is proven that for large domains the correlations are sharply concentrated around their mean values. Probabilistic bounds are derived via implications of the Azuma-Hoeffding Inequality, holding also without the ”naive Bayes assumption”. It is shown that the performance of random classifiers is almost deterministic, in the sense that either a given class of computational models can approximate well almost all tasks or none of them. Consequences for the choice of optimal computational models are derived