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

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

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

История

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

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

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

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

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

  • Начало 1900-х годов - Стабильность в теории обучения впервые описывалась в терминах непрерывности обучающей карты. , прослеживается до Андрей Николаевич Тихонов.
  • 1979 - Деврой и Вагнер заметили, что поведение алгоритма «исключение по одному» связано с его чувствительностью к небольшим изменениям в выборке.[1]
  • 1999 - Кернс и Рон обнаружили связь между конечной размерностью ВК и стабильностью.[2]
  • 2002 - В исторической статье Буске и Элиссефф предложили понятие единообразная устойчивость гипотез алгоритма обучения и показал, что он предполагает низкую ошибку обобщения. Однако единообразная стабильность гипотез является сильным условием, которое не применяется к большим классам алгоритмов, включая алгоритмы ERM с пространством гипотез только из двух функций.[3]
  • 2002 - Кутин и Нийоги расширили результаты Буске и Элиссеффа, предоставив оценки обобщения для нескольких более слабых форм устойчивости, которые они назвали почти везде стабильность. Более того, они сделали первый шаг в установлении взаимосвязи между стабильностью и согласованностью в алгоритмах ERM в настройке «Вероятно приблизительно правильно» (PAC).[4]
  • 2004 - Poggio et al. доказали общую взаимосвязь между стабильностью и согласованностью ERM. Они предложили статистическую форму стабильности по принципу исключения одного исключения, которую они назвали CVEEEloo стабильностьи показал, что это а) достаточно для обобщения в классах с ограниченными потерями и б) необходимо и достаточно для согласованности (и, следовательно, обобщения) алгоритмов ERM для определенных функций потерь, таких как квадрат потерь, абсолютное значение и потери двоичной классификации. .[5]
  • 2010 - Шалев Шварц заметил проблемы с исходными результатами Vapnik из-за сложных отношений между пространством гипотез и классом потерь. Они обсуждают понятия стабильности, которые охватывают разные классы потерь и разные типы обучения, контролируемого и неконтролируемого.[6]

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

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

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

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

и имеет размер в

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

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

Утрата гипотезы относительно примера тогда определяется как .

Эмпирическая ошибка является .

Истинная ошибка является

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм называется стабильный, когда значение уменьшается как .

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

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

Определение (CVloo) устойчивости таково: эквивалент к Точечно-гипотезе устойчивости видели ранее.

Ожидаемая ошибка исключения () Стабильность

Алгоритм имеет устойчивость, если для каждого n существует и такой, что:

, с и идет к нулю для

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

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

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

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

Из Mukherjee et al. (06):

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

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

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

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

  • Линейная регрессия[7]
  • Классификатор k-NN с функцией потерь {0-1}.[8]
  • Машина опорных векторов (SVM) классификация с ограниченным ядром и где регуляризатор является нормой в гильбертовом пространстве воспроизводящего ядра. Большая константа регуляризации приводит к хорошей стабильности.[9]
  • Классификация Soft margin SVM.[10]
  • Регулярный Регрессия методом наименьших квадратов.[11]
  • Алгоритм минимальной относительной энтропии для классификации.[12]
  • Версия упаковка регуляризаторы с номером регрессоров увеличивается с .[13]
  • Мультиклассовая классификация SVM.[14]
  • Все алгоритмы обучения с регуляризацией Тихонова удовлетворяют критериям равномерной устойчивости и, таким образом, являются обобщаемыми.[15]

Рекомендации

  1. ^ Л. Деврой и Вагнер, Границы производительности без распределения для правил потенциальных функций, IEEE Trans. Инф. Теория 25 (5) (1979) 601–604.
  2. ^ М. Кирнс и Д. Рон, Алгоритмическая стабильность и границы проверки работоспособности для перекрестной проверки исключения по одному, Neural Comput. 11 (6) (1999) 1427–1453.
  3. ^ О. Буске и А. Элиссефф. Устойчивость и обобщение. J. Mach. Учиться. Res., 2: 499–526, 2002.
  4. ^ С. Кутин и П. Нийоги, Почти всюду алгоритмическая стабильность и ошибка обобщения, Технический отчет TR-2002-03, Чикагский университет (2002).
  5. ^ С. Мукерджи, П. Нийоги, Т. Поджио и Р. М. Рифкин. Теория обучения: стабильность достаточна для обобщения и необходима и достаточна для согласованности минимизации эмпирического риска. Adv. Comput. Матем., 25 (1-3): 161–193, 2006.
  6. ^ Шалев Шварц, С., Шамир, О., Сребро, Н., Шридхаран, К., Обучаемость, стабильность и равномерная конвергенция, Журнал исследований в области машинного обучения, 11 (октябрь): 2635-2670, 2010.
  7. ^ Элиссефф, А. Исследование об алгоритмической стабильности и их связи с характеристиками обобщения. Технический отчет. (2000)
  8. ^ Л. Деврой и Вагнер, Границы производительности без распределения для правил потенциальных функций, IEEE Trans. Инф. Теория 25 (5) (1979) 601–604.
  9. ^ О. Буске и А. Элиссефф. Устойчивость и обобщение. J. Mach. Учиться. Res., 2: 499–526, 2002.
  10. ^ О. Буске и А. Элиссефф. Устойчивость и обобщение. J. Mach. Учиться. Res., 2: 499–526, 2002.
  11. ^ О. Буске и А. Элиссефф. Устойчивость и обобщение. J. Mach. Учиться. Res., 2: 499–526, 2002.
  12. ^ О. Буске и А. Элиссефф. Устойчивость и обобщение. J. Mach. Учиться. Res., 2: 499–526, 2002.
  13. ^ Рифкин, Р. Все старое снова новое: новый взгляд на исторические подходы в машинном обучении. Кандидат наук. Диссертация, Массачусетский технологический институт, 2002 г.
  14. ^ Рифкин, Р. Все старое снова новое: новый взгляд на исторические подходы в машинном обучении. Кандидат наук. Диссертация, Массачусетский технологический институт, 2002 г.
  15. ^ http://www.mit.edu/~9.520/spring09/Classes/class10_stability.pdf

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

  • Кутин С., Нийоги П. Практически везде алгоритмическая устойчивость и ошибка обобщения. В Proc. от UAI 18, 2002 г.
  • С. Рахлин, С. Мукерджи и Т. Поджио. Стабильность приводит к теории обучения. Анализ и приложения, 3 (4): 397–419, 2005.
  • В.Н. Вапник. Природа статистической теории обучения. Спрингер, 1995 г.
  • Вапник В. Статистическая теория обучения. Уайли, Нью-Йорк, 1998 г.
  • Поджио, Т., Рифкин, Р., Мукерджи, С. и Нийоги, П., "Теория обучения: общие условия предсказуемости", Nature, Vol. 428, 419-422, 2004 г.
  • Андре Элиссефф, Теодорос Евгениу, Массимилиано Понтил, Стабильность алгоритмов рандомизированного обучения, Журнал исследований машинного обучения, 6, 55–79, 2010 г.
  • Элиссефф, А. Понтил, М., Ошибка исключения одного и того же и стабильность алгоритмов обучения с приложениями, NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES, 2003, VOL 190, страницы 111-130
  • Шалев Шварц, С., Шамир, О., Сребро, Н., Шридхаран, К., Обучаемость, стабильность и равномерная конвергенция, Журнал исследований в области машинного обучения, 11 (октябрь): 2635-2670, 2010 г.