Минимизация эмпирического риска

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

СТАТЬЯ В РАЗРАБОТКЕ: Этот материал сейчас находится в процессе активного редактирования и доработки участником Polina Khadralinova.

Минимизация эмпирического риска (англ. Empirical Risk Minimization, ERM) — один из фундаментальных принципов в теории машинного обучения, определяющий метод построения алгоритмов обучения с учителем. Суть принципа заключается в выборе параметрической модели, которая минимизирует среднюю ошибку (функцию потерь) на заданной обучающей выборке.

Данный принцип является строгой математической формализацией эмпирической индукции Фрэнсиса Бэкона: на основе частных опытных данных (прецедентов) строится общее закономерное правило (модель), способное делать предсказания для новых объектов.

Содержание

1 Историческая справка
2 Ожидаемый и эмпирический риск
3 Условия состоятельности и переобучение
- 3.1 Регуляризация
4 Основные типы функций потерь
5 Методы оптимизации
6 См. также
7 Примечания

Историческая справка

Идейным предшественником принципа ERM является метод наименьших квадратов, предложенный Карлом Фридрихом Гауссом (1795) и Адриеном Мари Лежандром (1805) для астрономических вычислений. Они первыми предложили искать параметры модели, минимизируя сумму квадратов отклонений на известных точках^[1].

Строгое математическое и статистическое обоснование принципа минимизации эмпирического риска было разработано в 1960–1970-х годах в рамках статистической теории обучения (теории Вапника — Червоненкиса). В. Н. Вапник и А. Я. Червоненкис доказали теоремы о равномерной сходимости частот к вероятностям, определив условия, при которых минимизация ошибки на обучающей выборке гарантирует низкую ошибку на новых данных^[1].

Ожидаемый и эмпирический риск

Пусть дано пространство объектов $X$ и пространство ответов $Y$ . Предполагается, что существует неизвестная совместная плотность распределения вероятностей $p(x, y)$ , из которой порождаются данные.

Имеется параметрическое семейство моделей:

$A = \{ a(x, w) \mid w \in W \}$ ,

где $W \subseteq \mathbb{R}^N$ — пространство параметров (весов).

Качество предсказания оценивается с помощью функции потерь (loss function) $\mathcal{L}(a(x, w), y)$ .

Истинный (ожидаемый) риск $R(w)$ — это математическое ожидание функции потерь по всему распределению $p(x, y)$ :

$R(w) = \mathbb{E}_{x,y \sim p(x, y)} [\mathcal{L}(a(x, w), y)]$ .

Идеальная цель машинного обучения — найти параметры $w$ , минимизирующие истинный риск. Однако на практике распределение $p(x, y)$ неизвестно.

Вместо этого доступна конечная обучающая выборка:

$X^{\ell} = \{ (x_1, y_1), \dots, (x_{\ell}, y_{\ell}) \}$ .

В соответствии с законом больших чисел, истинный риск заменяется его выборочной оценкой — эмпирическим риском:

