ніяка ймовірність була суворо дорівнює нулю.
Наївний байєсовський класифікатор об'єднує модель з правилом рішення. Одне загальне правило має вибрати найбільш ймовірну гіпотезу; воно відоме як апостеріорне правило прийняття рішення (MAP). Відповідний класифікатор - це функція певна наступним чином:
2.3 SVM
Метод опорних векторів (англ. SVM, support vector machine) - набір схожих алгоритмів навчання з учителем, що використовуються для задач класифікації та регресійного аналізу. Належить до сімейства лінійних класифікаторів, може також розглядатися як спеціальний випадок регуляризації по Тихонову. Особливою властивістю методу опорних векторів є невпинне зменшення емпіричної помилки класифікації і збільшення зазору, тому метод також відомий як метод класифікатора з максимальним зазором.
Основна ідея методу - переклад вихідних векторів у простір більш високої розмірності і пошук розділяє гіперплощини з максимальним зазором в цьому просторі. Дві паралельні гіперплощини будуються по обидва боки гіперплощини, що розділяє наші класи. Розділяє гиперплоскостью буде гіперплоскость, максимизирующая відстань до двох паралельних гіперплоскостей. Алгоритм працює в припущенні, що чим більша різниця або відстань між цими паралельними гіперплоскостямі, тим менше буде середня помилка класифікатора.
Часто в алгоритмах машинного навчання виникає необхідність класифікувати дані. Кожен об'єкт даних представлений як вектор (точка) в -мірному просторі (послідовність p чисел). Кожна з цих точок належить тільки одного з двох класів. Нас цікавить, чи можемо ми розділити точки гиперплоскостью розмірністю Це типовий випадок лінійної разделимости. Таких гіперплоскостей може бути багато. Тому цілком природно вважати, що максимізація зазору між класами сприяє більш впевненою класифікації. Тобто чи можемо ми знайти таку гіперплоскость, щоб відстань від неї до найближчої точки було максимальним. Це б означало, що відстань між двома найближчими точками, що лежать по різні сторони гіперплощини, максимально. Якщо така гіперплоскость існує, то вона нас буде цікавити найбільше; вона називається оптимальною розділяє гиперплоскостью, а відповідний їй лінійний класифікатор називається оптимально поділяючим класифікатором.
Формально можна описати завдання наступним чином.
Вважаємо, що точки мають вигляд:, де приймає значення 1 або? 1, залежно від того, якого класу належить точка. Кожне - це -мірний речовинний вектор, зазвичай нормалізований значеннями або. Якщо крапки не будуть нормалізовані, то точка з великими відхиленнями від середніх значень координат точок занадто сильно вплине на класифікатор. Ми можемо розглядати це як навчальну колекцію, в якій для кожного елемента вже заданий клас, до якого він належить. Ми хочемо, щоб алгоритм методу опорних векторів класифікував їх таким же чином. Для цього ми будуємо розділяє гіперплоскость, яка має вигляд:
Вектор - перпендикуляр до розділяє гіперплощини. Параметр дорівнює по модулю віддалі від гіперплощини до початку координат. Якщо параметр дорівнює нулю, гіперплоскость проходить через початок координат, що обмежує рішення.
Так як нас цікавить оптимальний розподіл, нас цікавлять опорні вектора і гіперплощини, паралельні оптимальною і найближчі до опорних векторах двох класів. Можна показати, що ці паралельні гіперплощини можуть бути описані наступними рівнянням (з точністю до нормування).
Якщо навчальна вибірка лінійно роздільна, то ми можемо вибрати гіперплощини таким чином, щоб між ними не лежала жодна точка обучающеїй вибірки і потім максимізувати відстань між гіперплоскостямі. Ширину смуги між ними легко знайти з міркувань геометрії, вона дорівнює, таким чином наше завдання мінімізувати. Щоб виключити всі точки зі смуги, ми повинні переконатися для всіх, що
Це може бути також записано у вигляді:
У разі лінійної разделимости класів, проблема побудови оптимальної розділяє гіперплощини зводиться до мінімізації за умови (1). Це завдання квадратичної оптимізації, яка має вигляд:
За теоремою Куна - Таккера ця задача еквівалентна двоїстої задачі пошуку седловой точки функції Лагранжа.
Де - вектор двоїстих змінних
Зведемо цю задачу до еквівалентної задачі квадратичного програмування, що містить тільки двоїсті змінні:
Припустимо ми вирішили дану задачу, тоді й можна знайти за формулами:
У підсумку алгоритм класифікації може бути записаний у вигляді:
При цьому підсумов...
