Ошибка обобщения

Мера точности алгоритма

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

Определение

В задаче обучения цель состоит в том, чтобы разработать функцию , которая предсказывает выходные значения для каждого входного значения . Нижний индекс указывает, что функция разработана на основе набора данных точек данных. Ошибка обобщения или ожидаемая потеря или риск конкретной функции по всем возможным значениям и является ожидаемым значением функции потерь : ^[1] ${\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 V(f)}$

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

где — неизвестное совместное распределение вероятностей для и . ${\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 _{n\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}}$

То есть, цель состоит в том, чтобы охарактеризовать вероятность того, что ошибка обобщения меньше эмпирической ошибки плюс некоторая граница ошибки (обычно зависящая от и ). Для многих типов алгоритмов было показано, что алгоритм имеет границы обобщения, если он соответствует определенным критериям устойчивости . В частности, если алгоритм симметричен (порядок входных данных не влияет на результат), имеет ограниченные потери и соответствует двум условиям устойчивости, он будет обобщать. Первое условие устойчивости, устойчивость перекрестной проверки с исключением одного , гласит, что для обеспечения устойчивости ошибка прогнозирования для каждой точки данных при использовании перекрестной проверки с исключением одного должна сходиться к нулю как . Второе условие, устойчивость ожидаемой ошибки с исключением одного (также известная как устойчивость гипотезы, если работает в норме ) выполняется, если прогноз по исключенной точке данных не изменяется при удалении одной точки данных из обучающего набора данных. ^[3] ${\displaystyle 1-\delta _{n}}$ ${\displaystyle \epsilon }$ ${\displaystyle \delta }$ ${\displaystyle n}$ ${\displaystyle n\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)}}$

и стремится к нулю, стремясь к бесконечности. ^[3] ${\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 n\rightarrow \infty }$

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

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

с стремлением к нулю по мере стремления к бесконечности. ^[3] ${\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}$

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

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

Ссылки

1. Mohri, M., Rostamizadeh A., Talwakar A., ​​(2018) Основы машинного обучения , 2-е изд., Бостон: MIT Press
2. Y S. Абу-Мостафа, M. Магдон-Исмаил и H.-T. Лин (2012) Обучение на основе данных, AMLBook Press. ISBN  978-1600490064
3. Мукерджи, С.; Ниёги, П.; Поджио, Т.; Рифкин, Р.М. (2006). «Теория обучения: стабильность достаточна для обобщения и необходима и достаточна для согласованности минимизации эмпирического риска» (PDF) . Adv. Comput. Math . 25 (1–3): 161–193. doi :10.1007/s10444-004-7634-z. S2CID  2240256.

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

• Оливье, Буске; Люксбург, Ульрике; Ратш, Гуннар, ред. (2004). Продвинутые лекции по машинному обучению. Конспект лекций по информатике. Том 3176. С. 169–207. doi :10.1007/b100712. ISBN 978-3-540-23122-6. S2CID  431437 . Получено 10 декабря 2022 г. .
• Буске, Оливье; Елисефф, Андре (1 марта 2002 г.). «Устойчивость и обобщение». Журнал исследований машинного обучения . 2 : 499–526. doi :10.1162/153244302760200704. S2CID  1157797 . Получено 10 декабря 2022 г. .
• Мохри, М., Ростамизаде А., Талвакар А., (2018) Основы машинного обучения , 2-е изд., Бостон: MIT Press.
• Муди, Дж. Э. (1992), «Эффективное число параметров: анализ обобщения и регуляризации в нелинейных обучающихся системах. Архивировано 10 сентября 2016 г. в Wayback Machine », в книге Муди, Дж. Э., Хансон, С. Дж. и Липпманн, Р. П., Достижения в области нейронных систем обработки информации, 4, 847–854.
• Уайт, Х. (1992b), Искусственные нейронные сети: теория аппроксимации и обучения , Блэквелл.