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

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

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

Текущая версия

Содержание

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

Комбинаторная теория переобучения изучает проблему надёжности принятия решений по неполной информации в следующей дискретной постановке. Задана бинарная матрица ошибок. Её строки соответствуют объектам, столбцы — алгоритмам; единица в матрице означает, что данный алгоритм ошибается на данном объекте. Требуется найти алгоритм, число ошибок которого как можно меньше, при условии, что наблюдается не вся матрица, а только случайное подмножество её строк. Говорят также, что алгоритм обучается по наблюдаемым данным. Предполагается, что все разбиения множества объектов на $\ell$ наблюдаемых и $k$ скрытых могут реализоваться с равной вероятностью. Если найденный алгоритм мало ошибается на скрытых объектах, то говорят, что метод обучения способен к обобщению. Если же частота ошибок найденного алгоритма на скрытых объектах существенно выше частоты его ошибок на наблюдаемых объектах, то говорят, что произошло переобучение. Основными задачами комбинаторной теории переобучения является получение оценок вероятности переобучения и полного скользящего контроля, разработка эффективных методов их вычисления, создание на их основе новых методов восстановления закономерностей по эмпирическим данным.

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

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

Оценки обобщающей способности: история вопроса

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

VC-теория

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

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

где

$A$ — семейство алгоритмов, из которого по обучающей выборке $X$ выбирается некоторый алгоритм;

$P(a)$ — вероятность ошибки алгоритма $a \in A$ ;

$\nu(a,X)$ — частота ошибок алгоритма $a \in A$ на независимой обучающей выборке длины $\ell$ ;

$\mathbb{P}_X$ — некоторая неизвестная вероятностная мера на множестве объектов.

Смысл этого функционала в том, что если частота ошибок не сильно отклоняется от вероятности ошибки одновременно для всех алгоритмов $a \in A$ , то алгоритм, найденный путём минимизации эмпирического риска,

$a^{*} = \arg\min_{a\in A} \nu(a,X),$

будет иметь малую вероятность ошибиться и на новых данных, иными словами, будет иметь хорошую обобщающую способность.

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

«Для любого $a \in A$ с вероятностью не менее $1-\eta$ выполняется $P(a) \leq \nu(a,X)+\varepsilon(\eta)$ »,

где $\varepsilon(\eta)$ — функция, обратная к $\eta(\varepsilon) = P_\varepsilon(A)$ .

У функционала $P_\varepsilon$ есть несколько недостатков.

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

Супремум в VC-теории вводится для того, чтобы получить наиболее общую оценку, не зависящую от конкретного метода обучения $\mu$ , который по обучающей выборке $X$ находит алгоритм $a\in A$ . Однако на самом деле было бы правильнее оценивать вероятность переобучения — вероятность того, что частота ошибок найденного алгоритма на контроле будет существенно больше частоты его ошибок на обучении
$\delta_\mu(X) = \nu(\mu(X),\bar X)-\nu(\mu(X),X) \geq \varepsilon$ ,
где величина $\delta_\mu(X)$ называется переобученностью. Введение супремума приводит к верхней оценке вероятности переобучения. Эта оценка может оказаться сильно завышенной, поскольку при решении прикладных задач методы обучения возвращают не любые алгоритмы из $A$ , а лишь те, которые в определённом смысле «похожи» на восстанавливаемую зависимость.

Наконец, имеет смысл оценивать сверху саму переобученность, а не её абсолютную величину, поскольку частоту ошибок на контрольной выборке хотелось бы ограничивать именно сверху, а не снизу.

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

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

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

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

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

Вероятность $\mathbb{P}$ понимается здесь и далее в смысле равномерного распределения на множестве всех $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) семейства алгоритмов.

Комбинаторная оценка для одного алгоритма

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

Теорема (one-classifier bound, OC-bound). Для любого алгоритма $a$ , любой выборки $X^L$ и любого $\varepsilon\in(0,1)$

$Q_\varepsilon(a,X^L) = 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}$ — функция гипергеометрического распределения.

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

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

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

Комбинаторная VC-оценка

Оценка для общего случая получается путём суммирования OC-оценок по всему семейству.

Теорема (Vapnik-Chervonenkis bound, VC-bound). Для любого семейства $A$ , любого метода обучения $\mu$ , любой выборки $X^L$ и любого $\varepsilon\in(0,1)$

$Q_\varepsilon(\mu,X^L) \;\leq\; \sum_{a\in A} H_L^{\ell,m} \bigl( \frac{\ell}{L}(m-\varepsilon k) \bigr),$

где

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

$H_L^{\ell,m}(s)$ — функция гипергеометрического распределения.

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

Шаг 1. Вероятность переобучения оценивается сверху вероятностью большого равномерного отклонения частот (uniform bound). В результате получаем оценку, справедливую для любого метода обучения $\mu$ .

$Q_\varepsilon(\mu,X^L) = \mathbb{P} \Bigl[ \delta_\mu(X) \geq \varepsilon \Bigr] \;\leq\; \tilde Q_\varepsilon(A,X^L) = \mathbb{P} \max_{a\in A} \Bigl[ \delta_a(X) \geq \varepsilon \Bigr].$

Шаг 2. Максимум бинарных величин оценивается сверху их суммой. Или, что то же самое, вероятность объединения событий оценивается сверху суммой их вероятностей. Это называется неравенством Буля или union bound:

$\tilde Q_\varepsilon(A,X^L) \;\leq\; \sum_{a\in A} \mathbb{P} \Bigl[ \delta_a(X) \geq \varepsilon \Bigr].$

Теперь остаётся применить OC-оценку под знаком суммы. Теорема доказана.

Чтобы получить VC-оценку в классической записи, необходимо положить $\ell=k$ и сделать ещё два чисто технических огрубления: во-первых, оценить сверху функцию гипергеометрического распределения при наихудшем $m$ ; во-вторых, применить асимптотическую оценку для левого хвоста гипергеометрического распределения.

Следствие.

$Q_\varepsilon(\mu,X^L) \;\leq\; |A| \,\cdot\, \exp(-\ell^2\varepsilon).$

Эта оценка является сильно завышенной. Она справедлива для любой восстанавливаемой зависимости, любой выборки и любого метода обучения. Следовательно, это оценка худшего случая. Примерно понятно, что есть «худший случай» — когда никакой зависимости в данных нет, а метод обучения настолько глуп, что выбирает алгоритм наугад. Очевидно, худший случай не интересен, и на практике никогда не реализуется.

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

Развитие теории вычислительного обучения

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

Теория равномерной сходимости [Вапник, Червоненкис, 1968]

Показано, что достаточным условием обучаемости является конечная ёмкость (VC-размерность) семейства алгоритмов. Отсюда многие исследователи делали неправильный вывод, что для хорошей обучаемости необходимо органичивать сложность семейства. Позже работы Матросова и алгоритм бустинга перевернули эти представления. Заметим, что для доказательства основных содержательных утверждений VC-теории применялись чисто комбинаторные методы.

Корректные алгоритмические композиции ограниченной ёмкости [Матросов, 1980]

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

Theory of learnable (PAC-learning) [Valiant, 1982]

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

Data-dependent bounds [Haussler, 1992]

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

Concentration inequalities [Talagrand, 1995]

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

Connected function classes [Sill, 1995]

Неудачная попытка учесть связность в семействах алгоритмов. Учитывалась только связность в обычном понимании теории графов, как возможность построить путь между любыми двумя алгоритмами. Оценка оказалась лишь немного лучше VC, и эта работа осталась незамеченной. Только теперь стало ясно, что надо было учитывать количество связей у каждого алгоритма.

Similar classifiers VC bounds [Bax, 1997]

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

Margin based bounds [Bartlett, 1998]

Генеральное направление развития теории обобщающей способности в конце 90-х — начале 00-х. Учёт распределения отступов на обучающей выборке действительно позволил улучшить оценки обобщающей способности, но не радикально. Самое главное — он привёл к конструктивным обоснованиям линейных алгоритмов классификации, алгоритма бустинга, нейронных сетей.

Self-bounding learning algorithms [Freund, 1998]

Метод структурной минимизации риска в VC-теории требовал заранее задавать структуру вложенных подсемейств в семействе алгоритмов, и затем с помощью оценки обобщающей способности выбирать из них подсемейство оптимальной сложности. Самоограничивающие алгоритмы строят структуру вложенных подсемейств в процессе обучения. Таким образом, оценка оказывается зависящей от данных.

Rademacher complexity [Koltchinskii, 1998]

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

Adaptive microchoice bounds [Langford, Blum, 2001]

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

Algorithmic stability [Bousquet, Elisseeff, 2002]

Концепция стабильности (устойчивости) метода обучения относительно состава обучающей выборки некоторое время казалась перспективной альтернативой VC-теории. Например, ещё в 70-е годы такие оценки были получены для метода ближайших соседей и метода потенциальных функций. Однако на этом пути так и не удалось получить численно точных оценок. Само понятие стабильности оказалось довольно трудно определить, было введено около двух десятков различных понятий стабильности, и установлены нетривиальные связи между ними. Доказана стабильность многих практических методов обучения. Однако завышенность оценок, основанных на стабильности, оставалась на том же уровне, что и завышенность VC-оценок.

Algorithmic luckiness [Herbrich, Williamson, 2002]

Попытка учесть расслоение семейства алгоритмов, не вполне удачная, так как вся сложность задачи «упрятывалась» в некоторую функцию удачности (luckiness function), которую предлагалось угадывать в каждом конкретном случае, без чётко проработанной методологии такого угадывания.

Shell bounds [Langford, 2002]

Попытка учесть расслоение семейства алгоритмов, не вполне удачная, так как снова использовалась оценка union bound (а теперь мы знаем, что при этом невозможно учесть сходство алгоритмов). Несмотря на рекламные заявления автора, что оценки могут быть очень точны, эксперименты, проведённые Денисом Кочедыковым, показали, что они лишь немного лучше VC-оценок.

PAC-Bayes bounds [McAllester, 1999; Langford, 2005]

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

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

В комбинаторном подходе оцениваемый функционал $Q_\varepsilon$ легко измерить эмпирически методом Монте-Карло, взяв среднее по некоторому случайному подмножеству разбиений полной выборки на две подвыборки, обучающую и контрольную. Более того, можно оценить и промежуточные величины, которые появляются в ходе вывода VC-оценки, и узнать, какова потеря точности на каждом шаге. Заметим, что ничего подобного в исходной вероятностной постановке сделать нельзя, так как функционал $P_\varepsilon(A)$ с трудом поддаётся эмпирическому измерению. Методика его измерения была предложена Вапником и Ботту (1994), однако эти работы остались практически незамеченными, что не удивительно: измеренные значения функционала $P_\varepsilon(A)$ близки к единице, что свидетельствует о сильной завышенности равномерной оценки (uniform bound) и слишком явно говорит о непрактичности функционала, положенного в основу VC-теории.

Содержательные эксперименты стали возможны только после того, как 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-оценок обусловлена тем, что они учитывают только длину выборки $L$ и число различных алгоритмов $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 алгоритмов. Основная масса «плохих» алгоритмов вообще не вносит вклад в переобучение.
При отсутствии либо расслоения, либо связности вероятность переобучения становится порядка $0.5$ уже при нескольких десятках алгоритмов.
Это означает, что реальные семейства, состоящие из огромного числа различных алгоритмов, с необходимостью должны быть расслоенными и связными.
Семейство без расслоения и без связности — это и есть тот наихудший случай, который изучается в VC-теории.

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

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

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

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

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

Оценки расслоения–связности

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

