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

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

(Различия между версиями)

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

Версия 14:01, 3 мая 2010

Содержание

1 Как были выявлены эффекты расслоения и сходства
2 Точные оценки вероятности переобучения
3 Методы получения точных оценок переобучения
4 Профиль расслоения и связности
5 Литература
6 См. также

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

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

Как были выявлены эффекты расслоения и сходства

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

VC-теория

Основной задачей в 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})$ размера $L{\times}D$ . Строки матрицы соотвествуют объектам полной выборки, столбцы — алгоритмам, значение $I_{id}=1$ означает, что алгоритм $a_d$ допускает ошибку на объекте $x_i$ . Столбец этой матрицы называется вектором ошибок алгоритма $a_d$ . Предполагается, что все векторы ошибок различны. Число столбцов $D$ в матрице ошибок называется также коэффициентом разнообразия (shattering coefficient) семейства алгоритмов.

В VC-теории доказывается верхняя оценка (при $\ell=k$ ), которая является сильно завышенной:

$Q_\varepsilon(\mu,X^L) \leq D \exp(\ell^2\varepsilon).$

Правая часть зависит только от размерных характеристик матрицы ошибок $L, D$ , но не от её содержимого. Этих величин явно недостаточно, чтобы характеризовать столь «тонкий» процесс, как обучение по прецедентам. В этом и заключается основная концептуальная причина завышенности классических VC-оценок.

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

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

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

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

В экспериментах вычислялся также эффективный локальный коэффициент разнообразия (ЭЛКР). Это такое число $D$ , при котором VC-оценка не являлась бы завышенной. Для него были получены удивительно небольшие значения — порядка $10^0..10^2$ в разных задачах, в то время как число $D$ имело порядки $10^6..10^{12}$ .

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

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

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

Зависимость $Q_\varepsilon(D)$ для четырёх семейств при $\ell=k=100,\; \varepsilon=0.05,\; m_0=10$ ; число разбиений в методе Монте-Карло — 10000;
[+Ц] — цепочка, [+Р] — с расслоением,
[-Ц] — не-цепочка, [-Р] — без расслоения.

Простейшим примером семейства алгоритмов с расслоением и связностью является монотонная цепочка алгоритмов. Оно строится следующим образом. Задаётся «лучший алгоритм», допускающий $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-теории.

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

Свойство расслоения

Определение. Расслоением семейства алгоритмов $A$ называется его разбиение на непересекающиеся подмножества — слои:

$A = A_0 \sqcup A_1 \sqcup \dots \sqcup A_L,$

где $m$ -й слой есть подмножество алгоритмов с $m$ ошибками на полной выборке:

$A_m = \bigl\{ a\in A:\: n(a,X^L)=m \bigr\}.$

Используемые на практике семейства алгоритмов, как правило, универсальны, то есть предназначены для решения очень широкого класса задач. Однако нас интересует решение лишь одной фиксированной задачи, в частности, восстановление конкретной функциональной зависимости $y(x)$ по выборке прецедентов $X=\bigl\{(x_i,y_i=y(x_i)):\: i=1,\ldots,\ell\bigr\}$ . При фиксированной целевой зависимости $y(x)$ подавляющее большинство алгоритмов допускают слишком много ошибок. Они практически никогда не будут выбираться методом обучения, каков бы ни был состав объектов $x_i,\: i=1,\ldots,\ell$ в обучающей выборке. Эффективно работают лишь алгоритмы из нескольких нижних слоёв, остальная часть семейства фактически остаётся незадействованной.

Свойство связности

Определение. Связностью $q(a)$ алгоритма $a\in A$ называется число алгоритмов в следующем слое, вектор ошибок которых отличается от $a$ только на одном объекте

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

Граф расслоения-связности

Определение. Графом расслоения-связности семейства алгоритмов $A$ называется граф, вершины которого соответствуют векторам ошибок; рёбрами соединяются векторы ошибок, отличающиеся только на одном объекте (хэммингово расстояние между которыми равно 1). Этот граф можно рассматривать как ориентированный, если договориться, что рёбра направлены от алгоритмов с меньшим числом ошибок к алгоритмам с большим числом ошибок.

