Русская Википедия:Минимизация эмпирического риска
Минимизация эмпирического риска (МЭР, Шаблон:Lang-en, ERM) — это принцип статистической теории обучения, который определяет семейство обучающихся алгоритмов и который задаёт теоретические границы результативности.
Основания
Рассмотрим следующую ситуацию, которая является основной установкой многих задач контролируемого обучения. Мы имеем два пространства объектов <math>X</math> и <math>Y</math> и хотели бы натренировать функцию <math>\ h: X \to Y</math> (часто именуемую гипотезой), которая ставит объект <math>y \in Y</math> в соответствие объекту <math>x \in X</math>. Для этого мы имеем в распоряжении тренировочный набор из <math>n</math> экземпляров <math>\ (x_1, y_1), \ldots, (x_n, y_n)</math>, где <math>x_i \in X</math> является входом, а <math>y_i \in Y</math> является соответствующим ответом, который мы хотим получить от <math>\ h(x_i)</math>.
Выражаясь более формально, предположим, что существует совместное распределение <math>P(x, y)</math> над <math>X</math> и <math>Y</math>, и что тренировочный набор состоит из <math>n</math> экземпляров <math>\ (x_1, y_1), \ldots, (x_n, y_n)</math>, выбранных из независимых случайно распределённых величин из <math>P(x, y)</math>. Заметим, что допущение о совместном распределении позволяет симулировать неопределённость в предсказании (например, из-за шума в данных), поскольку <math>y</math> не является детерминированной функцией от <math>x</math>, а скорее случайной величиной с условным распределением <math>P(y | x)</math> для фиксированного <math>x</math>.
Предположим также, что нам дана неотрицательная вещественнозначная функция потери <math>L(\hat{y}, y)</math>, которая измеряет то, насколько отличается предсказание <math>\hat{y}</math> гипотезы от истинного выхода <math>y.</math> Шаблон:Не переведено 5, ассоциированный с гипотезой <math>h(x)</math>, определяется тогда как математическое ожидание функции потери:
- <math>R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y)\,dP(x, y).</math>
Часто в качестве функции потери в теории используется 0-1 функция потери: <math>L(\hat{y}, y) = I(\hat{y} \ne y)</math>, где <math>I(\dots)</math> означает индикатор.
Высшей целью обучающегося алгоритма является отыскание гипотезы <math> h^*</math> в фиксированном классе функций <math>\mathcal{H}</math>, для которых риск <math>R(h)</math> минимален:
- <math>h^* = \arg \min_{h \in \mathcal{H}} R(h).</math>
Минимизация эмпирического риска
В общем случае риск <math>R(h)</math> не может быть вычислен, поскольку распределение <math>P(x, y)</math> неизвестно для обучающего алгоритма (эта ситуация называется агностическим обучением). Однако мы можем вычислить аппроксимацию, именуемую эмпирическим риском, путём усреднения функции потери на тренировочном наборе:
- <math>\! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i).</math>
Принцип минимизации эмпирического риска (МЭР) Шаблон:Sfn утверждает, что обучающийся алгоритм должен выбирать гипотезу <math>\hat{h}</math>, которая минимизирует риск:
- <math>\hat{h} = \arg \min_{h \in \mathcal{H}} R_{\text{emp}}(h).</math>
Тогда обучающийся алгоритм, определённый принципом МЭР состоит в решении вышеуказанной задачи оптимизации.
Свойства
Вычислительная сложность
Известно, что минимизация эмпирического риска для задачи классификации с 0-1 функцией потери является NP-трудной даже для такого относительно простого класса функций задач, как линейные классификаторыШаблон:Sfn. Хотя она может быть эффективно решена, когда минимальный эмпирический риск равен нулю, то есть данные линейно сепарабельны.
На практике автоматически обучающиеся алгоритмы справляются с этим либо путём выпуклой аппроксимации до 0-1 функции потери (подобно Шаблон:Не переведено 5 для машин опорных элементов), которую проще оптимизировать, либо выдвижением допущения о распределении <math>P(x, y)</math> (а тогда обучающийся алгоритм перестаёт быть агностическим).
См. также
Примечания
Литература
Литература для дальнейшего чтения
