Мінімізація емпіричного ризику
Емпіричний ризик (Empirical Risk) - це середня величина помилки алгоритму на навчальній вибірці.
Метод мінімізації емпіричного ризику (Empirical Risk Minimization, ERM) - це загальний підхід до вирішення широкого класу задач навчання по прецедентах. в першу чергу - завдань навчання з учителем. включаючи завдання класифікації і регресії.
визначення
Завдання навчання по прецедентах
Нехай - безліч описів об'єктів, - безліч допустимих відповідей. Передбачається, що існує невідома цільова залежність - відображення: \: ">, значення якої відомі тільки на об'єктах кінцевої навчальної вибірки.
Завдання навчання по прецедентах полягає в тому, щоб побудувати алгоритм, який наближав би невідому цільову залежність як на елементах вибірки, так і на всьому безлічі.
Функція втрат і емпіричний ризик
Вводиться функція втрат, що характеризує величину відхилення відповіді від правильної відповіді на довільному об'єкті.
Вводиться модель алгоритмів, в рамках якої буде вестися пошук відображення, що наближає невідому цільову залежність.
Емпіричний ризик - це функціонал якості, що характеризує середню помилку алгоритму на вибірці:
Метод мінімізація емпіричного ризику полягає в тому, щоб в заданій моделі алгоритмів знайти алгоритм, який доставляє мінімальне значення функціоналу емпіричного ризику:
Різновиди функцій втрат
У задачах класифікації найбільш природним вибором є порогова функція втрат
Коли функція втрат розривна, мінімізація емпіричного ризику виявляється складним завданням комбінаторної оптимізації. У багатьох практично важливих випадках ця зводиться до пошуку максимальної спільної підсистеми в системі нерівностей (число нерівностей збігається з число об'єктів навчання) і є NP -повної.
Поряд з граничними фукцией втрат використовуються всілякі їх безперервні апроксимації. що дозволяє застосовувати досить ефективні класичні методи безперервної оптимізації, в тому числі градієнтні методи. Більш того, виявляється, що використання деяких аппроксимаций здатне покращувати узагальнюючу здатність алгоритму класифікації. Більш докладно безперервні апроксимації розглядаються в статті «Лінійний класифікатор».
У завданнях регресії найбільш типовим вибором є квадратична функція втрат
Переваги і недоліки методу
Основна перевага полягає в тому, що це конструктивний і універсальний підхід, що дозволяє зводити задачу навчання до завдань чисельної оптимізації.
Основний недолік - явище перенавчання. яке виникає практично завжди при використанні методу мінімізації емпіричного ризику.
Різновиди моделей алгоритмів
- Лінійні моделі класифікації
- Лінійні моделі регресії
- Нелінійні моделі класифікації
- Нелінійні моделі регресії