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

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

Версия 13:11, 23 сентября 2008

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

Мотивация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

• 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.
• К. В. Воронцов — страница на сайте ВЦ РАН.

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