Граф расслоения-связности зависит от семейства алгоритмов и от конкретной выборки.

Пример. На следующих рисунках показан начальный фрагмент матрицы ошибок (три нижних слоя) и граф расслоения-связности, порождаемые семейством линейных классификаторов на выборке из 10 объектов, по 5 объектов в каждом классе.

0-й слой (1 корректный алгоритм):	1-й слой (5 алгоритмов):	2-й слой (8 алгоритмов):

Матрица ошибок:	Граф расслоения-связности:

О природе переобучения

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

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

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

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

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

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

Один алгоритм

Если множество алгоритмов состоит из единственного элемента, $A=\{a\}$ , то именно он и возвращается методом обучения при любой обучающей выборке. Собственно, никакого обучения нет. Этот случай интересен тем, что вероятность переобучения выражается через гипергеометрическое распределение и является точной.

$Q_\varepsilon = H_L^{\ell,m} \bigl( \frac{\ell}{L}(m-\varepsilon k) \bigr),$

где

$m = n(a,X^L)$ — число ошибок алгоритма $a$ на полной выборке;

$H_L^{\ell,m}(s) = \sum_{t=0}^{\lfloor s \rfloor}\frac{C_m^s C_{L-m}^{\ell-t}}{C_L^\ell}$ — левый «хвост» гипергеометрического распределения.

Эта оценка является аналогом закона больших чисел в слабой вероятностной аксиоматике.

Эта оценка является «строительным блоком» для многих более сложных случаев.

Эта оценка является ненаблюдаемой, поскольку правая часть зависит от числа ошибок на контрольной выборки, которая скрыта в момент обучения. Однако, зная число ошибок на обучающей выборке $s = n(a,X)$ , нетрудно построить доверительный интервал для неизвестной величины $m$ .

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

Множество алгоритмов состоит из двух элементов, $A=\{a_1,a_2\}$ . Задаётся три параметра:

$m_1$ — число объектов полной выборки, на которых только $a_1$ допускает ошибку;

$m_2$ — число объектов полной выборки, на которых только $a_2$ допускает ошибку;

$m_0$ — число объектов полной выборки, на которых оба алгоритма допускают ошибку.

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

Оценка зависит от ненаблюдаемых параметров $m_0,m_1,m_2$ . Зная соотвествующие три величины на обучающей выборке $s_0,s_1,s_2$ , нетрудно построить доверительную область для неизвестных величин $m_0,m_1,m_2$ .

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

Если два алгоритма почти одинаковы, то переобучения почти нет (эффект сходства).
Если один из двух алгоритмов существенно лучше другого, то переобучения почти нет (эффект расслоения).
Переобучение максимально и достигает VC-оценки только когда алгоритмы максимально плохи (каждый допускает ошибки на половине объектов) и максимально различны.

Монотонная цепочка алгоритмов

Монотонная цепочка алгоритмов является моделью связного семейства с одним непрерывным параметром. Это именно то модельное семейство, которое использовалось во втором эксперименте (см. выше).

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

Монотонная цепочка почти не переобучается
Нескольких алгоритмов с наименьшим числом ошибок уже достаточно, чтобы очень точно вычислить вероятность переобучения монотонной цепочки.

Унимодальная цепочка алгоритмов

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

Получение точной оценки для унимодальной цепочки технически гораздо сложнее, чем для монотонной цепочки.

Единичная окрестность лучшего алгоритма

Единичная окрестность лучшего алгоритма — это множество алгоритмов, состоящее из фиксированного алгоритма, называемого «лучшим», и некоторого числа $D$ алгоритмов, допускающих ошибки на тех же объектах, что и «лучший» алгоритм, плюс ещё на каком-то одном объекте.

Связка монотонных цепочек

Это семейство является обобщением трёх предыдущих. Унимодальная цепочка — это связка из двух монотонных цепочек. Единичная окрестность — это связка из $D$ цепочек длины 2.

