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

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

Передумови

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

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

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

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

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

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

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

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

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

Властивості

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

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

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

Примітки

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

Література

  • Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4. (англ.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.