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

В машинному навчанні ме́тод опо́рних векторі́в — це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рнове́кторними маши́нами (ОВМ, англ. support vector machines, SVM, також опо́рнове́кторними мере́жами, англ. support vector networks). Для заданого набору тренувальних зразків, кожен із яких відмічено як належний до однієї чи іншої з двох категорій, алгоритм тренування ОВМ будує модель, яка відносить нові зразки до однієї чи іншої категорії, роблячи це неймовірнісним бінарним лінійним класифікатором. Модель ОВМ є представленням зразків як точок у просторі, відображених таким чином, що зразки з окремих категорій розділено якнайширшою чистою прогалиною. Нові зразки тоді відображують до цього самого простору, й роблять передбачення про їхню належність до категорії на основі того, на який бік прогалини вони потрапляють.

На додачу до виконання лінійної класифікації, ОВМ можуть ефективно виконувати нелінійну класифікацію при застосуванні так званого ядрового трюку, неявно відображуючи свої входи до просторів ознак високої вимірності.

Коли дані не є міченими, кероване навчання є неможливим, і виникає необхідність у некерованому навчанні, яке намагається знайти природне кластерування даних на групи, а потім відображувати нові дані на ці сформовані групи. Алгоритм кластерування, який забезпечує вдосконалення опорновекторним машинам, називається опо́рнове́кторним кластерува́нням (англ. support vector clustering), і його часто використовують у промислових застосуваннях, коли дані або не мічені, або коли мічені лише деякі дані як попередня обробка перед проходом класифікації.

Постановка задачі

H₁ не розділяє ці класи. H₂ розділяє, але лише з невеликим розділенням. H₃ розділяє їх із максимальним розділенням.

В машинному навчанні поширеною задачею є класифікація даних. Розгляньмо деякі задані точки даних, кожна з яких належить до одного з двох класів, а метою є вирішувати, в якому класі буде нова точка даних. У випадку опорновекторних машин точку даних розглядають як $p$-вимірний вектор (список $p$ чисел), і хочуть дізнатися, чи можливо розділити такі точки $(p-1)$-вимірною гіперплощиною. Це називається лінійним класифікатором. Існує багато гіперплощин, які могли би розділяти одні й ті ж дані. Одним із варіантів розумного вибору найкращої гіперплощини є такий, який пропонує найбільший проміжок, або розділення (англ. margin) між двома класами. Тож ми обираємо гіперплощину таким чином, щоби відстань від неї до найближчих точок даних з кожного боку була максимальною. Така гіперплощина, якщо вона існує, відома як максимально розділова гіперплощина (англ. maximum-margin hyperplane), а лінійний класифікатор, що вона його визначає, — як максимально розділовий класифікатор (англ. maximum margin classifier); або, рівнозначно, як перцептрон оптимальної стабільності (англ. perceptron of optimal stability).^{[джерело?]}

Визначення

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

Ядрова машина

В той час, як первинну задачу може бути сформульовано у скінченновимірному просторі, часто трапляється так, що множини, які треба розрізнювати, не є лінійно роздільними в ньому. З цієї причини було запропоновано відображувати первинний скінченновимірний простір до простору набагато вищої вимірності, здогадно роблячи розділення простішим у тому просторі. Для збереження помірного обчислювального навантаження, відображення, які використовують у методі опорних векторів, розробляють такими, щоби забезпечувати можливість простого обчислення скалярних добутків у термінах змінних первинного простору, визначаючи їх у термінах ядрових функцій $k(x,y)$, що їх обирають відповідно до задачі. Гіперплощини в просторі вищої вимірності визначають як геометричне місце точок, скалярні добутки яких із вектором у цьому просторі сталі. Вектори, які визначають гіперплощини, можуть обиратися як лінійні комбінації з параметрами $\alpha _{i}$ відображень векторів ознак $x_{i}$, які трапляються в базі даних. За такого вибору гіперплощини, точки $x$ простору ознак, які відображаються на гіперплощину, визначаються відношенням $\textstyle \sum _{i}\alpha _{i}k(x_{i},x)=\mathrm {constant} .$ Зауважте, що якщо $k(x,y)$ стає малою з віддаленням $y$ від $x$, то кожен член цієї суми вимірює ступінь близькості пробної точки $x$ до відповідних основних точок даних $x_{i}$. Таким чином, наведена вище сума ядер може використовуватися для вимірювання відносної близькості кожної пробної точки до точок даних, які походять з однієї або іншої з множин, які треба розрізнювати. Зверніть увагу на той факт, що множина точок $x$, відображена на будь-яку гіперплощину, може бути в результаті доволі вигнутою, уможливлюючи набагато складніше розрізнювання між множинами, які взагалі не є опуклими в первинному просторі.

Застосування

ОВМ можуть застосовуватися для розв'язання різноманітних практичних задач:

