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

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

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

История

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

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

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

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

Резюме классических результатов

• Начало 1900-х - Стабильность в теории обучения впервые была описана в терминах непрерывности карты обучения , восходящей к Андрею Николаевичу Тихонову .${\displaystyle L}$
• 1979 - Деврой и Вагнер заметили, что поведение алгоритма с исключением одного элемента связано с его чувствительностью к небольшим изменениям в выборке.
• 1999 - Кернс и Рон обнаружили связь между конечной размерностью ВК и стабильностью.
• 2002 - В знаменательной статье Буске и Элиссефф предложили понятие устойчивости единой гипотезы алгоритма обучения и показали, что оно подразумевает низкую ошибку обобщения. Однако единообразная стабильность гипотез является сильным условием, которое не применяется к большим классам алгоритмов, включая алгоритмы ERM с пространством гипотез только из двух функций.
• 2002 - Кутин и Нийоги расширили результаты Буске и Элиссеффа, предоставив оценки обобщения для нескольких более слабых форм устойчивости, которые они назвали стабильностью почти всюду . Кроме того, они сделали первый шаг в установлении взаимосвязи между стабильностью и согласованностью в алгоритмах ERM в настройке «Вероятно, приблизительно правильно» (PAC).
• 2004 - Поджио и др. доказали общую взаимосвязь между стабильностью и согласованностью ERM. Они предложили статистическую форму устойчивости по принципу исключения одного исключения, которую они назвали стабильностью CVEEEloo , и показали, что она а) достаточна для обобщения в классах с ограниченными потерями и б) необходима и достаточна для согласованности (и, следовательно, обобщения) алгоритмов ERM. для некоторых функций потерь, таких как квадратные потери, абсолютное значение и потери двоичной классификации.
• 2010 - Шалев Шварц и др. заметил проблемы с исходными результатами Vapnik из-за сложных отношений между пространством гипотез и классом потерь. Они обсуждают понятия стабильности, которые охватывают разные классы потерь и разные типы обучения, контролируемого и неконтролируемого.

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

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

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

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

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

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

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

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

Утрата гипотезы относительно примера определяется как . ${\displaystyle V}$${\displaystyle f}$${\displaystyle z=(x,y)}$${\displaystyle V(f,z)=V(f(x),y)}$

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

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

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

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

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

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

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

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

Стабильность гипотез

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

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

Точечная гипотеза устойчивости

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

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

Устойчивость к ошибкам

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

${\displaystyle \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 }$

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

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

${\displaystyle \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 }$

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

${\displaystyle \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 }$

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

Перекрестная проверка без исключения (CVloo) Стабильность

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

${\displaystyle \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) устойчивости эквивалентно устойчивости поточечной гипотезы, рассмотренной ранее.

Ожидаемая ошибка исключения ( ) Стабильность${\displaystyle Eloo_{err}}$

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

${\displaystyle \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}}$, с и стремясь к нулю для${\displaystyle \beta _{EL}^{m}}$${\displaystyle \delta _{EL}^{m}}$${\displaystyle m,\rightarrow \infty }$

Классические теоремы

От Буске и Элиссефф (02) :

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

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

Из Mukherjee et al. (06) :

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

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

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

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

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

использованная литература

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