Комбинаторная теория переобучения (виртуальный семинар)

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

Версия от 21:02, 2 мая 2010; Vokov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Содержание

1 Мотивация
2 Точные оценки вероятности переобучения
3 Ссылки
4 Литература
5 См. также

Данный виртуальный семинар предназначен для обсуждения

эффектов расслоения и сходства в семействах алгоритмов классификации;
влияния этих эффектов на обобщающую способность;
математических техник, позволяющих учитывать эти эффекты в оценках вероятности переобучения.

Мотивация

Точные оценки вероятности переобучения необходимы для создания методов обучения по прецедентам, гарантирующих высокое качество классификации новых объектов, не вошедших в обучающую выборку. Получение точных оценок обобщающей способности остаётся открытой проблемой в теории статистического обучения уже более 40 лет, начиная с VC-теории, предложенной В. Н. Вапником и А. Я. Червоненкисом. Наиболее точные из известных оценок всё ещё сильно завышены.

Основной задачей в теории статистического обучения является получение верхних оценок для функционала

$P_\varepsilon(A) = \mathbb{P}_X\Bigl( \sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon \Bigr),$

где

$A$ — семейство алгоритмов, из которого по обучающей выборке выбирается некоторый конкретный алгоритм;
$P(a)$ — вероятность ошибки алгоритма $a \in A$ ;
$\nu(a,X)$ — частота ошибок алгоритма $a \in A$ на независимой обучающей выборке длины $\ell$ ;
$\mathbb{P}_X$ — некоторая неизвестная вероятностная мера на множестве объектов.

У этого функционала есть несколько недостатков.

Если вероятностная мера $P(a)$ неизвестна, то измерить функционал $P_\varepsilon(A)$ непосредственно в эксперименте очень трудно, поскольку невозможно идентифицировать наступление события $\sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon$ . А экспериментальное измерение необходимо для количественного анализа и понимания причин завышенности оценок. Выход заключается в том, чтобы вместо $P(a)$ оценивать $\nu(a,\bar X)$ — частоту ошибок алгоритма $a$ на независимой контрольной выборке произвольной длины $k$ . Тогда эмпирическое измерение функционала $P_\varepsilon(A)$ становится возможным, например, методом Монте-Карло — путём генерации некоторого числа случайных разбиений полной выбоки $X^L = X \sqcup \bar X$ на обучение и контроль. Здесь через $L=\ell+k$ обозначена длина полной выборки.
Супремум в VC-теории вводится для того, чтобы получить наиболее общую оценку, не зависящую от конкретного метода обучения $\mu$ , который по обучающей выборке $X$ находит алгоритм $a\in A$ . Однако на самом деле было бы правильнее оценивать вероятность переобучения, то есть вероятность события $|\delta_\mu(X,\bar X)| \geq \varepsilon$ , где разность $\delta_\mu(X,\bar X) = \nu(\mu(X),\bar X)-\nu(\mu(X),X)$ называется переобученностью. Введение супремума уже само по себе приводит к верхней оценке вероятности переобучения. Эта оценка может оказаться сильно завышенной, поскольку при решении прикладных задач методы обучения возвращают не любые алгоритмы из $A$ , а лишь те, которые в определённом смысле «похожи» на восстанавливаемую зависимость.
Наконец, имеет смысл оценивать саму переобученность, а не её абсолютную величину, поскольку частоту ошибок на контрольной выборке, по смыслу задачи, необходимо ограничивать именно сверху, а не снизу.

Таким образом, более адекватным функционалом обобщающей способности является вероятность переобучения:

$Q_\varepsilon(\mu,X^L) = \mathbb{P}_{X,\bar X}\Bigl( \delta_\mu(X,\bar X) \geq \varepsilon \Bigr).$

Этот функционал является локальной оценкой обобщающей способности, поскольку он зависит от метода обучения и полной выборки.

Термин переобучение понимается здесь в строго формальном смысле, как событие $\delta_\mu(X,\bar X) \geq \varepsilon$ .

Вероятность $\mathbb{P}_{X,\bar X}$ понимается здесь и далее в смысле равномерного распределения на множестве всех $C_L^\ell$ разбиений неслучайной полной выбоки $X^L = X \sqcup \bar X$ . Это позволяет применять чисто комбинаторные методы для получения оценок вероятности переобучения, и во многих случаях получать точные оценки (не завышенные, не асимптотические). См. также слабая вероятностная аксиоматика.