• ОВМ корисні для категоризації текстів та гіпертекстів, бо їхнє застосування може значно знижувати потребу в мічених тренувальних зразках як у стандартній індуктивній, так і в трансдуктивній постановках.
• Із застосуванням ОВМ може виконуватися й класифікація зображень. Експериментальні результати показують, що ОВМ можуть досягати значно вищої точності пошуку, ніж традиційні схеми уточнення запиту, всього лише після трьох-чотирьох раундів зворотного зв'язку про відповідність. Це є вірним і для систем сегментування зображень, включно з тими, які використовують видозмінену версію ОВМ, яка застосовує привілейований підхід, запропонований Вапником.
• За допомогою ОВМ може здійснюватися розпізнавання рукописних символів.
• Алгоритм ОВМ широко застосовують у біологічних та інших науках. Їх було використано для класифікації білків з правильною класифікацією до 90 % складу. Як механізм інтерпретування моделей ОВМ було запропоновано пермутаційний тест на основі вагових коефіцієнтів ОВМ. Вагові коефіцієнти опорновекторних машин використовувалися для інтерпретування моделей ОВМ і в минулому. Ретроспективне інтерпретування моделей опорновекторних машин з метою ідентифікування ознак, які використовує модель для здійснення передбачень, є відносно новою областю досліджень з особливим значенням у біологічних науках.

Історія

Первинний алгоритм ОВМ було винайдено Володимиром Вапником та Олексієм Червоненкісом 1963 року. 1992 року Бернхард Босер, Ізабель Гійон та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку. Поточне стандартне втілення (м'яке розділення) було запропоновано Корінною Кортес та Володимиром Вапником 1993 року й опубліковано 1995 року.

Лінійна ОВМ

В нас є тренувальний набір даних з $n$ точок вигляду

$({\vec {x}}_{1},y_{1}),\,\ldots ,\,({\vec {x}}_{n},y_{n})$

де $y_{i}$ є або 1, або -1, і кожен з них вказує клас, до якого належить точка ${\vec {x}}_{i}$. Кожен ${\vec {x}}_{i}$ є $p$-вимірним дійсним вектором. Нам потрібно знайти «максимально розділову гіперплощину», яка відділяє групу точок ${\vec {x}}_{i}$, для яких $y_{i}=1$, від групи точок, для яких $y_{i}=-1$, і визначена таким чином, що відстань між цією гіперплощиною та найближчою точкою ${\vec {x}}_{i}$ з кожної з груп максимальна.

Будь-яку гіперплощину може бути записано як множину точок ${\vec {x}}$, які задовольняють

${\vec {w}}\cdot {\vec {x}}-b=0,\,$

де ${\vec {w}}$ є (не обов'язково нормалізованим) вектором нормалі до цієї гіперплощини. Параметр ${\tfrac {b}{\|{\vec {w}}\|}}$ визначає зсув гіперплощини від початку координат вздовж вектора нормалі ${\vec {w}}$.

Жорстке розділення

Максимально розділова гіперплощина та межі для ОВМ, натренованої зразками з двох класів. Зразки на межах називаються опорними векторами.

Якщо тренувальні дані лінійно роздільні, то ми можемо обрати дві паралельні гіперплощини, які розділяють два класи даних так, що відстань між ними якомога більша. Область, обмежену цими двома гіперплощинами, називають «розділенням» (англ. margin), а максимально розділова гіперплощина це гіперплощина, яка лежить посередині між цими двома. Ці гіперплощини може бути описано рівняннями

${\vec {w}}\cdot {\vec {x}}-b=1\,$ (будь-що на або вище цієї межі належить до класу з міткою 1)

та

${\vec {w}}\cdot {\vec {x}}-b=-1.\,$ (будь-що на або нижче цієї межі належить до класу з міткою -1)

З геометричної точки зору, відстанню між цими двома гіперплощинами є ${\tfrac {2}{\|{\vec {w}}\|}}$, тож для максимізації відстані між ними нам треба мінімізувати $\|{\vec {w}}\|$. А що ми також маємо завадити потраплянню точок даних до розділення, ми додаємо таке обмеження: для кожного $i$, або

${\vec {w}}\cdot {\vec {x}}_{i}-b\geqslant 1,$ якщо $y_{i}=1,$

або

${\vec {w}}\cdot {\vec {x}}_{i}-b\leqslant -1,$ якщо $y_{i}=-1.$

Ці обмеження стверджують, що кожна точка даних мусить лежати з правильного боку розділення.

Ці дві нерівності можна записати як одну:

$y_{i}({\vec {w}}\cdot {\vec {x}}_{i}-b)\geqslant 1,\quad$ для всіх $1\geqslant i\geqslant n.\qquad \qquad (1)$

Ми можемо зібрати це докупи, щоби отримати задачу оптимізації:

«Мінімізувати $\|{\vec {w}}\|$ за умови $y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\geqslant 1$ для $i=1,\,\ldots ,\,n$»

${\vec {w}}$ та $b$, які розв'язують цю задачу, визначають наш класифікатор, ${\vec {x}}\mapsto \operatorname {sgn}({\vec {w}}\cdot {\vec {x}}-b)$.

Очевидним, але важливим наслідком цього геометричного опису є те, що максимально розділова гіперплощина повністю визначається тими ${\vec {x}}_{i}$, які лежать найближче до неї. Ці ${\vec {x}}_{i}$ називають опорними векторами (англ. support vectors).

М'яке розділення

Для розширення ОВМ на випадки, в яких дані не є лінійно роздільними, ми вводимо заві́сну функцію втрат (англ. hinge loss function),

$\max \left(0,1-y_{i}({\vec {w}}\cdot {\vec {x}}_{i}-b)\right).$

Зауважимо, що $y_{i}$ є i-ю цілю (англ. target) (тобто, в нашому випадку, 1 або -1) та $({\vec {w}}\cdot {\vec {x}}_{i}-b)$ - поточний результат.

Ця функція нульова, якщо справджується обмеження в (1), іншими словами, якщо ${\vec {x}}_{i}$ лежить із правильного боку розділення. Для даних із неправильного боку розділення значення цієї функції пропорційне відстані від розділення.

Тоді нам треба мінімізувати

$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\right)\right]+\lambda \lVert {\vec {w}}\rVert ^{2},$

