ування йде не по всій вибірці, а тільки по опорних векторах, для яких
У разі лінійної нероздільності класів, для того, щоб алгоритм міг працювати, дозволимо йому допускати помилки на навчальній вибірці. Введемо набір додаткових змінних, що характеризують величину помилки на об'єктах. Візьмемо за відправну точку (2), пом'якшимо обмеження нерівності, так само введемо в мінімізіруемую функціонал штраф за сумарну помилку:
Коефіцієнт - параметр настройки методу, який дозволяє регулювати відношення між максимізацією ширини розділяє смуги і мінімізацією сумарної помилки.
Аналогічно, по теоремі Куна-Таккера зводимо задачу до пошуку седловой точки функції Лагранжа:
За аналогією зведемо цю задачу до еквівалентної:
На практиці для побудови машини опорних векторів вирішують саме це завдання, а не (3), так як гарантувати лінійну разделімость точок на два класи в загальному випадку не представляється можливим. Цей варіант алгоритму називають алгоритмом з м'яким зазором (soft-margin SVM), тоді як в лінійно разделімого випадку говорять про жорсткому зазорі (hard-margin SVM).
Для алгоритму класифікації зберігається формула (4), з тією лише різницею, що тепер ненульовими володіють не тільки опорні об'єкти, але й об'єкти-порушники. У певному сенсі це недолік, оскільки порушниками часто виявляються шумові викиди, і побудоване на них вирішальне правило, по суті справи, спирається на шум.
Константу зазвичай вибирають за критерієм ковзаючого контролю. Це трудомісткий спосіб, так як завдання доводиться вирішувати заново при кожному значенні.
Якщо є підстави вважати, що вибірка майже лінійно роздільна, і лише об'єкти-викиди класифікуються невірно, то можна застосувати фільтрацію викидів. Спочатку завдання вирішується при деякому C, і з вибірки видаляється невелика частка об'єктів, що мають найбільшу величину помилки. Після цього завдання вирішується заново по усіченої вибірці. Можливо, доведеться виконати кілька таких ітерацій, поки що залишилися об'єкти не виявляться лінійно разделімого.
Алгоритм побудови оптимальної розділяє гіперплощини, запропонований в 1963 році Володимиром Вапніка та Олексієм Червоненкіса - алгоритм лінійної класифікації. Однак в 1992 році Бернхард Босер, Изабелл Гійон і Вапник запропонували спосіб створення нелінійного класифікатора, в основі якого лежить перехід від скалярних творів до довільних ядрам, так званий kernel trick (запропонований вперше М.А. Айзерманом, Е.М. Браверман і Л. В. Розоноером для методу потенційних функцій), що дозволяє будувати нелінійні роздільники. Результуючий алгоритм вкрай схожий на алгоритм лінійної класифікації, з тією лише різницею, що кожне скалярний добуток в наведених вище формулах замінюється нелінійної функцією ядра (скалярним добутком у просторі з більшою розмірністю). У цьому просторі вже може існувати оптимальна розділяє гіперплоскость. Так як розмірність одержуваного простору може бути більше розмірності вихідного, то перетворення, зіставляє скалярні твори, буде нелінійним, а значить функція, відповідна у вихідному просторі оптимальної розділяє гіперплощини, буде також нелінійної.
Варто відзначити, що якщо початковий простір має досить високу розмірність, то можна сподіватися, що в ньому вибірка виявиться лінійно разделімого.
Найбільш поширені ядра:
. Лінійне ядро:
2. Поліноміальний (однорідне):
3. RBF функція:
4. Сигмоид:
У рамках поставленого перед нами завдання будемо використовувати лінійне однорідне ядро. Дане ядро ??показало відмінні результати в задачах Document Classification, хоча в порівнянні з Наївним байесовськими Класифікатором навчання даної класифікатора займається порівняно великий проміжок часу. Також перевірена робота всіх інших ядер з даного списку і виявлено, що їхнє навчання займає значно більший проміжок часу, при цьому не привносячи особливих поліпшень в точності класифікації.
Для прискорення навчання ми будемо використовувати метод під назвою Стохастичний Градієнтний Спуск, який дозволяє значно прискорити навчання класифікатора, не сильно жертвуючи його точністю.
.3.1 Стохастичний Градієнтний Спуск
Градієнтні методи - це широкий клас оптимізаційних алгоритмів, що використовуються не тільки в машинному навчанні. Тут градієнтний підхід буде розглянутий як способу підбору вектора синаптичних ваг в лінійному класифікаторі. Нехай - цільова залежність, відома тільки на об'єктах навчальної вибірки:
Знайдемо алгори...