Определение. Расслоением семейства алгоритмов $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\}.$

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

Используемые на практике семейства алгоритмов, как правило, универсальны, то есть предназначены для решения очень широкого класса задач. Однако нас интересует решение лишь одной фиксированной задачи, в частности, восстановление конкретной функциональной зависимости $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$ только на одном объекте.

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

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

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

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

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

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

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

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

Эксперименты с линейными классификаторами проведены Ильёй Решетняком.

Оценка расслоения–связности

Теорема (splitting and connectivity bound, SC-bound). Если $\mu$ — метод минимизации эмпирического риска, то для любой выборки $X^L$ и любого $\varepsilon\in(0,1)$ справедлива оценка сверху:

$Q_\varepsilon(\mu,X^L) \;\leq\; \sum_{a\in A} W_{rq} H_{L-q-r}^{\ell-q,\,m-r}\Bigl(\frac{\ell}{L}(m-\varepsilon k)\Bigr),$

$\mathbb{P}\bigl[ \mu(X)=a \bigr] \;\leq\; W_{rq} = \frac{C_{L-q-r}^{\ell-q}}{C_{L}^{\ell}},$

где

$q=q(a)$ — верхняя связность алгоритма $a$ ;

$r=r(a)$ — неоптимальность алгоритма $a$ ;

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

$H_L^{\ell,m}(s)$ — функция гипергеометрического распределения.

Эта оценка является взвешенной суммой OC-оценок с весами $W_{rq}$ , имеющими следующие свойства:

вес $W_{rq}=1$ при $r=q=0$ ; это означает, что если пренебречь расслоением и связностью, то SC-оценка перейдёт непосредственно в VC-оценку;
вес $W_{rq}$ является верхней оценкой вероятности того, что алгоритм будет получен в результате обучения по случайной обучающей подвыборке;
вес $W_{rq}$ убывает экспоненциально по $r$ и по $q$ .

Отсюда вытекают два главных вывода:

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

Нижние слои содержат, как правило, очень малую долю алгоритмов. Поэтому можно надеяться, что перебор алгоритмов из нижних слоёв позволит достаточно эффективно вычислять SC-оценки.

Оценка равномерноcти–связности

Лемма. Если в качестве метода обучения $\mu$ взять метод максимизации отклонения частот (discrepancy maximization),

$\mu(X) = \arg\max_{a\in A} \delta_a(X),$

то функционал равномерного отклонения совпадёт с функционалом вероятности переобучения:

$Q_\varepsilon(\mu,X^L) = \mathbb{P} \Bigl[ \delta_\mu(X) \geq \varepsilon \Bigr] \;=\; \tilde Q_\varepsilon(A,X^L) = \mathbb{P} \Bigl[ \max_{a\in A} \delta_a(X) \geq \varepsilon \Bigr].$

Теорема (uniform connectivity bound, UC-bound). Для любого семейства $A$ , любой выборки $X^L$ и любого $\varepsilon\in(0,1)$ справедлива оценка сверху:

$\tilde Q_\varepsilon(A,X^L) \;\leq\; \sum_{a\in A} \tilde W_{pq} H_{L-q-p}^{\ell-q,\,m-p}\Bigl(\frac{\ell}{L}(m-\varepsilon k)\Bigr),$

$\mathbb{P}\bigl[ \mu(X)=a \bigr] \;\leq\; \tilde W_{pq} = \frac{C_{L-q-p}^{\ell-q}}{C_{L}^{\ell}},$

где

$\mu$ — метод максимизации отклонения частот;

$q=q(a)$ — верхняя связность алгоритма $a$ ;

$p=p(a)$ — нижняя связность алгоритма $a$ ;

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

$H_L^{\ell,m}(s)$ — функция гипергеометрического распределения.

Эта оценка, как и SC-оценка, является взвешенной суммой OC-оценок.

Если пренебречь связностью, $q=p=0$ , то UC-оценка также переходит в VC-оценку.

UC-оценка может быть только выше SC-оценки, поскольку $p(a) \leq r(a)$ для любого алгоритма $a$ .

Сравнение с SC-оценкой показывает также, что UC-оценка пренебрегает расслоением. Вместо неоптимальности алгоритма $r(a)$ , которая растёт линейно с ростом номера слоя, в ней фигурирует нижняя связность $p(a)$ , которая примерно равна верхней связности и примерно одинакова у всех алгоритмов.

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

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

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

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

Множество алгоритмов состоит из двух элементов, $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|$ .

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

Точные оценки вероятности переобучения для хэммингова шара и его слоёв получены Ильёй Толстихиным.

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

Монотонная сетка алгоритмов является многомерным обобщением монотонной цепочки алгоритмов. Монотонная $h$ -мерная сетка является моделью связного семейства алгоритмов с $h$ непрерывными параметрами. Есть основания полагать, что нижние слои монотонных сеток могут быть использованы в качестве достаточно адекватных моделей реальных семейств, при надлежащем подборе параметра размерности $h$ .

Точные оценки вероятности переобучения для монотонных и унимодальных многомерных сеток получены Павлом Ботовым.

Слева: одномерная монотонная сетка высоты 3 (монотонная цепочка). Справа: двумерная монотонная сетка высоты 3. Горизонтальные линии отмечают слои — число ошибок на полной выборке. Объекты вдоль стрелок означают, что переход от нижнего алгоритма к верхнему связан с появлением ошибки на данном объекте.

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

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

Вероятность переобучения унимодальной сетки приблизительно равно вероятности переобучения монотонной сетки удвоенной размерности.

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

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

Метод основан на следующем предположении.

Гипотеза 1. Для любого алгоритма семейства $a\in A$ можно указать порождающее множество объектов $X_a\subseteq X^L$ и запрещающее множество объектов $X'_a\subseteq X^L$ такие, что для любого разбиения полной выборки на обучение и контроль, $X^L = X\sqcup\bar X$ справедливо

