Мініміза́ція емпіри́чного ри́зику (МЕР, ) — це принцип у теорії статистичного навчання, який визначає сімейство алгоритмів навчання, і застосовується для отримування теоретичних меж продуктивності алгоритмів навчання.
Передумови
Розгляньмо наступну ситуацію, яка є загальною постановкою для багатьох задач керованого навчання. Ми маємо два простори об'єктів, та , і хотіли би навчитися функції (яку часто називають гіпотезою, ), яка видає об'єкт для заданого . Для здійснення цього ми маємо у своєму розпорядження тренувальний набір () із невеликої кількості зразків , де є входом, а є відповідним відгуком, який ми хотіли би отримувати від .
Висловлюючись формальніше, ми припускаємо, що існує спільний розподіл імовірності над та , і що тренувальний набір складається з зразків , взятих н. о. р. із . Зауважте, що припущення про спільний розподіл імовірності дозволяє нам моделювати невизначеність у передбаченнях (наприклад, від шуму в даних), оскільки є не детермінованою функцією , а радше випадковою змінною з умовним розподілом для зафіксованого .
Ми також припускаємо, що нам було надано невід'ємну дійснозначну функцію втрат , яка вимірює, наскільки передбачення гіпотези відрізняється від справжнього виходу . Тоді , пов'язаний із гіпотезою , визначається як математичне сподівання функції втрат:
В теорії зазвичай використовується функція втрат 0-1: , де є індикаторним позначенням.
Кінцевою метою алгоритму навчання є знайти гіпотезу серед зафіксованого класу функцій , для якої ризик є мінімальним:
Мінімізація емпіричного ризику
В загальному випадку ризик не може бути обчислено, оскільки розподіл не є відомим алгоритмові навчання (цю ситуацію називають ). Проте ми можемо обчислювати наближення, яке називається емпіричним ризиком (), шляхом усереднення функції втрат на тренувальному наборі:
Принцип емпіричної мінімізації ризику стверджуєV. Vapnik (1992). Principles of Risk Minimization for Learning Theory. , що алгоритм навчання повинен вибрати таку гіпотезу , яка мінімізує емпіричний ризик:
Таким чином, алгоритм навчання, визначений принципом МЕР, полягає у розв'язання наведеної вище задачі оптимізації.
Властивості
Обчислювальна складність
Відомо, що мінімізація емпіричного ризику для задачі класифікації з функцією втрат 0-1 є NP-складною задачею, навіть для таких відносно простих класів функцій, як лінійні класифікатори.V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (Див. саму працю та посилання в ній) Проте вона може розв'язуватися ефективно, коли мінімальний емпіричний ризик є нульовим, тобто дані є лінійно роздільними.
На практиці алгоритми машинного навчання впоруються з цим, або застосовуючи опуклу оптимізацію до функції втрат 0-1 (як у заві́сних втратах для ОВМ), що простіше оптимізувати, або формулюючи припущення про розподіл (і відтак перестаючи бути алгоритмами агностичного навчання, до яких застосовується наведений вище результат).
Примітки
Література