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

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