Ошибка обобщения - Generalization error

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

Определение

В задаче обучения цель состоит в том, чтобы разработать функцию, которая предсказывает выходные значения для каждого входного элемента данных . Нижний индекс указывает, что функция разработана на основе набора данных точек данных. Ошибка обобщения или ожидаемые потери или риска , в той или иной функции по всем возможным значениям и является: ${\ displaystyle f_ {n} ({\ vec {x}})}$${\ displaystyle y}$${\ displaystyle {\ vec {x}}}$${\ displaystyle n}$${\ displaystyle f_ {n}}$${\ displaystyle n}$${\ displaystyle I [f]}$${\ displaystyle f}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

${\ displaystyle I [f] = \ int _ {X \ times Y} V (f ({\ vec {x}}), y) \ rho ({\ vec {x}}, y) d {\ vec { x}} dy,}$

где обозначает функцию потерь, а - неизвестное совместное распределение вероятностей для и . ${\ displaystyle V}$${\ displaystyle \ rho ({\ vec {x}}, y)}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

Невозможно вычислить, не зная совместного распределения вероятностей . Вместо этого мы можем вычислить ошибку на выборочных данных, которая называется эмпирической ошибкой (или эмпирическим риском ). При заданных точках данных эмпирическая ошибка функции-кандидата составляет: ${\ displaystyle \ rho}$${\ displaystyle I [f]}$${\ displaystyle n}$${\ displaystyle f}$

${\ displaystyle I_ {n} [f] = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} V (f ({\ vec {x}} _ {i}), y_ {i})}$

Алгоритм называется обобщающим, если:

${\ displaystyle \ lim _ {п \ rightarrow \ infty} I [f] -I_ {n} [f] = 0}$

Особое значение имеет ошибка обобщения функции , зависящей от данных, которая обнаруживается алгоритмом обучения на основе выборки. Опять же, для неизвестного распределения вероятностей вычислить невозможно. Вместо этого цель многих задач в теории статистического обучения состоит в том, чтобы ограничить или охарактеризовать разницу ошибки обобщения и эмпирической ошибки в вероятности: ${\ displaystyle I [f_ {n}]}$${\ displaystyle f_ {n}}$${\ displaystyle I [f_ {n}]}$

${\ displaystyle P_ {G} = P (I [f_ {n}] - I_ {n} [f_ {n}] \ leq \ epsilon) \ geq 1- \ delta _ {n}}$

То есть цель состоит в том, чтобы охарактеризовать вероятность того, что ошибка обобщения меньше эмпирической ошибки плюс некоторая граница ошибки (обычно зависит от и ). Для многих типов алгоритмов было показано, что алгоритм имеет границы обобщения, если он удовлетворяет определенным критериям устойчивости . В частности, если алгоритм является симметричным (порядок входных данных не влияет на результат), имеет ограниченные потери и удовлетворяет двум условиям устойчивости, он будет обобщен. Первое условие стабильности, стабильность перекрестной проверки с исключением одного исключения , гласит, что для обеспечения стабильности ошибка прогнозирования для каждой точки данных, когда используется перекрестная проверка с исключением одного, должна сходиться к нулю как . Второе условие, устойчивость ожидаемой к исключению единичной ошибки (также известная как стабильность гипотез при работе в норме ), выполняется, если прогноз для оставленной точки данных не изменяется, когда одна точка данных удаляется из набор обучающих данных. ${\ displaystyle 1- \ delta _ {n}}$${\ displaystyle \ epsilon}$${\ displaystyle \ delta}$${\ displaystyle n}$${\ Displaystyle п \ rightarrow \ infty}$${\ displaystyle L_ {1}}$

Эти условия можно формализовать как:

Стабильность перекрестной проверки без исключения

