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

В машинному навчанні ме́тод опо́рних векторі́в — це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рно-ве́кторними маши́нами (ОВМ, англ. 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 из курса «Алгоритмы для Интернета» (рос.)