Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{TOCright}} Данный виртуальный семинар предназначен для обсуждения проблемы учёта расслоения семейства алгоритмов и сходства алгоритмов в оценках [[обобщающая способность|обобщающей способности]]. == Мотивация == Получение точных верхних оценок вероятности [[переобучение|переобучения]] остаётся открытой проблемой в [[теория вычислительного обучения|теории статистического обучения]] уже более 40 лет, начиная с работ [[Вапник, Владимир Наумович|В. Н. Вапника]] и [[Червоненкис, Алексей Яковлевич|А. Я. Червоненкиса]]. Наиболее точные из известных оценок всё ещё сильно завышены. === Первый эксперимент === В экспериментах на реальных задачах классификации установлены основные причины завышенности и вычислены ''степени завышенности'' — коэффициенты, показывающие, во сколько раз каждая из этих причин завышает оценку вероятности переобучения. Причины, в&nbsp;порядке убывания важности: # Пренебрежение эффектом ''расслоения'' (или ''локализации'') семейства алгоритмов. Чем хуже классификатор решает данную задачу, тем меньше шансов получить его в результате настройки по обучающей выборке. Это означает, что реально работает не всё семейство, а только какая-то его часть, своя в каждой задаче. '''Степень завышенности:''' от нескольких десятков раз до сотен тысяч раз, в зависимости от задачи. # Пренебрежение сходством алгоритмов. При выводе оценок используется оценка вероятности объединения событий суммой их вероятностей (union bound). «События» соответствуют алгоритмам; точнее, ''d''-м «событием» является слишком большое уклонение частоты ошибок на тестовой и обучающей выборках для ''d''-го алгоритма. Union bound становится чрезвычайно завышенной оценкой, если среди событий (то есть среди алгоритмов) есть похожие. '''Степень завышенности:''' от нескольких сотен до десятков тысяч раз. Этот фактор всегда существенен и не так сильно зависит от задачи, как первый. # Экспоненциальная аппроксимация хвоста гипергеометрического распределения. Вроде бы точность аппроксимации увеличивается с ростом длины выборки — оба хвоста быстро стремятся к нулю. Тем не менее, относительная погрешность (отношение аппроксимации к точному значению) с ростом выборки растёт! Формула с экспонентой, конечно, приятна на глаз, но '''степень завышенности''' может достигать нескольких десятков. Отсюда вывод: по возможности не пользоваться аппроксимациями. # Верхняя оценка профиля разнообразия одним скалярным [[коэффициент разнообразия|коэффициентом разнообразия]] (shatter coefficient). '''Степень завышенности''' часто порядка единицы, но в некоторых задачах может достигать нескольких десятков. Этот результат получен для [[логическая закономерность|логических закономерностей]]; если оценивать классификаторы, а не закономерности, то этот фактор завышенности должен возрасти. Фактор достаточно просто исключается из оценки для семейства алгоритмов, если union bound используется для объединения оценок отдельных алгоритмов, не зависящих от неизвестной вероятности ошибки каждого алгоритма. Так устроена, к примеру, оценка [[Occam Razor оценка вероятности переобучения|Occam Razor]]. === Замечание о природе переобучения === Вообще, [[переобучение]] возникает из-за того, что выбирается алгоритм с минимальным числом ошибок на обучающей выборке. Сделаем мысленный эксперимент. Представим, что все алгоритмы семейства имеют одинаковую вероятность ошибок. Тогда число ошибок на конечной выборке подчиняется биномиальному распределению, имеющему форму пика. Шансы отдельному алгоритму угодить в левый хвост распределения невелики. Однако чем больше алгоритмов мы будем брать, тем дальше влево будет смещаться минимальное (по всем взятым алгоритмам) число ошибок; тем больше будет разность между частотой и вероятностью ошибок у «лучшего» алгоритма. Но&nbsp;это и есть переобучение. Это всё так, если алгоритмы берутся из распределения случайно и независимо. Однако, если алгоритмы зависимы (а&nbsp;в&nbsp;реальной ситуации они именно зависимы, причём очень сильно), то возникает надежда, что выбираемые алгоритмы будут концентрироваться гуще, и пик эмпирического распределения числа ошибок окажется более узким. === Пара алгоритмов === Получены точные формулы для вероятности переобучения при выборе лучшего из двух алгоритмов. Если алгоритмы совпадают, то вероятность переобучения равна вероятности большого уклонения частот в двух подвыборках для отдельного алгоритма, и описывается гипергеометрическим распределением. Если алгоритмы существенно различны, но имеют одинаковый уровень ошибок, то вероятность переобучения увеличивается вдвое. Если алгоритмы имеют существенно различный уровень ошибок, то вероятность переобучения уменьшается. '''Выводы:''' уже при выборе одного из двух алгоритмов может возникать переобучение. Расслоение алгоритмов по числу ошибок и увеличение сходства уменьшают вероятность переобучения. === Как устроены реально используемые семейства === Многие параметрические семейства алгоритмов обладают следующим свойством: при изменении вектора параметров по некоторой непрерывной траектории каждое изменение вектора ошибок происходит только на одном объекте. Одновременное изменение нескольких координат возможно, но только для «редких» траекторий, образующих в пространстве траекторий множество меры нуль. В&nbsp;частности, этим свойством обладают классификаторы с непрерывной по параметрам разделяющей поверхностью: [[линейный классификатор|линейные классификаторы]], [[SVM]] с непрерывными ядрами, [[нейронная сеть|нейронные сети]] с непрерывными функциями активации, [[решающее дерево|решающие деревья]] с пороговыми условиями ветвления, и многие другие. J.&nbsp;Sill называет такие семейства ''связными'', так как множество векторов ошибок всех алгоритмов семейства представляется в виде связного графа. E.&nbsp;Bax предлагает кластеризовать семейство на группы схожих классификаторов. === Цепочки алгоритмов === Цепочкой будем называть такую последовательность векторов ошибок, в которой хэммингово расстояние между последовательными векторами равно 1. Эксперименты показывают следующее. * Для цепочек вероятность переобучения растёт гораздо медленнее с увеличением числа алгоритмов, чем для не-цепочек. * Расслоение приводит к снижению максимального уровня вероятности переобучения; если семейство не расслаивается, то вероятность переобучения с ростом числа алгоритмов быстро достигает единицы. * Семейство без расслоения и без цепочек — как раз и есть тот наихудший случай, который изучается [[Теориея Вапника-Червоненкиса|теорией Вапника-Червоненкиса]]. На&nbsp;практике, как правило, приходится работать со связными и расслоёнными семействами. === Основной вопрос данного виртуального семинара === Как учесть связность и расслоенность в семействах алгоритмов для получения незавышенных оценок вероятности переобучения? == Точные оценки вероятности переобучения == В декабре 2008 удалось доказать одну общую теорему, позволяющую получать '''точные оценки вероятности переобучения'''. Очевидно, они учитывают и связность, и расслоенность. Частные результаты пока получены только для нескольких искусственных семейств: монотонных и унимодальных цепочек, единичной окрестности оптимального алгоритма, двухэлементного семейства. Есть основания полагать, что новый комбинаторный подход удастся распространить и на семейства более общего вида. {{well| '''Список открытых проблем''', оформленный в виде задач по спецкурсу «[[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)|Теория надёжности обучения по прецедентам]]».<br>'''[[Media:Voron09exact.pdf|(PDF, 180&nbsp;КБ)]]'''. }} == Ссылки == Более подробно результаты можно посмотреть здесь: * март 2009. '''Точные оценки вероятности переобучения'''. '''[[Media:Voron09exact.pdf|(PDF, 336&nbsp;КБ)]]'''. * октябрь 2008. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. Развёрнутая версия статьи на [[РОАИ|РОАИ-9-2008]]. '''[[Media:Voron09roai2008.pdf|(PDF, 354&nbsp;КБ)]]'''. * 17 сентября 2008. Пути повышения точности оценок обобщающей способности (комбинаторный подход). Пленарный доклад на международной конференции [[РОАИ|РОАИ-9-2008]], Нижний Новгород. Презентация на&nbsp;английском '''[[Media:VoronBeam-PRIA-2008(eng).pdf|(PDF,&nbsp;846&nbsp;КБ)]]''', на русском '''[[Media:VoronBeam-PRIA-2008(rus).pdf|(PDF,&nbsp;844&nbsp;КБ)]]''', тезисы доклада на&nbsp;русском '''[[Media:Vorontsov-ROAI-2008-rus.pdf|(PDF,&nbsp;243&nbsp;КБ)]]'''. * 12 июня 2008. Слабая вероятностная аксиоматика, оценки надёжности эмпирических предсказаний, расслоение и различность алгоритмов. Конференция [[ИОИ]]-2008. '''[[Media:VoronBeam-IOI-2008.pdf|(PDF,&nbsp;950&nbsp;КБ)]]'''. * 28 апреля 2008. Ломоносовские чтения 2008. Оценки надёжности эмпирических предсказаний (комбинаторный подход). '''[[Media:VoronBeam2008-04-18.pdf|(PDF,&nbsp;804&nbsp;КБ)]]'''. == Литература == # ''Sill J.'' [http://citeseer.ist.psu.edu/127284.html Generalization bounds for connected function classes]. # ''Bax E. T.'' [http://citeseer.ist.psu.edu/bax97similar.html Similar classifiers and VC error bounds]: Tech. Rep. CalTech-CS-TR97-14:6 1997. # ''Langford J.'' [http://citeseer.ist.psu.edu/langford02quantitatively.html Quantitatively tight sample complexity bounds]. — 2002. — Carnegie Mellon Thesis. == См. также == * [[Слабая вероятностная аксиоматика]] * [[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)]] * [[Участник:Vokov|К. В. Воронцов]] — страница на MachineLearning.RU. * [http://www.ccas.ru/voron К.&nbsp;В.&nbsp;Воронцов] — страница на сайте ВЦ РАН. {{stop| '''Это незавершённая статья о незавершённом исследовании.'''<br/> }} [[Категория:Виртуальные семинары]] [[Категория:Открытые проблемы и полемика]] [[Категория:Теория вычислительного обучения]]

• Шаблон:Mbox
• Шаблон:Stop
• Шаблон:TOCright
• Шаблон:Биб.статья
• Шаблон:Диссертация
• Шаблон:Переводы
• Шаблон:Подробнее
• Публикация:Воронцов 2010 Комбинаторная теория

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