Основным объектом изучения в комбинаторно-дискретной постановке является бинарная матрица ошибок $I = (I_{id})$ . Строки матрицы соотвествуют объектам полной выборки, столбцы — алгоритмам, значение $I_{id}=1$ означает, что алгоритм $a_d$ допускает ошибку на объекте $x_i$ . Столбец этой матрицы называется вектором ошибок алгоритма $a_d$ .

Первый эксперимент (на реальных данных)

В экспериментах на реальных задачах классификации удалось количественно оценить отдельные факторы завышенности классических VC-оценок.

Основные причины завышенности, в порядке убывания важности:

Пренебрежение эффектом расслоения (или локализации) семейства алгоритмов. Чем хуже классификатор решает данную задачу, тем меньше шансов получить его в результате настройки по обучающей выборке. Это означает, что реально работает не всё семейство, а только какая-то его часть, своя в каждой задаче.
Степень завышенности: от нескольких десятков раз до сотен тысяч раз, в зависимости от задачи.
Пренебрежение эффектом сходства алгоритмов. При выводе классических VC-оценок используется неравенство Буля (union bound) — оценка вероятности объединения событий суммой их вероятностей. Эта оценка становится чрезвычайно завышенной, если среди алгоритмов есть похожие.
Степень завышенности: от нескольких сотен до десятков тысяч раз. Этот фактор всегда существенен и не так сильно зависит от задачи, как первый.
Экспоненциальная аппроксимация хвоста гипергеометрического распределения. Вроде бы точность аппроксимации увеличивается с ростом длины выборки — хвосты быстро стремятся к нулю. Однако относительная погрешность (отношение аппроксимированного значения к точному) с ростом выборки растёт! Отсюда вывод: при получении численно точных оценок не стоит пользоваться аппроксимациями.
Степень завышенности: порядка нескольких десятков.

Основные выводы:

Завышенность VC-оценок обусловлена тем, что они учитывают только длину выборки и число различных алгоритмов, но не учитывают степень их различности, игнорируют внутреннюю структуру семейства.
Для получения точных оценок необходимо одновременно учесть оба эффекта — и расслоение, и сходство.

Второй эксперимент (на модельных данных)

Простейшим примером семейства алгоритмов с расслоением и связностью является монотонная цепочка алгоритмов. Оно строится следующим образом. Задаётся «лучший алгоритм», допускающий $m_0$ ошибок на полной выборке. Каждый следующий алгоритм $a_{d+1}$ допускает ошибки на тех же объектах, что и предыдущий $a_{d}$ , плюс ошибку ещё на одном объекте. Перестановкой строк можно добиться, чтобы матрица ошибок такого семейства содержала верхнюю треугольную подматрицу.

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

Монотонной цепочке можно поставить в соотвествие цепочку без расслоения. В этом семействе каждый следующий алгоритм также отличается от предыдущего только на одном объекте, но число ошибок, чередуясь, принимает лишь два значения: $m_0, m_0+1$ .

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

Итак, получается четыре модельных семейства, заданных непосредственно своими маатрицами ошибок. Для каждого из них вероятность переобучения нетрудно оценить методом Монте-Карло (у хороших студентов реализация такого экспериментального стенда занимает обычно около пары часов работы). Результаты сопоставляются на графиках зависимости вероятности переобучения $Q_\varepsilon$ от числа $D$ первых алгоритмов $a_1,\ldots,a_D$ , из которых метод обучения $\mu(X)$ выбирает алгоритм с наименьшей частотой ошибок на обучающей выборке. В VC-теории такой метод обучения называется минимизацией эмпирического риска.

Этот эксперимент позволяет сделать чрезвычайно важные выводы и, по сути дела, указывает, в каком направлении следует развивать теорию переобучения.

Связность заметно снижает темп роста зависимости $Q_\varepsilon(D)$.
Расслоение понижает уровень горизонтальной асимптоты $Q_\varepsilon(D)$.
Только при наличии обоих эффектов вероятность переобучения приемлемо мала, причём кривая «выходит на насыщение» после первых 5–7 алгоритмов. Основная масса «плохих» алгоритмов вообще не вносит вклад в переобучение.
При отсутствии либо расслоения, либо связности переобучение наступает уже при нескольких десятках алгоритмов.
Это означает, что реальные семейства, состоящие из огромного числа различных алгоритмов, с необходимостью должны быть расслоенными и связными.
Семейство без расслоения и без связности — это и есть тот наихудший случай, который изучается в VC-теории.

Замечание о природе переобучения

Вообще, переобучение возникает из-за того, что выбирается алгоритм с минимальным числом ошибок на обучающей выборке.

