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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Передумови[ред. | ред. код]

Розгляньмо наступну ситуацію, яка є загальною постановкою для багатьох задач керованого навчання. Ми маємо два простори об'єктів, та , і хотіли би навчитися функції (яку часто називають гіпотезою, англ. hypothesis), яка видає об'єкт для заданого . Для здійснення цього ми маємо у своєму розпорядження тренувальний набір (англ. training set) із невеликої кількості зразків , де є входом, а є відповідним відгуком, який ми хотіли би отримувати від .

Висловлюючись формальніше, ми припускаємо, що існує спільний розподіл імовірності над та , і що тренувальний набір складається з зразків , взятих н. о. р. із . Зауважте, що припущення про спільний розподіл імовірності дозволяє нам моделювати невизначеність у передбаченнях (наприклад, від шуму в даних), оскільки є не детермінованою функцією , а радше випадковою змінною з умовним розподілом для зафіксованого .

Ми також припускаємо, що нам було надано невід'ємну дійснозначну функцію втрат , яка вимірює, наскільки передбачення гіпотези відрізняється від справжнього виходу . Тоді ризик[en], пов'язаний із гіпотезою , визначається як математичне сподівання функції втрат:

В теорії зазвичай використовується функція втрат 0-1: , де є індикаторним позначенням.

Кінцевою метою алгоритму навчання є знайти гіпотезу серед зафіксованого класу функцій , для якої ризик є мінімальним:

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

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

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

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

Властивості[ред. | ред. код]

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

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

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

Примітки[ред. | ред. код]

  1. V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (Див. саму працю та посилання в ній) (англ.)

Література[ред. | ред. код]