Алгоритм имеет стабильность, если для каждого из них существует и такое, что: ${\ displaystyle L}$${\ displaystyle CVloo}$${\ displaystyle n}$${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$

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

и и перейти к нулю, стремится к бесконечности. ${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$${\ displaystyle n}$

Ожидаемая ошибка с отсутствием единичной ошибки Стабильность

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

${\ displaystyle \ forall i \ in \ {1, ..., n \}, \ mathbb {P} _ {S} \ left \ {\ left | I [f_ {S}] - {\ frac {1} {n}} \ sum _ {i = 1} ^ {N} V \ left (f_ {S ^ {i}}, z_ {i} \ right) \ right | \ leq \ beta _ {EL} ^ {( n)} \ right \} \ geq 1- \ delta _ {EL} ^ {(n)}}$

с и стремится к нулю для . ${\ displaystyle \ beta _ {EL} ^ {(n)}}$${\ displaystyle \ delta _ {EL} ^ {(n)}}$${\ Displaystyle п \ rightarrow \ infty}$

Для устойчивости в норме с исключением одного-одного это то же самое, что и для устойчивости гипотезы: ${\ displaystyle L_ {1}}$

${\ Displaystyle \ mathbb {E} _ {S, z} [| V (f_ {S}, z) -V (f_ {S ^ {i}}, z) |] \ leq \ beta _ {H} ^ {(n)}}$

с переходом к нулю, как и к бесконечности. ${\ displaystyle \ beta _ {H} ^ {(n)}}$${\ displaystyle n}$

Алгоритмы с доказанной стабильностью

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

Отношение к переобучению

Этот рисунок иллюстрирует взаимосвязь между переобучением и ошибкой обобщения I [ f _n ] - I _S [ f _n ]. Точки данных были сгенерированы из отношения y = x с добавлением белого шума к значениям y . В левом столбце набор тренировочных точек показан синим цветом. Полиномиальная функция седьмого порядка соответствовала обучающим данным. В правом столбце функция тестируется на данных, взятых из базового совместного распределения вероятностей x и y . В верхнем ряду функция соответствует образцу набора данных из 10 точек. В нижнем ряду функция соответствует набору данных из 100 точек. Как мы видим, для малых размеров выборки и сложных функций ошибка обучающего набора мала, но ошибка основного распределения данных велика, и мы переобучили данные. В результате ошибка обобщения велика. По мере увеличения количества точек выборки ошибка прогнозирования обучающих и тестовых данных сходится, а ошибка обобщения становится равной 0.

Понятия ошибки обобщения и переобучения тесно связаны. Переобучение происходит, когда изученная функция становится чувствительной к шуму в сэмпле. В результате функция будет хорошо работать на обучающем наборе, но не будет хорошо работать на других данных из совместного распределения вероятностей и . Таким образом, чем больше происходит переоснащение, тем больше ошибка обобщения. ${\ displaystyle f_ {S}}$${\ displaystyle x}$${\ displaystyle y}$

Величину переобучения можно проверить с помощью методов перекрестной проверки , которые разбивают выборку на моделируемые обучающие выборки и тестовые выборки. Затем модель обучается на обучающей выборке и оценивается на тестовой выборке. Тестовая выборка ранее невидима для алгоритма и поэтому представляет собой случайную выборку из совместного распределения вероятностей и . Этот тестовый образец позволяет нам приблизить ожидаемую ошибку и, как результат, приблизить конкретную форму ошибки обобщения. ${\ displaystyle x}$${\ displaystyle y}$

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

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

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

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

• Bousquet, O., S. Boucheron и G. Lugosi. Введение в статистическую теорию обучения . Расширенные лекции по машинному обучению Лекционные заметки по искусственному интеллекту 3176, 169-207. (Ред.) Буске, О., У. фон Люксбург и Г. Ратч, Springer, Гейдельберг, Германия (2004)
• Буске, О. и А. Элиссиф (2002), Стабильность и обобщение, Журнал исследований в области машинного обучения, 499-526.
• Деврое Л., Л. Дьёрфи и Г. Лугоши (1996). Вероятностная теория распознавания образов. Springer-Verlag. ISBN   978-0387946184 .
• Поджио Т. и С. Смейл. Математика обучения: работа с данными . Уведомления AMS, 2003 г.
• Вапник, В. (2000). Природа статистической теории обучения. Информатика и статистика. Springer-Verlag. ISBN   978-0-387-98780-4 .
• Бишоп К.М. (1995), Нейронные сети для распознавания образов , Оксфорд: Oxford University Press, особенно раздел 6.4.
• Финке М., Мюллер К.-Р. (1994), « Оценка апостериорных вероятностей с использованием стохастических сетевых моделей », в Mozer, Smolensky, Touretzky, Elman, & Weigend, eds., Proceedings of the Connectionist Models Summer School 1993 , Hillsdale, NJ: Lawrence Erlbaum Associates, стр. 324–331.
• Геман, С., Биненсток, Э. и Дурсат, Р. (1992), « Нейронные сети и дилемма смещения / дисперсии », Neural Computing , 4, 1-58.
• Хусмайер, Д. (1999), Нейронные сети для оценки условной вероятности: прогнозирование, выходящее за рамки точечных предсказаний , Берлин: Springer Verlag, ISBN   1-85233-095-3 .
• Маккаллах П. и Нелдер Дж. А. (1989) Обобщенные линейные модели , 2-е изд., Лондон: Chapman & Hall.
• Мохри М., Ростамизаде А., Талвакар А. (2018) Основы машинного обучения , 2-е изд., Бостон: MIT Press.
• Moody, JE (1992), « Эффективное количество параметров: анализ обобщения и регуляризации в нелинейных обучающих системах », в Moody, JE, Hanson, SJ, и Lippmann, RP, Advances in Neural Information Processing Systems 4, 847- 854.
• Рипли, Б.Д. (1996) Распознавание образов и нейронные сети , Кембридж: Издательство Кембриджского университета.
• Rohwer, R., и van der Rest, JC (1996), « Минимальная длина описания, регуляризация и мультимодальные данные », Neural Computing, 8, 595-609.
• Рохас, Р. (1996), " Краткое доказательство свойства апостериорной вероятности нейронных сетей классификатора ", Нейронные вычисления , 8, 41-43.
• Уайт, Х. (1990), " Коннекционистская непараметрическая регрессия: многослойные сети прямого распространения могут изучать произвольные сопоставления ", Neural Networks , 3, 535-550. Печатается в белом цвете (1992).
• Уайт, Х. (1992a), « Непараметрическая оценка условных квантилей с использованием нейронных сетей », в Пейдж, К. и Ле Пейдж, Р. (ред.), Труды 23-го симпсума по интерфейсу: вычислительная наука и статистика , Александрия , Вирджиния: Американская статистическая ассоциация, стр. 190–199. Перепечатано в белом цвете (1992b).
• Уайт, Х. (1992b), Искусственные нейронные сети: теория приближения и обучения , Blackwell.