Стабильность (теория обучения)

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

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

История

Основная цель разработки системы машинного обучения — гарантировать, что алгоритм обучения будет обобщать или точно работать на новых примерах после обучения на конечном их числе. В 1990-е годы были достигнуты важные результаты в получении границ обобщения для алгоритмов обучения с учителем . Техника, исторически использовавшаяся для доказательства обобщения, заключалась в том, чтобы показать, что алгоритм непротиворечив , используя свойства равномерной сходимости эмпирических величин к их средним значениям. Этот метод был использован для получения границ обобщения для большого класса алгоритмов минимизации эмпирического риска (ERM). Алгоритм ERM — это алгоритм, который выбирает решение из пространства гипотез. $H$ таким образом, чтобы минимизировать эмпирическую ошибку на обучающем наборе $S$.

Общий результат, доказанный Владимиром Вапником для алгоритмов бинарной классификации ERM, заключается в том, что для любой целевой функции и входного распределения любое пространство гипотез $H$ с размером VC $d$, и $n$ обучающих примеров, алгоритм последовательен и выдаст ошибку обучения, не превышающую $O\left({\sqrt {\frac {d}{n}}}\right)$ (плюс логарифмические коэффициенты) от истинной ошибки. Позже результат был распространен на почти ERM-алгоритмы с классами функций, не имеющими уникальных минимизаторов.

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

Анализ устойчивости был разработан в 2000-х годах для теории вычислительного обучения и является альтернативным методом получения границ обобщения. Стабильность алгоритма — это свойство процесса обучения, а не прямое свойство пространства гипотез. $H$, и его можно оценить в алгоритмах, которые имеют пространства гипотез с неограниченным или неопределенным VC-размером, например, ближайший сосед. Стабильный алгоритм обучения — это алгоритм, для которого изученная функция не сильно меняется при небольшом изменении обучающего набора, например, при исключении примера. Мера ошибки «Оставить одно исключено» используется в алгоритме перекрестной проверки «Оставить одно исключенным» (CVloo) для оценки устойчивости алгоритма обучения по отношению к функции потерь. Таким образом, анализ стабильности — это применение анализа чувствительности к машинному обучению.

Сводка

• Начало 1900-х годов . Стабильность в теории обучения раньше всего описывалась как непрерывность карты обучения. $L$, traced to Andrey Nikolayevich Tikhonov .
• 1979 - Деврой и Вагнер заметили, что поведение алгоритма с исключением одного связано с его чувствительностью к небольшим изменениям в выборке.
• 1999 — Кернс и Рон обнаружили связь между конечной VC-размерностью и стабильностью.
• 2002 - В знаковой статье Буске и Елисеев предложили понятие единой гипотезы устойчивости алгоритма обучения и показали, что это подразумевает низкую ошибку обобщения. Однако равномерная устойчивость гипотезы является сильным условием, которое не применимо к большим классам алгоритмов, включая алгоритмы ERM с пространством гипотез всего из двух функций.
• 2002 — Кутин и Нийоги расширили результаты Буске и Елисеева, предоставив оценки обобщения для нескольких более слабых форм устойчивости, которые они назвали устойчивостью почти всюду . Кроме того, они сделали первый шаг в установлении взаимосвязи между стабильностью и согласованностью алгоритмов ERM в настройке «Вероятно приблизительно правильно» (PAC).
• 2004 г. - Поджо и др. доказали общую взаимосвязь между стабильностью и согласованностью ERM. Они предложили статистическую форму стабильности по принципу исключения одного, которую они назвали стабильностью CVEEEloo , и показали, что она а) достаточна для обобщения в ограниченных классах потерь и б) необходима и достаточна для согласованности (и, следовательно, обобщения) алгоритмов ERM. для определенных функций потерь, таких как квадратичная потеря, абсолютное значение и потеря двоичной классификации.
• 2010 - Шалев Шварц и др. заметил проблемы с исходными результатами Вапника из-за сложных отношений между пространством гипотез и классом потерь. Они обсуждают понятия стабильности, охватывающие различные классы потерь и разные типы обучения, контролируемого и неконтролируемого.
• 2016 - Мориц Хардт и др. доказанная стабильность градиентного спуска при определенных предположениях относительно гипотезы и количестве раз, когда каждый экземпляр используется для обновления модели.

Предварительные определения

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

Алгоритм машинного обучения, также известный как карта обучения. $L$, отображает набор обучающих данных, который представляет собой набор помеченных примеров. $(x,y)$, на функцию $f$ от $X$ к $Y$, где $X$ и $Y$ находятся в том же пространстве обучающих примеров. Функции $f$ выбираются из гипотетического пространства функций, называемых $H$.

Обучающий набор, на котором обучается алгоритм, определяется как

$S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}$

и имеет размер $m$ в $Z=X\times Y$

взят iid из неизвестного дистрибутива D.

Таким образом, карта обучения $L$ определяется как отображение из $Z_{m}$ в $H$, отображение обучающего набора $S$ на функцию $f_{S}$ от $X$ к $Y$. Здесь мы рассматриваем только детерминированные алгоритмы, в которых $L$ симметричен относительно $S$, т.е. не зависит от порядка элементов в обучающем наборе. Кроме того, мы предполагаем, что все функции измеримы и все множества счетны.

Потеря $V$ гипотезы $f$ что касается примера $z=(x,y)$ затем определяется как $V(f,z)=V(f(x),y)$.

Эмпирическая ошибка $f$ является $I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})$.

Истинная ошибка $f$ является $I[f]=\mathbb {E} _{z}V(f,z)$

