Вычислимые комбинаторные оценки вероятности переобучения

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