$Q(w, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(a(x_i, w), y_i)$ .

Принцип ERM утверждает, что оптимальные параметры модели $w^*$ должны доставлять минимум функционалу эмпирического риска:

$w^* = \arg \min_{w \in W} Q(w, X^{\ell})$ .

Условия состоятельности и переобучение

Главная проблема принципа ERM заключается в том, что при высокой сложности семейства моделей $A$ (например, в глубоких нейронных сетях) и малом объёме выборки $\ell$ , минимум эмпирического риска не гарантирует минимума истинного риска. Возникает эффект переобучения (overfitting), когда $Q(w^*, X^{\ell}) \approx 0$ , но истинный риск $R(w^*)$ оказывается огромным.

Согласно теории Вапника — Червоненкиса, с вероятностью $1 - \eta$ истинный риск ограничен сверху:

$R(w) \le Q(w, X^{\ell}) + \sqrt{\frac{h (\ln(2\ell/h) + 1) - \ln(\eta/4)}{\ell}}$ ,

где $h$ — VC-размерность (мера сложности) семейства моделей. Для состоятельности принципа ERM необходимо, чтобы объем выборки значительно превосходил сложность модели ( $\ell \gg h$ ).

Регуляризация

Для борьбы с переобучением применяется регуляризация. К эмпирическому риску добавляется штрафное слагаемое $\mathcal{R}(w)$ , ограничивающее эффективную сложность модели:

$Q_{\text{reg}}(w, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(a(x_i, w), y_i) + \tau \mathcal{R}(w) \to \min_{w}$ ,

где $\tau$ — коэффициент регуляризации. Наиболее популярны $L_2$ -норма (сокращение весов) и $L_1$ -норма (отбор признаков).

Основные типы функций потерь

Выбор $\mathcal{L}$ зависит от типа прикладной задачи.

В задачах регрессии:

Квадратичная ошибка (MSE): $\mathcal{L}(w, x_i) = (a(x_i, w) - y_i)^2$ .
Абсолютная ошибка (MAE, для робастности к выбросам): $\mathcal{L}(w, x_i) = |a(x_i, w) - y_i|$ .

В задачах бинарной классификации (где $y \in \{-1, +1\}$ ) функция потерь зависит от отступа $M_i(w) = a(x_i, w)y_i$ :

Логистическая функция (в логистической регрессии): $\mathcal{L}(M) = \ln(1 + e^{-M})$ .
Кусочно-линейная функция (в SVM): $\mathcal{L}(M) = \max(0, 1 - M)$ .

Методы оптимизации

В современных задачах с большими данными прямое вычисление градиента эмпирического риска по всей выборке $X^\ell$ вычислительно неэффективно. Применяется метод стохастического градиента (SG). На каждой итерации $t$ градиентный шаг делается на основе потери только на одном случайно выбранном объекте $x_i$ :

$w^{(t+1)} = w^{(t)} - h ( \nabla \mathcal{L}(a(x_i, w^{(t)}), y_i) + \tau \nabla \mathcal{R}(w^{(t)}) )$ .

См. также

Примечания

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%8D%D0%BC%D0%BF%D0%B8%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%80%D0%B8%D1%81%D0%BA%D0%B0»

Категории: Машинное обучение | Математические методы | Теория вычислительного обучения

@@ Строка 1: / Строка 1: @@
-{{TOCright}}
+{{well|'''СТАТЬЯ В РАЗРАБОТКЕ:''' Этот материал сейчас находится в процессе активного редактирования и доработки участником Polina Khadralinova.}}
-'''Эмпирический риск''' (Empirical Risk) — это средняя величина ошибки [[алгоритм]]а на [[обучающая выборка|обучающей выборке]].
+'''Минимизация эмпирического риска''' (англ. ''Empirical Risk Minimization, ERM'') — один из фундаментальных принципов в [[Теория вычислительного обучения|теории машинного обучения]], определяющий метод построения [[Обучение с учителем|алгоритмов обучения с учителем]]. Суть принципа заключается в выборе параметрической модели, которая минимизирует среднюю ошибку (функцию потерь) на заданной [[Выборка|обучающей выборке]].
-Метод '''минимизации эмпирического риска''' (Empirical Risk Minimization, ERM) — это общий подход к решению широкого класса задач [[обучение по прецедентам|обучения по прецедентам]], в первую очередь — задач [[обучение с учителем|обучения с учителем]], включая задачи [[классификация|классификации]] и [[регрессия|регрессии]].
+Данный принцип является строгой математической формализацией [[Эмпирическая индукция|эмпирической индукции]] Фрэнсиса Бэкона: на основе частных опытных данных (прецедентов) строится общее закономерное правило (модель), способное делать предсказания для новых объектов.
-== Определения ==
+== Историческая справка ==
+Идейным предшественником принципа ERM является [[Метод наименьших квадратов|метод наименьших квадратов]], предложенный Карлом Фридрихом Гауссом (1795) и Адриеном Мари Лежандром (1805) для астрономических вычислений. Они первыми предложили искать параметры модели, минимизируя сумму квадратов отклонений на известных точках<ref>Gauss C. F. Theoria motus corporum coelestium in sectionibus conicis solem ambientium. — 1809.</ref>.
-=== Задача обучения по прецедентам ===
+Строгое математическое и статистическое обоснование принципа минимизации эмпирического риска было разработано в 1960–1970-х годах в рамках статистической теории обучения (теории Вапника — Червоненкиса). В. Н. Вапник и А. Я. Червоненкис доказали теоремы о равномерной сходимости частот к вероятностям, определив условия, при которых минимизация ошибки на обучающей выборке гарантирует низкую ошибку на новых данных<ref>Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.</ref>.
-Пусть <tex>X</tex> — множество описаний объектов,
-<tex>Y</tex> — множество допустимых ответов.
-Предполагается, что существует неизвестная ''целевая зависимость'' — отображение
-<tex>y^{*}:\: X\to Y</tex>,
-значения которой известны только на объектах конечной [[обучающая выборка|обучающей выборки]]
-<tex>X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}</tex>.
-''Задача обучения по прецедентам'' состоит в том, чтобы построить алгоритм
+== Ожидаемый и эмпирический риск ==
-<tex>a:\: X\to Y</tex>,
+Пусть дано [[Пространство объектов|пространство объектов]] <tex>X</tex> и пространство ответов <tex>Y</tex>. Предполагается, что существует неизвестная совместная плотность распределения вероятностей <tex>p(x, y)</tex>, из которой порождаются данные.
-который приближал бы неизвестную целевую зависимость как на элементах выборки, так и на всём множестве <tex>X</tex>.
-=== Функция потерь и эмпирический риск ===
+Имеется параметрическое семейство моделей:
-Вводится ''[[функция потерь]]''
+:<tex>A = \{ a(x, w) \mid w \in W \}</tex>,
-<tex>{\mathcal L}(y,y')</tex>,
+где <tex>W \subseteq \mathbb{R}^N</tex> — пространство параметров (весов).
-характеризующая величину отклонения ответа
-<tex>y=a(x)</tex>
-от правильного ответа
-<tex>y'=y^{*}(x)</tex>
-на произвольном объекте <tex>x\in X</tex>.
-Вводится ''[[модель алгоритмов]]'' <tex>A= \{a:\: X\to Y\}</tex>,
+Качество предсказания оценивается с помощью '''функции потерь''' (loss function) <tex>\mathcal{L}(a(x, w), y)</tex>.
-в&nbsp;рамках которой будет вестись поиск отображения,
-приближающего неизвестную целевую зависимость.
-''Эмпирический риск'' — это функционал качества, характеризующий
+'''Истинный (ожидаемый) риск''' <tex>R(w)</tex> — это математическое ожидание функции потерь по всему распределению <tex>p(x, y)</tex>:
-среднюю ошибку алгоритма <tex>a</tex> на выборке <tex>X^m</tex>:
+:<tex>R(w) = \mathbb{E}_{x,y \sim p(x, y)} [\mathcal{L}(a(x, w), y)]</tex>.
-::<tex>Q(a,X^m) = \frac{1}{m} \sum_{i=1}^m {\mathcal L}(a(x_i),y^{*}(x_i)).</tex>
+Идеальная цель машинного обучения — найти параметры <tex>w</tex>, минимизирующие истинный риск. Однако на практике распределение <tex>p(x, y)</tex> неизвестно.
-''Метод минимизация эмпирического риска'' заключается в том, чтобы
+Вместо этого доступна конечная обучающая выборка:
-в&nbsp;заданной ''модели алгоритмов''&nbsp;<tex>A</tex>
+:<tex>X^{\ell} = \{ (x_1, y_1), \dots, (x_{\ell}, y_{\ell}) \}</tex>.
-найти алгоритм, доставляющий минимальное значение функционалу эмпирического риска:
-::<tex>a = \mathrm{arg}\min_{a\in A} Q(a,X^m).</tex>
-=== Разновидности функций потерь ===
+В соответствии с [[Закон больших чисел|законом больших чисел]], истинный риск заменяется его выборочной оценкой — '''эмпирическим риском''':
-'''В задачах [[Задача классификации|классификации]]''' наиболее естественным выбором является ''пороговая функция потерь''
+:<tex>Q(w, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(a(x_i, w), y_i)</tex>.
-::<tex>{\mathcal L}(y,y') = [y'\neq y].</tex>
-Когда функция потерь разрывна,
-минимизация эмпирического риска оказывается сложной задачей комбинаторной оптимизации.
-Во&nbsp;многих практически важных случаях эта сводится к поиску [[Максимальная совместная подсистема|максимальной совместной подсистемы]] в системе неравенств (число неравенств совпадает с число объектов обучения&nbsp;<tex>m</tex>) и является [[NP-полная задача|''NP''-полной]].
-Наряду с пороговыми фукциями потерь используются всевозможные их ''непрерывные аппроксимации'',
+Принцип ERM утверждает, что оптимальные параметры модели <tex>w^*</tex> должны доставлять минимум функционалу эмпирического риска:
-что позволяет применять достаточно эффективные классические методы непрерывной оптимизации,
+:<tex>w^* = \arg \min_{w \in W} Q(w, X^{\ell})</tex>.
-в&nbsp;том числе градиентные методы.
-Более того, оказывается, что использование некоторых аппроксимаций
-способно улучшать [[обобщающая способность|обобщающую способность]] алгоритма классификации.
-Более подробно непрерывные аппроксимации рассматриваются в статье «[[Линейный классификатор]]».
-'''В задачах [[Задача регрессии|регрессии]]''' наиболее типичным выбором является ''квадратичная функция потерь''
+== Условия состоятельности и переобучение ==
-::<tex>{\mathcal L}(y,y') = (y'-y)^2.</tex>
+Главная проблема принципа ERM заключается в том, что при высокой сложности семейства моделей <tex>A</tex> (например, в глубоких нейронных сетях) и малом объёме выборки <tex>\ell</tex>, минимум эмпирического риска не гарантирует минимума истинного риска. Возникает эффект '''[[Переобучение|переобучения]]''' (overfitting), когда <tex>Q(w^*, X^{\ell}) \approx 0</tex>, но истинный риск <tex>R(w^*)</tex> оказывается огромным.
-== Достоинства и недостатки метода ==
+Согласно теории Вапника — Червоненкиса, с вероятностью <tex>1 - \eta</tex> истинный риск ограничен сверху:
-Основное достоинство заключается в том, что это конструктивный и универсальный подход,
+:<tex>R(w) \le Q(w, X^{\ell}) + \sqrt{\frac{h (\ln(2\ell/h) + 1) - \ln(\eta/4)}{\ell}}</tex>,
-позволяющий сводить задачу обучения к задачам численной оптимизации.
+где <tex>h</tex> — [[Емкость (машинное обучение)|VC-размерность]] (мера сложности) семейства моделей. Для состоятельности принципа ERM необходимо, чтобы объем выборки значительно превосходил сложность модели (<tex>\ell \gg h</tex>).
-Основной недостаток — явление ''[[переобучение|переобучения]]'', которое возникает практически всегда при использовании метода минимизации эмпирического риска.
+=== Регуляризация ===
-* Ограничение сложности модели
+Для борьбы с переобучением применяется '''[[Регуляризация|регуляризация]]'''. К эмпирическому риску добавляется штрафное слагаемое <tex>\mathcal{R}(w)</tex>, ограничивающее эффективную сложность модели:
-** [[Метод структурной минимизации риска]]
+:<tex>Q_{\text{reg}}(w, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} \mathcal{L}(a(x_i, w), y_i) + \tau \mathcal{R}(w) \to \min_{w}</tex>,
-** [[Отбор признаков]]
+где <tex>\tau</tex> — коэффициент регуляризации. Наиболее популярны <tex>L_2</tex>-норма (сокращение весов) и <tex>L_1</tex>-норма (отбор признаков).
-* Наложение дополнительных ограничений на параметры модели
-** [[Регуляризация]]
-** [[Байесовская регуляризация]]
-== Разновидности моделей алгоритмов ==
+== Основные типы функций потерь ==
-* Линейные модели классификации
+Выбор <tex>\mathcal{L}</tex> зависит от типа прикладной задачи.
-* Линейные модели регрессии
-* Нелинейные модели классификации
-* Нелинейные модели регрессии
-== Литература ==
+В задачах '''[[Регрессионный анализ|регрессии]]''':
-# {{П:Вапник 74}}
+* Квадратичная ошибка (MSE): <tex>\mathcal{L}(w, x_i) = (a(x_i, w) - y_i)^2</tex>.
-# {{П:Вапник 79}}
+* Абсолютная ошибка (MAE, для [[Робастное обучение|робастности]] к выбросам): <tex>\mathcal{L}(w, x_i) = |a(x_i, w) - y_i|</tex>.
-# {{П:Hastie 2001 The Elements of Statistical Learning}}
+В задачах '''[[Классификация|бинарной классификации]]''' (где <tex>y \in \{-1, +1\}</tex>) функция потерь зависит от отступа <tex>M_i(w) = a(x_i, w)y_i</tex>:
+* Логистическая функция (в [[Логистическая регрессия|логистической регрессии]]): <tex>\mathcal{L}(M) = \ln(1 + e^{-M})</tex>.
+* Кусочно-линейная функция (в [[Метод опорных векторов|SVM]]): <tex>\mathcal{L}(M) = \max(0, 1 - M)</tex>.
+== Методы оптимизации ==
+В современных задачах с большими данными прямое вычисление градиента эмпирического риска по всей выборке <tex>X^\ell</tex> вычислительно неэффективно. Применяется метод '''[[Стохастический градиентный спуск|стохастического градиента]]''' (SG). На каждой итерации <tex>t</tex> градиентный шаг делается на основе потери только на одном случайно выбранном объекте <tex>x_i</tex>:
+:<tex>w^{(t+1)} = w^{(t)} - h ( \nabla \mathcal{L}(a(x_i, w^{(t)}), y_i) + \tau \nabla \mathcal{R}(w^{(t)}) )</tex>.
 == См. также ==
-* [[Переобучение]]
-* [[Теория вычислительного обучения]]
-* [[Восстановление зависимостей по эмпирическим данным]]
 * [[Теория Вапника-Червоненкиса]]
-* [[Линейный классификатор]]
+* [[Переобучение]]
+* [[Регуляризация (машинное обучение)]]
-== Ссылки ==
+== Примечания ==
+<references/>
-{{stub}}
+[[Категория:Машинное обучение]]
+[[Категория:Математические методы]]
 [[Категория:Теория вычислительного обучения]]