Слой булева куба

Слой булева куба — это множество всех $C_L^m$ алгоритмов, векторы ошибок которых содержат ровно $m$ единиц. Это пример семейства без расслоения. Оценка вероятности переобучения в этом случае является вырожденной и принимает только значения 0 или 1:

$Q_\varepsilon = \bigl[ \varepsilon k \leq m \leq L-\varepsilon\ell \bigr].$

Интервал булева куба и его расслоение

Интервал булева куба ранга $m$ — это множество алгоритмов, векторы ошибок которых определяются двумя множествами объектов:

$m_0$ «плохих» объектов, на которых все алгоритмы допускают ошибку;

$m$ «пограничных» объектов, на которых алгоритмы данного семейства допускают ошибки всеми возможными $2^m$ способами;

остальные $L-m_0-m$ объектов являются «хорошими»: на них ни один из алгоритмов не допускает ошибок.

Интервал булева куба содержит ровно $2^m$ алгоритмов.

Точная оценка получена как для интервала, так и для $d$ нижних слоёв интервала (это множество из $C_m^0+\cdots+C_m^d$ алгоритмов).

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

Вероятность переобучения очень быстро растёт по $m$ и по $d$ . Доля «пограничных» объектов в выборке практически гарантированно добавляется к величине переобученности.
Гипотеза о существовании пограничного слоя объектов выглядит весьма разумной для задач классификации. Однако в реальных семействах, скорее всего, реализуются далеко не все дихотомии множества пограничных объектов (иначе переобучение было бы слишком велико). Полный интервал булева куба вряд ли может служить адекватной моделью задач с пограничными объектами, а небольшое количество нижних слоёв интервала — вполне может.

Хэммингов шар и его расслоение

Хэммингов шар радиуса $R$ — это множество векторов ошибок, отличающихся от заданного вектора $a_0$ не более чем на $R$ объектах.

Хэммингов шар является моделью максимально плотного связного семейства с расслоением. Слой хэммингова шара (пересечение шара со слоем булева куба) является моделью максимально плотного связного семейства без расслоения. Поэтому оценку вероятности переобучения для слоя шара возможно использовать как нижнюю оценку вероятность переобучения для слоя заданной мощности $|A_m|$ .

Уже самый нижний слой хэммингова шара содержит слишком много алгоритмов, поэтому хэмминговы шаров вряд ли могут служить адекватными моделями нижних слоёв реальных семейств.

Монотонная многомерная сетка алгоритмов

Монотонная многомерная сетка алгоритмов является обобщением монотонной цепочки алгоритмов.

Унимодальная многомерная сетка алгоритмов

Методы получения точных оценок переобучения

Метод порождающих и запрещающих множеств

Рекуррентный метод

Блочный метод

Метод цепных разложений

Теоретико-групповой подход

Неравенства Бонферрони-Галамбоса

Профиль расслоения и связности

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

Литература

Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 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://www.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»

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

@@ Строка 6: / Строка 6: @@
 * математических техник, позволяющих учитывать эти эффекты в оценках [[Вероятность переобучения|вероятности переобучения]].
-== Точность оценок обобщающей способности ==
+== Как были выявлены эффекты расслоения и сходства ==
 Точные оценки [[Вероятность переобучения|вероятности переобучения]] необходимы для создания методов обучения по прецедентам, гарантирующих высокое качество классификации новых объектов, не вошедших в обучающую выборку.
@@ Строка 12: / Строка 12: @@
 Наиболее точные из известных оценок всё ещё сильно завышены.
-Основной задачей в теории статистического обучения является получение верхних оценок для функционала
+=== VC-теория ===
+Основной задачей в VC-теории считается получение верхних оценок для функционала
 ::<tex>P_\varepsilon(A) = \mathbb{P}_X\Bigl( \sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon \Bigr),</tex>
 где
