О сложности обучения логических процедур классификации

Исследуются вопросы сложности логического анализа целочисленных данных. Для специальных задач поиска частых и нечастых элементов в данных, на решении которых базируется обучение логических процедур классификации, приведены асимптотики типичного числа решений. Технические основы получения указанных оценок опираются на методы получения аналогичных оценок для труднорешаемой дискретной задачи построения (перечисления) тупиковых покрытий целочисленной матрицы, формулируемой в работе как задача поиска «минимальных» нечастых элементов. Новые результаты в основном касаются изучения метрических (количественных) свойств частых элементов. Полученные оценки типичного числа часто встречающихся фрагментов в описаниях прецедентов позволяют сделать вывод о перспективности применения алгоритмов поиска таких фрагментов на этапе обучения логических классификаторов типа «Кора».