де параметр $\lambda$ визначає компроміс між збільшенням розміру розділення та забезпеченням того, що ${\vec {x}}_{i}$ лежить із правильного боку розділення. Отже, для достатньо малих значень $\lambda$ ОВМ із м'яким розділенням (англ. soft-margin SVM) поводитиметься так само, як ОВМ із жорстким розділенням (англ. hard-margin SVM), якщо вхідні дані є лінійно класифіковними, але, тим не менше, вчитиметься життєздатного правила класифікації, якщо ні.

Нелінійна класифікація

Ядрова машина

Первинний алгоритм максимально розділової гіперплощини, запропонований Володимиром Вапником у 1963 році, будував лінійний класифікатор. Проте 1992 року Бернхард Босер, Ізабель Гійон та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку (первинно запропонованого Айзерманом та ін.). Отриманий алгоритм є формально аналогічним, за винятком того, що кожен скалярний добуток замінено нелінійною ядровою функцією. Це дозволяє алгоритмові узгоджувати максимально розділову гіперплощину в перетвореному просторі ознак. Перетворення може бути нелінійним, а перетворений простір — великої вимірності; хоч класифікатор і є гіперплощиною в перетвореному просторі ознак, у первинному вхідному просторі він може бути нелінійним.

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

До деяких найпоширеніших ядер належать:

• Поліноміальне (однорідне): $k\left({\vec {x_{i}}},{\vec {x_{j}}}\right)=\left({\vec {x_{i}}}\cdot {\vec {x_{j}}}\right)^{d}$
• Поліноміальне (неоднорідне): $k\left({\vec {x_{i}}},{\vec {x_{j}}}\right)=\left({\vec {x_{i}}}\cdot {\vec {x_{j}}}+1\right)^{d}$
• Ґаусова радіально-базисна функція: $k\left({\vec {x_{i}}},{\vec {x_{j}}}\right)=\exp \left(-\gamma \,\left\|{\vec {x_{i}}}-{\vec {x_{j}}}\right\|^{2}\right)$ для $\gamma >0$. Іноді використовують $\gamma ={\dfrac {1}{2\sigma ^{2}}}$, але частіше цей гіперпараметр підбирають з допомогою перехресного затверджування
• Сигмоїдне (гіперболічний тангенс): $k\left({\vec {x_{i}}},{\vec {x_{j}}}\right)=\tanh \left(\kappa \,{\vec {x_{i}}}\cdot {\vec {x_{j}}}+c\right)$ для деяких (не всіх) $\kappa >0$ та $c<0$

Ядро пов'язано з перетворенням $\varphi \left({\vec {x_{i}}}\right)$ через рівняння $k\left({\vec {x_{i}}},{\vec {x_{j}}}\right)=\varphi \left({\vec {x_{i}}}\right)\cdot \varphi \left({\vec {x_{j}}}\right)$. Значення w також знаходиться в перетвореному просторі, з $\textstyle {\vec {w}}=\displaystyle \sum \limits _{i}\alpha _{i}y_{i}\varphi \left({\vec {x_{i}}}\right)$. Скалярні добутки з w для класифікації, знов-таки, може бути обчислювано за допомогою ядрового трюку, тобто, $\textstyle {\vec {w}}\cdot \varphi \left({\vec {x}}\right)=\displaystyle \sum \limits _{i}\alpha _{i}y_{i}k\left({\vec {x_{i}}},{\vec {x_{\left.\right.}}}\right)$.

Обчислення ОВМ-класифікатора

Обчислення ОВМ-класифікатора (з м'яким розділенням) становить мінімізацію виразу вигляду

$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}.\qquad (2)$

Ми зосереджуємося на класифікаторі з м'яким розділенням, оскільки, як зауважено вище, вибір достатньо малого значення $\lambda$ для лінійно роздільних вхідних даних дає класифікатор із жорстким розділенням. Нижче описано класичний підхід, який включає зведення (2) до задачі квадратичного програмування. А потім буде обговорено сучасніші підходи, такі як субградієнтний та координатний спуск.

Пряме

Мінімізацію (2) може бути переписано як обмежену задачу оптимізації з диференційовною цільовою функцією наступним чином.

Для кожного $i\in \{1,\,\ldots ,\,n\}$ ми вводимо змінну $\zeta _{i}=\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)$. Зверніть увагу, що $\zeta _{i}$ є найменшим невід'ємним числом, яке задовольняє $y_{i}(w\cdot x_{i}+b)\geq 1-\zeta _{i}.$

Отже, ми можемо переписати задачу оптимізації таким чином:

мінімізувати ${\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|w\|^{2}$

за умов $y_{i}(x_{i}\cdot w+b)\geq 1-\zeta _{i}\,$ та $\,\zeta _{i}\geq 0,$ для всіх $i$.

Це називається прямою задачею (англ. primal problem).

Двоїсте

Шляхом розв'язання лагранжевої двоїстості наведеної вище задачі отримується спрощена задача:

максимізувати $\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},$

за умов $\sum _{i=1}^{n}c_{i}y_{i}=0$ та $0\leq c_{i}\leq {\frac {1}{2n\lambda }}$ для всіх $i$.

