Теория Вапника-Червоненкиса

Материал из MachineLearning.

Теория Вапника-Червоненкиса, в исходных работах статистическая теория восстановления зависимостей по эмпирическим данным.

Содержание 1 Основные предпосылки 2 Основные предположения 3 Основные результаты 4 Основные ограничения 5 Ссылки 6 Литература

Основные предпосылки

Значительный опыт решения прикладных задач обучения по прецедентам, в первую очередь задач распознавания, восстановления регрессии и прогнозирования был накоплен уже к середине 60-х годов XX века. Большую популярность приобрёл подход, основанный на построении модели восстанавливаемой зависимости в виде параметрического семейства алгоритмов. С помощью численной оптимизации подбираются такие значения параметров модели, при которых алгоритм допускает наименьшее число ошибок на заданной обучающей выборке прецедентов. Проще говоря, осуществляется подгонка модели под выборку. Этот метод получил название минимизации эмпирического риска.

На практике исследователи столкнулись с проблемой переобучения. Чем больше у алгоритма свободных параметров, тем меньшего числа ошибок на обучении можно добиться путём оптимизации. Однако по мере нарастания сложности модели «оптимальные» алгоритмы начинают слишком хорошо подстраиваться под конкретные данные, улавливая не только черты восстанавливаемой зависимости, но и ошибки измерения обучающей выборки, и погрешность самой модели. В результате ухудшается качество работы алгоритма вне обучающей выборки, или, как говорят, его способность к обобщению (generalization ability).

Из этого наблюдения был сделан вывод, что для всякой задачи существует оптимальная сложность модели, при которой достигается наилучшее качество обобщения. Первое формальное обоснование этого практического опыта было дано в статистической теории восстановления зависимостей, разработанной В. Н. Вапником и А. Я. Червоненкисом в конце 60-х — начале 70-х. Эта теория получила широкую мировую известность и признание в середине 80-х. Работы В. Н. Вапника и А. Я. Червоненкиса послужили отправной точкой для создания теории вычислительного обучения, которая в настоящее время является наиболее теоретическим разделом машинного обучения.

Основные предположения

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

Основные результаты

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

Основные ограничения

Основной проблемой статистической теории является завышенность оценок. Непосредственный расчёт показывает, что для надёжного обучения необходимо иметь порядка 10⁶–10⁸ объектов. Это существенно превышает объёмы выборок, с которыми обычно приходится сталкиваться на практике. Тем не менее, прикладные задачи решаются, и вполне успешно. Наиболее интересные случаи — малых выборок и сложных семейств алгоритмов — находятся за границами применимости теории. По сути дела, теория дает лишь качественное обоснование некоторых принципов построения обучаемых алгоритмов, которые фактически так и остаются эвристическими принципами.

Основной причиной завышенности статистических оценок является их чрезмерная общность. Они не учитывают существенных особенностей метода обучения, восстанавливаемой зависимости и распределения объектов в пространстве. Иными словами, теория пессимистично настроена на «худший случай», который почти невозможно встретить на практике. Реально приходится сталкиваться лишь с «достаточно хорошими» задачами, которые составляют исчезающе малую долю всех гипотетически возможных задач.

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

Ссылки

• В. Н. Вапник — домашняя страница
• А. Я. Червоненкис — домашняя страница
• Выдающиеся ученые ИПУ РАН страница на сайте Института проблем управления РАН
• Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)

Литература

1. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
2. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.