Abstract:
The issues of the complexity of the correct training of supervised classification procedures that based on the use of logical data analysis methods are investigated. The metric (quantitative) properties of informative fragments of feature descriptions of precedents are studied in the case when the number of features is significantly greater than the number of precedents. The asymptotics of a typical number of fragments frequently found in descriptions of precedents that distinguish objects from different classes and are called regular representative elementary classifiers are given. The typical length of the desired fragment is specified. The technical foundations of the estimates presented are based on a methodology for obtaining similar estimates for the intractable discrete problem of enumerating irredanded coverings of an integer matrix, formulated in this paper as the problem of searching for minimal infrequent elementary classifiers. New results on the complexity of the implementation of logical classifiers allow us to theoretically substantiate the effectiveness of the training procedure based on the search for the regular representative elementary classifiers and confirm the prospects of the approach in terms of time costs.
Key words:logical data analysis, supervised classification, regular representative elementary classifier, irredanded covering of an integer matrix, intractable discrete problem, asymptotically optimal algorithm.
