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

теория статистического обучения, оценки обобщающей способности, теория Вапника-Червоненкиса, функция роста, локальная функция роста, минимизация эмпирического риска, структурная минимизация риска, степень некорректности, профиль компактности, профиль монотонности

Математические вопросы и теория численных методов