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

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

Фон [ править ]

Рассмотрим следующую ситуацию, которая является общей постановкой многих задач контролируемого обучения . У нас есть два пространства объектов и и хотели бы узнать функцию (часто называемая гипотеза ) , который выводит объект , заданное . Чтобы сделать это, мы имеем в нашем распоряжении обучающего набора из примеров , где есть вход и есть соответствующий ответ , который мы хотим получить от . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle \ h: от X \ до 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 \ ч (х_ {я})}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Февраль 2010 г. )

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

[1] В. Вапник (1992). [ http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf Принципы минимизации рисков для теории обучения. ]

[2] В. Фельдман, В. Гурусвами, П. Рагхавендра и Йи Ву (2009). Агностическое изучение мономов полупространствами сложно. (См. Статью и ссылки в ней)