On the complexity of logical classification learning procedures

The issues of integer data logical analysis complexity are investigated. For special tasks of searching in data for frequent and infrequent elements, on the solution of which logical supervised classification procedures are based, asymptotics of a typical number of solutions are given. The technical foundations for obtaining these estimates are based on methods for obtaining similar estimates for intractable discrete problem of constructing (enumerating) irredundant coverings of integer matrix formulated in the paper as the problem of finding “minimal” infrequent elements. The new results mainly concern the study of metric (quantitative) properties of frequent elements. The obtained estimates for the typical number of frequently occurring fragments in precedent descriptions allow one to conclude that the use of algorithms for finding such fragments at the stage of training logical classifiers of the “Kora” type is promising.