Метод опорних векторів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод опорних векторів (англ. SVM, ) належить до групи граничних методів; визначає класи за допомогою меж просторів. Опорними векторами вважаються об’єкти множини, що лежать на цих межах. Класифікація вважається вдалою, якщо простір між межами – пустий .[1]

Визначення[ред.ред. код]

Метод опорних векторів - це набір схожих алгоритмів виду «навчання із вчителем». Ці алгоритми зазвичай використовуються для задач класифікації та регресійного аналізу. Метод належить до розряду лінійних класифікаторів. Також може розглядатись як особливий випадок регуляризації за А. Н. Тихоновим. Особливою властивістю методу опорних векторів є безперервне зменшення емпіричної помилки класифікації та збільшення проміжку. Тому цей метод також відомий як метод класифікатора з максимальним проміжком. Основна ідея методу опорних векторів – перевід вихідних векторів у простір більш високої розмірності та пошук роздільної гіперплощини з максимальним проміжком у цьому просторі. Дві паралельні гіперплощини будуються по обидва боки гіперплощини, що розділяє наші класи. Роздільною гіперплощиною буде та, що максимізує відстань до двох паралельних гіперплощин. Алгоритм працює у припущенні, що чим більша різниця або відстань між цими паралельними гіперплощинами, тим меншою буде середня помилка класифікатора.[2]

Історія[ред.ред. код]

Метод опорних векторів був розроблений Володимиром Вапніком в 1995 році на основі принципу структурної мінімізації ризику – одночасного контролю кількості помилок класифікації на множині для навчання та «ступеню узагальнення» виявлених залежностей. Метод вперше був застосований до задачі класифікації текстів Йоахімсом в 1998 році. В своєму початковому вигляді метод опорних векторів вирішував задачу розрізнення об’єктів двох класів.[3],[4]

Постановка задачі[ред.ред. код]

В алгоритмах машинного навчання часто виникає необхідність класифікувати дані. Кожен об’єкт даних представлено як вектор (точку) в -мірному просторі (послідовність чисел). Кожна з цих точок належить лише одному з двох класів. Нас цікавить, чи можливо розділити точки гіперплощини розмірністю ( -1). Це – типовий приклад лінійної роздільності. Таких гіперплощин може бути багато. А тому цілком природньо припустити, що максимізація проміжку між класами сприяє кращій класифікації. Тобто, маємо вияснити, чи можемо ми знайти таку гіперплощину, щоб відстань від неї до найближчої точки була максимальною. Це б означало, що відстань між двома найближчими точками, що лежать по різні сторони гіперплощини, - максимальна. Якщо така гіперплощина існує, то вона нас і цікавитиме більш за все. Вона зветься роздільною гіперплощиною, а відповідний їй класифікатор – оптимально роздільним класифікатором.

Формальний опис задачі[ред.ред. код]

Припустимо, що точки мають такий вигляд:

\{ (\mathbf{x}_1, c_1), (\mathbf{x}_2, c_2), \ldots, (\mathbf{x}_n, c_n)\}, де ci приймає значення 1 або −1 залежно від того, якому класу належить точка \mathbf{x}_i . Кожна точка  \mathbf{x}_i — це p-мірний дійсний вектор, що зазвичай нормалізується значеннями [0,1] або [-1,1]. Якщо точки не будуть нормалізовані, то точка з більшими відхиленнями від середніх значень координат точок матиме сильний вплив на класифікатор. Можемо розглядати це як навчальну колекцію, в якій для кожного елементу уже задано клас, до якого він належить. Потрібно, аби алгоритм методу опорних векторів класифікував їх таким же чином. Для цього будується роздільна гіперплощина, що матиме такий вигляд:
Оптимальна січна гіперплощина для метода опорних векторів, побудована на точках з двох класів. Найближчі точки до паралельних гіперплощин називаються опорними векторами
\mathbf{w}\cdot\mathbf{x} - b=0.

Вектор \mathbf{w} є перпендикуляром до роздільної гіперплощини. Параметр b залежить від найкоротшої відстані гіперплощини до початку координат. Якщо параметр b дорівнює нулю, то це означає, що гіперплощина проходить через початок координат. А це – обмежує рішення. З метою знайти оптимальне розділення, маємо звернути увагу на опорні вектори та гіперплощини, що є паралельними до оптимальної, та найближчими до опорних векторів двох класів. Можна показати, що ці паралельні гіперплощини можуть бути описані такими рівняннями (з точністю до нормування):

