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

Минимизация эмпирического риска (ERM) - принцип теория статистического обучения который определяет семью алгоритмы обучения и используется для теоретических оценок их производительности. Основная идея заключается в том, что мы не можем точно знать, насколько хорошо алгоритм будет работать на практике (истинный «риск»), потому что мы не знаем истинного распределения данных, с которыми будет работать алгоритм, но вместо этого мы можем измерить его производительность на известный набор обучающих данных («эмпирический» риск).

Фон

Рассмотрим следующую ситуацию, которая является общей для многих контролируемое обучение проблемы. У нас есть два пространства объектов ${\displaystyle X}$ и ${\displaystyle Y}$ и хотел бы изучить функцию ${\displaystyle \ h:X\to Y}$ (часто называют гипотеза) который выводит объект ${\displaystyle y\in Y}$, данный ${\displaystyle x\in X}$. Для этого в нашем распоряжении Обучающий набор из ${\displaystyle n}$ Примеры ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ куда ${\displaystyle x_{i}\in X}$ это вход и ${\displaystyle y_{i}\in Y}$ это соответствующий ответ, который мы хотим получить от ${\displaystyle \ h(x_{i})}$.

Выражаясь более формально, мы предполагаем, что существует совместное распределение вероятностей ${\displaystyle P(x,y)}$ над ${\displaystyle X}$ и ${\displaystyle Y}$, и что обучающая выборка состоит из ${\displaystyle n}$ экземпляры ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ нарисованный i.i.d. из ${\displaystyle P(x,y)}$. Обратите внимание, что предположение о совместном распределении вероятностей позволяет нам моделировать неопределенность в прогнозах (например, из-за шума в данных), потому что ${\displaystyle y}$ не является детерминированной функцией ${\displaystyle x}$, а скорее случайная переменная с условное распределение ${\displaystyle P(y|x)}$ для фиксированного ${\displaystyle x}$.

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

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

В теории обычно используется функция потерь: 0-1 функция потерь: ${\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{ If }}\quad {\hat {y}}\neq y\\0&{\mbox{ If }}\quad {\hat {y}}=y\end{cases}}}$.

Конечная цель алгоритма обучения - найти гипотезу ${\displaystyle h^{*}}$ среди фиксированного класса функций ${\displaystyle {\mathcal {H}}}$ для которого риск ${\displaystyle R(h)}$ минимально:

${\displaystyle h^{*}=\arg \min _{h\in {\mathcal {H}}}R(h).}$

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

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

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

Принцип минимизации эмпирического риска^[1] утверждает, что алгоритм обучения должен выбрать гипотезу ${\displaystyle {\hat {h}}}$ что минимизирует эмпирический риск:

${\displaystyle {\hat {h}}=\arg \min _{h\in {\mathcal {H}}}R_{\text{emp}}(h).}$

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

Характеристики

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

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

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

Смотрите также

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

Рекомендации

1. В. Вапник (1992). [http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf Принципы минимизации рисковдля теории обучения.]
2. В. Фельдман, В. Гурусвами, П. Рагхавендра и Йи Ву (2009). Агностическое изучение мономов полупространствами сложно. (См. Статью и ссылки в ней)

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

• Вапник, В. (2000). Природа статистической теории обучения. Информатика и статистика. Springer-Verlag. ISBN  978-0-387-98780-4.