@@ Строка 23: / Строка 24: @@
 * Если вероятностная мера <tex>P(a)</tex> неизвестна, то измерить функционал <tex>P_\varepsilon(A)</tex> непосредственно в эксперименте очень трудно, поскольку невозможно идентифицировать наступление события <tex>\sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon</tex>. А&nbsp;экспериментальное измерение необходимо для количественного анализа и понимания причин завышенности оценок. Выход заключается в том, чтобы вместо <tex>P(a)</tex> оценивать <tex>\nu(a,\bar X)</tex> — частоту ошибок алгоритма <tex>a</tex> на независимой контрольной выборке произвольной длины <tex>k</tex>. Тогда эмпирическое измерение функционала <tex>P_\varepsilon(A)</tex> становится возможным, например, методом Монте-Карло — путём генерации некоторого числа случайных разбиений полной выбоки <tex>X^L = X \sqcup \bar X</tex> на обучение и контроль. Здесь через <tex>L=\ell+k</tex> обозначена длина полной выборки.
 * Супремум в [[Теория Вапника-Червоненкиса|VC-теории]] вводится для того, чтобы получить наиболее общую оценку, не зависящую от конкретного [[метод обучения|метода обучения]] <tex>\mu</tex>, который по обучающей выборке <tex>X</tex> находит алгоритм <tex>a\in A</tex>. Однако на самом деле было бы правильнее оценивать [[вероятность переобучения]], то есть вероятность события <tex>|\delta_\mu(X,\bar X)| \geq \varepsilon</tex>, где разность <tex>\delta_\mu(X,\bar X) = \nu(\mu(X),\bar X)-\nu(\mu(X),X)</tex> называется ''переобученностью''. Введение супремума уже само по себе приводит к верхней оценке вероятности переобучения. Эта оценка может оказаться сильно завышенной, поскольку при решении прикладных задач методы обучения возвращают не любые алгоритмы из <tex>A</tex>, а лишь те, которые в определённом смысле «похожи» на восстанавливаемую зависимость.
-* Наконец, имеет смысл оценивать саму переобученность, а не её абсолютную величину, поскольку частоту ошибок на контрольной выборке, по смыслу задачи, необходимо ограничивать именно сверху, а не снизу.
+* Наконец, имеет смысл оценивать сверху саму переобученность, а не её абсолютную величину, поскольку частоту ошибок на контрольной выборке хотелось ограничивать именно сверху, а не снизу.
 === Понятие вероятности переобучения ===
@@ Строка 38: / Строка 39: @@
 Основным объектом изучения в комбинаторно-дискретной постановке является бинарная ''матрица ошибок'' <tex>I = (I_{id})</tex> размера <tex>L{\times}D</tex>.
-Строки матрицы соотвествуют объектам полной выборки, столбцы — алгоритмам, значение <tex>I_{id}=1</tex> означает, что алгоритм <tex>a_d</tex> допускает ошибку на объекте <tex>x_i</tex>. Столбец этой матрицы называется ''вектором ошибок'' алгоритма <tex>a_d</tex>.
+Строки матрицы соотвествуют объектам полной выборки, столбцы — алгоритмам, значение <tex>I_{id}=1</tex> означает, что алгоритм <tex>a_d</tex> допускает ошибку на объекте <tex>x_i</tex>.
+Столбец этой матрицы называется ''вектором ошибок'' алгоритма <tex>a_d</tex>.
-Число столбцов <tex>D</tex> в матрице ошибок (равное числу алгоритмов семейства, различимых на полной выборке) называется также [[коэффициент разнообразия|коэффициентом разнообразия]] (shattering coefficient) семейства алгоритмов.
+Предполагается, что все векторы ошибок различны.
+Число столбцов <tex>D</tex> в матрице ошибок называется также [[коэффициент разнообразия|коэффициентом разнообразия]] (shattering coefficient) семейства алгоритмов.
 В VC-теории доказывается верхняя оценка (при <tex>\ell=k</tex>), которая является сильно завышенной:
 ::<tex>Q_\varepsilon(\mu,X^L) \leq D \exp(\ell^2\varepsilon). </tex>
