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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Основания[править | править код]

Рассмотрим следующую ситуацию, которая является основной установкой многих задач обучения с учителем. Мы имеем два пространства объектов и и хотели бы обучить функцию (часто называемую гипотезой), которая сопоставляет объект объекту . Чтобы это сделать, мы имеем в распоряжении тренировочный набор из экземпляров , где является входом, а является соответствующим ответом, который мы хотим получить от .

Чтобы изложить более формально, предположим, что существует совместное распределение над и , и что тренировочный набор состоит из экземпляров , выбранных из независимых случайно распределённых величин из . Заметим, что предположение совместного распределения позволяет моделировать неопределённость в предсказании (например, из-за шума в данных), поскольку не является детерминированной функцией от , а скорее случайной величиной с условным распределением для фиксированного .

Предположим также, что нам дана неотрицательная вещественнозначная функция потерь , которая измеряет, насколько отличается предсказание гипотезы от истинного выхода Риск[en], ассоциированный с гипотезой , определяется тогда как математическое ожидание функции потерь:

Часто в качестве функции потерь в теории используется 0-1 функция потерь: , где означает индикатор.

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

Минимизация эмпирического риска[править | править код]

В общем случае риск не может быть вычислен, поскольку распределение неизвестно для обучающего алгоритма (эта ситуация называется агностическим обучением). Однако мы можем вычислить приближение, называемое эмпирическим риском, путём усреднения функции потерь на тренировочном множестве:

Принцип минимизации эмпирического риска (МЭР) [1] утверждает, что алгоритм обучения должен выбирать гипотезу , которая минимизирует риск:

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

Свойства[править | править код]

Вычислительная сложность[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]

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