Це називається двоїстою задачею (англ. dual problem). Оскільки двоїста задача максимізації є квадратичною функцією $c_{i}$ з лінійними обмеженнями, вона ефективно розв'язна алгоритмами квадратичного програмування.

Тут змінні $c_{i}$ визначено таким чином, що

${\vec {w}}=\sum _{i=1}^{n}c_{i}y_{i}{\vec {x}}_{i}$.

Крім того, $c_{i}=0$ саме тоді, коли ${\vec {x}}_{i}$ лежить з правильного боку розділення, а $0<c_{i}<(2n\lambda )^{-1}$ коли ${\vec {x}}_{i}$ лежить на межі розділення. З цього випливає, що ${\vec {w}}$ може бути записано як лінійну комбінацію опорних векторів.

Зсув $b$ може бути з'ясовано знаходженням ${\vec {x}}_{i}$ на межі розділення, і розв'язанням

$y_{i}({\vec {w}}\cdot {\vec {x}}_{i}+b)=1\iff b=y_{i}-{\vec {w}}\cdot {\vec {x}}_{i}.$

(Зверніть увагу, що $y_{i}^{-1}=y_{i}$, бо $y_{i}=\pm 1$.)

Ядровий трюк

Припустімо тепер, що ми хотіли би вчитися нелінійного правила класифікації, яке відповідає лінійному правилу класифікації для перетворених точок даних $\varphi ({\vec {x}}_{i}).$ Крім того, в нас є ядрова функція $k$, яка задовольняє $k({\vec {x}}_{i},{\vec {x}}_{j})=\varphi ({\vec {x}}_{i})\cdot \varphi ({\vec {x}}_{j})$.

Ми знаємо, що вектор класифікації ${\vec {w}}$ у перетвореному просторі задовольняє

${\vec {w}}=\sum _{i=1}^{n}c_{i}y_{i}\varphi ({\vec {x}}_{i}),$

де $c_{i}$ отримують розв'язанням задачі оптимізації

мінімізувати ${\begin{aligned}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi ({\vec {x}}_{i})\cdot \varphi ({\vec {x}}_{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k({\vec {x}}_{i},{\vec {x}}_{j})y_{j}c_{j}\\\end{aligned}}$

за умов $\sum _{i=1}^{n}c_{i}y_{i}=0$ та $0\leq c_{i}\leq {\frac {1}{2n\lambda }}$ для всіх $i$.

Як і раніше, коефіцієнти $c_{i}$ може бути знайдено розв'язанням задачі квадратичного програмування. Знов-таки, ми можемо знайти такий індекс $i$, що $0<c_{i}<(2n\lambda )^{-1}$, так що $\varphi ({\vec {x}}_{i})$ лежить на межі розділення у перетвореному просторі, й тоді розв'язати

${\begin{aligned}b={\vec {w}}\cdot \varphi ({\vec {x}}_{i})-y_{i}&=\left[\sum _{k=1}^{n}c_{k}y_{k}\varphi ({\vec {x}}_{k})\cdot \varphi ({\vec {x}}_{i})\right]-y_{i}\\&=\left[\sum _{k=1}^{n}c_{k}y_{k}k({\vec {x}}_{k},{\vec {x}}_{i})\right]-y_{i}.\end{aligned}}$

Нарешті, нові точки може бути класифіковано обчисленням

${\vec {z}}\mapsto \operatorname {sgn}({\vec {w}}\cdot \varphi ({\vec {z}})+b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k({\vec {x}}_{i},{\vec {z}})\right]+b\right).$

Сучасні методи

До сучасних алгоритмів знаходження ОВМ-класифікаторів належать субградієнтний та координатний спуск. Обидві методики довели, що вони пропонують значні переваги над традиційним підходом при роботі з великими, розрідженими наборами даних — субградієнтні методи є особливо дієвими, коли є багато тренувальних зразків, а координатний спуск — коли розмірність простору ознак є високою.

Субградієнтний спуск

Алгоритми субградієнтного спуску для ОВМ працюють безпосередньо з виразом

$f({\vec {w}},b)=\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}.$

Зауважте, що $f$ є опуклою функцією ${\vec {w}}$ та $b$. Як такі, традиційні методи градієнтного (або стохастичного градієнтного) спуску може бути адаптовано, коли замість здійснення кроку в напрямку градієнту функції крок здійснюють у напрямку вектора, вибраного з субградієнту функції. Цей підхід має ту перевагу, що для деяких реалізацій кількість ітерацій не масштабується $n$, кількістю точок даних.

Координатний спуск

Алгоритми координатного спуску для ОВМ працюють над двоїстою задачею

максимізувати $f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},$

за умов $\sum _{i=1}^{n}c_{i}y_{i}=0$ та $0\leq c_{i}\leq {\frac {1}{2n\lambda }}$ для всіх $i$.

Для кожного $i\in \{1,\,\ldots ,\,n\}$, ітеративно, коефіцієнт $c_{i}$ коригують у напрямку $\partial f/\partial c_{i}$. Потім отриманий вектор коефіцієнтів $(c_{1}',\,\ldots ,\,c_{n}')$ проєціюють на найближчий вектор коефіцієнтів, який задовольняє задані обмеження. (Зазвичай застосовують евклідові відстані.) Цей процес повторюють доти, поки не буде отримано вектор коефіцієнтів, близький до оптимального. Отриманий алгоритм є дуже швидким на практиці, хоча доведених гарантій продуктивності мало.

