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

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

Мініміза́ція емпіри́чного ри́зику (МЕР, англ. 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$. Тоді ризик, пов'язаний із гіпотезою $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}).$

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

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

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

Властивості

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

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

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

Література

• Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4. (англ.)