Введення
У цій статті я задався метою висвітлити деякі фундаментальні результати теорії машинного навчання таким чином, щоб концепції були зрозумілі читачам, трохи знайомими із завданнями класифікації та регресії. Ідея написати таку статтю все чіткіше проявлялася в моїй свідомості з кожною прочитаною книгою, в якій ідеї навчання машин розпізнаванню розповідалися як би з середини і абсолютно не зрозуміло, на що автори того чи іншого методу спиралися при його розробці. З іншого боку існує ряд книг, присвячених основним концепціям в машинному навчанні, але виклад матеріалу в них може здатися занадто складним для першого прочитання.
Мотивація
Розглянемо таке завдання. У нас є яблука двох класів - смачні і не смачні, 1 і 0. Яблука мають ознаки - колір і розмір. Колір змінюється безперервно від 0 до 1, тобто 0 -повністю зелене яблуко, 1 - повністю червоне. Розмір може змінюватися аналогічно, 0 - яблуко маленьке, 1 - велике. Ми хотіли б розробити алгоритм, який би отримував на вхід колір і розмір, а на виході віддавав клас яблука - смачне воно чи ні. Дуже бажано, щоб число помилок при цьому було чим менше тим краще. При цьому ми володіємо кінцевим списком, в якому вказані історичні дані про колір, розмір і клас яблук. Як би ми могли вирішувати таку задачу?
Логічний підхід
Вирішуючи наше завдання, перший метод, який можливо прийде на думку, може бути такий: давайте вручну складемо правила типу if-else і залежно від значень кольору і розміру будемо присвоювати яблуку певний клас. Тобто. у нас є передумови - це колір і розмір, і є наслідок - смак яблука. Цілком розумно, коли ознак трохи і можна на око оцінити пороги для порівняння. Але може трапиться так, що придумати чіткі умови не вийде, і з даних не очевидно які пороги брати, та й число ознак може збільшуватися в перспективі. А що робити, якщо в нашому списку з історичними даними, ми виявили два яблука з однаковими кольором і розміром, але одне позначено як смачне, а інше ні? Таким чином наш перший метод не настільки гнучкий і масштабований, як нам би хотілося.
Позначення
Введемо наступну нотацію. Будемо позначати -е яблуко як. У свою чергу кожен складається з двох чисел - кольору і розміру. Цей факт ми будемо позначати парою чисел: . Клас кожного яблука ми позначимо як. Список з історичними даними позначимо буквою, довжина цього списку рівна. -ий елемент цього списку є значення ознак яблука і його клас. Тобто. Так само будемо називати вибіркою. Великими літерами і ми позначимо змінні, які можуть приймати значення конкретної ознаки і класу. Віїдемо нове поняття - вирішальне правило є функція, яка приймає на вхід значення кольору і розміру, а на виході повертає мітку класу:
Ймовірний підхід
Розвиваючи ідею логічного методу з передумовами і слідствами, поставимо собі запитання - а яка ймовірність того, що -е яблуко, яке не належить нашій вибірці буде смачне, за умови вимірених значень кольору і розміру? У нотації теорії ймовірностей це питання можна записати так:
У цьому вираженні можна інтерпретувати як посилку, як наслідок, але перехід від посилки до слідства буде підпорядковуватися ймовірнісним законам, а не логічним. Тобто. замість таблиці істинності з булевськими значеннями 0 і 1 для класу, будуть значення ймовірності, які приймають значення від 0 до 1. Застосуймо формулу Байєса і отримаємо такий вираз:
Розгляньмо праву частину цього виразу докладніше. Множник називається апріорною ймовірністю і означає ймовірність зустріти смачне яблуко серед усіх можливих яблук. Апріорна ймовірність зустріти несмачне яблуко є. Ця ймовірність може відображати наше особисте знання про те, як розподілені смачні і несмачні яблука в природі. Наприклад, з нашого минулого досвіду ми знаємо, що 80% всіх яблук - смачні. Або ми можемо оцінити це значення просто порахувавши частку смачних яблук у нашому списку з історичними даними S. Наступний множник - показує, наскільки ймовірно отримати конкретне значення кольору і розміру для яблука класу 1. Цей вираз так само називається функцією правдоподібності і може мати вигляд якогось конкретного розподілу, наприклад, нормального. Знаменник ми використовуємо як нормувальну константу, щоб шукана ймовірність змінювалася в межах від 0 до 1. Нашою кінцевою метою є не пошук ймовірностей, а пошук вирішального правила, яке б відразу давало нам клас. Кінцевий вигляд вирішального правила залежить від того, які значення і параметри нам відомі. Наприклад, ми можемо знати тільки значення апріорної ймовірності, а інші значення оцінити неможливо. Тоді вирішальне правило буде таке - ставити всім яблукам значення того класу, для якого апріорна ймовірність найбільша. Тобто. якщо ми знаємо, що 80% яблук у природі смачні, то кожному яблуку ставимо клас 1. Тоді наша помилка складе 20%. Якщо ж ми до того ж можемо оцінити значення функції правдоподібності $ p (X = x _ m | Y = 1) $, то можемо і знайти значення шуканої ймовірності за формулою Байєса, як написано зверху. Вирішальне правило тут буде таким: поставити мітку того класу, для якого ймовірність максимальна:
Це правило назвемо Байєсовським класифікатором. Оскільки ми маємо справу з імовірностями, то навіть велике значення ймовірності не дає гарантій, що яблуко не належить до класу 0. Оцінимо ймовірність помилки на яблуку наступним чином: якщо вирішальне правило повернуло значення класу рівне 1, то ймовірність помилитися буде і навпаки:
Нас цікавить ймовірність помилки класифікатора не тільки на даному конкретному прикладі, але і взагалі для всіх можливих яблук:
Цей вираз є математичним, очікуємо помилки. Отже, вирішуючи вихідну проблему ми прийшли до байєсівського класифікатора, але які у нього є недоліки? Головна проблема - оцінити з даних умовну ймовірність. У нашому випадку ми представляємо об'єкт парою чисел - колір і розмір, але в більш складних завданнях розмірність ознак може бути в рази вище і для оцінки ймовірності багатовимірної випадкової величини може не вистачити числа спостережень з нашого списку з історичними даними. Далі ми спробуємо узагальнити наше поняття помилки класифікатора, а так само подивимося, чи можна підібрати якийсь інший класифікатор для вирішення проблеми.
Втрати від помилок класифікатора
Припустимо, що у нас вже є якесь вирішальне правило. Тоді воно може зробити два типи помилок - перший, це зарахувати об'єкт до класу 0, у якого реальний клас 1 і навпаки, зарахувати об'єкт до класу 1, у якого реальний клас 0. У деяких завданнях буває важливо розрізняти ці випадки. Наприклад, ми страждаємо більше від того, що яблуко, позначене як смачне, виявилося несмачним і навпаки. Ступінь нашого дискомфорту від обдурених очікувань ми формалізуємо в понятті Більш загально - у нас є функція втрат, яка повертає число для кожної помилки класифікатора. Нехай - реальна мітка класу. Тоді функція втрат повертає величину втрат для реальної мітки класу і значення нашого вирішального правила. Приклад застосування цієї функції - беремо з яблуко з відомим класом, передаємо яблуко на вхід нашому вирішальному правилу, отримуємо оцінку класу від вирішального правила, якщо значення і збіглися, то вважаємо що класифікатор не помилився і втрат немає, якщо значення не збігаються, то величину втрат скаже наша функція
Умовний і байєсівський ризик
Тепер, коли у нас є функція втрат і ми знаємо, скільки ми втрачаємо від неправильної класифікації об'єкта, було б непогано зрозуміти, скільки ми втрачаємо в середньому, на багатьох об'єктах. Якщо ми знаємо величину - ймовірність того, що -е яблуко буде смачне, за умови вимірених значень кольору і розміру, а так само реальне значення класу (наприклад візьмемо яблуко з вибірки S, див. на початку статті), то можемо ввести поняття умовного ризику. Умовний ризик є середня величина втрат на об'єкті для вирішального правила:
У нашому випадку бінарної класифікації коли виходить:
Коли a (x) = 0
Щоб порахувати середні втрати на всіх можливих об'єктах, вводиться поняття байєсовського ризику, який є математичним очікуванням умовного ризику:
Вище ми описували вирішальне правило, яке відносить об'єкт до того класу, який має найбільше значення ймовірності Таке правило доставляє мінімум нашим середнім втратам (байєсовському ризику), тому Байєсовський класифікатор є оптимальним з точки зору введеного нами функціоналу ризику. Це означає, що Байєсовський класифікатор має найменшу можливу помилку класифікації.
Деякі стандартні функції втрат
Однією з найчастіших функцій втрат є симетрична функція, коли втрати від першого і другого типів помилок рівнозначні. Наприклад, функція втрат 1-0 (zero-one loss) визначається так:
Тоді умовний ризик для a (x) = 1 буде просто значенням ймовірності отримати клас 0 на об'єкті:
Подібно до a (x) = 0:
Функція втрат 1-0 приймає значення 1, якщо класифікатор робить помилку на об'єкті і 0 якщо не робить. Тепер зробимо так, щоб значення на помилці дорівнювало не 1, а іншій функції Q, залежної від вирішального правила і реальної мітки класу:
Тоді умовний ризик можна записати так:
Зауваження нотації
Попередній текст був написаний згідно нотації, прийнятої в книзі Дуди і Харта. В оригінальній книзі В.Н. Вапника розглядався такий процес: природа вибирає об'єкт за розподілом $ p (x) $, а потім ставить йому мітку класу згідно з умовним розподілом $ p (y'x) $. Тоді ризик (маточікування втрат) визначається як
Де - функція, якою ми намагаємося апроксимувати невідому залежність, - функція втрат для реального значення і значення нашої функції. Ця нотації більш наочна для того щоб ввести слідче поняття - емпіричний ризик.
Емпіричний ризик
На даному етапі ми вже з'ясували, що логічний метод нам не підходить, тому що він недостатньо гнучкий, а байєсовський класифікатор ми не можемо використовувати, коли ознак багато, а даних для навчання обмежене число і ми не зможемо відновити ймовірність. Так само нам відомо, що байєсовський класифікатор має найменшу можливу помилку класифікації. Якщо вже ми не можемо використовувати байєсовський класифікатор, давайте візьмемо що-небудь по простіше. Давайте зафіксуємо деяке параметричне сімейство функцій H і будемо підбирати класифікатор з цього сімейства.
Приклад: нехай безліч всіх функцій виду
Всі функції цієї безлічі будуть відрізнятися один від одного тільки коефіцієнтами Коли ми вибрали таке сімейство, ми припустили, що в координатах колір-розмір між точками класу 1 і точками класу 0 можна провести пряму лінію з коефіцієнтами таким чином, що точки з різними класами знаходяться по різні сторони від прямої. Відомо, що у прямого такого виду вектор коефіцієнтів є нормаллю до прямої. Тепер робимо так - беремо наше яблуко, міряємо у нього колір і розмір і наносимо точку з отриманими координатами на графік в осях колір-розмір. Далі міряємо кут між цією точкою і вектором $ w $. Зауважуємо, що наша точка може лежати або по одну, або по іншу сторону від прямої. Тоді кут між і точкою буде або гострий, або тупий, а скалярний твір або позитивний, або негативний. Звідси випливає вирішальне правило:
Після того як ми зафіксували клас функцій $ Н $, виникає питання - як вибрати з нього функцію з потрібними коефіцієнтами? Відповідь - давайте виберемо ту функцію, яка доставляє мінімум нашому байєсівському ризику $ R () $. Знову проблема - щоб порахувати значення байєсовського ризику, потрібно знати розподіл $ p (x, y) $, а воно нам не дано, і віднови його не завжди можливо. Інша ідея - мінімізувати ризик не на всіх можливих об'єктах, а тільки на вибірці. Тобто. мінімізувати функцію:
Ця функція і називається емпіричним ризиком. Наступне питання - чому ми вирішили, що мінімізуючи емпіричний ризик, ми при цьому так само мінімізуємо байєсовський ризик? Нагадаю, що наше завдання практичне - допустити якомога менше помилок класифікації. Чим менше помилок, тим менше байєсовський ризик. Обґрунтування про схожість емпіричного ризику до байєсовського зі зростанням обсягу даних було отримано в 70-ті роки двома вченими - В. Н. Вапніком і А. Я. Червоненкісом.
Гарантії схожості. Найпростіший випадок
Отже, ми прийшли до того, що байєсівський класифікатор дає найменшу можливою помилку, але навчити його в більшості випадків ми не можемо і помилку (ризик) порахувати ми теж не в силах. Однак, ми можемо порахувати наближення до байєсовського ризику, яке називається емпіричний ризик, а знаючи емпіричний ризик підібрати таку апроксимуючу функцію, яка б мінімізувала емпіричний ризик. Давайте розглянемо найпростішу ситуацію, коли мінімізація емпіричного ризику дає класифікатор, так само мінімізуючий байєсовський ризик. Для найпростішого випадку нам доведеться зробити припущення, яке рідко виконується на практиці, але яке надалі можна буде послабити. Зафіксуємо кінцевий клас функцій з якого ми будемо вибирати наш класифікатор і припустимо, що справжня функція, яку використовує природа для розмітки наших яблук на смаки знаходиться в цій кінцевій безлічі гіпотез: . Так само у нас є вибірка, отримана з розподілу над об'єктами. Всі об'єкти вибірки вважаємо однаково незалежно розподіленими (iid). Тоді буде вірна наступна
Теорема
Вибираючи функцію з класу за допомогою мінімізації емпіричного ризику ми гарантовано знайдемо таку, що вона має невелике значення байєсовського ризику якщо вибірка, на якій ми виробляємо мінімізацію має достатній розмір.
Що означає «невелике значення» і «достатній розмір» див. у літературі нижче.
Ідея доказу
За умовою теореми ми отримуємо вибірку з розподілу, тобто процес вибору об'єктів з природи випадковий. Кожен раз, коли ми збираємо вибірку вона буде з того ж розподілу, але самі об'єкти в ній можуть бути різні. Головна ідея доказу полягає в тому, що ми можемо отримати таку невдалу вибірку, що алгоритм, який ми виберемо за допомогою мінімізації емпіричного ризику на даній вибірці буде погано мінімізувати байєсовський ризик але при цьому добре мінімізувати емпіричний ризик, але ймовірність отримати таку вибірку мала і зростанням розміру вибірки ця ймовірність падає. Подібні теореми існують і для більш реалістичних припущень, але тут ми не будемо їх розглядати.
Практичні результати
Маючи докази того, що функція, знайдена при мінімізації емпіричного ризику не буде мати велику помилку на раніше не спостережуваних даних при достатньому розмірі навчальної вибірки ми можемо використовувати цей принцип на практиці, наприклад, наступним чином - беремо вираз:
І підставляємо різні функції втрат, залежно від вирішуваної задачі. Для лінійної регресії:
Для логістичної регресії:
Незважаючи на те, що за методом опорних векторів лежить в основному геометрична мотивація, його так само можна уявити як проблему мінімізації емпіричного ризику.
Ув'язнення
Багато методів навчання з учителем можна розглядати в тому числі як приватні випадки теорії, розробленої В. Н. Вапніком і А. Я. Червоненкісом. Ця теорія дає гарантії щодо помилки на тестовій вибірці за умови достатнього розміру навчальної вибірки та деяких вимог до простору гіпотез, в якому ми шукаємо наш алгоритм.
Література, яку використовують
- The Nature of Statistical Learning Theory, Vladimir N. Vapnik
- Pattern Classification, 2nd Edition, Richard O. Duda, Peter E. Hart, David G. Stork
- Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David
P.S. Прохання писати в личку про всі неточності та опечатки
P.P.S. Велике спасибі авторам цієї статті за TeX-редактор