Мінімізація емпіричного ризику

Описана вище опорновекторна машина з м'яким розділенням є прикладом алгоритму мінімізації емпіричного ризику (англ. empirical risk minimization, ERM) для заві́сних втрат (англ. hinge loss). При розгляді під цим кутом, опорновекторні машини належать до природного класу алгоритмів статистичного висновування, і багато їхніх унікальних властивостей обумовлено поведінкою заві́сних втрат. Ця точка зору може запропонувати подальше розуміння того, як і чому ОВМ працюють, і дозволити нам краще моделювати їхні статистичні властивості.

Мінімізація ризику

У навчанні з підкріпленням задають набір тренувальних зразків $X_{1}\ldots X_{n}$ із мітками $y_{1}\ldots y_{n}$, і потрібно передбачувати $y_{n+1}$ для заданого $X_{n+1}$. Для здійснення цього формують гіпотезу, $f$, таку, що $f(X_{n+1})$ є «добрим» наближенням $y_{n+1}$. «Добре» наближення зазвичай визначають за допомогою функції втрат, $\ell (y,z)$, яка характеризує, наскільки поганим є $z$ як передбачення $y$. Потім треба обрати гіпотезу, яка мінімізує очікуваний ризик:

$\varepsilon (f)=\mathbb {E} \left[\ell (y_{n+1},f(X_{n+1}))\right]$

В більшості випадків ми не знаємо спільного розподілу $X_{n+1},\,y_{n+1}$ безпосередньо. В цих випадках загальною стратегією є обирати гіпотезу, яка мінімізує емпіричний ризик (англ. empirical risk):

${\hat {\varepsilon }}(f)={\frac {1}{n}}\sum _{k=1}^{n}\ell (y_{k},f(X_{k}))$

За деяких припущень про послідовність випадкових змінних $X_{k},\,y_{k}$ (наприклад, що їх породжено скінченним марковським процесом), якщо множина розгляданих гіпотез достатньо мала, то мінімізатор емпіричного ризику щільно наближуватиме мінімізатор очікуваного ризику зі зростанням $n$. Цей підхід називається мінімізацією емпіричного ризику (англ. empirical risk minimization, ERM).

Регуляризація та стійкість

Щоби задача мінімізації мала добре визначений розв'язок, ми маємо накласти обмеження на множину ${\mathcal {H}}$ розгляданих гіпотез. Якщо ${\mathcal {H}}$ — нормований простір (як у випадку ОВМ), то особливо дієва методика — розглядати лише ті гіпотези $f$, для яких $\lVert f\rVert _{\mathcal {H}}<k$. Це рівнозначне накладенню регуляризаційного штрафу (англ. regularization penalty) ${\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}$, і розв'язанню нової задачі оптимізації

${\hat {f}}=\mathrm {arg} \min _{f\in {\mathcal {H}}}{\hat {\varepsilon }}(f)+{\mathcal {R}}(f)$.

Цей підхід називається регуляризацією Тихонова.

У загальнішому сенсі, ${\mathcal {R}}(f)$ може бути деякою мірою складності гіпотези $f$, щоби перевага віддавалася простішим гіпотезам.

ОВМ та завісні втрати

Пригадайте, що ОВМ-класифікатор (із м'яким розділенням) ${\hat {w}},b:x\mapsto \operatorname {sgn}({\hat {w}}\cdot x+b)$ обирають так, щоби мінімізувати такий вираз:

$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}$

Зважаючи на вищенаведене, видно, що методика ОВМ є рівнозначною мінімізації емпіричного ризику з регуляризацією Тихонова, де в цьому випадку функцією втрат є заві́сні втрати

$\ell (y,z)=\max \left(0,1-yz\right).$

З цієї точки зору ОВМ є тісно пов'язаними з іншими фундаментальними алгоритмами класифікації, такими як регуляризовані найменші квадрати та логістична регресія. Різниця між цими трьома полягає у виборі функції втрат: регуляризовані найменші квадрати зводяться до мінімізації емпіричного ризику з квадратичними втратами, $\ell _{sq}(y,z)=(y-z)^{2}$, а логістична регресія використовує логістичні втрати, $\ell _{\log }(y,z)=\ln(1+e^{-yz})$.

Цільові функції

Різницю між заві́сними втратами та цими іншими функціями втрат найкраще формулювати в термінах цільових функцій (англ. target functions) — функції, яка мінімізує очікуваний ризик для заданої пари випадкових змінних $X,\,y$.

Зокрема, нехай $y_{x}$ позначає $y$, обумовлений подією, що $X=x$. У постановці класифікації ми маємо

$y_{x}={\begin{cases}1\\-1\end{cases}}$	з імовірністю $p_{x}$
	з імовірністю $1-p_{x}$

Отже, оптимальним класифікатором є

$f^{*}(x)={\begin{cases}1\\-1\end{cases}}$	якщо $p_{x}\geq 1/2$
	інакше

Для квадратичних втрат цільовою функцією є функція умовного математичного сподівання, $f_{sq}(x)=\mathbb {E} \left[y_{x}\right]$; для логістичних втрат це логістична функція, $f_{\log(}x)=\ln \left(p_{x}/({1-p_{x}})\right)$. І хоча обидві ці функції видають правильний класифікатор, бо $\operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}$, вони дають нам більше інформації, ніж ми потребуємо. Фактично, вони дають нам достатньо інформації, щоби повністю описати розподіл $y_{x}$.