-Правая часть зависит от двух весьма грубых скалярных характеристик <tex>L, D</tex>, то есть, фактически, только от размера матрицы ошибок.
+Правая часть зависит только от размерных характеристик матрицы ошибок <tex>L, D</tex>, но не от её содержимого.
-Вряд&nbsp;ли этих величин может быть достаточно, чтобы характеризовать столь «тонкий» процесс, как обучение по прецедентам.
+Этих величин явно недостаточно, чтобы характеризовать столь «тонкий» процесс, как обучение по прецедентам.
 В&nbsp;этом и заключается основная концептуальная причина завышенности классических VC-оценок.
@@ Строка 68: / Строка 70: @@
 * Завышенность VC-оценок обусловлена тем, что они учитывают только длину выборки <tex>\ell</tex> и число различных алгоритмов&nbsp;<tex>D</tex>, но не учитывают степень их различности, то есть полностью игнорируют содержимое матрицы ошибок.
 * Для получения точных оценок необходимо ''одновременно'' учесть оба эффекта — и расслоение, и сходство.
-* Ни одна из существовавших до сих пор теорий не в состоянии объяснить столь низких значений локального эффективного коэффициента разнообразия.
+* Ни одна из существовавших до сих пор теорий не в состоянии объяснить столь низких значений коэффициента разнообразия.
 === Второй эксперимент (на модельных данных) ===
-[[Изображение:TestAlgsChain-200_100_10_all.png|300px|thumb|Зависимость <tex>Q_\varepsilon(D)</tex> для четырёх семейств при <tex>\ell=k=100</tex>, <tex>\varepsilon=0.05</tex>, <tex>m_0=10</tex>; число разбиений в методе Монте-Карло — 10000; [Ц]&nbsp;—&nbsp;цепочка, [Р]&nbsp;—&nbsp;расслоение.]]
+[[Изображение:TestAlgsChain-200_100_10_all.png|300px|thumb|Зависимость <tex>Q_\varepsilon(D)</tex> для четырёх семейств при <tex>\ell=k=100,\; \varepsilon=0.05,\; m_0=10</tex>; число разбиений в методе Монте-Карло — 10000; <br>[+Ц]&nbsp;—&nbsp;цепочка, [+Р]&nbsp;—&nbsp;с&nbsp;расслоением, <br>[-Ц]&nbsp;—&nbsp;не-цепочка, [-Р]&nbsp;—&nbsp;без расслоения.]]
 Простейшим примером семейства алгоритмов с расслоением и связностью является ''монотонная цепочка алгоритмов''.
@@ Строка 95: / Строка 97: @@
 * Связность заметно снижает темп роста зависимости <tex>Q_\varepsilon(D)</tex>.
 * Расслоение понижает уровень горизонтальной асимптоты <tex>Q_\varepsilon(D)</tex>.
-* Только при наличии обоих эффектов вероятность переобучения приемлемо мала, причём кривая «выходит на насыщение» после первых 5–7 алгоритмов. Основная масса «плохих» алгоритмов вообще не вносит вклад в переобучение.
+* Только при одновременном наличии и связности, и расслоения вероятность переобучения приемлемо мала, причём кривая «выходит на насыщение» после первых 5–7 алгоритмов. Основная масса «плохих» алгоритмов вообще не вносит вклад в переобучение.
 * При отсутствии либо расслоения, либо связности переобучение наступает уже при нескольких десятках алгоритмов.
 * Это означает, что реальные семейства, состоящие из огромного числа различных алгоритмов, с необходимостью должны быть расслоенными и связными.
 * Семейство без расслоения и без связности — это и есть тот наихудший случай, который изучается в [[Теория Вапника-Червоненкиса|VC-теории]].