\mathbf{w}\cdot\mathbf{x} - b=1,
\mathbf{w}\cdot\mathbf{x} - b=-1.

Якщо навчальна вибірка лінійно роздільна, то ми можемо вибрати гіперплощини таким чином, аби між ними не лежала жодна точка навчальної вибірки, і після цього – максимізувати відстань між гіперплощинами. Можна легко знайти ширину полоси між ними, яка дорівнює \frac{2}{\|\mathbf{w}\|}[5]. Тепер потрібно мінімізувати \|\mathbf{w}\|. Аби виключити всі точки із полоси, маємо переконатись для всіх i, що


\left[\begin{array}{lcr}
\mathbf{w}\cdot\mathbf{x_i} - b \ge 1,\ c_i=1\mathrm{}\\
\mathbf{w}\cdot\mathbf{x_i} - b \le -1,\ c_i=-1\mathrm{}\\
\end{array}\right.

Це також може бути записано таким чином:

c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\qquad\qquad(1)

Випадок лінійної роздільності[ред.ред. код]

Проблема поюудови оптимальної роздільної гіперплощини зводиться до мінімізації \|\mathbf{w}\|, за умови (1). Це задача квадратичної оптимізації, що має такий вигляд: \left\{\begin{array}{lcr}
\|\mathbf{w}\|^2 \to \min \\
c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\\
\end{array}\right.

За теоремою Куна-Таккера, ця задача еквівалентна двоїстій задачі пошуку сідлової точки функції Лагранжа \left\{\begin{array}{lcr}
\mathbf{L} (\mathbf{w}, \mathbf{b}; \mathbf{\lambda}) = \frac{1}{2} \|\mathbf{w}\|^2 - 
  \sum_{i=1}^n \mathbf{\lambda_i}(c_i((\mathbf{w}\cdot\mathbf{x_i})-b)-1)\to \min_{w,b} \max_{\lambda} \\
\mathbf{\lambda_i} \ge 0, \quad 1 \le i \le n\\
\end{array}\right.(2) де \mathbf{\lambda}=(\mathbf{\lambda_1},\ldots, \mathbf{\lambda_n}) - вектор двоїстих змінних.

Зведемо цю задачу до еквівалентної задачі квадратичного програмування, що містить лише двоїсті змінні:

\left\{\begin{array}{lcr}
-\mathbf{L} (\mathbf{\lambda}) = -\sum_{i=1}^n \mathbf{\lambda_i}+ \frac{1}{2} 
  \sum_{i=1}^n\sum_{j=1}^n \mathbf{\lambda_i}\mathbf{\lambda_j}c_i c_j(\mathbf{x_i}\cdot \mathbf{x_j}) \to \min_{\lambda} \\
\mathbf{\lambda_i} \ge 0, \quad 1 \le i \le n\\
\sum_{i=1}^n \mathbf{\lambda_i}c_i = 0
 \\
\end{array}\right.(3)

Якщо припустити, що цю задачу розв’язано, тоді w і b можна знайти за формулами:

\mathbf{w} = \sum_{i=1}^n \mathbf{\lambda_i} c_i \mathbf{x_i}

\mathbf{b} = \mathbf{w} \cdot \mathbf{x_i} - c_i, \quad \mathbf \lambda_i > 0

Врешті, алгоритм класифікації можна записати таким чином:

a(x) = sign \left(\sum_{i=1}^n \mathbf{\lambda_i} c_i \mathbf{x_i}\cdot \mathbf{x} - b\right)(4)

При цьому сума рахується не по всій вибірці, а лише по опорним векторам, для яких \mathbf{\lambda_i}\ne0.

Випадок лінійної нероздільності[ред.ред. код]

Для того, аби алгоритм міг працювати у випадку, якщо класи лінійно нероздільні, треба дозволити йому припускатись помилок на навчальній вибірці. Введемо набір додаткових змінних \xi_i\ge0, що характеризують величину помилки на об’єктах \mathbf{x}_i , \quad 1 \le i \le n . За відправну точку беремо (2), помякшивши обмеження нерівності. Також введемо до мінімізуємого функціоналу штраф за сумарну помилку: \left\{\begin{array}{lcr}
\frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \to \min_{w,b,\xi_i}\\
c_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, \quad 1 \le i \le n \\
\xi_i\ge0, \quad 1 \le i \le n\\
\end{array}\right.

Коефіцієнт C - параметр налаштування методу, що дозволяє регулювати відношення між максимізацією ширини роздільної полоси та мінімізацією сумарної помилки. Аналогічно, за теоремою Куна-Такера, зводимо задачу до пошуку сідловок точки функції Лагранжа:

>\left\{\begin{array}{lcr} \mathbf{L} (\mathbf{w}, \mathbf{b}, \mathbf{\xi}; \mathbf{\lambda},\mathbf{\eta}) = \frac{1}{2} \|\mathbf{w}\|^2 -

 \sum_{i=1}^n \mathbf{\lambda_i}(c_i(\mathbf{w}\cdot\mathbf{x_i})-1)
 -\sum_{i=1}^n \mathbf{\xi_i} (\mathbf{\lambda_i}+\mathbf{\eta_i}-C)

\to \min_{w,b,\xi} \max_{\lambda,\eta} \\ \mathbf{\xi_i} \ge 0, \mathbf{\lambda_i} \ge 0, \mathbf{\eta_i} \ge 0, \quad 1 \le i \le n\\

\left[\begin{array}{lcr} \mathbf{\lambda_i} = 0 \\ c_i(\mathbf{w}\cdot\mathbf{x_i} - b )=1-\xi_i, \\ \end{array}\right. \quad 1 \le i \le n \\

\left[\begin{array}{lcr} \mathbf{\eta_i} = 0 \\ \mathbf{\xi_i} =0, \\ \end{array}\right. \quad 1 \le i \le n

\end{array}\right.</math>

За аналогією, зведемо цю задачу до еквівалентної:

\left\{\begin{array}{lcr}
-\mathbf{L} (\mathbf{\lambda}) = -\sum_{i=1}^n \mathbf{\lambda_i}+ \frac{1}{2} 
  \sum_{i=1}^n\sum_{j=1}^n \mathbf{\lambda_i}\mathbf{\lambda_j}c_i c_j(\mathbf{x_i}\cdot \mathbf{x_j}) \to \min_{\lambda} \\
0 \le \mathbf{\lambda_i} \le \mathbf{C}, \quad 1 \le i \le n\\
\sum_{i=1}^n \mathbf{\lambda_i}c_i = 0
 \\
\end{array}\right.

На практиці для побудови машин опорних векторів розв’язують саме цю задачу, а не (3), через те що гарантувати лінійну роздільність точок на два класи в загальному випадку неможливо. Цей варіант алгоритму називають алгоритмом з мяким проміжком (soft-margin SVM), тоді як у випадку лінійно роздільного алгоритму говорять про жорсткий проміжок (hard-margin SVM). Для алгоритму класифікації зберігається формула (4), з тою лише різницею, що тепер ненулевим володіють не лише опорні обєкти, але й обєкти-порушники. Певним чином – це недолік, оскільки порушниками часто виявляються шумові викиди, і побудоване на них кінцеве правило,по суті, опирається на шум. Константу С зазвичай обирають за критерієм ковзкого контролю. Це спосіб, що потребує досить багато сил. Аджу задачу доводиться вирішувати заново при кожному значенні C. Якщо є підстави вважати, що вибірка майже лінійно роздільна, і лише об'єкти-викиди класифікуються неправильно, то можна застосувати фільтрацію викидів. Спочатку задача вирішується при деякому значенні C, і з вибірки видаляється невелика частка об'єктів, що мають найбільшу величину помилки \mathbf{\lambda_i}. Після цього завдання вирішується заново по скороченій вибірці. Можливо, доведеться проробити кілька таких ітерацій, поки об’єкти, що лишились, не виявляться лінійно роздільними.

Ядра[ред.ред. код]

Алгоритм побудови оптимальної роздільної гіперплощини, запропонований в 1963 році Володимиром Вапником та Олексієм Червоненкісом є алгоритмом лінійної класифікації. Однак у 1992 році Бернхард Босер, Ізабель Гійон та Вапник запропонували спосіб створення нелінійного класифікатору, в основі якого лежить перехід від скалярних добутків до довільних ядер - так званий kernel trick ( вперше запропонований М. А. Айзерманом, Е. М. Броверманом і Л. В. Розоноером для методу потенційних функцій). Він дозволяє будувати нелінійні роздільники. Кінцевий алгоритм вкрай схожий на алгоритм лінійної класифікації, з тією лише різницею, що кожен скалярний добуток в наведених вище формулах замінюється нелінійною функцією ядра (скалярним добутком в просторі з більшою розмірністю). У цьому просторі вже може існувати оптимальна роздільна гіперплощина. Через те, що розмірність отримуваного простору може бути більшою розмірності вихідного, то перетворення, що зіставляє скалярні добутки, буде нелінійним. А отже функція, що відповідає у початковому просторі оптимальній роздільній гіперплощині, буде також нелінійною. Варто відзначити, що якщо початковий простір має досить високу розмірність, то можна сподіватися, що вибірка в ньому виявиться лінійно роздільною.

Найбільш поширені ядра:

  • Поліноміальне (однорідне): k(\mathbf{x},\mathbf{x}')=(\mathbf{x} \cdot \mathbf{x'})^d
  • Поліноміальне (неоднорідне): k(\mathbf{x},\mathbf{x}')=(\mathbf{x} \cdot \mathbf{x'} + 1)^d
  • Радіальна базисна функція: k(\mathbf{x},\mathbf{x}')=\exp(-\gamma \|\mathbf{x} - \mathbf{x'}\|^2), для \gamma > 0
  • Радіальна базисна функція Гаусса: k(\mathbf{x},\mathbf{x}')=\exp\left(- \frac{\|\mathbf{x} - \mathbf{x'}\|^2}{2 \sigma^2}\right)
  • Сигмоид: k(\mathbf{x},\mathbf{x}')=\tanh(\kappa \mathbf{x} \cdot \mathbf{x'}+c), для почти всех \kappa > 0 и  c < 0

Розширення простору ознак. Метод класифікації роздільною полосою має два недоліки:

  • В пошуці роздільної полоси істотне значення мають лише примежові точки;
  • В багатьох випадках знайти оптимальну роздільну полосу – неможливо.

Таким чином, необхідно якось покращити метод. Якщо згадати – умови задачі оптимізації, сформульованої за допомогою змінних Лагранжа, залежали лише від скалярних добутків між навчальними документами. А тому для покращення методу можна спробувати змінити скалярні добутки. Тут на допомогу приходить ідея розширеного простору. Побудова машини опорних векторів:

  1. Оберемо відображення φ(x) векторів х в новий, розширений простір.
  2. Автоматично виходить нова функція скалярного добутку К (х, у) = \omega(у).

На практиці зазвичай обирають не відображення φ(х), а одразу функцію К (х, у), яка могла би бути скалярним добутком за умови деякого відображення \omega(x). Функція К (х, у) називається ядром. Ця функція є головним параметром налаштування машини опорних векторів.

  1. Знаходимо роздільну гіперплощину в новому просторі: за допомогою функції К (х, у) складажмо нову матрицю коефіцієнтів для задачі оптимізації, підставляючи значення К (хі, xj) замість (хі * xj), і вирішуємо нову задачу.
  2. Знайшовши w і b, отримуємо класифікуючу площину w•\omega(x)−b в новому, розширеному просторі[6].

Переваги методу опорних векторів* - найшвидший метод знаходження вирішальних функцій;

  • - метод зводиться до вирішення задачі квадратичного програмування у випуклій області, яка завжди має єдине вирішення;
  • - метод знаходить роздільну полосу максимальної ширини, що дозволяє надалі здійснювати кращу класифікацію ;
  • - за умови різного вибору ядер можна емулювати інші підходи. Наприклад, великий клас нейронних мереж можна вредставити у вигляді методу опорних векторів з визначеними ядрами;
  • - теоретичне обгрунтування: кінцеве правило обирається не за допомогою деяких евристик, а відповідно до оптимізації деякої функції .

Недоліки методу опорних векторів.* - мала кількість параметрів для налаштування: після того як ядро зафіксували, єдиним варіативним параметром лишається коефіцієнт помилки С;

  • - метод чутливий до шумів та стандартизації даних;
  • - не існує загального підходу до автоматичного вибору ядра у випадку лінійної нероздільності класів :
  • - повільне навчання .

Посилання[ред.ред. код]

  1. А. А. Шумейко, С. Л. Сотник, М. В. Лысак. Использование генетических алгоритмов в задачах классификации текстов.
  2. І. А. Жуков, Г. М. Кременецький. Динамічна просторово-логічна кластеризація нейронної мережі.
  3. В. Г. Зайцев. Лан Чуньлинь. Способы повышения эффективности классификации документов для конечного множества языков.
  4. А. Дрозд. Методы машинного обучения (Data Mining).
  5. К. В. Воронцов. Лекции по методу опорных векторов
  6. Ю. Лифшиц. Метод опорних векторов