Учитывая обучающий набор S размера m, мы построим для всех i = 1....,m модифицированные обучающие наборы следующим образом:

• Удалив i-й элемент

$S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}$

• Заменив i-й элемент

$S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{m}\}$

Определения стабильности

Гипотеза

Алгоритм $L$ имеет устойчивость гипотезы β относительно функции потерь V, если выполняется следующее:

$\forall i\in \{1,...,m\},\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{|i}},z)|]\leq \beta .$

Устойчивость гипотезы по точкам

Алгоритм $L$ имеет поточечную устойчивость гипотезы β относительно функции потерь V, если выполняется следующее:

$\forall i\in \ \{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .$

Стабильность ошибок

Алгоритм $L$ имеет устойчивость к ошибкам β относительно функции потерь V, если выполняется следующее:

$\forall S\in Z^{m},\forall i\in \{1,...,m\},|\mathbb {E} _{z}[V(f_{S},z)]-\mathbb {E} _{z}[V(f_{S^{|i}},z)]|\leq \beta$

Равномерная стабильность

Алгоритм $L$ имеет равномерную устойчивость β относительно функции потерь V, если выполняется следующее:

$\forall S\in Z^{m},\forall i\in \{1,...,m\},\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta$

Вероятностная версия равномерной устойчивости β:

$\forall S\in Z^{m},\forall i\in \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta \}\geq 1-\delta$

Алгоритм называется устойчивым , если значение $\beta$ уменьшается по мере $O({\frac {1}{m}})$.

Перекрестная проверка с исключением одного (

Алгоритм $L$ имеет CVloo-стабильность β относительно функции потерь V, если выполняется следующее:

$\forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}$

Определение стабильности (CVloo) эквивалентно устойчивости поточечной гипотезы, рассмотренной ранее.

Ожидаемая ошибка пропуска одного ( $Eloo_{err}$) Стабильность

Алгоритм $L$ имеет $Eloo_{err}$ устойчивость, если для каждого n существует $\beta _{EL}^{m}$ и $\delta _{EL}^{m}$ такой, что:

$\forall i\in \{1,...,m\},\mathbb {P} _{S}\{|I[f_{S}]-{\frac {1}{m}}\sum _{i=1}^{m}V(f_{S^{|i}},z_{i})|\leq \beta _{EL}^{m}\}\geq 1-\delta _{EL}^{m}$, с $\beta _{EL}^{m}$ и $\delta _{EL}^{m}$ стремится к нулю для $m,\rightarrow \infty$

теоремы

От Буске и Елисеева (02) :

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

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

Из Мукерджи и др. (06) :

• Для симметричных алгоритмов обучения с ограниченными потерями, если алгоритм имеет как стабильность перекрестной проверки с исключением одного (CVloo), так и ошибку ожидаемого исключения одного ( $Eloo_{err}$) Стабильность определена выше, тогда алгоритм обобщается.
• Ни одно из условий само по себе не является достаточным для обобщения. Однако оба вместе обеспечивают обобщение (а обратное неверно).
• В частности, для алгоритмов ERM (скажем, для потери квадратов) стабильность перекрестной проверки с исключением одного (CVloo) необходима и достаточна для обеспечения согласованности и обобщения.

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

Стабильные алгоритмы

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

• Линейная регрессия
• Классификатор k-NN с функцией потерь {0-1}.
• Классификация машины опорных векторов (SVM) с ограниченным ядром, где регуляризатор является нормой в гильбертовом пространстве воспроизводящего ядра. Большая константа регуляризации $C$ приводит к хорошей стабильности.
• Классификация SVM с мягкой маржой.
• Регуляризованная регрессия наименьших квадратов.
• Алгоритм минимальной относительной энтропии для классификации.
• Вариант упаковки регуляризаторов с номером $k$ регрессоров увеличивается с $n$.
• Многоклассовая классификация SVM.
• Все алгоритмы обучения с регуляризацией Тихонова удовлетворяют критериям равномерной устойчивости и, следовательно, являются обобщаемыми.

Дальнейшее чтение

• С.Кутин и П.Ниёги.Почти всюду алгоритмическая устойчивость и ошибка обобщения. В Proc. УАИ 18, 2002 г.
• С. Рахлин, С. Мукерджи и Т. Поджо. Стабильность приводит к теории обучения. Анализ и приложения, 3(4):397–419, 2005 г.
• В. Н. Вапник. Природа статистической теории обучения. Спрингер, 1995 г.
• Вапник В. Статистическая теория обучения. Уайли, Нью-Йорк, 1998 г.
• Поджио Т., Рифкин Р., Мукерджи С. и Нийоги П., «Теория обучения: общие условия прогнозирования», Nature, Vol. 428, 419-422, 2004 г.
• Андре Елисеев, Теодорос Евгениу, Массимилиано Понтил, Стабильность алгоритмов рандомизированного обучения, Журнал исследований машинного обучения 6, 55–79, 2010 г.
• Елисеев, А. Понтил, М., Ошибка исключения и стабильность алгоритмов обучения с приложениями, НАУЧНАЯ СЕРИЯ НАТО ПОДСЕРИЯ III КОМПЬЮТЕРНЫЕ И СИСТЕМНЫЕ НАУКИ, 2003, ТОМ 190, страницы 111-130
• Шалев Шварц С., Шамир О., Сребро Н., Шридхаран К., Обучаемость, стабильность и равномерная конвергенция, Журнал исследований машинного обучения, 11 (октябрь): 2635-2670, 2010 г.