Мінімізація емпіричного ризику

Мініміза́ція емпіри́чного ри́зику (МЕР, англ. empirical risk minimization, ERM) — це принцип у теорії статистичного навчання, який визначає сімейство алгоритмів навчання, і застосовується для отримування теоретичних меж продуктивності алгоритмів навчання.

Передумови

Розгляньмо наступну ситуацію, яка є загальною постановкою для багатьох задач керованого навчання. Ми маємо два простори об'єктів, ${\displaystyle X}$ та ${\displaystyle Y}$, і хотіли би навчитися функції ${\displaystyle \ h:X\to Y}$ (яку часто називають гіпотезою, англ. hypothesis), яка видає об'єкт ${\displaystyle y\in Y}$ для заданого ${\displaystyle x\in X}$. Для здійснення цього ми маємо у своєму розпорядження тренувальний набір (англ. training set) із невеликої кількості зразків ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$, де ${\displaystyle x_{i}\in X}$ є входом, а ${\displaystyle y_{i}\in Y}$ є відповідним відгуком, який ми хотіли би отримувати від ${\displaystyle \ h(x_{i})}$.

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

Ми також припускаємо, що нам було надано невід'ємну дійснозначну функцію втрат ${\displaystyle L({\hat {y}},y)}$, яка вимірює, наскільки передбачення гіпотези ${\displaystyle {\hat {y}}}$ відрізняється від справжнього виходу ${\displaystyle y}$. Тоді ^[en], пов'язаний із гіпотезою ${\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)=I({\hat {y}}\neq y)}$, де ${\displaystyle I(\dots )}$ є індикаторним позначенням.

Кінцевою метою алгоритму навчання є знайти гіпотезу ${\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)}$ не є відомим алгоритмові навчання (цю ситуацію називають ). Проте ми можемо обчислювати наближення, яке називається емпіричним ризиком (англ. empirical risk), шляхом усереднення функції втрат на тренувальному наборі:

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

Принцип емпіричної мінімізації ризику стверджує, що алгоритм навчання повинен вибрати таку гіпотезу ${\displaystyle {\hat {h}}}$, яка мінімізує емпіричний ризик:

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

Таким чином, алгоритм навчання, визначений принципом МЕР, полягає у розв'язання наведеної вище задачі оптимізації.

Властивості

Обчислювальна складність

Відомо, що мінімізація емпіричного ризику для задачі класифікації з функцією втрат 0-1 є NP-складною задачею, навіть для таких відносно простих класів функцій, як лінійні класифікатори. Проте вона може розв'язуватися ефективно, коли мінімальний емпіричний ризик є нульовим, тобто дані є лінійно роздільними.

На практиці алгоритми машинного навчання впоруються з цим, або застосовуючи опуклу оптимізацію до функції втрат 0-1 (як у заві́сних втратах для ОВМ), що простіше оптимізувати, або формулюючи припущення про розподіл ${\displaystyle P(x,y)}$ (і відтак перестаючи бути алгоритмами агностичного навчання, до яких застосовується наведений вище результат).

Примітки

1. V. Vapnik (1992). Principles of Risk Minimization for Learning Theory. [ 4 серпня 2016 у Wayback Machine.]
2. V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. [ 22 лютого 2012 у Wayback Machine.] (Див. саму працю та посилання в ній) (англ.)

Література

• Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN . (англ.)