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

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

Версия 21:45, 21 ноября 2009

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

Мотивация

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

Первый эксперимент

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

1. Пренебрежение эффектом расслоения (или локализации) семейства алгоритмов. Чем хуже классификатор решает данную задачу, тем меньше шансов получить его в результате настройки по обучающей выборке. Это означает, что реально работает не всё семейство, а только какая-то его часть, своя в каждой задаче. Степень завышенности: от нескольких десятков раз до сотен тысяч раз, в зависимости от задачи.
2. Пренебрежение сходством алгоритмов. При выводе оценок используется оценка вероятности объединения событий суммой их вероятностей (union bound). «События» соответствуют алгоритмам; точнее, d-м «событием» является слишком большое уклонение частоты ошибок на тестовой и обучающей выборках для d-го алгоритма. Union bound становится чрезвычайно завышенной оценкой, если среди событий (то есть среди алгоритмов) есть похожие. Степень завышенности: от нескольких сотен до десятков тысяч раз. Этот фактор всегда существенен и не так сильно зависит от задачи, как первый.
3. Экспоненциальная аппроксимация хвоста гипергеометрического распределения. Вроде бы точность аппроксимации увеличивается с ростом длины выборки — оба хвоста быстро стремятся к нулю. Тем не менее, относительная погрешность (отношение аппроксимации к точному значению) с ростом выборки растёт! Формула с экспонентой, конечно, приятна на глаз, но степень завышенности может достигать нескольких десятков. Отсюда вывод: по возможности не пользоваться аппроксимациями.
4. Верхняя оценка профиля разнообразия одним скалярным коэффициентом разнообразия (shatter coefficient). Степень завышенности часто порядка единицы, но в некоторых задачах может достигать нескольких десятков. Этот результат получен для логических закономерностей; если оценивать классификаторы, а не закономерности, то этот фактор завышенности должен возрасти. Фактор достаточно просто исключается из оценки для семейства алгоритмов, если union bound используется для объединения оценок отдельных алгоритмов, не зависящих от неизвестной вероятности ошибки каждого алгоритма. Так устроена, к примеру, оценка Occam Razor.

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

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

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

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

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

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

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

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

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

Цепочки алгоритмов

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

Эксперименты показывают следующее.

• Для цепочек вероятность переобучения растёт гораздо медленнее с увеличением числа алгоритмов, чем для не-цепочек.
• Расслоение приводит к снижению максимального уровня вероятности переобучения; если семейство не расслаивается, то вероятность переобучения с ростом числа алгоритмов быстро достигает единицы.
• Семейство без расслоения и без цепочек — как раз и есть тот наихудший случай, который изучается теорией Вапника-Червоненкиса. На практике, как правило, приходится работать со связными и расслоёнными семействами.

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

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

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

В декабре 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 КБ).

Литература

1. Sill J. Generalization bounds for connected function classes.
2. Bax E. T. Similar classifiers and VC error bounds: Tech. Rep. CalTech-CS-TR97-14:6 1997.
3. Langford J. Quantitatively tight sample complexity bounds. — 2002. — Carnegie Mellon Thesis.

См. также

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

• Комбинаторные неравенства
• Неравенство Бонферрони

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