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

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

Предыстория [ править ]

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

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

Также предполагается, что существует неотрицательная действительная функция потерь. $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^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,{R(h)}.

Для задач классификации классификатор Байеса определяется как классификатор, минимизирующий риск, определенный с помощью функции потерь 0–1.

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

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

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

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

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

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

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

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

Для простоты, рассматривая случай задач бинарной классификации, можно ограничить вероятность выбранного классификатора: $\phi _{n}$ быть намного хуже, чем лучший из возможных классификаторов $\phi ^{*}$ . Учитывайте риск $L$ определенный в классе гипотез ${\mathcal {C}}$ с функцией роста ${\mathcal {S}}({\mathcal {C}},n)$ учитывая набор данных размером $n$ . Тогда для каждого $\epsilon >0$ : ^[3]

\mathbb {P} \left(L(\phi _{n})-L(\phi ^{*})\right)\leq {\mathcal {8}}S({\mathcal {C}},n)\exp\{-n\epsilon ^{2}/32\}

Аналогичные результаты справедливы и для задач регрессии. ^[2] Эти результаты часто основаны на единых законах больших чисел , которые контролируют отклонение эмпирического риска от истинного риска равномерно по всему классу гипотез. ^[3]

Результаты невозможности [ править ]

Также возможно показать нижние границы производительности алгоритма, если не делать никаких предположений о распределении. ^[4] Иногда это называют теоремой отсутствия бесплатных обедов . Несмотря на то, что конкретный алгоритм обучения может обеспечить асимптотически оптимальную производительность для любого распределения, производительность на конечной выборке всегда низкая, по крайней мере, для одного распределения данных. Это означает, что ни один классификатор не может указать ошибку для данного размера выборки для всех распределений. ^[3]

В частности, пусть $\epsilon >0$ и рассмотрим размер выборки $n$ и правило классификации $\phi _{n}$ , существует распределение $(X,Y)$ с риском $L^{*}=0$ (это означает, что идеальное предсказание возможно), такое, что: ^[3]

\mathbb {E} L_{n}\geq 1/2-\epsilon .

Кроме того, можно показать, что скорость сходимости алгоритма обучения низкая для некоторых распределений. В частности, дана последовательность убывающих положительных чисел $a_{i}$ стремясь к нулю, можно найти такое распределение, что:

\mathbb {E} L_{n}\geq a_{i}

для всех $n$ . Этот результат показывает, что универсально хороших правил классификации не существует в том смысле, что правило должно быть низкого качества хотя бы для одного распределения. ^[3]

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

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

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

В случае овыпуклости лемма Чжана учитывает избыточный риск исходной задачи, используя избыточный риск овыпуклой задачи. ^[6] Минимизация последнего с помощью выпуклой оптимизации также позволяет контролировать первое.

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

Наклонная минимизация эмпирического риска — это метод машинного обучения, используемый для изменения стандартных функций потерь, таких как квадратичная ошибка, путем введения параметра наклона. Этот параметр динамически регулирует вес точек данных во время обучения, позволяя алгоритму сосредоточиться на определенных регионах или характеристиках распределения данных. Наклонная минимизация эмпирического риска особенно полезна в сценариях с несбалансированными данными или когда необходимо подчеркнуть ошибки в определенных частях пространства прогнозирования.

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

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

^ В. Вапник (1992). Принципы минимизации рисков для теории обучения.
↑ Перейти обратно: Перейти обратно: ^а ^б Дьёрфи, Ласло; Колер, Майкл; Кшизак, Адам; Уок, Харро (01 декабря 2010 г.). Теория непараметрической регрессии без распределения (перепечатка оригинального 1-го изд. в мягкой обложке). Нью-Йорк: Спрингер. ISBN 978-1-4419-2998-3 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Деврой Л., Дьерфи Л. и Лугоши Г. Вероятностная теория распознавания образов. Дискретная прикладная математика 73, 192–194 (1997)
^ Деврой, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996). «Вероятностная теория распознавания образов» . Стохастическое моделирование и прикладная теория вероятности . 31 . дои : 10.1007/978-1-4612-0711-5 . ISBN 978-1-4612-6877-2 . ISSN 0172-4568 .
^ В. Фельдман, В. Гурусвами, П. Рагхавендра и И Ву (2009). Агностическое изучение мономов с помощью полупространств сложно. (См. статью и ссылки в ней)
^ «Математика машинного обучения. Лекция 9. Конспект | Математика машинного обучения | Математика» . MIT OpenCourseWare . Проверено 28 октября 2023 г.

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

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

[1] В. Вапник (1992). Принципы минимизации рисков для теории обучения.

[lg-2] Перейти обратно: Перейти обратно: ^а ^б Дьёрфи, Ласло; Колер, Майкл; Кшизак, Адам; Уок, Харро (01 декабря 2010 г.). Теория непараметрической регрессии без распределения (перепечатка оригинального 1-го изд. в мягкой обложке). Нью-Йорк: Спрингер. ISBN 978-1-4419-2998-3 .

[patt-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Деврой Л., Дьерфи Л. и Лугоши Г. Вероятностная теория распознавания образов. Дискретная прикладная математика 73, 192–194 (1997)

[4] Деврой, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996). «Вероятностная теория распознавания образов» . Стохастическое моделирование и прикладная теория вероятности . 31 . дои : 10.1007/978-1-4612-0711-5 . ISBN 978-1-4612-6877-2 . ISSN 0172-4568 .

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

[6] «Математика машинного обучения. Лекция 9. Конспект | Математика машинного обучения | Математика» . MIT OpenCourseWare . Проверено 28 октября 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]