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

Минимизация эмпирического риска (МЭР, англ. Empirical risk minimization, ERM) — это принцип статистической теории обучения, который определяет семейство обучающихся алгоритмов и который задаёт теоретические границы результативности.

Основания

Рассмотрим следующую ситуацию, которая является основной установкой многих задач контролируемого обучения. Мы имеем два пространства объектов [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] и хотели бы натренировать функцию [math]\displaystyle{ \ h: X \to Y }[/math] (часто именуемую гипотезой), которая ставит объект [math]\displaystyle{ y \in Y }[/math] в соответствие объекту [math]\displaystyle{ x \in X }[/math]. Для этого мы имеем в распоряжении тренировочный набор из [math]\displaystyle{ n }[/math] экземпляров [math]\displaystyle{ \ (x_1, y_1), \ldots, (x_n, y_n) }[/math], где [math]\displaystyle{ x_i \in X }[/math] является входом, а [math]\displaystyle{ y_i \in Y }[/math] является соответствующим ответом, который мы хотим получить от [math]\displaystyle{ \ h(x_i) }[/math].

Выражаясь более формально, предположим, что существует совместное распределение [math]\displaystyle{ P(x, y) }[/math] над [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math], и что тренировочный набор состоит из [math]\displaystyle{ n }[/math] экземпляров [math]\displaystyle{ \ (x_1, y_1), \ldots, (x_n, y_n) }[/math], выбранных из независимых случайно распределённых величин из [math]\displaystyle{ P(x, y) }[/math]. Заметим, что допущение о совместном распределении позволяет симулировать неопределённость в предсказании (например, из-за шума в данных), поскольку [math]\displaystyle{ y }[/math] не является детерминированной функцией от [math]\displaystyle{ x }[/math], а скорее случайной величиной с условным распределением [math]\displaystyle{ P(y | x) }[/math] для фиксированного [math]\displaystyle{ x }[/math].

Предположим также, что нам дана неотрицательная вещественнозначная функция потери [math]\displaystyle{ L(\hat{y}, y) }[/math], которая измеряет то, насколько отличается предсказание [math]\displaystyle{ \hat{y} }[/math] гипотезы от истинного выхода [math]\displaystyle{ y. }[/math] Риск, ассоциированный с гипотезой [math]\displaystyle{ h(x) }[/math], определяется тогда как математическое ожидание функции потери:

[math]\displaystyle{ R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y)\,dP(x, y). }[/math]

Часто в качестве функции потери в теории используется 0-1 функция потери: [math]\displaystyle{ L(\hat{y}, y) = I(\hat{y} \ne y) }[/math], где [math]\displaystyle{ I(\dots) }[/math] означает индикатор.

Высшей целью обучающегося алгоритма является отыскание гипотезы [math]\displaystyle{ h^* }[/math] в фиксированном классе функций [math]\displaystyle{ \mathcal{H} }[/math], для которых риск [math]\displaystyle{ R(h) }[/math] минимален:

[math]\displaystyle{ h^* = \arg \min_{h \in \mathcal{H}} R(h). }[/math]

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

В общем случае риск [math]\displaystyle{ R(h) }[/math] не может быть вычислен, поскольку распределение [math]\displaystyle{ P(x, y) }[/math] неизвестно для обучающего алгоритма (эта ситуация называется агностическим обучением). Однако мы можем вычислить аппроксимацию, именуемую эмпирическим риском, путём усреднения функции потери на тренировочном наборе:

[math]\displaystyle{ \! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i). }[/math]

Принцип минимизации эмпирического риска (МЭР) утверждает, что обучающийся алгоритм должен выбирать гипотезу [math]\displaystyle{ \hat{h} }[/math], которая минимизирует риск:

[math]\displaystyle{ \hat{h} = \arg \min_{h \in \mathcal{H}} R_{\text{emp}}(h). }[/math]

Тогда обучающийся алгоритм, определённый принципом МЭР состоит в решении вышеуказанной задачи оптимизации.

Свойства

Вычислительная сложность

Известно, что минимизация эмпирического риска для задачи классификации с 0-1 функцией потери является NP-трудной даже для такого относительно простого класса функций задач, как линейные классификаторы. Хотя она может быть эффективно решена, когда минимальный эмпирический риск равен нулю, то есть данные линейно сепарабельны.

На практике автоматически обучающиеся алгоритмы справляются с этим либо путём выпуклой аппроксимации до 0-1 функции потери (подобно кусочно-линейной функции потерь для машин опорных элементов), которую проще оптимизировать, либо выдвижением допущения о распределении [math]\displaystyle{ P(x, y) }[/math] (а тогда обучающийся алгоритм перестаёт быть агностическим).

См. также

• Метод максимального правдоподобия

Литература для дальнейшего чтения

• Vapnik V. The Nature of Statistical Learning Theory. — 2000. — (Information Science and Statistics). — ISBN 978-0-387-98780-4.