Комбинаторная теория переобучения

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