-Этот эксперимент показал, что в теории переобучения необходимо развивать методы оценивания, учитывающие одновремнно оба эффекта — расслоение и сходство.
+Этот эксперимент показал направление дальнейших исследований: для получения точных оценок вероятности переобучения необходимо развивать методы, одновременно учитывающие эффекты расслоения и сходства в семействе алгоритмов.
+=== Свойство расслоения ===
+'''Определение.'''
+''Расслоением семейства'' алгоритмов <tex>A</tex> называется его разбиение на непересекающиеся подмножества — слои:
+::<tex>A = A_0 \sqcup A_1 \sqcup  \dots \sqcup A_L,</tex>
+где <tex>m</tex>-й ''слой'' есть подмножество алгоритмов с <tex>m</tex>&nbsp;ошибками на полной выборке:
+::<tex>A_m = \bigl\{ a\in A:\: n(a,X^L)=m \bigr\}.</tex>
+Используемые на практике семейства алгоритмов, как правило, универсальны, то есть предназначены для решения очень широкого класса задач.
+Однако нас интересует решение лишь одной фиксированной задачи, в&nbsp;частности, восстановление конкретной функциональной зависимости <tex>y(x)</tex> по выборке прецедентов <tex>X=\bigl\{(x_i,y_i=y(x_i)):\: i=1,\ldots,\ell\bigr\}</tex>.
+При фиксированной целевой зависимости <tex>y(x)</tex> подавляющее большинство алгоритмов допускают слишком много ошибок.
+Они практически никогда не будут выбираться методом обучения, каков бы ни был состав объектов <tex>x_i,\: i=1,\ldots,\ell</tex> в обучающей выборке.
+Эффективно работают лишь алгоритмы из нескольких нижних слоёв, остальная часть семейства фактически остаётся незадействованной.
+=== Свойство связности ===
+'''Определение.'''
+''Связностью'' <tex>q(a)</tex> алгоритма <tex>a\in A</tex> называется число алгоритмов в следующем слое, вектор ошибок которых отличается от <tex>a</tex> только на одном объекте
-=== О свойстве связности ===
 Многие параметрические семейства алгоритмов обладают следующим свойством:
 при изменении вектора параметров по некоторой непрерывной траектории каждое изменение вектора ошибок происходит только на одном объекте. Одновременное изменение нескольких координат возможно, но только для «редких» траекторий, образующих в пространстве траекторий множество меры нуль.
@@ Строка 109: / Строка 127: @@
 J.&nbsp;Sill называет такие семейства ''связными'', так как множество векторов ошибок всех алгоритмов семейства представляется в виде связного графа.
 E.&nbsp;Bax предлагает кластеризовать семейство на группы схожих классификаторов.
+=== Граф расслоения-связности ===
+'''Определение.'''
+''Графом расслоения-связности'' семейства алгоритмов <tex>A</tex> называется граф, вершины которого соответствуют векторам ошибок; рёбрами соединяются векторы ошибок, отличающиеся только на одном объекте (хэммингово расстояние между которыми равно&nbsp;1).
+Этот граф можно рассматривать как ориентированный, если договориться, что рёбра направлены от алгоритмов с меньшим числом ошибок к алгоритмам с большим числом ошибок.
+Граф расслоения-связности зависит от семейства алгоритмов и от конкретной выборки.
+'''Пример.'''
+На следующих рисунках показан начальный фрагмент матрицы ошибок (три нижних слоя) и граф расслоения-связности, порождаемые семейством линейных классификаторов на выборке из 10&nbsp;объектов, по&nbsp;5&nbsp;объектов в&nbsp;каждом классе.
+{|
+|-
+| 0-й слой (1 корректный алгоритм):
+| 1-й слой (5 алгоритмов):
+| 2-й слой (8 алгоритмов):
+|-
+| [[Изображение:SimpleSample0num.PNG|300px]]
+| [[Изображение:SimpleSample1.PNG|300px]]
+| [[Изображение:SimpleSample2.PNG|300px]]
+|}
+{|
+|-
+| Матрица ошибок:
+| Граф расслоения-связности:
+|-
+| [[Изображение:SimpleMatrix.png|600px]]
+| [[Изображение:SimpleGraph.PNG|300px]]
+|}
 === О природе переобучения ===
@@ Строка 123: / Строка 171: @@
 Это всё так, если алгоритмы берутся из распределения случайно и независимо.