Сделаем мысленный эксперимент. Представим, что все алгоритмы семейства имеют одинаковую вероятность ошибок. Тогда число ошибок на конечной выборке подчиняется биномиальному распределению, имеющему форму пика. Шансы отдельному алгоритму угодить в левый хвост распределения невелики. Однако чем больше алгоритмов мы будем брать, тем дальше влево будет смещаться минимальное (по всем взятым алгоритмам) число ошибок; тем больше будет разность между частотой и вероятностью ошибок у «лучшего» алгоритма. Но это и есть переобучение.

Это всё так, если алгоритмы берутся из распределения случайно и независимо. Однако, если алгоритмы зависимы (а в реальной ситуации они именно зависимы, причём очень сильно), то возникает надежда, что выбираемые алгоритмы будут концентрироваться гуще, и пик эмпирического распределения числа ошибок окажется более узким.

Пара алгоритмов

Получены точные формулы для вероятности переобучения при выборе лучшего из двух алгоритмов. Если алгоритмы совпадают, то вероятность переобучения равна вероятности большого уклонения частот в двух подвыборках для отдельного алгоритма, и описывается гипергеометрическим распределением. Если алгоритмы существенно различны, но имеют одинаковый уровень ошибок, то вероятность переобучения увеличивается вдвое. Если алгоритмы имеют существенно различный уровень ошибок, то вероятность переобучения уменьшается.

Выводы: уже при выборе одного из двух алгоритмов может возникать переобучение. Расслоение алгоритмов по числу ошибок и увеличение сходства уменьшают вероятность переобучения.

Как устроены реально используемые семейства

Многие параметрические семейства алгоритмов обладают следующим свойством: при изменении вектора параметров по некоторой непрерывной траектории каждое изменение вектора ошибок происходит только на одном объекте. Одновременное изменение нескольких координат возможно, но только для «редких» траекторий, образующих в пространстве траекторий множество меры нуль. В частности, этим свойством обладают классификаторы с непрерывной по параметрам разделяющей поверхностью: линейные классификаторы, SVM с непрерывными ядрами, нейронные сети с непрерывными функциями активации, решающие деревья с пороговыми условиями ветвления, и многие другие. J. Sill называет такие семейства связными, так как множество векторов ошибок всех алгоритмов семейства представляется в виде связного графа. E. Bax предлагает кластеризовать семейство на группы схожих классификаторов.

Основной вопрос данного виртуального семинара

Как учесть связность и расслоенность в семействах алгоритмов для получения незавышенных оценок вероятности переобучения?

Точные оценки вероятности переобучения

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

Список открытых проблем, оформленный в виде задач по спецкурсу «Теория надёжности обучения по прецедентам».
(PDF, 180 КБ).

Ссылки

Более подробно результаты можно посмотреть здесь:

март 2009. Точные оценки вероятности переобучения. (PDF, 336 КБ).
октябрь 2008. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. Развёрнутая версия статьи на РОАИ-9-2008. (PDF, 354 КБ).
17 сентября 2008. Пути повышения точности оценок обобщающей способности (комбинаторный подход). Пленарный доклад на международной конференции РОАИ-9-2008, Нижний Новгород. Презентация на английском (PDF, 846 КБ), на русском (PDF, 844 КБ), тезисы доклада на русском (PDF, 243 КБ).
12 июня 2008. Слабая вероятностная аксиоматика, оценки надёжности эмпирических предсказаний, расслоение и различность алгоритмов. Конференция ИОИ-2008. (PDF, 950 КБ).
28 апреля 2008. Ломоносовские чтения 2008. Оценки надёжности эмпирических предсказаний (комбинаторный подход). (PDF, 804 КБ).

Литература

Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с. (подробнее)
Sill J. Generalization bounds for connected function classes.
Bax E. T. Similar classifiers and VC error bounds: Tech. Rep. CalTech-CS-TR97-14:6 1997.
Langford J. Quantitatively tight sample complexity bounds. — 2002. — Carnegie Mellon Thesis.

См. также

Теория Вапника-Червоненкиса
Слабая вероятностная аксиоматика
Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)
К. В. Воронцов — страница на MachineLearning.RU.
К. В. Воронцов — страница на сайте ВЦ РАН.

Это незавершённая статья о незавершённом исследовании.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BF%D0%B5%D1%80%D0%B5%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_%28%D0%B2%D0%B8%D1%80%D1%82%D1%83%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80%29»

Категории: Виртуальные семинары | Открытые проблемы и полемика | Теоретические исследования | Теория вычислительного обучения