$[\mu(X)=a] \;=\; [X_a\subseteq X][X'_a\subseteq \bar X].$

Это предположение справедливо для монотонной цепочки, единичной окрестности и многомерной монотонной сетки. Зная для любого алгоритма $a\in A$ его порождающее и запрещающее множества, можно без труда выписать точные оценки вероятности переобучения, а также $P_a = \mathbb{P}[\mu(X)=a]$ — вероятности того, что данный алгоритм будет выбран в результате обучения.

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

Гипотеза 2. Для любого алгоритма семейства $a\in A$ можно указать совокупность $V_a$ пар множеств: порождающие множества объектов $X_{av}\subseteq X^L$ и запрещающие множества объектов $X'_{av}\subseteq X^L$ такие, что для любого разбиения полной выборки на обучение и контроль, $X^L = X\sqcup\bar X$ справедливо

$[\mu(X)=a] \;=\; \sum_{v\in V_a} c_{av}[X_{av}\subseteq X][X'_{av}\subseteq \bar X],$

при некоторых вещественных коэффициентах $c_{av}$ (пока не известны ситуации, когда $c_{av}\neq\pm 1$ ).

Зная для любого алгоритма $a\in A$ все пары порождающих и запрещающих множеств, также можно без труда выписать точные оценки вероятности переобучения, а также вероятности $P_a = \mathbb{P}[\mu(X)=a]$ .

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

Гипотеза 3. Для любого алгоритма семейства $a\in A$ можно указать порождающее множество объектов $X_a\subseteq X^L$ и запрещающее множество объектов $X'_a\subseteq X^L$ такие, что для любого разбиения полной выборки на обучение и контроль, $X^L = X\sqcup\bar X$ справедливо

$[\mu(X)=a] \;\leq\; [X_a\subseteq X][X'_a\subseteq \bar X].$

С помощью Гипотезы 3 Андреем Ивахненко получены верхние оценки вероятности переобучения для семейства конъюнкций одномерных пороговых правил. Это семейство широко применяется на практике в логических алгоритмах классификации. Полученные оценки оказались не сильно завышенными, причём завышенность тем меньше, чем выше информативность закономерности. Таким образом, в данном случае завышенность не мешает осуществлять отбор наиболее информативных закономерностей. Эксперименты показали, что модификация критерия информативности с учётом переобучения улучшает обобщающую способность логических алгоритмов классификации. Эта работа, выполненая Андреем Ивахненко в рамках кандидатской диссертации, стала первым примером практического применения комбинаторных оценок вероятности переобучения.

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

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

Теорема. Пусть в $A$ есть алгоритм, не допускающий ошибок на полной выборке. Пусть $\Delta_{mq}$ — профиль расслоения–связности — число алгоритмов в $m$ -м слое со связностью $q$ . Тогда справедлива верхняя оценка вероятности переобучения

$Q_\eps \leq \sum_{m=\lceil \eps k\rceil}^L \sum_{q=0}^L \Delta_{mq} \frac{C_{L-m-q}^{\ell-q}}{C_L^\ell}.$

В этой оценке комбинаторный множитель убывает экспоненциально (быстрее геометрической прогрессии) по $m$ и по $q$ .

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

Только нижние слои графа расслоения–связности могут вносить существенной вклад в вероятность переобучения.
С ростом связности эта оценка улучшается экспоненциально по сравнению с классической VC-оценкой.
Эксперименты показывают, что значения связности концентрируются вблизи размерности пространства параметров. Действительно, связность $q(a)$ — это число способов (степеней свободы), которыми можно «испортить» алгоритм, перейдя от него к другому алгоритму, допускающему ещё на одну ошибку больше.

Открытые проблемы:

Оценка является ненаблюдаемой. Необходимо научиться оценивать профиль расслоения–связности $\Delta_{mq}$ по наблюдаемой обучающей подвыборке $X\subset X^L$ .
Ограничение корректности является техническим и, по всей видимости, его удастся снять.
Обосновать, что эффекты расслоения и связности «практически независимы», то есть что двумерную матрицу профиля расслоения–связности можно с большой точностью представлять в виде произведения одномерных профилей:

$\Delta_{mq} \approx D_m \,\cdot\, \lambda_q,$

где

$D_m = |A_m|$ — профиль расслоения;

$\lambda_q = \frac1{|A|}\left|\bigl\{a\in A:\: q(a)=q \bigr\}\right|$ — профиль связности.

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

Метод цепных разложений использовался Денисом Кочедыковым для получения оценок функционала $\tilde Q_\varepsilon(A,X^L)$ (вероятности равномерного отклонения), учитывающих связность. Он также позволяет снять ограничение корректности. Однако UC-оценки, получаемые методом порождающих и запрещающих множеств для метода максимизации отклонения, являются более точными.

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

Метод основан на предположении, что в матрице ошибок есть много одинаковых строк, которые объединяются в блоки. Число блоков — это число попарно различных строк. Выписывается точная оценка вероятности переобучения, трудоёмкость вычисления которой экспоненциальна по числу блоков. С помощью этого метода удаётся выписывать вероятность переобучения для произвольных матриц ошибок с небольшим числом столбцов, в частности, для пары и тройки алгоритмов. Однако объём вычислений в общем случае растёт как $O(2^D)$ , и при числе алгоритмов порядка длины выборки использование данного метода практически теряет смысл.

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

Теоретико-групповой подход, предложенный Александром Фреем, позволяет выписывать точные оценки вероятности переобучения для симметричных семейств алгоритмов и рандомизированного метода обучения. С помощью этой техники получены оценки для связки монотонных цепочек и хэммингова шара (Ильёй Толстихиным).

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

Попытки применить неравенства типа Бонферрони для получения оценок вероятности переобучения пока не привели к заметным успехам. Пока единственный результат следующий. Если семейство алгоритмов является связным и в графе расслоения—связности можно выделить полный подграф — дерево, то в оценках Вапника–Червоненкиса «хвост» гипергеометрического распределения можно заменить на значение гипергеометрической вероятности в той же точке. Это даёт несущественное улучшение точности оценки.

Публикации

Vorontsov K. V. Combinatorial probability and the tightness of generalization bounds // Pattern Recognition and Image Analysis. 2008. Vol. 18, no. 2. Pp. 243–259
Воронцов К. В. Точные оценки вероятности переобучения // Доклады РАН, 2009, Т. 429. №1. С. 15–18.
Воронцов К. В. Комбинаторный подход к проблеме переобучения // Математические методы распознавания образов: 14-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2009. С. 18–21.
Воронцов К. В., Иванов М. Н. Отбор эталонов, основанный на минимизации функционала полного скользящего контроля // Математические методы распознавания образов: 14-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2009. С. 119-122.
Vorontsov K. V. The effects of splitting and connectedness in function sets and their influence on the probability of overfitting // Pattern Recognition and Image Analysis, 2009, Vol. 19, No. 3, Pp. 412–420.
Vorontsov K. V. Exact Combinatorial Bounds on the Probability of Overfitting for Empirical Risk Minimization // Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 3, pp. 269–285.
Ivanov M. N. Prototype Selection Based on Minimization of the Complete Cross Validation // Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 4, pp. 427–437.
Воронцов К. В., Решетняк И. М. Точные комбинаторные оценки обобщающей способности онлайнового обучения // Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 24–27.
Ботов П. В. Точные оценки вероятности переобучения для несимметричных многомерных семейств алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 20–4.
Ивахненко А. А. О вероятности переобучения пороговых конъюнкций Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 57–0.
Толстихин И. О. Вероятность переобучения плотных и разреженных семейств алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 83–6.
Фрей А.И. Вероятность переобучения плотных и разреженных многомерных сеток алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 87–0.
Kochedykov D. A. A combinatorial approach to hypothesis similarity in generalization bounds // Pattern Recognition and Image Analysis. — 2011. — Vol. 21. — Pp. 616–629.
Vorontsov K. V., Ivahnenko A. A. Tight Combinatorial Generalization Bounds for Threshold Conjunction Rules // Lecture Notes on Computer Science. 4th International Conference on Pattern Recognition and Machine Intelligence (PReMI’11), Russia, Moscow, June 27–July 1, 2011. Pp 66–73.
Гуз И. С. Конструктивные оценки полного скользящего контроля для пороговой классификации // Математическая биология и биоинформатика. — Т.6. — В.2. — 2011.
Ботов П. В. Уменьшение вероятности переобучения итерационных методов статистического обучения // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 44–47.
Гуз И. C. Гибридные оценки полного скользящего контроля для монотонных классификаторов // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 68–71.
Животовский Н. К. Комбинаторные оценки вероятности отклонения тестовой ошибки от ошибки скользящего контроля // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 52–55.
Фрей А. И. Метод порождающих и запрещающих множеств для рандомизированной минимизации эмпирического риска // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 60–63.
Животовский Н. К., Воронцов К. В. Критерии точности комбинаторных оценок обобщающей способности // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 25–28.
Воронцов К. В. Комбинаторная теория переобучения: результаты, приложения и открытые проблемы // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 40–43.
Воронцов К. В., Махина Г. А. Принцип максимизации зазора для монотонного классификатора ближайшего соседа // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 64–67.
Ивахненко А. А., Воронцов К.В. Критерии информативности пороговых логических правил с поправкой на переобучение порогов // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 48–51.
Соколов Е. А., Воронцов К. В. Минимизация вероятности переобучения для композиций линейных классификаторов низкой размерности // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 82–85.
Толстихин И. О. Локализация оценок избыточного риска в комбинаторной теории переобучения // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 54–57.
Фрей А. И., Ивахненко А. А., Решетняк И. М. Применение комбинаторных оценок вероятности переобучения в простом голосовании пороговых конъюнкций // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 86–89.
Воронцов К. В., Фрей А. И., Соколов Е. А. Вычислимые комбинаторные оценки вероятности переобучения // Машинное обучение и анализ данных. — 2013. — T. 1, № 6. — С. 734–743.
Фрей А. И., Толстихин И. О. Комбинаторные оценки вероятности переобучения на основе кластеризации и покрытий множества алгоритмов // Машинное обучение и анализ данных. 2013. T. 1, № 5. C. 751–767.

Литература

Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с. (подробнее). Презентация на защите (PDF, 1760 КБ).
Воронцов К.В. Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам» (PDF, 180 КБ).
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»

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

@@ Строка 1: / Строка 1: @@
 {{TOCright}}
-Данный виртуальный семинар предназначен для обсуждения проблемы учёта расслоения семейства алгоритмов и сходства алгоритмов в оценках [[обобщающая способность|обобщающей способности]].
+'''Комбинаторная теория переобучения''' изучает проблему надёжности принятия решений по неполной информации в следующей дискретной постановке. Задана бинарная ''матрица ошибок''. Её строки соответствуют объектам, столбцы — алгоритмам; единица в матрице означает, что данный алгоритм ошибается на данном объекте. Требуется найти алгоритм, число ошибок которого как можно меньше, при условии, что наблюдается не вся матрица, а только случайное подмножество её строк. Говорят также, что алгоритм ''обучается'' по наблюдаемым данным. Предполагается, что все разбиения множества объектов на <tex>\ell</tex> наблюдаемых и <tex>k</tex> скрытых могут реализоваться с равной вероятностью. Если найденный алгоритм мало ошибается на скрытых объектах, то говорят, что метод обучения [[обобщающая способность|способен к обобщению]]. Если же частота ошибок найденного алгоритма на скрытых объектах существенно выше частоты его ошибок на наблюдаемых объектах, то говорят, что произошло [[переобучение]].
+Основными задачами ''комбинаторной теории переобучения'' является получение оценок [[Вероятность переобучения|вероятности переобучения]] и [[Полный скользящий контроль|полного скользящего контроля]], разработка эффективных методов их вычисления, создание на их основе новых методов восстановления закономерностей по эмпирическим данным.
-== Мотивация ==
+Данный виртуальный семинар предназначен для обсуждения
-Получение точных верхних оценок вероятности [[переобучение|переобучения]] остаётся открытой проблемой в [[теория вычислительного обучения|теории статистического обучения]] уже более 40 лет, начиная с работ [[Вапник, Владимир Наумович|В. Н. Вапника]] и [[Червоненкис, Алексей Яковлевич|А. Я. Червоненкиса]]. Наиболее точные из известных оценок всё ещё сильно завышены.
+* эффектов расслоения и сходства в семействах алгоритмов [[классификация|классификации]];
+* влияния этих эффектов на [[обобщающая способность|обобщающую способность]];
+* математических техник, позволяющих учитывать эти эффекты в оценках [[Вероятность переобучения|вероятности переобучения]].
-=== Первый эксперимент ===
+== Оценки обобщающей способности: история вопроса ==
-В экспериментах на реальных задачах классификации установлены основные причины завышенности и вычислены ''степени завышенности'' — коэффициенты, показывающие, во сколько раз каждая из этих причин завышает оценку вероятности переобучения.
-Причины, в&nbsp;порядке убывания важности:
-# Пренебрежение эффектом ''расслоения'' (или ''локализации'') семейства алгоритмов. Чем хуже классификатор решает данную задачу, тем меньше шансов получить его в результате настройки по обучающей выборке. Это означает, что реально работает не всё семейство, а только какая-то его часть, своя в каждой задаче. '''Степень завышенности:''' от нескольких десятков раз до сотен тысяч раз, в зависимости от задачи.
-# Пренебрежение сходством алгоритмов. При выводе оценок используется оценка вероятности объединения событий суммой их вероятностей (union bound). «События» соответствуют алгоритмам; точнее, ''d''-м «событием» является слишком большое уклонение частоты ошибок на тестовой и обучающей выборках для ''d''-го алгоритма. Union bound становится чрезвычайно завышенной оценкой, если среди событий (то есть среди алгоритмов) есть похожие. '''Степень завышенности:''' от нескольких сотен до десятков тысяч раз. Этот фактор всегда существенен и не так сильно зависит от задачи, как первый.
-# Экспоненциальная аппроксимация хвоста гипергеометрического распределения. Вроде бы точность аппроксимации увеличивается с ростом длины выборки — оба хвоста быстро стремятся к нулю. Тем не менее, относительная погрешность (отношение аппроксимации к точному значению) с ростом выборки растёт! Формула с экспонентой, конечно, приятна на глаз, но '''степень завышенности''' может достигать нескольких десятков. Отсюда вывод: по возможности не пользоваться аппроксимациями.
-# Верхняя оценка профиля разнообразия одним скалярным [[коэффициент разнообразия|коэффициентом разнообразия]] (shatter coefficient). '''Степень завышенности''' часто порядка единицы, но в некоторых задачах может достигать нескольких десятков. Этот результат получен для [[логическая закономерность|логических закономерностей]]; если оценивать классификаторы, а не закономерности, то этот фактор завышенности должен возрасти.
-=== Замечание о природе переобучения ===
+Точные оценки [[Вероятность переобучения|вероятности переобучения]] необходимы для создания методов обучения по прецедентам, гарантирующих высокое качество классификации новых объектов, не вошедших в обучающую выборку.
-Вообще, [[переобучение]] возникает из-за того, что выбирается алгоритм с минимальным числом ошибок на обучающей выборке.
+Получение точных оценок [[обобщающая способность|обобщающей способности]] остаётся открытой проблемой в [[теория вычислительного обучения|теории статистического обучения]] уже более 40 лет, начиная с [[Теория Вапника-Червоненкиса|VC-теории]], предложенной [[Вапник, Владимир Наумович|В. Н. Вапником]] и [[Червоненкис, Алексей Яковлевич|А. Я. Червоненкисом]].
+Наиболее точные из известных оценок всё ещё сильно завышены.
+=== VC-теория ===
+Основной задачей в VC-теории считается получение верхних оценок для функционала
+::<tex>P_\varepsilon(A) = \mathbb{P}_X\Bigl( \sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon \Bigr),</tex>
+где
+: <tex>A</tex> — семейство алгоритмов, из которого по обучающей выборке <tex>X</tex> выбирается некоторый алгоритм;
+: <tex>P(a)</tex> — вероятность ошибки алгоритма <tex>a \in A</tex>;
+: <tex>\nu(a,X)</tex> — частота ошибок алгоритма <tex>a \in A</tex> на независимой обучающей выборке длины <tex>\ell</tex>;
+: <tex>\mathbb{P}_X</tex> — некоторая неизвестная вероятностная мера на множестве объектов.
+Смысл этого функционала в том, что если частота ошибок не сильно отклоняется от вероятности ошибки одновременно для всех алгоритмов <tex>a \in A</tex>, то алгоритм, найденный путём ''минимизации эмпирического риска'',
+:: <tex>a^{*} = \arg\min_{a\in A} \nu(a,X),</tex>
+будет иметь малую вероятность ошибиться и на новых данных, иными словами, будет иметь хорошую [[обобщающая способность|обобщающую способность]].
+Это утверждение записывают также в эквивалентном виде:
+:: «''Для любого <tex>a \in A</tex> с вероятностью не менее <tex>1-\eta</tex> выполняется <tex>P(a) \leq \nu(a,X)+\varepsilon(\eta)</tex>''»,
+где <tex>\varepsilon(\eta)</tex> — функция, обратная к <tex>\eta(\varepsilon) = P_\varepsilon(A)</tex>.
+У функционала <tex>P_\varepsilon</tex> есть несколько недостатков.
+*Если вероятностная мера <tex>P(a)</tex> неизвестна, то измерить функционал <tex>P_\varepsilon</tex> непосредственно в эксперименте очень трудно, поскольку невозможно идентифицировать наступление события <br
+>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>\sup_{a\in A} |P(a)-\nu(a,X)| \geq \varepsilon.</tex> <br
+>Экспериментальное измерение необходимо для количественного анализа и понимания причин завышенности оценок функционала&nbsp;<tex>P_\varepsilon</tex>. Выход заключается в том, чтобы вместо <tex>P(a)</tex> оценивать <tex>\nu(a,\bar X)</tex> — частоту ошибок алгоритма <tex>a</tex> на независимой контрольной выборке длины <tex>k</tex>. Тогда эмпирическое измерение функционала <tex>P_\varepsilon</tex> становится возможным, например, методом Монте-Карло — путём генерации некоторого числа случайных разбиений полной выбоки <tex>X^L = X \sqcup \bar X</tex> на обучение и контроль. Через <tex>L=\ell+k</tex> обозначается длина полной выборки.
+* Супремум в [[Теория Вапника-Червоненкиса|VC-теории]] вводится для того, чтобы получить наиболее общую оценку, не зависящую от конкретного [[метод обучения|метода обучения]]&nbsp;<tex>\mu</tex>, который по обучающей выборке <tex>X</tex> находит алгоритм <tex>a\in A</tex>. Однако на самом деле было бы правильнее оценивать [[вероятность переобучения]] — вероятность того, что частота ошибок найденного алгоритма на контроле будет существенно больше частоты его ошибок на обучении <br
+>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>\delta_\mu(X) = \nu(\mu(X),\bar X)-\nu(\mu(X),X) \geq \varepsilon</tex>,<br
+> где величина <tex>\delta_\mu(X)</tex> называется ''переобученностью''. Введение супремума приводит к верхней оценке вероятности переобучения. Эта оценка может оказаться сильно завышенной, поскольку при решении прикладных задач методы обучения возвращают не любые алгоритмы из <tex>A</tex>, а&nbsp;лишь&nbsp;те, которые в&nbsp;определённом смысле «похожи» на восстанавливаемую зависимость.
+* Наконец, имеет смысл оценивать сверху саму переобученность, а не её абсолютную величину, поскольку частоту ошибок на контрольной выборке хотелось бы ограничивать именно сверху, а не снизу.
+=== Понятие вероятности переобучения ===
+Наиболее адекватным функционалом обобщающей способности является ''вероятность переобучения'':
+::<tex>Q_\varepsilon(\mu,X^L) = \mathbb{P}\Bigl[ \delta_\mu(X) \geq \varepsilon \Bigr].</tex>
+Этот функционал является ''локальной'' оценкой обобщающей способности, поскольку он зависит от метода обучения и полной выборки.
+Термин ''переобучение'' понимается здесь в строго формальном смысле, как событие <tex>\delta_\mu(X) \geq \varepsilon</tex>.
+Вероятность <tex>\mathbb{P}</tex> понимается здесь и далее в смысле равномерного распределения на множестве всех <tex>C_L^\ell</tex> разбиений неслучайной полной выбоки <tex>X^L = X \sqcup \bar X</tex>.
+Это позволяет применять чисто комбинаторные методы для получения оценок вероятности переобучения, и во многих случаях получать ''точные оценки'' (не завышенные, не асимптотические).
+См. также [[слабая вероятностная аксиоматика]].
+Основным объектом изучения в комбинаторно-дискретной постановке является бинарная ''матрица ошибок'' <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>D</tex> в матрице ошибок называется также [[коэффициент разнообразия|коэффициентом разнообразия]] (shattering coefficient) семейства алгоритмов.
+=== Комбинаторная оценка для одного алгоритма ===
+Если множество алгоритмов состоит из единственного элемента, <tex>A=\{a\}</tex>, то именно он и возвращается методом обучения при любой обучающей выборке.
+Собственно, никакого обучения нет.
+Этот случай интересен тем, что вероятность переобучения выражается через [[гипергеометрическое распределение]] и является точной.
+'''Теорема (one-classifier bound, OC-bound). '''
+Для любого алгоритма <tex>a</tex>, любой выборки <tex>X^L</tex> и любого <tex>\varepsilon\in(0,1)</tex>
+::<tex>Q_\varepsilon(a,X^L) = H_L^{\ell,m} \bigl( \frac{\ell}{L}(m-\varepsilon k) \bigr), </tex>
+где
+: <tex>m = n(a,X^L)</tex> — число ошибок алгоритма <tex>a</tex> на полной выборке;
+: <tex>H_L^{\ell,m}(s) = \sum_{t=0}^{\lfloor s \rfloor}\frac{C_m^s C_{L-m}^{\ell-t}}{C_L^\ell}</tex> — функция гипергеометрического распределения.
+Эта оценка является аналогом [[закон больших чисел|закона больших чисел]] в [[слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
+Эта оценка является «строительным блоком» для более сложных случаев, когда метод обучения выбирает алгоритм из множества <tex>A</tex>.
+Эта оценка является ''ненаблюдаемой'', поскольку правая часть зависит от числа ошибок на контрольной выборке, которая скрыта в момент обучения.
+Однако, зная число ошибок на обучающей выборке <tex>s = n(a,X)</tex>, нетрудно построить доверительный интервал для неизвестной величины <tex>m</tex>.
+=== Комбинаторная VC-оценка ===
+Оценка для общего случая получается путём суммирования OC-оценок по всему семейству.
+'''Теорема (Vapnik-Chervonenkis bound, VC-bound). '''
+Для любого семейства <tex>A</tex>, любого метода обучения <tex>\mu</tex>, любой выборки <tex>X^L</tex> и любого <tex>\varepsilon\in(0,1)</tex>
+::<tex>Q_\varepsilon(\mu,X^L) \;\leq\; \sum_{a\in A} H_L^{\ell,m} \bigl( \frac{\ell}{L}(m-\varepsilon k) \bigr), </tex>
+где
+: <tex>m = n(a,X^L)</tex> — число ошибок алгоритма <tex>a</tex> на полной выборке;
+: <tex>H_L^{\ell,m}(s)</tex> — функция гипергеометрического распределения.
+'''Доказательство ''' состоит из двух шагов, на каждом из которых происходит существенная потеря точности оценки.
+'''Шаг 1. '''
+Вероятность переобучения оценивается сверху вероятностью большого равномерного отклонения частот (''uniform bound'').
+В результате получаем оценку, справедливую для любого метода обучения <tex>\mu</tex>.
+::<tex>Q_\varepsilon(\mu,X^L) = \mathbb{P} \Bigl[ \delta_\mu(X) \geq \varepsilon \Bigr] \;\leq\; \tilde Q_\varepsilon(A,X^L) = \mathbb{P} \max_{a\in A} \Bigl[ \delta_a(X) \geq \varepsilon \Bigr].</tex>
+'''Шаг 2. '''
+Максимум бинарных величин оценивается сверху их суммой.
+Или, что то же самое, вероятность объединения событий оценивается сверху суммой их вероятностей.
+Это называется неравенством Буля или ''union bound'':
+::<tex>\tilde Q_\varepsilon(A,X^L) \;\leq\; \sum_{a\in A} \mathbb{P} \Bigl[ \delta_a(X) \geq \varepsilon \Bigr].</tex>
+Теперь остаётся применить OC-оценку под знаком суммы. Теорема доказана.
+Чтобы получить VC-оценку в классической записи, необходимо положить <tex>\ell=k</tex> и сделать ещё два чисто технических огрубления:
+во-первых, оценить сверху функцию гипергеометрического распределения при наихудшем <tex>m</tex>;
+во-вторых, применить асимптотическую оценку для левого хвоста гипергеометрического распределения.
+'''Следствие. '''
+::<tex>Q_\varepsilon(\mu,X^L) \;\leq\; |A| \,\cdot\, \exp(-\ell^2\varepsilon). </tex>
+Эта оценка является сильно завышенной.
+Она справедлива для любой восстанавливаемой зависимости, любой выборки и любого метода обучения.
+Следовательно, это оценка худшего случая.
+Примерно понятно, что есть «худший случай» — когда никакой зависимости в данных нет, а метод обучения настолько глуп, что выбирает алгоритм наугад.
+Очевидно, худший случай не интересен, и на практике никогда не реализуется.
+Правая часть VC-оценки зависит только от размерных характеристик матрицы ошибок <tex>L</tex> и <tex>D=|A|</tex>, но не от её содержимого.
+Этих величин явно недостаточно, чтобы характеризовать столь сложный процесс, как обучение по прецедентам.
+В&nbsp;этом и заключается основная концептуальная причина завышенности классических VC-оценок.
+=== Развитие теории вычислительного обучения ===
+Последующие работы были направлены на получение более точных оценок,
+учитывающих больше априорной информации и позволяющих управлять процессом обучения.
+* Теория равномерной сходимости [Вапник, Червоненкис, 1968]
+: Показано, что ''достаточным'' условием обучаемости является конечная ёмкость (VC-размерность) семейства алгоритмов. Отсюда многие исследователи делали неправильный вывод, что для хорошей обучаемости ''необходимо'' органичивать сложность семейства. Позже работы Матросова и алгоритм бустинга перевернули эти представления. Заметим, что для доказательства основных содержательных утверждений VC-теории применялись чисто комбинаторные методы.
+* Корректные алгоритмические композиции ограниченной ёмкости [Матросов, 1980]
+: Показано, что сложное семейство алгоритмов, гарантирующее существование корректного алгоритма, тем не менее, может обладать конечной ёмкостью, то есть быть обучаемым. Полученные оценки опирались на VC-теорию (так как ничего другого тогда ещё не было), были сильно завышены и потому неприменимы для практических целей. Кроме того, они были получены для конкретного семейства алгоритмов.
+* Theory of learnable (PAC-learning) [Valiant, 1982]
+: Теория Валианта объединила теорию Вапника-Червоненкиса с теорией вычислительной сложности. Постулировалось требование, чтобы достижение заданной обобщающей способности не требовало экспоненциального объёма вычислений. Были введены понятия экспоненциальной и полиномиальной обучаемости. В дальнейшем стало ясно, что объединение этих теорий в значительной степени надуманно и искусственно. Большинство применяемых на практике способов повышения обобщающей способности не требуют экспоненциального роста объёма вычислений.
+* Data-dependent bounds [Haussler, 1992]
+: Показано, что оценки обобщающей способности, не зависящие от данных, в принципе не могут быть точными. С этого момента основные исследования были направлены на то, чтобы определить, какого вида дополнительная информация о задаче ещё должна быть использована, кроме частоты ошибок на обучающей выборке.
+* Concentration inequalities [Talagrand, 1995]
+: Неравенства концентрации вероятностной меры, основанные на математическом аппарате функционального анализа, становятся основным методом получения оценок обобщающей способности. К сожалению, все эти оценки завышены. Выяснить причины, измерив степень завышенности эмпирически, весьма проблематично, поскольку оцениваются ненаблюдаемые величины. Начиная с этого момента происходит отказ от комбинаторных методов доказательства в пользу вероятностных методов, существенно эксплуатирующих теорию меры.
+* Connected function classes [Sill, 1995]
+: Неудачная попытка учесть связность в семействах алгоритмов. Учитывалась только связность в обычном понимании теории графов, как возможность построить путь между любыми двумя алгоритмами. Оценка оказалась лишь немного лучше VC, и эта работа осталась незамеченной. Только теперь стало ясно, что надо было учитывать количество связей у каждого алгоритма.
+* Similar classifiers VC bounds [Bax, 1997]
+: Неудачная попытка учесть сходство алгоритмов в семействе. Довольно грубая техника кластеризации не привела к заметным улучшениям оценки. Эта работа также осталась незамеченной.
+* Margin based bounds [Bartlett, 1998]
+: Генеральное направление развития теории обобщающей способности в конце 90-х — начале 00-х. Учёт распределения отступов на обучающей выборке действительно позволил улучшить оценки обобщающей способности, но не радикально. Самое главное — он привёл к конструктивным обоснованиям линейных алгоритмов классификации, алгоритма бустинга, нейронных сетей.
+* Self-bounding learning algorithms [Freund, 1998]
+: Метод структурной минимизации риска в VC-теории требовал заранее задавать структуру вложенных подсемейств в семействе алгоритмов, и затем с помощью оценки обобщающей способности выбирать из них подсемейство оптимальной сложности. Самоограничивающие алгоритмы строят структуру вложенных подсемейств в процессе обучения. Таким образом, оценка оказывается зависящей от данных.
+* Rademacher complexity [Koltchinskii, 1998]
+: Одна из самых красивых и плодотворных теорий. Введение понятия радемахеровской (а также гауссовской) сложности позволило полностью отказаться от применения неравенства Буля (union bound) при выводе оценок. Легко прошло обобщение на произвольные (не бинарные) функции потерь. Легко и изящно прошло доказательство того факта, что взвешенное голосование любого числа классификаторов не увеличивает сложность семейства. Это позволило тут же обосновать бустинг и другие методы построения композиций классификаторов. Оценка радемахеровской сложности для линейных классификаторов привела к обоснованию методов обучения, основанных на сочетании двух принципов — непрерывной аппроксимации пороговой функции потерь и регуляризации эмпирического риска. Некоторую неудовлетворённость вызывает лишь то, что в теории радемахеровской сложности, как и в VC-теории, оценивается вероятность равномерного отклонения. Следовательно, эффект расслоения учитывается не в полной мере. С этим пытаются бороться, вводя локализованную радемахеровскую сложность, в которой максимум берётся не по всему семейству, а по некоторому подсемейству, зависящему от выборки.  Удобных, универсальных и практически полезных способов реализации этой идеи пока не найдено.
+* Adaptive microchoice bounds [Langford, Blum, 2001]
+: Дальнейшее развитие принципа самоограничивающих алгоритмов. Рассматриваются методы обучения, представляющие собой последовательность принимаемых решений, причём каждое решение приводит к сужению подсемейства алгоритмов, внутри которого ищется оптимальный алгоритм. Процесс принятия решений адаптивно управляется с помощью оценок обобщающей способности, зависящих от данных.
+* Algorithmic stability [Bousquet, Elisseeff, 2002]
+: Концепция стабильности (устойчивости) метода обучения относительно состава обучающей выборки некоторое время казалась перспективной альтернативой VC-теории. Например, ещё в 70-е годы такие оценки были получены для метода ближайших соседей и метода потенциальных функций. Однако на этом пути так и не удалось получить численно точных оценок. Само понятие стабильности оказалось довольно трудно определить, было введено около двух десятков различных понятий стабильности, и установлены нетривиальные связи между ними. Доказана стабильность многих практических методов обучения. Однако завышенность оценок, основанных на стабильности, оставалась на том же уровне, что и завышенность VC-оценок.
+* Algorithmic luckiness [Herbrich, Williamson, 2002]
+: Попытка учесть расслоение семейства алгоритмов, не вполне удачная, так как вся сложность задачи «упрятывалась» в некоторую ''функцию удачности'' (luckiness function), которую предлагалось угадывать в каждом конкретном случае, без чётко проработанной методологии такого угадывания.
+* Shell bounds [Langford, 2002]
+: Попытка учесть расслоение семейства алгоритмов, не вполне удачная, так как снова использовалась оценка union bound (а теперь мы знаем, что при этом невозможно учесть сходство алгоритмов). Несмотря на рекламные заявления автора, что оценки могут быть очень точны, эксперименты, проведённые Денисом Кочедыковым, показали, что они лишь немного лучше VC-оценок.
+* PAC-Bayes bounds [McAllester, 1999; Langford, 2005]
+: Одна из самых плодотворных теорий, но в то же время наиболее сложная для понимания. Оценки выводятся для рандомизированного метода обучения, который возвращает не один алгоритм, а распределение на всём семействе алгоритмов. Затем по данному распределению выполняется голосование, которое в (наиболее распространённом) случае бесконечных семейств сводится к интегрированию. Несмотря на искусственность такого построения, как правило, удаётся доказать, что результат интегрирования совпадает с некоторым известным детерминированным алгоритмом. Чтобы такое совпадение произошло, должны быть специальным образом подобраны априорные распределения на семействе алгоритмов, что является искусством. Как и радемахеровские оценки, данный подход приводит к методам обучения, совмещающим непрерывную аппроксимацию пороговой функции потерь и регуляризацию эмпирического риска.
+== Как были выявлены эффекты расслоения и сходства ==
+В комбинаторном подходе оцениваемый функционал <tex>Q_\varepsilon</tex> легко измерить эмпирически методом Монте-Карло, взяв среднее по некоторому случайному подмножеству разбиений полной выборки на две подвыборки, обучающую и контрольную.
+Более того, можно оценить и промежуточные величины, которые появляются в ходе вывода VC-оценки, и узнать, какова потеря точности на каждом шаге.
+Заметим, что ничего подобного в исходной вероятностной постановке сделать нельзя, так как функционал <tex>P_\varepsilon(A)</tex> с трудом поддаётся эмпирическому измерению.
+Методика его измерения была предложена Вапником и Ботту (1994), однако эти работы остались практически незамеченными, что не удивительно:
+измеренные значения функционала <tex>P_\varepsilon(A)</tex> близки к единице,
+что свидетельствует о сильной завышенности равномерной оценки (uniform bound) и слишком явно говорит о непрактичности функционала, положенного в основу VC-теории.
+Содержательные эксперименты стали возможны только после того, как VC-оценки были переписаны в слабой вероятностной аксиоматике для вероятности переобучения, которая легко измеряется эмпирически.
+=== Первый эксперимент (на реальных данных) ===
+В экспериментах на реальных задачах классификации удалось количественно оценить отдельные ''факторы завышенности'' классических VC-оценок.
+Основные причины завышенности, в&nbsp;порядке убывания важности:
+* Пренебрежение эффектом ''расслоения'' (или ''локализации'') семейства алгоритмов. Чем хуже классификатор решает данную задачу, тем меньше шансов получить его в результате настройки по обучающей выборке. Это означает, что реально работает не всё семейство, а только какая-то его часть, своя в каждой задаче. <br>'''Степень завышенности:''' порядка <tex>10^2..10^5</tex>, в зависимости от задачи.
+* Пренебрежение эффектом ''сходства'' алгоритмов. При выводе классических VC-оценок используется [[неравенство Буля]] (union bound) — оценка вероятности объединения событий суммой их вероятностей. Эта оценка становится чрезвычайно завышенной, если среди алгоритмов есть похожие. <br>'''Степень завышенности:''' порядка <tex>10^3..10^4</tex>. Этот фактор всегда существенен и не так сильно зависит от задачи, как первый.
+* Экспоненциальная аппроксимация хвоста гипергеометрического распределения. Вроде бы точность аппроксимации увеличивается с ростом длины выборки — хвосты быстро стремятся к нулю. Однако относительная погрешность (отношение аппроксимированного значения к точному) с ростом выборки растёт! Отсюда вывод: при получении численно точных оценок не стоит пользоваться аппроксимациями. <br>'''Степень завышенности:''' порядка <tex>10^0..10^2</tex>.
+<!---
+* Верхняя оценка профиля разнообразия одним скалярным [[коэффициент разнообразия|коэффициентом разнообразия]] (shatter coefficient). '''Степень завышенности''' часто порядка единицы, но в некоторых задачах может достигать нескольких десятков. Этот результат получен для [[логическая закономерность|логических закономерностей]]; если оценивать классификаторы, а не закономерности, то этот фактор завышенности должен возрасти. Фактор достаточно просто исключается из оценки для семейства алгоритмов, если union bound используется для объединения оценок отдельных алгоритмов, не зависящих от неизвестной вероятности ошибки каждого алгоритма. Так устроена, к примеру, оценка [[Occam Razor оценка вероятности переобучения|Occam Razor]].
+--->
+В экспериментах вычислялся также [[эффективный локальный коэффициент разнообразия]] (ЭЛКР).
+Это такое число <tex>D</tex>, при котором VC-оценка не была бы завышенной.
+Для него были получены удивительно небольшие значения — порядка <tex>10^0..10^2</tex> в&nbsp;разных задачах,
+в&nbsp;то время как число <tex>D</tex> имело порядки <tex>10^6..10^{12}</tex>.
+'''Основные выводы:'''
+* Завышенность VC-оценок обусловлена тем, что они учитывают только длину выборки <tex>L</tex> и число различных алгоритмов&nbsp;<tex>D</tex>, но не учитывают степень их различности, то есть полностью игнорируют содержимое матрицы ошибок.
+* Для получения точных оценок необходимо ''одновременно'' учесть оба эффекта — и расслоение, и сходство.
+* Ни одна из существовавших до сих пор теорий не в состоянии объяснить столь низких значений эффективного коэффициента разнообразия.
+=== Второй эксперимент (на модельных данных) ===
+[[Изображение: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;без расслоения.]]
+Простейшим примером семейства алгоритмов с расслоением и связностью является ''монотонная цепочка алгоритмов''.
+Оно строится следующим образом.
+Задаётся «лучший алгоритм», допускающий <tex>m_0</tex> ошибок на полной выборке.
+Каждый следующий алгоритм <tex>a_{d+1}</tex> допускает ошибки на тех же объектах, что и предыдущий <tex>a_{d}</tex>, плюс ошибку ещё на одном объекте.
+Перестановкой строк можно добиться, чтобы матрица ошибок такого семейства содержала верхнюю треугольную подматрицу.
+Монотонная цепочка алгоритмов является довольно реалистичной моделью связного семейства с&nbsp;одним непрерывным параметром: чем дальше значение параметра от оптимального значения, тем больше ошибок, но в&nbsp;силу непрерывности (и&nbsp;при гипотезе, что точки выборки общего положения) ошибка не может появиться сразу на нескольких объектах.
+Вообще, ''связным семейством'' будем называть такое множество алгоритмов, в котором для каждого алгоритма найдётся другой алгоритм, вектор ошибок которого отличается от данного только на одном объекте.
+Монотонной цепочке можно поставить в соотвествие ''цепочку без расслоения''. В&nbsp;этом семействе каждый следующий алгоритм также отличается от предыдущего только на одном объекте, но число ошибок, чередуясь, принимает лишь два значения: <tex>m_0, m_0+1</tex>.
+Каждому из этих двух семейств можно сопоставить ''не-цепочку''. Чтобы разрушить эффект связности, достаточно в каждом столбце матрицы ошибок случайным образом переставить все элементы.
+Итак, получается четыре ''модельных семейства'', заданных непосредственно своими матрицами ошибок.
+Для каждого из них вероятность переобучения нетрудно оценить методом Монте-Карло
+(у&nbsp;хороших студентов реализация такого экспериментального стенда занимает пару часов работы).
+Результаты сопоставляются на графиках зависимости вероятности переобучения <tex>Q_\varepsilon</tex> от числа <tex>D</tex> первых алгоритмов <tex>a_1,\ldots,a_D</tex>, из которых метод обучения <tex>\mu(X)</tex> выбирает алгоритм с наименьшей частотой ошибок на обучающей выборке.
+В&nbsp;VC-теории такой метод обучения называется [[Минимизация эмпирического риска|минимизацией эмпирического риска]].
+'''Основные выводы:'''
+* Связность заметно снижает темп роста зависимости <tex>Q_\varepsilon(D)</tex>.
+* Расслоение понижает уровень горизонтальной асимптоты <tex>Q_\varepsilon(D)</tex>.
+* Только при одновременном наличии и связности, и расслоения вероятность переобучения приемлемо мала, причём кривая «выходит на насыщение» после первых 5–7 алгоритмов. Основная масса «плохих» алгоритмов вообще не вносит вклад в переобучение.
+* При отсутствии либо расслоения, либо связности вероятность переобучения становится порядка <tex>0.5</tex> уже при нескольких десятках алгоритмов.
+* Это означает, что реальные семейства, состоящие из огромного числа различных алгоритмов, с необходимостью должны быть расслоенными и связными.
+* Семейство без расслоения и без связности — это и есть тот наихудший случай, который изучается в [[Теория Вапника-Червоненкиса|VC-теории]].
+Этот эксперимент показал направление дальнейших исследований: для получения точных оценок вероятности переобучения необходимо развивать методы, одновременно учитывающие эффекты расслоения и сходства в семействе алгоритмов.
+=== О природе переобучения ===
+Вообще, [[переобучение]] возникает из-за того, что решение о выборе лучшего алгоритма принимается по неполным данным — обучающей выборке <tex>X</tex>, которая является лишь частью полной выборки <tex>X^L</tex>.
 Сделаем мысленный эксперимент.
@@ Строка 24: / Строка 232: @@
 тем дальше влево будет смещаться минимальное (по всем взятым алгоритмам) число ошибок;
 тем больше будет разность между частотой и вероятностью ошибок у «лучшего» алгоритма.
-Но&nbsp;это и есть переобучение.
+Это и есть переобучение.
 Это всё так, если алгоритмы берутся из распределения случайно и независимо.
-Однако, если алгоритмы зависимы
+Однако, если алгоритмы зависимы,
-(а&nbsp;в&nbsp;реальной ситуации они именно зависимы, причём очень сильно),
+то&nbsp;возникает надежда, что выбираемые алгоритмы будут концентрироваться гуще,
-то возникает надежда, что выбираемые алгоритмы будут концентрироваться гуще,
+и&nbsp;пик эмпирического распределения числа ошибок окажется более узким.
-и пик эмпирического распределения числа ошибок окажется более узким.
+В&nbsp;реальной ситуации алгоритмы зависимы, причём очень сильно, благодаря свойствам расслоения и сходства.
-=== Пара алгоритмов ===
+== Оценки расслоения–связности ==
-Получены точные формулы для вероятности переобучения при выборе лучшего из двух алгоритмов.
-Если алгоритмы совпадают, то вероятность переобучения равна вероятности большого уклонения частот в двух подвыборках для отдельного алгоритма, и описывается гипергеометрическим распределением.
-Если алгоритмы существенно различны, но имеют одинаковый уровень ошибок, то вероятность переобучения увеличивается вдвое.
-Если алгоритмы имеют существенно различный уровень ошибок, то вероятность переобучения уменьшается.
-'''Выводы:''' уже при выборе одного из двух алгоритмов может возникать переобучение.
+=== Свойство расслоения ===
-Расслоение алгоритмов по числу ошибок и увеличение сходства уменьшают вероятность переобучения.
+'''Определение. '''
+''Расслоением семейства'' алгоритмов <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>
-=== Как устроены реально используемые семейства ===
+'''Определение. '''
+''Неоптимальностью'' <tex>r(a)</tex> алгоритма <tex>a\in A</tex> называется число объектов, на которых данный алгоритм допускает ошибку, таких, что существует другой алгоритм, не допускающий ошибки на данном объекте и на объектах, на которых не ошибается алгоритм <tex>a\in A</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> только на одном объекте.
+'''Определение. '''
+''Нижней связностью'' <tex>p(a)</tex> алгоритма <tex>a\in A</tex> называется число алгоритмов в предыдущем слое, вектор ошибок которых отличается от <tex>a</tex> только на одном объекте.
 Многие параметрические семейства алгоритмов обладают следующим свойством:
@@ Строка 47: / Строка 269: @@
 В&nbsp;частности, этим свойством обладают классификаторы с непрерывной по параметрам разделяющей поверхностью:
 [[линейный классификатор|линейные классификаторы]], [[SVM]] с непрерывными ядрами, [[нейронная сеть|нейронные сети]] с непрерывными функциями активации, [[решающее дерево|решающие деревья]] с пороговыми условиями ветвления, и многие другие.
-J.&nbsp;Sill называет такие семейства ''связными'', так как множество векторов ошибок всех алгоритмов семейства представляется в виде связного графа. E.&nbsp;Bax предлагает кластеризовать семейство на группы схожих классификаторов.
+J.&nbsp;Sill называет такие семейства ''связными'', так как множество векторов ошибок всех алгоритмов семейства представляется в виде связного графа.
+E.&nbsp;Bax предлагает кластеризовать семейство на группы схожих классификаторов.
-=== Цепочки алгоритмов ===
+=== Граф расслоения-связности ===
-Цепочкой будем называть такую последовательность векторов ошибок, в которой хэммингово расстояние между последовательными векторами равно 1.
+'''Определение. '''
+''Графом расслоения-связности'' семейства алгоритмов <tex>A</tex> называется граф, вершины которого соответствуют векторам ошибок; рёбрами соединяются векторы ошибок, отличающиеся только на одном объекте (хэммингово расстояние между которыми равно&nbsp;1).
+Этот граф можно рассматривать как ориентированный, если договориться, что рёбра направлены от алгоритмов с меньшим числом ошибок к алгоритмам с большим числом ошибок.
-Эксперименты показывают следующее.
+Граф расслоения-связности зависит от семейства алгоритмов и от конкретной выборки.
-* Для цепочек вероятность переобучения растёт гораздо медленнее с увеличением числа алгоритмов, чем для не-цепочек.
-* Расслоение приводит к снижению максимального уровня вероятности переобучения; если семейство не расслаивается, то вероятность переобучения с ростом числа алгоритмов быстро достигает единицы.
-* Семейство без расслоения и без цепочек — как раз и есть тот наихудший случай, который изучается [[Теориея Вапника-Червоненкиса|теорией Вапника-Червоненкиса]]. На&nbsp;практике, как правило, приходится работать со связными и расслоёнными семействами.
-=== Основной вопрос данного виртуального семинара ===
+'''Пример. '''
-Как учесть связность и расслоенность в семействах алгоритмов для получения незавышенных оценок вероятности переобучения?
+На следующих рисунках показан начальный фрагмент матрицы ошибок (три нижних слоя) и граф расслоения-связности, порождаемые семейством линейных классификаторов на выборке из 10&nbsp;объектов, по&nbsp;5&nbsp;объектов в&nbsp;каждом классе.
-=== Ссылки ===
+{|
-Более подробно результаты экспериментов можно посмотреть здесь:
+|-
-* 12 июня 2008.  Слабая вероятностная аксиоматика, оценки надёжности эмпирических предсказаний, расслоение и различность алгоритмов.  Конференция [[ИОИ]]-2008. '''[[Media:VoronBeam-IOI-2008.pdf|PDF&nbsp;[950Кб]]]'''
+| 0-й слой (1 корректный алгоритм):
-* 28 апреля 2008. Ломоносовские чтения 2008. Оценки надёжности эмпирических предсказаний (комбинаторный подход). '''[[Media:VoronBeam2008-04-18.pdf|PDF&nbsp;[804Кб]]]'''.
+| 1-й слой (5 алгоритмов):
+| 2-й слой (8 алгоритмов):
+|-
+| [[Изображение:SimpleSample0num.PNG|300px]]
+| [[Изображение:SimpleSample1.PNG|300px]]
+| [[Изображение:SimpleSample2.PNG|300px]]
+|}
+{|
+|-
+| Матрица ошибок:
+| Граф расслоения-связности:
+|-
+| [[Изображение:SimpleMatrix.png|600px]]
+| [[Изображение:SimpleGraph.PNG|300px]]
+|}
+Эксперименты с линейными классификаторами проведены Ильёй Решетняком.
+=== Оценка расслоения–связности ===
+'''Теорема (splitting and connectivity bound, SC-bound). '''
+Если <tex>\mu</tex> — метод минимизации эмпирического риска, то для любой выборки <tex>X^L</tex> и любого <tex>\varepsilon\in(0,1)</tex> справедлива оценка сверху:
+::<tex>Q_\varepsilon(\mu,X^L) \;\leq\; \sum_{a\in A} W_{rq} H_{L-q-r}^{\ell-q,\,m-r}\Bigl(\frac{\ell}{L}(m-\varepsilon k)\Bigr),</tex>
+::<tex>\mathbb{P}\bigl[ \mu(X)=a \bigr] \;\leq\; W_{rq} = \frac{C_{L-q-r}^{\ell-q}}{C_{L}^{\ell}},</tex>
+где
+:<tex>q=q(a)</tex> — верхняя связность алгоритма <tex>a</tex>;
+:<tex>r=r(a)</tex> — неоптимальность алгоритма <tex>a</tex>;
+:<tex>m=n(a,X^L)</tex> — число ошибок на полной выборке алгоритма <tex>a</tex>;
+:<tex>H_L^{\ell,m}(s)</tex> — функция гипергеометрического распределения.
+Эта оценка является взвешенной суммой OC-оценок с весами <tex>W_{rq}</tex>, имеющими следующие свойства:
+* вес <tex>W_{rq}=1</tex> при <tex>r=q=0</tex>; это означает, что если пренебречь расслоением и связностью, то SC-оценка перейдёт непосредственно в VC-оценку;
+* вес <tex>W_{rq}</tex> является верхней оценкой вероятности того, что алгоритм будет получен в результате обучения по случайной обучающей подвыборке;
+* вес <tex>W_{rq}</tex> убывает экспоненциально по <tex>r</tex> и по <tex>q</tex>.
+Отсюда вытекают два главных вывода:
+* чем сильнее связность, тем меньше вероятность переобучения;
+* основной вклад в вероятность переобучения вносят нижние слои.
+Нижние слои содержат, как правило, очень малую долю алгоритмов.
+Поэтому можно надеяться, что перебор алгоритмов из нижних слоёв позволит достаточно эффективно вычислять SC-оценки.
+=== Оценка равномерноcти–связности ===
+'''Лемма. '''
+Если в качестве метода обучения <tex>\mu</tex> взять метод максимизации отклонения частот (discrepancy maximization),
+::<tex>\mu(X) = \arg\max_{a\in A} \delta_a(X),</tex>
+то функционал равномерного отклонения совпадёт с функционалом вероятности переобучения:
+::<tex>Q_\varepsilon(\mu,X^L) = \mathbb{P} \Bigl[ \delta_\mu(X) \geq \varepsilon \Bigr] \;=\; \tilde Q_\varepsilon(A,X^L) = \mathbb{P} \Bigl[ \max_{a\in A} \delta_a(X) \geq \varepsilon \Bigr].</tex>
+'''Теорема (uniform connectivity bound, UC-bound). '''
+Для любого семейства <tex>A</tex>, любой выборки <tex>X^L</tex> и любого <tex>\varepsilon\in(0,1)</tex> справедлива оценка сверху:
+::<tex>\tilde Q_\varepsilon(A,X^L) \;\leq\; \sum_{a\in A} \tilde W_{pq} H_{L-q-p}^{\ell-q,\,m-p}\Bigl(\frac{\ell}{L}(m-\varepsilon k)\Bigr),</tex>
+::<tex>\mathbb{P}\bigl[ \mu(X)=a \bigr] \;\leq\; \tilde W_{pq} = \frac{C_{L-q-p}^{\ell-q}}{C_{L}^{\ell}},</tex>
+где
+:<tex>\mu</tex> — метод максимизации отклонения частот;
+:<tex>q=q(a)</tex> — верхняя связность алгоритма <tex>a</tex>;
+:<tex>p=p(a)</tex> — нижняя связность алгоритма <tex>a</tex>;
+:<tex>m=n(a,X^L)</tex> — число ошибок на полной выборке алгоритма <tex>a</tex>;
+:<tex>H_L^{\ell,m}(s)</tex> — функция гипергеометрического распределения.
+Эта оценка, как и SC-оценка, является взвешенной суммой OC-оценок.
+Если пренебречь связностью, <tex>q=p=0</tex>, то UC-оценка также переходит в VC-оценку.
+UC-оценка может быть только выше SC-оценки, поскольку <tex>p(a) \leq r(a)</tex> для любого алгоритма <tex>a</tex>.
+Сравнение с SC-оценкой показывает также, что UC-оценка пренебрегает расслоением.
+Вместо неоптимальности алгоритма <tex>r(a)</tex>, которая растёт линейно с ростом номера слоя, в ней фигурирует нижняя связность <tex>p(a)</tex>, которая примерно равна верхней связности и примерно одинакова у всех алгоритмов.
+== Точные оценки вероятности переобучения ==
+Точные оценки вероятности переобучения в настоящее время удалось получить для ряда модельных семейств алгоритмов.
+Все эти семейства являются «искусственными» в том смысле, что они задаются непосредственно бинарной матрицей ошибок, а не каким-либо реальным семейством алгоритмов и реальной выборкой.
+В&nbsp;некоторых случаях удаётся строить примеры выборок, для которых порождаются именно такие матрицы ошибок.
+Однако число этих случаев исчезающе мало в сравнении с числом всевозможных матриц, порождаемых реальными задачами обучения.
+Все модельные семейства отличаются некоторой «регулярностью» или симметрией, которой, как правило, не обладают реальные семейства.
+Тем не менее, изучение модельных семейств представляется перспективным по нескольким причинам.
+* Во-первых, они хорошо иллюстрируют эффекты расслоения и связности.
+* Во-вторых, на них отрабатываются математические приёмы, которые могут оказаться полезными при получении оценок более общего вида.
+* В-третьих, рассмотрение большого числа разнообразных частных случаев ведёт к постепенному обобщению модельных семейств и получению оценок, неплохо аппроксимирующих вероятность переобучения реальных семейств. Такой путь развития комбинаторной теории переобучения представляется наиболее реалистичным.
+* Наконец, это просто интересные задачки по комбинаторике.
+=== Пара алгоритмов ===
+Множество алгоритмов состоит из двух элементов, <tex>A=\{a_1,a_2\}</tex>.
+Задаётся три параметра:
+: <tex>m_1</tex> — число объектов полной выборки, на которых только <tex>a_1</tex> допускает ошибку;
+: <tex>m_2</tex> — число объектов полной выборки, на которых только <tex>a_2</tex> допускает ошибку;
+: <tex>m_0</tex> — число объектов полной выборки, на которых оба алгоритма допускают ошибку.
+Это первый частный случай, для которого была получена точная комбинаторная оценка вероятности переобучения.
+Оценка доказывается путём довольно элементарных комбинаторных рассуждений.
+Оценка зависит от ''ненаблюдаемых'' параметров <tex>m_0,m_1,m_2</tex>.
+Зная соотвествующие три величины на обучающей выборке <tex>s_0,s_1,s_2</tex>, нетрудно построить доверительную область для неизвестных величин <tex>m_0,m_1,m_2</tex>.
+'''Основные выводы:'''
+* Если два алгоритма почти одинаковы, то переобучения почти нет (эффект сходства).
+* Если один из двух алгоритмов существенно лучше другого, то переобучения почти нет (эффект расслоения).
+* Переобучение максимально и достигает VC-оценки только когда алгоритмы максимально плохи (каждый допускает ошибки на половине объектов) и максимально различны.
+=== Монотонная цепочка алгоритмов ===
+Монотонная цепочка алгоритмов является моделью связного семейства с&nbsp;одним непрерывным параметром.
+Это именно то модельное семейство, которое использовалось во втором эксперименте (см. выше).
+'''Основные выводы:'''
+* Монотонная цепочка почти не переобучается
+* Нескольких алгоритмов с наименьшим числом ошибок уже достаточно, чтобы очень точно вычислить вероятность переобучения монотонной цепочки.
+=== Унимодальная цепочка алгоритмов ===
+Унимодальная цепочка алгоритмов является более реалистичной моделью связного семейства с&nbsp;одним непрерывным параметром, по сравнению с монотонной цепочкой. Представляется естественным, что если непрерывный параметр имеет оптимальное значение, то отклонение от него в обе стороны — как в сторону возрастания, так и в сторону убывания — приводит к росту числа ошибок на полной выборке.
+Получение точной оценки для унимодальной цепочки технически гораздо сложнее, чем для монотонной цепочки.
+=== Единичная окрестность лучшего алгоритма ===
+Единичная окрестность лучшего алгоритма — это множество алгоритмов, состоящее из фиксированного алгоритма, называемого «лучшим», и некоторого числа <tex>D</tex> алгоритмов, допускающих ошибки на тех же объектах, что и «лучший» алгоритм, плюс ещё на каком-то одном объекте.
+=== Связка монотонных цепочек ===
+Это семейство является обобщением трёх предыдущих.
+Унимодальная цепочка — это связка из двух монотонных цепочек.
+Единичная окрестность — это связка из <tex>D</tex> цепочек длины&nbsp;2.
+Точные оценки вероятности переобучения для связки монотонных цепочек получены Александром Фреем.
+=== Слой булева куба ===
+Слой булева куба — это множество всех <tex>C_L^m</tex> алгоритмов, векторы ошибок которых содержат ровно <tex>m</tex> единиц.
+Это пример семейства без расслоения.
+Оценка вероятности переобучения в этом случае является вырожденной и принимает только значения 0 или 1:
+::<tex>Q_\varepsilon = \bigl[ \varepsilon k \leq m \leq L-\varepsilon\ell \bigr]. </tex>
+=== Интервал булева куба и его расслоение ===
+Интервал булева куба ранга <tex>m</tex> — это множество алгоритмов, векторы ошибок которых определяются двумя множествами объектов:
+: <tex>m_0</tex> «плохих» объектов, на которых все алгоритмы допускают ошибку;
+: <tex>m</tex> «пограничных» объектов, на которых алгоритмы данного семейства допускают ошибки всеми возможными <tex>2^m</tex> способами;
+: остальные <tex>L-m_0-m</tex> объектов являются «хорошими»: на них ни один из алгоритмов не допускает ошибок.
+Интервал булева куба содержит ровно <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>.
+Уже самый нижний слой хэммингова шара содержит слишком много алгоритмов, поэтому хэмминговы шаров вряд ли могут служить адекватными моделями нижних слоёв реальных семейств.
+Точные оценки вероятности переобучения для хэммингова шара и его слоёв получены Ильёй Толстихиным.
+=== Монотонная многомерная сетка алгоритмов ===
+Монотонная сетка алгоритмов является многомерным обобщением монотонной цепочки алгоритмов.
+Монотонная <tex>h</tex>-мерная сетка является моделью связного семейства алгоритмов с&nbsp;<tex>h</tex>&nbsp;непрерывными параметрами.
+Есть основания полагать, что нижние слои монотонных сеток могут быть использованы в качестве достаточно адекватных моделей реальных семейств, при надлежащем подборе параметра размерности&nbsp;<tex>h</tex>.
+Точные оценки вероятности переобучения для монотонных и унимодальных многомерных сеток получены Павлом Ботовым.
+[[Изображение:MonotoneLattice.png|thumb|center|600px|'''Слева:''' одномерная монотонная сетка высоты&nbsp;3 (монотонная цепочка). '''Справа:''' двумерная монотонная сетка высоты&nbsp;3. Горизонтальные линии отмечают слои — число ошибок на полной выборке. Объекты вдоль стрелок означают, что переход от нижнего алгоритма к верхнему связан с появлением ошибки на данном объекте.]]
+=== Унимодальная многомерная сетка алгоритмов ===
+Унимодальная сетка алгоритмов является более адекватной моделью связного семейства алгоритмов с <tex>h</tex> непрерывными параметрами. В&nbsp;отличие от монотонной сетки предполагается, что отклонение любого параметра от оптимального значения ''в&nbsp;обе стороны'' должно приводить к увеличению числа ошибок.
+Вероятность переобучения унимодальной сетки приблизительно равно вероятности переобучения монотонной сетки удвоенной размерности.
+== Методы получения точных оценок переобучения ==
+=== Метод порождающих и запрещающих множеств ===
+Метод основан на следующем предположении.
+'''Гипотеза 1.'''
+Для любого алгоритма семейства <tex>a\in A</tex> можно указать ''порождающее множество'' объектов <tex>X_a\subseteq X^L</tex> и ''запрещающее множество'' объектов <tex>X'_a\subseteq X^L</tex> такие, что для любого разбиения полной выборки на обучение и контроль, <tex>X^L = X\sqcup\bar X</tex> справедливо
+::<tex>[\mu(X)=a] \;=\; [X_a\subseteq X][X'_a\subseteq \bar X].</tex>
+Это предположение справедливо для монотонной цепочки, единичной окрестности и многомерной монотонной сетки.
+Зная для любого алгоритма <tex>a\in A</tex> его порождающее и запрещающее множества, можно без труда выписать точные оценки вероятности переобучения, а также <tex>P_a = \mathbb{P}[\mu(X)=a]</tex> —&nbsp;вероятности того, что данный алгоритм будет выбран в результате обучения.
+Для унимодальных цепочек и сеток Гипотеза&nbsp;1 уже не верна.
+Доказано, что следующее её обобщение верно всегда.
+'''Гипотеза 2.'''
+Для любого алгоритма семейства <tex>a\in A</tex> можно указать совокупность <tex>V_a</tex> пар множеств: ''порождающие множества'' объектов <tex>X_{av}\subseteq X^L</tex> и ''запрещающие множества'' объектов <tex>X'_{av}\subseteq X^L</tex> такие, что для любого разбиения полной выборки на обучение и контроль, <tex>X^L = X\sqcup\bar X</tex> справедливо
+::<tex>[\mu(X)=a] \;=\; \sum_{v\in V_a} c_{av}[X_{av}\subseteq X][X'_{av}\subseteq \bar X],</tex>
+при некоторых вещественных коэффициентах <tex>c_{av}</tex> (пока не известны ситуации, когда <tex>c_{av}\neq\pm 1</tex>).
+Зная для любого алгоритма <tex>a\in A</tex> все пары порождающих и запрещающих множеств, также можно без труда выписать точные оценки вероятности переобучения, а также вероятности <tex>P_a = \mathbb{P}[\mu(X)=a]</tex>.
+Другой путь обобщения Гипотезы&nbsp;1 заключается в том, чтобы ослабить условие получения алгоритма до необходимого условия, получив тем самым верхнюю оценку.
+'''Гипотеза 3.'''
+Для любого алгоритма семейства <tex>a\in A</tex> можно указать ''порождающее множество'' объектов <tex>X_a\subseteq X^L</tex> и ''запрещающее множество'' объектов <tex>X'_a\subseteq X^L</tex> такие, что для любого разбиения полной выборки на обучение и контроль, <tex>X^L = X\sqcup\bar X</tex> справедливо
+::<tex>[\mu(X)=a] \;\leq\; [X_a\subseteq X][X'_a\subseteq \bar X].</tex>
+С помощью Гипотезы&nbsp;3 Андреем Ивахненко получены верхние оценки вероятности переобучения для семейства конъюнкций одномерных пороговых правил.
+Это семейство широко применяется на практике в логических алгоритмах  классификации.
+Полученные оценки оказались не сильно завышенными, причём завышенность тем меньше, чем выше информативность закономерности.
+Таким образом, в данном случае завышенность не мешает осуществлять отбор наиболее информативных закономерностей.
+Эксперименты показали, что модификация критерия информативности с учётом переобучения улучшает обобщающую способность логических алгоритмов классификации.
+Эта работа, выполненая Андреем Ивахненко в рамках кандидатской диссертации, стала первым примером практического применения комбинаторных оценок вероятности переобучения.
+=== Рекуррентный метод ===
+Рекуррентный метод основан на методе порождающих и запрещающих множеств.
+Он позволяет вычислять точные оценки вероятности переобучения в том случае, когда семейство <tex>A</tex> наращивается по одному алгоритму.
+На&nbsp;каждом шаге в&nbsp;семейство добавляется один алгоритм; для него формируется запрещающее множество (доказывается, что порождающее пусто, и других пар порождающих–запрещающих множеств у него нет); затем для всех предыдущих алгоритмов корректируются пары порождающих–запрещающих множеств.
+При этом могут возникать новые пары.
+В&nbsp;некоторых случаях это может приводить к экспоненциальному росту объёма вычислений.
+Оказывается, что если в этом алгоритме всегда пропускать тот шаг, который может приводить к возникновению новых пар, то будет получена верхняя оценка вероятности переобучения.
+Оказывается также, что эта оценка не сильно завышена и учитывает граф расслоения-связности.
+'''Теорема.'''
+Пусть в <tex>A</tex> есть алгоритм, не допускающий ошибок на полной выборке.
+Пусть <tex>\Delta_{mq}</tex> — ''профиль расслоения–связности'' — число алгоритмов в&nbsp;<tex>m</tex>-м слое со связностью&nbsp;<tex>q</tex>.
+Тогда справедлива верхняя оценка вероятности переобучения
+::<tex>Q_\eps \leq \sum_{m=\lceil \eps k\rceil}^L \sum_{q=0}^L \Delta_{mq} \frac{C_{L-m-q}^{\ell-q}}{C_L^\ell}.</tex>
+В этой оценке комбинаторный множитель убывает экспоненциально (быстрее геометрической прогрессии) по&nbsp;<tex>m</tex> и&nbsp;по&nbsp;<tex>q</tex>.
+'''Основные выводы:'''
+* Только нижние слои графа расслоения–связности могут вносить существенной вклад в вероятность переобучения.
+* С ростом связности эта оценка улучшается экспоненциально по сравнению с классической VC-оценкой.
+* Эксперименты показывают, что значения связности концентрируются вблизи размерности пространства параметров. Действительно, связность <tex>q(a)</tex> — это число способов (степеней свободы), которыми можно «испортить» алгоритм, перейдя от него к другому алгоритму, допускающему ещё на одну ошибку больше.
+'''Открытые проблемы:'''
+* Оценка является ненаблюдаемой. Необходимо научиться оценивать ''профиль расслоения–связности'' <tex>\Delta_{mq}</tex> по наблюдаемой обучающей подвыборке <tex>X\subset X^L</tex>.
+* Ограничение корректности является техническим и, по всей видимости, его удастся снять.
+* Обосновать, что эффекты расслоения и связности «практически независимы», то есть что двумерную матрицу профиля расслоения–связности можно с большой точностью представлять в виде произведения одномерных профилей:
+::<tex>\Delta_{mq} \approx D_m \,\cdot\, \lambda_q,</tex>
+где
+:<tex>D_m = |A_m|</tex> — ''профиль расслоения'';
+:<tex>\lambda_q = \frac1{|A|}\left|\bigl\{a\in A:\: q(a)=q \bigr\}\right|</tex> — ''профиль связности''.
+=== Метод цепных разложений ===
+Метод цепных разложений использовался Денисом Кочедыковым для получения оценок функционала <tex>\tilde Q_\varepsilon(A,X^L)</tex> (вероятности равномерного отклонения), учитывающих связность.
+Он также позволяет снять ограничение корректности.
+Однако UC-оценки, получаемые методом порождающих и запрещающих множеств для метода максимизации отклонения, являются более точными.
+=== Блочный метод ===
+Метод основан на предположении, что в матрице ошибок есть много одинаковых строк, которые объединяются в блоки.
+Число блоков — это число попарно различных строк.
+Выписывается точная оценка вероятности переобучения, трудоёмкость вычисления которой экспоненциальна по числу блоков.
+С&nbsp;помощью этого метода удаётся выписывать вероятность переобучения для произвольных матриц ошибок с небольшим числом столбцов, в&nbsp;частности, для пары и тройки алгоритмов.
+Однако объём вычислений в&nbsp;общем случае растёт как <tex>O(2^D)</tex>, и при числе алгоритмов порядка длины выборки использование данного метода практически теряет смысл.
+=== Теоретико-групповой подход ===
+Теоретико-групповой подход, предложенный Александром Фреем, позволяет выписывать точные оценки вероятности переобучения для симметричных семейств алгоритмов и рандомизированного метода обучения.
+С&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;КБ)]]'''.
+--->
+== Публикации ==
+# Vorontsov K. V. Combinatorial probability and the tightness of generalization bounds // Pattern Recognition and Image Analysis. 2008. Vol. 18, no. 2. Pp. 243–259
+# Воронцов К. В. Точные оценки вероятности переобучения // Доклады РАН, 2009, Т. 429. №1. С. 15–18.
+# Воронцов К. В. Комбинаторный подход к проблеме переобучения // Математические методы распознавания образов: 14-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2009. С. 18–21.
+# Воронцов К. В., Иванов М. Н. Отбор эталонов, основанный на минимизации функционала полного скользящего контроля // Математические методы распознавания образов: 14-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2009. С. 119-122.
+# Vorontsov K. V. The effects of splitting and connectedness in function sets and their influence on the probability of overfitting // Pattern Recognition and Image Analysis, 2009, Vol. 19, No. 3, Pp. 412–420.
+# Vorontsov K. V. Exact Combinatorial Bounds on the Probability of Overfitting for Empirical Risk Minimization // Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 3, pp. 269–285.
+# Ivanov M. N. Prototype Selection Based on Minimization of the Complete Cross Validation // Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 4, pp. 427–437.
+# Воронцов К. В., Решетняк И. М. Точные комбинаторные оценки обобщающей способности онлайнового обучения // Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 24–27.
+# Ботов П. В. Точные оценки вероятности переобучения для несимметричных многомерных семейств алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 20–4.
+# Ивахненко А. А. О вероятности переобучения пороговых конъюнкций Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 57–0.
+# Толстихин И. О. Вероятность переобучения плотных и разреженных семейств алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 83–6.
+# Фрей А.И. Вероятность переобучения плотных и разреженных многомерных сеток алгоритмов Интеллектуализация обработки информации (ИОИ-2010): Докл. Москва: МАКС Пресс, 2010. С. 87–0.
+# Kochedykov D. A. A combinatorial approach to hypothesis similarity in generalization bounds // Pattern Recognition and Image Analysis. — 2011. — Vol. 21. — Pp. 616–629.
+# Vorontsov K. V., Ivahnenko A. A. Tight Combinatorial Generalization Bounds for Threshold Conjunction Rules // Lecture Notes on Computer Science. 4th International Conference on Pattern Recognition and Machine Intelligence (PReMI’11), Russia, Moscow, June 27–July 1, 2011. Pp 66–73.
+# Гуз И. С. Конструктивные оценки полного скользящего контроля для пороговой классификации // Математическая биология и биоинформатика. — Т.6. — В.2. — 2011.
+# Ботов П. В. Уменьшение вероятности переобучения итерационных методов статистического обучения // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 44–47.
+# Гуз И. C. Гибридные оценки полного скользящего контроля для монотонных классификаторов // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 68–71.
+# Животовский Н. К. Комбинаторные оценки вероятности отклонения тестовой ошибки от ошибки скользящего контроля // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 52–55.
+# Фрей А. И. Метод порождающих и запрещающих множеств для рандомизированной минимизации эмпирического риска // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 60–63.
+# Животовский Н. К., Воронцов К. В. Критерии точности комбинаторных оценок обобщающей способности // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 25–28.
+# Воронцов К. В. Комбинаторная теория переобучения: результаты, приложения и открытые проблемы // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 40–43.
+# Воронцов К. В., Махина Г. А. Принцип максимизации зазора для монотонного классификатора ближайшего соседа // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 64–67.
+# Ивахненко А. А., Воронцов К.В. Критерии информативности пороговых логических правил с поправкой на переобучение порогов // Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл. М.: МАКС Пресс, 2011. С. 48–51.
+# Соколов Е. А., Воронцов К. В. Минимизация вероятности переобучения для композиций линейных классификаторов низкой размерности // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 82–85.
+# Толстихин И. О. Локализация оценок избыточного риска в комбинаторной теории переобучения // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 54–57.
+# Фрей А. И., Ивахненко А. А., Решетняк И. М. Применение комбинаторных оценок вероятности переобучения в простом голосовании пороговых конъюнкций // Интеллектуализация обработки информации (ИОИ-2012): Докл. — Москва: Торус Пресс, 2012. С. 86–89.
+# Воронцов К. В., Фрей А. И., Соколов Е. А. Вычислимые комбинаторные оценки вероятности переобучения // Машинное обучение и анализ данных. — 2013. — T. 1, № 6. — С. 734–743.
+# Фрей А. И., Толстихин И. О. Комбинаторные оценки вероятности переобучения на основе кластеризации и покрытий множества алгоритмов // Машинное обучение и анализ данных. 2013. T. 1, № 5. C. 751–767.
 == Литература ==
+# {{П:Воронцов 2010 Комбинаторная теория}}. Презентация на защите [[Медиа:Voron10doct-slides.pdf|(PDF,&nbsp;1760&nbsp;КБ)]].
+# ''Воронцов К.В.'' Открытые проблемы и задачи по спецкурсу «[[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)|Теория надёжности обучения по прецедентам]]» '''[[Media:Voron09exact.pdf|(PDF, 180&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/>
 }}
 [[Категория:Виртуальные семинары]]
 [[Категория:Открытые проблемы и полемика]]
+[[Категория:Теоретические исследования]]
 [[Категория:Теория вычислительного обучения]]

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

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

Текущая версия

Содержание

Оценки обобщающей способности: история вопроса

VC-теория

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

Комбинаторная оценка для одного алгоритма

Комбинаторная VC-оценка

Развитие теории вычислительного обучения

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

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

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

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

Оценки расслоения–связности

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

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

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

Оценка расслоения–связности

Оценка равномерноcти–связности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

Литература

См. также

Просмотры

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

Навигация

Поиск

Инструменты