-Однако, если алгоритмы зависимы
+Однако, если алгоритмы зависимы,
-(а&nbsp;в&nbsp;реальной ситуации они именно зависимы, причём очень сильно),
 то&nbsp;возникает надежда, что выбираемые алгоритмы будут концентрироваться гуще,
 и&nbsp;пик эмпирического распределения числа ошибок окажется более узким.
+В&nbsp;реальной ситуации алгоритмы зависимы, причём очень сильно, благодаря свойствам расслоения и сходства.
 == Точные оценки вероятности переобучения ==
@@ Строка 185: / Строка 233: @@
 Унимодальная цепочка алгоритмов является более реалистичной моделью связного семейства с&nbsp;одним непрерывным параметром, по сравнению с монотонной цепочкой. Представляется естественным, что если непрерывный параметр имеет оптимальное значение, то отклонение от него в обе стороны — как в сторону возрастания, так и в сторону убывания — приводит к росту числа ошибок на полной выборке.
-Вывод оценки для унимодальной цепочки технически гораздо сложнее, чем для монотонной цепочки.
+Получение точной оценки для унимодальной цепочки технически гораздо сложнее, чем для монотонной цепочки.
 === Единичная окрестность лучшего алгоритма ===
@@ Строка 208: / Строка 256: @@
 Интервал булева куба содержит ровно <tex>2^m</tex> алгоритмов.
+Точная оценка получена как для интервала, так и для <tex>d</tex> нижних слоёв интервала (это множество из <tex>C_m^0+\cdots+C_m^d</tex> алгоритмов).
+'''Основные выводы:'''
+* Вероятность переобучения очень быстро растёт по <tex>m</tex> и по <tex>d</tex>. Доля «пограничных» объектов в выборке практически гарантированно добавляется к величине переобученности.
+* Гипотеза о существовании пограничного слоя объектов выглядит весьма разумной для задач классификации. Однако в реальных семействах, скорее всего, реализуются далеко не все дихотомии множества пограничных объектов (иначе переобучение было бы слишком велико). Полный интервал булева куба вряд ли может служить адекватной моделью задач с пограничными объектами, а небольшое количество нижних слоёв интервала — вполне может.
 === Хэммингов шар и его расслоение ===
+Хэммингов шар радиуса <tex>R</tex> — это множество векторов ошибок, отличающихся от заданного вектора <tex>a_0</tex> не более чем на <tex>R</tex> объектах.
+Хэммингов шар является моделью максимально плотного связного семейства с расслоением.
+Слой хэммингова шара (пересечение шара со слоем булева куба) является моделью максимально плотного связного семейства без расслоения.
+Поэтому оценку вероятности переобучения для слоя шара возможно использовать как нижнюю оценку вероятность переобучения для слоя заданной мощности <tex>|A_m|</tex>.
+Уже самый нижний слой хэммингова шара содержит слишком много алгоритмов, поэтому хэмминговы шаров вряд ли могут служить адекватными моделями нижних слоёв реальных семейств.
 === Монотонная многомерная сетка алгоритмов ===
+Монотонная многомерная сетка алгоритмов является обобщением монотонной цепочки алгоритмов.
 === Унимодальная многомерная сетка алгоритмов ===

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

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

Версия 14:01, 3 мая 2010

Содержание

Как были выявлены эффекты расслоения и сходства

VC-теория

Понятие вероятности переобучения

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

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

Свойство расслоения

Свойство связности

Граф расслоения-связности

О природе переобучения

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

Один алгоритм

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

Монотонная цепочка алгоритмов

Унимодальная цепочка алгоритмов

Единичная окрестность лучшего алгоритма

Связка монотонных цепочек

Слой булева куба

Интервал булева куба и его расслоение

Хэммингов шар и его расслоение

Монотонная многомерная сетка алгоритмов

Унимодальная многомерная сетка алгоритмов

Методы получения точных оценок переобучения

Метод порождающих и запрещающих множеств

Рекуррентный метод

Блочный метод

Метод цепных разложений

Теоретико-групповой подход

Неравенства Бонферрони-Галамбоса

Профиль расслоения и связности

Литература

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты