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

Шаблон:Машинне навчання Мініміза́ція емпіри́чного ри́зику (МЕР, Шаблон:Lang-en) — це принцип у теорії статистичного навчання, який визначає сімейство алгоритмів навчання, і застосовується для отримування теоретичних меж продуктивності алгоритмів навчання.

Передумови

Розгляньмо наступну ситуацію, яка є загальною постановкою для багатьох задач керованого навчання. Ми маємо два простори об'єктів, $X$ та $Y$, і хотіли би навчитися функції $h:X\to Y$ (яку часто називають гіпотезою, Шаблон:Lang-en), яка видає об'єкт $y\in Y$ для заданого $x\in X$. Для здійснення цього ми маємо у своєму розпорядження тренувальний набір (Шаблон:Lang-en) із невеликої кількості зразків $(x_1,y_1),\dots ,(x_m,y_m)$, де $x_i\in X$ є входом, а $y_i\in Y$ є відповідним відгуком, який ми хотіли би отримувати від $h(x_i)$.

Висловлюючись формальніше, ми припускаємо, що існує спільний розподіл імовірності $P(x,y)$ над $X$ та $Y$, і що тренувальний набір складається з $m$ зразків $(x_1,y_1),\dots ,(x_m,y_m)$, взятих н. о. р. із $P(x,y)$. Зауважте, що припущення про спільний розподіл імовірності дозволяє нам моделювати невизначеність у передбаченнях (наприклад, від шуму в даних), оскільки $y$ є не детермінованою функцією $x$, а радше випадковою змінною з умовним розподілом $P(y|x)$ для зафіксованого $x$.

Ми також припускаємо, що нам було надано невід'ємну дійснозначну функцію втрат $L(\hat{y},y)$, яка вимірює, наскільки передбачення гіпотези $\hat{y}$ відрізняється від справжнього виходу $y$. Тоді Шаблон:Нп, пов'язаний із гіпотезою $h(x)$, визначається як математичне сподівання функції втрат:

$R(h)=𝐄[L(h(x),y)]=\int L(h(x),y)dP(x,y).$

В теорії зазвичай використовується функція втрат 0-1: $L(\hat{y},y)=I(\hat{y}\ne y)$, де $I(\dots )$ є індикаторним позначенням.

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

$h^{*}=\arg \underset{h\in \mathscr{H}}{\min }R(h).$

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

В загальному випадку ризик $R(h)$ не може бути обчислено, оскільки розподіл $P(x,y)$ не є відомим алгоритмові навчання (цю ситуацію називають Шаблон:Нпні). Проте ми можемо обчислювати наближення, яке називається емпіричним ризиком (Шаблон:Lang-en), шляхом усереднення функції втрат на тренувальному наборі:

$R_{\text{emp}}(h)=\frac{1}{m}\sum _{i=1}^{m}L(h(x_i),y_i).$

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

$\hat{h}=\arg \underset{h\in \mathscr{H}}{\min }{R}_{\text{emp}}(h).$

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

Властивості

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

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

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

Література

• Шаблон:Cite book Шаблон:Ref-en