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

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

Передумови ред.

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

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

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

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

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

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

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

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

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

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

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

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

Властивості ред.

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

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

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

Примітки ред.

↑ V. Vapnik (1992). Principles of Risk Minimization for Learning Theory. [Архівовано 4 серпня 2016 у Wayback Machine.]
↑ 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 978-0-387-98780-4. (англ.)

[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.] (Див. саму працю та посилання в ній) (англ.)

[1]

[2]