З іншого боку, можна перевірити, що цільовою функцією заві́сних втрат є саме $f^{*}$. Отже, в достатньо багатому просторі гіпотез, — або, рівнозначно, для правильно обраного ядра, — ОВМ-класифікатор збігатиметься до найпростішої функції (в термінах ${\mathcal {R}}$), яка правильно класифікує дані. Це розширює геометричну інтерпретацію ОВМ — для лінійної класифікації емпіричний ризик мінімізує будь-яка функція, межі якої лежать між опорними векторами, і найпростіша з них — максимально розділовий класифікатор.

Властивості

ОВМ належать до сімейства узагальнених лінійних класифікаторів, і можуть бути інтерпретовані як розширення перцептрону. Їх також можна розглядати й як окремий випадок регуляризації Тихонова. Особливою властивістю є те, що вони одночасно мінімізують емпіричну похибку класифікації (англ. classification error), й максимізують геометричне розділення (англ. geometric margin); тому вони також відомі й як максимально розділові класифікатори (англ. maximum margin classifiers).

Маєром, Лішем та Горником було зроблено порівняння ОМВ з іншими класифікаторами.

Вибір параметрів

Ефективність ОВМ залежить від вибору ядра, параметрів ядра та параметра м'якого розділення C. Поширеним вибором є ґаусове ядро, що має єдиний параметр $\gamma$. Найкращу комбінацію C та $\gamma$ часто обирають ґратковим пошуком з послідовностями C та $\gamma$, які експоненційно зростають, наприклад, $C\in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}$; $\gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}$. Як правило, кожну комбінацію варіантів вибору параметрів перевіряють із застосуванням перехресного затверджування, й обирають параметри з найкращою точністю, показаною перехресним затверджуванням. Як альтернатива, для вибору C та $\gamma$ може застосовуватися недавня робота в баєсовій оптимізації, яка часто потребує оцінки набагато меншого числа комбінацій параметрів, ніж ґратковий пошук. Потім остаточну модель, яку використовують для перевірки та класифікації даних, тренують на всьому тренувальному наборі із застосуванням обраних параметрів.

Проблеми

До потенційних вад ОВМ належать наступні аспекти:

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

Розширення

Опорновекторне кластерування

Опорновекторне кластерування (англ. support vector clustering, SVC) — це подібний метод, який також будує ядрові функції, але підходить для некерованого навчання та добування даних. В науці про дані його вважають фундаментальним методом.

Багатокласові ОВМ

Багатокласові ОВМ (англ. multiclass SVM) спрямовані на призначення міток зразкам за допомогою опорновекторних машин, де мітки вибирають зі скінченного набору з декількох елементів.

Панівним підходом до цього є зведення єдиної багатокласової задачі до кількох задач бінарної класифікації. До поширених методів такого зведення належать:

• Побудова бінарних класифікаторів, що розрізняють (I) між однією з міток та рештою («один проти всіх», англ. one-versus-all) або (II) між кожною з пар класів («один проти одного», англ. one-versus-one). Класифікацію нових зразків для випадку «один проти всіх» здійснюють за стратегією «переможець забирає все», в якій класифікатор з найвищою вихідною функцією призначає клас (важливо, щоби вихідні функції було відкалібровано, щоби вони видавали порівнянні оцінки). Для підходу «один проти одного» класифікацію здійснюють за стратегією голосування «максимум перемагає», в якій кожен з класифікаторів відносить зразок до одного з двох класів, тоді голос за призначений клас збільшується на одиницю, і остаточно клас із більшістю голосів визначає клас зразка.
• ОВМ на орієнтованих ациклічних графах (англ. directed acyclic graph SVM, DAGSVM)
• Вихідні коди з виправленням похибки (англ. error-correcting output codes)

Краммер та Зінгер запропонували багатокласовий метод ОВМ, який зливає задачу багатокласової класифікації в єдину задачу оптимізації, замість розкладати її на кілька задач бінарної класифікації. Див. також Лі, Лін та Вахбу.

Трансдуктивні опорновекторні машини

Трансдуктивні опорновекторні машини розширюють ОВМ тим, що вони можуть також обробляти частково мічені дані в напівкерованому навчанні, дотримуючись принципів трансдукції. Тут, на додачу до тренувального набору ${\mathcal {D}}$, надається також набір

${\mathcal {D}}^{\star }=\{{\vec {x}}_{i}^{\star }\mid {\vec {x}}_{i}^{\star }\in \mathbb {R} ^{p}\}_{i=1}^{k}\,$

тестових зразків, які потрібно класифікувати. Формально, трансдуктивну опорновекторну машину визачає така пряма задача оптимізації:

Мінімізувати (за ${{\vec {w}},b,{\vec {y^{\star }}}}$)

${\frac {1}{2}}\|{\vec {w}}\|^{2}$

за умов (для всіх $i=1,\dots ,n$ та всіх $j=1,\dots ,k$)

$y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\geq 1,\,$

$y_{j}^{\star }({\vec {w}}\cdot {\vec {x_{j}^{\star }}}-b)\geq 1,$

та

$y_{j}^{\star }\in \{-1,1\}.\,$

Трансдуктивні опорновекторні машини було запропоновано Володимиром Вапником 1998 року.

Структурні ОВМ

