В машинному навчанні ме́тод опо́рних векторі́в — це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рнове́кторними маши́нами (ОВМ, , також опо́рнове́кторними мере́жами, ). Для заданого набору тренувальних зразків, кожен із яких відмічено як належний до однієї чи іншої з двох категорій, алгоритм тренування ОВМ будує модель, яка відносить нові зразки до однієї чи іншої категорії, роблячи це неймовірнісним бінарним лінійним класифікатором. Модель ОВМ є представленням зразків як точок у просторі, відображених таким чином, що зразки з окремих категорій розділено якнайширшою чистою прогалиною. Нові зразки тоді відображують до цього самого простору, й роблять передбачення про їхню належність до категорії на основі того, на який бік прогалини вони потрапляють.
На додачу до виконання лінійної класифікації, ОВМ можуть ефективно виконувати нелінійну класифікацію при застосуванні так званого ядрового трюку, неявно відображуючи свої входи до просторів ознак високої вимірності.
Коли дані не є міченими, кероване навчання є неможливим, і виникає необхідність у некерованому навчанні, яке намагається знайти природне кластерування даних на групи, а потім відображувати нові дані на ці сформовані групи. Алгоритм кластерування, який забезпечує вдосконалення опорновекторним машинам, називається опо́рнове́кторним кластерува́нням (),Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137. і його часто використовують у промислових застосуваннях, коли дані або не мічені, або коли мічені лише деякі дані як попередня обробка перед проходом класифікації.
Постановка задачі
В машинному навчанні поширеною задачею є класифікація даних. Розгляньмо деякі задані точки даних, кожна з яких належить до одного з двох класів, а метою є вирішувати, в якому класі буде нова точка даних. У випадку опорновекторних машин точку даних розглядають як -вимірний вектор (список чисел), і хочуть дізнатися, чи можливо розділити такі точки -вимірною гіперплощиною. Це називається лінійним класифікатором. Існує багато гіперплощин, які могли би розділяти одні й ті ж дані. Одним із варіантів розумного вибору найкращої гіперплощини є такий, який пропонує найбільший проміжок, або розділення () між двома класами. Тож ми обираємо гіперплощину таким чином, щоби відстань від неї до найближчих точок даних з кожного боку була максимальною. Така гіперплощина, якщо вона існує, відома як максимально розділова гіперплощина (), а лінійний класифікатор, що вона його визначає, — як максимально (); або, рівнозначно, як перцептрон оптимальної стабільності ()
Визначення
Формальніше, опорновекторна машина будує гіперплощину, або набір гіперплощин у просторі високої або нескінченної вимірності, які можна використовувати для класифікації, регресії та інших задач. Інтуїтивно, добре розділення досягається гіперплощиною, яка має найбільшу відстань до найближчих точок тренувальних даних будь-котрого з класів (так зване функційне розділення), оскільки в загальному випадку що більшим є розділення, то нижчою є похибка узагальнення класифікатора.
В той час, як первинну задачу може бути сформульовано у скінченновимірному просторі, часто трапляється так, що множини, які треба розрізнювати, не є лінійно роздільними в ньому. З цієї причини було запропоновано відображувати первинний скінченновимірний простір до простору набагато вищої вимірності, здогадно роблячи розділення простішим у тому просторі. Для збереження помірного обчислювального навантаження, відображення, які використовують у методі опорних векторів, розробляють такими, щоби забезпечувати можливість простого обчислення скалярних добутків у термінах змінних первинного простору, визначаючи їх у термінах , що їх обирають відповідно до задачі.* Гіперплощини в просторі вищої вимірності визначають як геометричне місце точок, скалярні добутки яких із вектором у цьому просторі сталі. Вектори, які визначають гіперплощини, можуть обиратися як лінійні комбінації з параметрами відображень векторів ознак , які трапляються в базі даних. За такого вибору гіперплощини, точки простору ознак, які відображаються на гіперплощину, визначаються відношенням Зауважте, що якщо стає малою з віддаленням від , то кожен член цієї суми вимірює ступінь близькості пробної точки до відповідних основних точок даних . Таким чином, наведена вище сума ядер може використовуватися для вимірювання відносної близькості кожної пробної точки до точок даних, які походять з однієї або іншої з множин, які треба розрізнювати. Зверніть увагу на той факт, що множина точок , відображена на будь-яку гіперплощину, може бути в результаті доволі вигнутою, уможливлюючи набагато складніше розрізнювання між множинами, які взагалі не є опуклими в первинному просторі.
Застосування
ОВМ можуть застосовуватися для розв'язання різноманітних практичних задач:
ОВМ корисні для категоризації текстів та гіпертекстів, бо їхнє застосування може значно знижувати потребу в мічених тренувальних зразках як у стандартній індуктивній, так і в постановках. Із застосуванням ОВМ може виконуватися й класифікація зображень. Експериментальні результати показують, що ОВМ можуть досягати значно вищої точності пошуку, ніж традиційні схеми уточнення запиту, всього лише після трьох-чотирьох раундів зворотного зв'язку про відповідність. Це є вірним і для систем сегментування зображень, включно з тими, які використовують видозмінену версію ОВМ, яка застосовує привілейований підхід, запропонований Вапником.Vapnik, V.: Invited Speaker. IPMU Information Processing and Management 2014) Barghout, Lauren. "Spatial-Taxon Information Granules as Used in Iterative Fuzzy-Decision-Making for Image Segmentation." Granular Computing and Decision-Making. Springer International Publishing, 2015. 285-318. За допомогою ОВМ може здійснюватися розпізнавання рукописних символів. Алгоритм ОВМ широко застосовують у біологічних та інших науках. Їх було використано для класифікації білків з правильною класифікацією до 90 % складу. Як механізм інтерпретування моделей ОВМ було запропоновано пермутаційний тест на основі вагових коефіцієнтів ОВМ.Bilwaj Gaonkar, Christos Davatzikos Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification R. Cuingnet, C. Rosso, M. Chupin, S. Lehéricy, D. Dormont, H. Benali, Y. Samson and O. Colliot, Spatial regularization of SVM for the detection of diffusion alterations associated with stroke outcome, Medical Image Analysis, 2011, 15 (5): 729–737 Вагові коефіцієнти опорновекторних машин використовувалися для інтерпретування моделей ОВМ і в минулому.Statnikov, A., Hardin, D., & Aliferis, C. (2006). Using SVM weight-based methods to identify causally relevant and non-causally relevant variables. sign, 1, 4. Ретроспективне інтерпретування моделей опорновекторних машин з метою ідентифікування ознак, які використовує модель для здійснення передбачень, є відносно новою областю досліджень з особливим значенням у біологічних науках.
Історія
Первинний алгоритм ОВМ було винайдено Володимиром Вапником та 1963 року. 1992 року , та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку. Поточне стандартне втілення (м'яке розділення) було запропоновано Корінною Кортес та Володимиром Вапником 1993 року й опубліковано 1995 року.
Лінійна ОВМ
В нас є тренувальний набір даних з точок вигляду
де є або 1, або -1, і кожен з них вказує клас, до якого належить точка . Кожен є -вимірним дійсним вектором. Нам потрібно знайти «максимально розділову гіперплощину», яка відділяє групу точок , для яких , від групи точок, для яких , і визначена таким чином, що відстань між цією гіперплощиною та найближчою точкою з кожної з груп максимальна.
Будь-яку гіперплощину може бути записано як множину точок , які задовольняють
де є (не обов'язково нормалізованим) вектором нормалі до цієї гіперплощини. Параметр визначає зсув гіперплощини від початку координат вздовж вектора нормалі .
Жорстке розділення
Якщо тренувальні дані лінійно роздільні, то ми можемо обрати дві паралельні гіперплощини, які розділяють два класи даних так, що відстань між ними якомога більша. Область, обмежену цими двома гіперплощинами, називають «розділенням» (), а максимально розділова гіперплощина це гіперплощина, яка лежить посередині між цими двома. Ці гіперплощини може бути описано рівняннями
(будь-що на або вище цієї межі належить до класу з міткою 1)
та
(будь-що на або нижче цієї межі належить до класу з міткою -1)
З геометричної точки зору, відстанню між цими двома гіперплощинами є , тож для максимізації відстані між ними нам треба мінімізувати . А що ми також маємо завадити потраплянню точок даних до розділення, ми додаємо таке обмеження: для кожного , або
якщо
або
якщо
Ці обмеження стверджують, що кожна точка даних мусить лежати з правильного боку розділення.
Ці дві нерівності можна записати як одну:
для всіх
Ми можемо зібрати це докупи, щоби отримати задачу оптимізації:
«Мінімізувати за умови для »
та , які розв'язують цю задачу, визначають наш класифікатор, .
Очевидним, але важливим наслідком цього геометричного опису є те, що максимально розділова гіперплощина повністю визначається тими , які лежать найближче до неї. Ці називають опорними векторами ().
М'яке розділення
Для розширення ОВМ на випадки, в яких дані не є лінійно роздільними, ми вводимо заві́сну функцію втрат (),
Зауважимо, що є i-ю цілю () (тобто, в нашому випадку, 1 або -1) та - поточний результат.
Ця функція нульова, якщо справджується обмеження в (1), іншими словами, якщо лежить із правильного боку розділення. Для даних із неправильного боку розділення значення цієї функції пропорційне відстані від розділення.
Тоді нам треба мінімізувати
де параметр визначає компроміс між збільшенням розміру розділення та забезпеченням того, що лежить із правильного боку розділення. Отже, для достатньо малих значень ОВМ із м'яким розділенням () поводитиметься так само, як ОВМ із жорстким розділенням (), якщо вхідні дані є лінійно класифіковними, але, тим не менше, вчитиметься життєздатного правила класифікації, якщо ні.
Нелінійна класифікація
Первинний алгоритм максимально розділової гіперплощини, запропонований Володимиром Вапником у 1963 році, будував лінійний класифікатор. Проте 1992 року , та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку (первинно запропонованого Айзерманом та ін. ). Отриманий алгоритм є формально аналогічним, за винятком того, що кожен скалярний добуток замінено нелінійною ядровою функцією. Це дозволяє алгоритмові узгоджувати максимально розділову гіперплощину в перетвореному просторі ознак. Перетворення може бути нелінійним, а перетворений простір — великої вимірності; хоч класифікатор і є гіперплощиною в перетвореному просторі ознак, у первинному вхідному просторі він може бути нелінійним.
Слід зазначити, що робота в просторі ознак високої вимірності збільшує похибку узагальнення опорновекторних машин, хоча за достатньої кількості зразків цей алгоритм все одно працює добре.
До деяких найпоширеніших ядер належать: Поліноміальне (однорідне): (неоднорідне): Ґаусова радіально-базисна функція: для . Іноді використовують , але частіше цей гіперпараметр підбирають з допомогою перехресного затверджування Сигмоїдне (гіперболічний тангенс): для деяких (не всіх) та
Ядро пов'язано з перетворенням через рівняння . Значення w також знаходиться в перетвореному просторі, з . Скалярні добутки з w для класифікації, знов-таки, може бути обчислювано за допомогою ядрового трюку, тобто, .
Обчислення ОВМ-класифікатора
Обчислення ОВМ-класифікатора (з м'яким розділенням) становить мінімізацію виразу вигляду