ОВМ було узагальнено до структурних ОВМ (англ. structured SVMs), у яких простір міток є структурним, і, можливо, нескінченного розміру.

Регресія

Версію ОВМ для регресії було запропоновано 1996 року Володимиром Вапником, Гаррісом Друкером, Крістофером Бургесом, Ліндою Кауфман та Олександром Смолою. Цей метод називається опорновекторною регресією (ОВР, англ. support vector regression, SVR). Модель, яку дає опорновекторна класифікація (як описано вище) залежить лише від підмножини тренувальних даних, адже функція втрат для побудови моделі не зважає на тренувальні точки, які лежать за межами розділення. Аналогічно, модель, яку дає опорновекторна регресія, залежить лише від підмножини тренувальних даних, позаяк функція втрат для побудови моделі ігнорує будь-які тренувальні дані, близькі до передбачення моделі. Іншу версію ОВМ, відому як опорновекторна машина найменших квадратів (англ. least squares support vector machine, LS-SVM), було запропоновано Сайкенсом та Вандервалле.

Тренування первинної ОВР означає розв'язання

мінімізувати ${\frac {1}{2}}\|w\|^{2}$

за умов ${\begin{cases}y_{i}-\langle w,x_{i}\rangle -b\leq \varepsilon \\\langle w,x_{i}\rangle +b-y_{i}\leq \varepsilon \end{cases}}$

де $x_{i}$ є тренувальним зразком із цільовим значенням $y_{i}$. Внутрішній добуток плюс відсікання $\langle w,x_{i}\rangle +b$ є передбаченням для цього зразка, а $\varepsilon$ є вільним параметром, що слугує порогом: всі передбачення мають бути в межах відстані $\varepsilon$ від справжніх передбачень. Зазвичай до наведеного вище додають фіктивні змінні, щоби дозволити похибки та наближення в разі, якщо наведена вище задача є нездійсненною.

Реалізація

Параметри максимально розділової гіперплощини виводять шляхом розв'язання задачі оптимізації. Існує декілька спеціалізованих алгоритмів для швидкого розв'язання задач КП, що виникають в ОВМ, вони здебільшого покладаються на евристики для розбиття задачі на менші підзадачі, з якими легше впоруватися.

Іншим підходом є застосування методу внутрішньої точки, який використовує ньютоно-подібні ітерації для пошуку розв'язку умов Каруша — Куна — Такера прямої та двоїстої задач. Замість розв'язання послідовності розбитих задач, цей підхід безпосередньо розв'язує задачу в цілому. Для уникнення розв'язання лінійної системи з великою ядровою матрицею в ядровому трюку часто використовують низькорангове наближення матриці.

Іншим поширеним методом є алгоритм послідовної мінімальної оптимізації Платта, який розбиває задачу на 2-вимірні підзадачі, які розв'язують аналітично, усуваючи потребу в алгоритмі числової оптимізації та в зберіганні матриці. Цей алгоритм є простим концептуально, простим у реалізації, зазвичай швидшим, і має кращі властивості масштабування для складних задач ОВМ.

Окремий випадок лінійних опорновекторних машин може розв'язуватися ефективніше алгоритмами того ж роду, що й використовують для оптимізації їхнього близького родича, логістичної регресії; цей клас алгоритмів включає субградієнтний спуск (наприклад, PEGASOS) та координатний спуск (наприклад, LIBLINEAR). LIBLINEAR володіє деякими привабливими властивостями часу тренування. Кожна ітерація збіжності займає час, лінійний по відношенню до часу, витраченого на читання тренувальних даних, й ітерації також володіють властивістю Q-лінійної збіжності, що робить цей алгоритм надзвичайно швидким.

Звичайні ядрові ОВМ також можуть розв'язуватися ефективніше при застосуванні субградієнтного спуску (наприклад, P-packSVM), особливо якщо дозволено розпаралелювання.

Ядрові ОВМ доступні в багатьох інструментаріях машинного навчання, включно з LIBSVM, MATLAB, SAS, SVMlight, kernlab, scikit-learn, Shogun, Weka, Shark, JKernelMachines, OpenCV та іншими.

Див. також

• Адаптивне табулювання на місці
• Ядрові машини
• Ядро Фішера
• Масштабування Платта
• Поліноміальне ядро
• Передбачувальна аналітика
• Перспективи регуляризації на опорновекторних машинах
• Доречно-векторна машина, ймовірнісна розріджена ядрова модель, ідентична у функційному вигляді до ОВМ
• Послідовна мінімальна оптимізація
• Методологія картографування
• Winnow (алгоритм)

Література

• Theodoridis, Sergios; and Koutroumbas, Konstantinos; "Pattern Recognition", 4th Edition, Academic Press, 2009, ISBN 978-1-59749-272-0 (англ.)
• Nello Cristianini, John Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. — Cambridge University Press, 2000. — ISBN 978-1-139-64363-4. (книга про ОВМ) (англ.)
• Huang, Te-Ming; Kecman, Vojislav; and Kopriva, Ivica (2006); Kernel Based Algorithms for Mining Huge Data Sets, in Supervised, Semi-supervised, and Unsupervised Learning, Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN 3-540-31681-7 (англ.)
• Kecman, Vojislav; Learning and Soft Computing — Support Vector Machines, Neural Networks, Fuzzy Logic Systems, The MIT Press, Cambridge, MA, 2001. (англ.)
• Schölkopf, Bernhard; and Smola, Alexander J.; Learning with Kernels, MIT Press, Cambridge, MA, 2002. ISBN 0-262-19475-9 (англ.)
• Schölkopf, Bernhard; Burges, Christopher J. C.; and Smola, Alexander J. (editors); Advances in Kernel Methods: Support Vector Learning, MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3. (англ.)
• Shawe-Taylor, John; and Cristianini, Nello; Kernel Methods for Pattern Analysis, Cambridge University Press, 2004. ISBN 0-521-81397-2 (крига про ядрові методи) (англ.)
• Steinwart, Ingo; and Christmann, Andreas; Support Vector Machines, Springer-Verlag, New York, 2008. ISBN 978-0-387-77241-7 (книга про ОВМ) (англ.)
• Tan, Peter Jing; and Dowe, David L. (2004); MML Inference of Oblique Decision Trees, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, pp. 1082–1088. (Ця праця використовує мінімальну довжину повідомлення, і фактично включає ймовірнісні опорновекторні машини в листках дерев рішень.) (англ.)
• Vapnik, Vladimir N.; The Nature of Statistical Learning Theory, Springer-Verlag, 1995. ISBN 0-387-98780-0 (англ.)
• Vapnik, Vladimir N.; and Kotz, Samuel; Estimation of Dependences Based on Empirical Data, Springer, 2006. ISBN 0-387-30865-2, 510 pages [це є передруком ранньої криги Вапника, яка описує філософію, що стоїть за підходом ОВМ. Доповнення 2006 року описує нові вдосконалення]. (англ.)
• Fradkin, Dmitriy; and Muchnik, Ilya; Support Vector Machines for Classification in Abello, J.; and Carmode, G. (Eds); Discrete Methods in Epidemiology, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 70, pp. 13–20, 2006. Стисло описує теоретичні ідеї, що лежать в основі ОВМ. (англ.)
• Bennett, Kristin P.; and Campbell, Colin; Support Vector Machines: Hype or Hallelujah?, SIGKDD Explorations, 2, 2, 2000, 1–13. Відмінне введення до ОВМ із корисними малюнками. (англ.)
• Ivanciuc, Ovidiu; Applications of Support Vector Machines in Chemistry, in Reviews in Computational Chemistry, Volume 23, 2007, pp. 291–400. (англ.)
• Catanzaro, Bryan; Sundaram, Narayanan; and Keutzer, Kurt; Fast Support Vector Machine Training and Classification on Graphics Processors, in International Conference on Machine Learning, 2008 (англ.)
• Campbell, Colin; and Ying, Yiming; Learning with Support Vector Machines, 2011, Morgan and Claypool. ISBN 978-1-60845-616-1. (англ.)
• Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137. (англ.)
• Владимир Вьюгин. Математические основы машинного обучения и прогнозирования. — МЦМНО, 2014. — 304 с. — ISBN 978-5-457-71889-0. (рос.)
• Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. A Gentle Introduction to Support Vector Machines in Biomedicine: Theory and methods. — World Scientific, 2011. — ISBN 978-981-4324-38-0. (англ.)
• Alexey Nefedov. Support Vector Machines: A Simple Tutorial. — 2016. (англ.)
• А. А. Шумейко, С. Л. Сотник, М. В. Лысак. Использование генетических алгоритмов в задачах классификации текстов. (рос.)
• Ю. Лифшиц. Метод опорних векторов (рос.)
• Andrew Ng (2016). Support Vector Machines (PDF). CS229 Course: Machine Learning. Stanford University. (англ.)
  • Дудин, В. Д. (2013). Сравнение и тестирование реализаций алгоритма SVM для задач классификации (PDF) (Курсовая работа). Санкт-Петербургский государственный университет. — частковий російськомовний плагіат (рос.)

Посилання

• www.support-vector.net Ключова книга про цей метод, «An Introduction to Support Vector Machines» з доступним онлайн програмним забезпеченням (англ.)
• Burges, Christopher J. C.; A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery 2:121–167, 1998 (англ.)
• www.kernel-machines.org (загальна інформація та збірка дослідницьких праць) (англ.)
• www.support-vector-machines.org (література, огляди, програмне забезпечення, посилання, пов'язані з опорновекторними машинами — академічний сайт) (англ.)
• svmtutorial.online Просте введення до ОВМ, легко доступне будь-кому з базовими знаннями в математиці (англ.)
• videolectures.net (відео-лекції, пов'язані з ОВМ) (англ.)
• Karatzoglou, Alexandros et al.; Support Vector Machines in R, Journal of Statistical Software April 2006, Volume 15, Issue 9. (англ.)
• libsvm — LIBSVM, популярна бібліотека для систем навчання ОВМ
• liblinear — бібліотека для великої лінійної класифікації, включно з деякими ОВМ
• Shark — бібліотека машинного навчання C++, яка реалізує різні типи ОВМ
• dlib — бібліотека C++ для роботи з ядровими методами та ОВМ
• SVM light — збірка програмних інструментів для навчання та класифікації із застосуванням ОВМ
• SVMJS live demo — ГІК-демонстрація реалізації ОВМ на JavaScript
• Gesture Recognition Toolkit містить зручну для застосування обгортку для libsvm
• Data Mining. 10. Лекция: Методы классификации и прогнозирования. Метод опорных векторов // Интуит.ру (рос.)
• Юрий Лифшиц. Метод опорных векторов (Слайды) — лекция № 7 из курса «Алгоритмы для Интернета» (рос.)