В машинному навчанні ме́тод опо́рних векторі́в — це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рно-ве́кторними маши́нами (ОВМ, англ. support vector machines, SVM, також опо́рно-ве́кторними мере́жами, англ. support vector networks). Для заданого набору тренувальних зразків, кожен із яких відмічено як належний до однієї чи іншої з двох категорій, алгоритм тренування ОВМ будує модель, яка відносить нові зразки до однієї чи іншої категорії, роблячи це неймовірнісним бінарним лінійним класифікатором. Модель ОВМ є представленням зразків як точок у просторі, відображених таким чином, що зразки з окремих категорій розділено чистою прогалиною, яка є щонайширшою. Нові зразки тоді відображуються до цього ж простору, й робиться передбачення про їхню належність до категорії на основі того, на який бік прогалини вони потрапляють.
На додачу до виконання лінійної класифікації, ОВМ можуть ефективно виконувати нелінійну класифікацію при застосуванні так званого ядрового трюку, неявно відображуючи свої входи до просторів ознак високої вимірності.
Коли дані не є міченими, кероване навчання є неможливим, і виникає необхідність у некерованому навчанні, яке намагається знайти природне кластерування даних на групи, а потім відображувати нові дані на ці сформовані групи. Алгоритм кластерування, який забезпечує вдосконалення опорно-векторним машинам, називається опо́рно-ве́кторним кластерува́нням (англ. support vector clustering), і часто використовується в промислових застосуваннях, коли дані або не є міченими, або коли лише деякі дані є міченими як попередня обробка перед проходом класифікації.
Постановка задачі
В машинному навчанні поширеною задачею є класифікація даних. Розгляньмо деякі задані точки даних, кожна з яких належить до одного з двох класів, а метою є вирішувати, в якому класі буде нова точка даних. У випадку опорно-векторних машин точку даних розглядають як -вимірний вектор (список чисел), і хочуть дізнатися, чи можливо розділити такі точки -вимірною гіперплощиною. Це називається лінійним класифікатором. Існує багато гіперплощин, які могли би розділяти одні й ті ж дані. Одним із варіантів розумного вибору найкращої гіперплощини є такий, який пропонує найбільший проміжок, або розділення (англ. margin) між двома класами. Тож ми обираємо гіперплощину таким чином, щоби відстань від неї до найближчих точок даних з кожного боку була максимальною. Така гіперплощина, якщо вона існує, відома як максимально розділова гіперплощина (англ. maximum-margin hyperplane), а лінійний класифікатор, що вона його визначає, — як максимально [en] (англ. maximum margin classifier); або, рівнозначно, як перцептрон оптимальної стабільності (англ. perceptron of optimal stability).[]
Визначення
Формальніше, опорно-векторна машина будує гіперплощину, або набір гіперплощин у просторі високої або нескінченної вимірності, які можна використовувати для класифікації, регресії та інших задач. Інтуїтивно, добре розділення досягається гіперплощиною, яка має найбільшу відстань до найближчих точок тренувальних даних будь-якого з класів (так зване функційне розділення), оскільки в загальному випадку що більшим є розділення, то нижчою є похибка узагальнення класифікатора.
В той час, як первинну задачу може бути сформульовано у скінченновимірному просторі, часто трапляється так, що множини, які треба розрізнювати, не є лінійно роздільними в ньому. З цієї причини було запропоновано відображувати первинний скінченновимірний простір до простору набагато вищої вимірності, здогадно роблячи розділення простішим у тому просторі. Для збереження помірного обчислювального навантаження, відображення, які використовуються методом опорних векторів, розробляють такими, щоби забезпечувати можливість простого обчислення скалярних добутків у термінах змінних первинного простору, визначаючи їх у термінах [en] , що їх обирають відповідно до задачі. Гіперплощини в просторі вищої вимірності визначаються як геометричне місце точок, чиї скалярні добутки з вектором у цьому просторі є сталими. Вектори, які визначають гіперплощини, можуть обиратися як лінійні комбінації з параметрами відображень векторів ознак , які трапляються в базі даних. За такого вибору гіперплощини, точки простору ознак, які відображаються на гіперплощину, визначаються відношенням Зауважте, що якщо стає малою з віддаленням від , то кожен член цієї суми вимірює ступінь близькості пробної точки до відповідних основних точок даних . Таким чином, наведена вище сума ядер може використовуватися для вимірювання відносної близькості кожної пробної точки до точок даних, які походять з однієї або іншої з множин, які треба розрізнювати. Зверніть увагу на той факт, що множина точок , відображена на будь-яку гіперплощину, може бути в результаті доволі вигнутою, уможливлюючи набагато складніше розрізнювання між множинами, які взагалі не є опуклими в первинному просторі.
Застосування
ОВМ можуть застосовуватися для розв'язання різноманітних практичних задач:
- ОВМ є корисними для категоризації текстів та гіпертекстів, оскільки їхнє застосування може значно знижувати потребу в мічених тренувальних зразках як у стандартній індуктивній, так і в [en] постановках.
- Із застосуванням ОВМ може виконуватися й класифікація зображень. Експериментальні результати показують, що ОВМ можуть досягати значно вищої точності пошуку, ніж традиційні схеми уточнення запиту, всього лише після трьох-чотирьох раундів зворотного зв'язку про відповідність. Це є вірним і для систем сегментування зображень, включно з тими, які використовують видозмінену версію ОВМ, яка застосовує привілейований підхід, запропонований Вапником.
- За допомогою ОВМ може здійснюватися розпізнавання рукописних символів.
- Алгоритм ОВМ широко застосовується в біологічних та інших науках. Їх було використано для класифікації білків з правильною класифікацією до 90 % складу. Як механізм інтерпретування моделей ОВМ було запропоновано пермутаційний тест на основі вагових коефіцієнтів ОВМ. Вагові коефіцієнти опорно-векторних машин використовувалися для інтерпретування моделей ОВМ і в минулому. Ретроспективне інтерпретування моделей опорно-векторних машин з метою ідентифікування ознак, які використовує модель для здійснення передбачень, є відносно новою областю досліджень з особливим значенням у біологічних науках.
Історія
Первинний алгоритм ОВМ було винайдено Володимиром Вапником та [en] 1963 року. 1992 року , та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку. Поточне стандартне втілення (м'яке розділення) було запропоновано Корінною Кортес та Володимиром Вапником 1993 року й опубліковано 1995 року.
Лінійна ОВМ
В нас є тренувальний набір даних з точок вигляду
де є або 1, або -1, і кожен з них вказує клас, до якого належить точка . Кожен є -вимірним дійсним вектором. Нам треба знайти «максимально розділову гіперплощину», яка відділяє групу точок , для яких , від групи точок, для яких , і визначається таким чином, що відстань між цією гіперплощиною та найближчою точкою з кожної з груп є максимальною.
Будь-яку гіперплощину може бути записано як множину точок , які задовольняють
де є (не обов'язково нормалізованим) вектором нормалі до цієї гіперплощини. Параметр визначає зсув гіперплощини від початку координат вздовж вектора нормалі .
Жорстке розділення
Якщо тренувальні дані лінійно роздільні, то ми можемо обрати дві паралельні гіперплощини, які розділяють два класи даних так, що відстань між ними якомога більша. Область, обмежена цими двома гіперплощинами, називається «розділенням» (англ. margin), а максимально розділова гіперплощина це гіперплощина, яка лежить посередині між цими двома. Ці гіперплощини може бути описано рівняннями
- (будь-що на або вище цієї межі належить до класу з міткою 1)
та
- (будь-що на або нижче цієї межі належить до класу з міткою -1)
З геометричної точки зору, відстанню між цими двома гіперплощинами є , тож для максимізації відстані між ними нам треба мінімізувати . Оскільки ми також маємо завадити потраплянню точок даних до розділення, ми додаємо таке обмеження: для кожного , або
- якщо
або
- якщо
Ці обмеження стверджують, що кожна точка даних мусить лежати з правильного боку розділення.
Ці дві нерівності можна записати як одну:
- для всіх
Ми можемо зібрати це докупи, щоби отримати задачу оптимізації:
- «Мінімізувати за умови для »
та , які розв'язують цю задачу, визначають наш класифікатор, .
Очевидним, але важливим наслідком цього геометричного опису є те, що максимально розділова гіперплощина повністю визначається тими , які лежать найближче до неї. Ці називають опорними векторами (англ. support vectors).
М'яке розділення
Для розширення ОВМ на випадки, в яких дані не є лінійно роздільними, ми вводимо заві́сну функцію втрат (англ. hinge loss function),
Зауважимо, що є i-ю цілю (англ. target) (тобто, в нашому випадку, 1 або -1) та - поточний результат.
Ця функція є нульовою, якщо обмеження в (1) задовольняється, іншими словами, якщо лежить із правильного боку розділення. Для даних із неправильного боку розділення значення цієї функції є пропорційним до відстані від розділення.
Тоді нам треба мінімізувати
де параметр визначає компроміс між збільшенням розміру розділення та забезпеченням того, що лежить із правильного боку розділення. Таким чином, для достатньо малих значень ОВМ із м'яким розділенням (англ. soft-margin SVM) поводитиметься однаково з ОВМ із жорстким розділенням (англ. hard-margin SVM), якщо вхідні дані є лінійно класифіковними, але, тим не менше, вчитиметься життєздатного правила класифікації, якщо ні.
Нелінійна класифікація
Первинний алгоритм максимально розділової гіперплощини, запропонований Володимиром Вапником у 1963 році, будував лінійний класифікатор. Проте 1992 року , та Володимир Вапник запропонували спосіб створювати нелінійні класифікатори шляхом застосування до максимально розділових гіперплощин ядрового трюку (первинно запропонованого Айзерманом та ін.). Отриманий алгоритм є формально аналогічним, за винятком того, що кожен скалярний добуток замінено нелінійною ядровою функцією. Це дозволяє алгоритмові узгоджувати максимально розділову гіперплощину в перетвореному просторі ознак. Перетворення може бути нелінійним, а перетворений простір — великої вимірності; хоч класифікатор і є гіперплощиною в перетвореному просторі ознак, у первинному вхідному просторі він може бути нелінійним.
Слід зазначити, що робота в просторі ознак високої вимірності збільшує похибку узагальнення опорно-векторних машин, хоча за достатньої кількості зразків цей алгоритм все одно працює добре.
До деяких найпоширеніших ядер належать:
- Поліноміальне (однорідне):
- [en] (неоднорідне):
- Ґаусова радіально-базисна функція: для . Іноді використовують , але частіше цей гіперпараметр підбирають з допомогою перехресного затверджування
- Сигмоїдне (гіперболічний тангенс): для деяких (не всіх) та
Ядро пов'язано з перетворенням через рівняння . Значення w також знаходиться в перетвореному просторі, з . Скалярні добутки з w для класифікації, знов-таки, може бути обчислювано за допомогою ядрового трюку, тобто, .
Обчислення ОВМ-класифікатора
Обчислення ОВМ-класифікатора (з м'яким розділенням) становить мінімізацію виразу вигляду
Ми зосереджуємося на класифікаторі з м'яким розділенням, оскільки, як зауважено вище, вибір достатньо малого значення для лінійно роздільних вхідних даних дає класифікатор із жорстким розділенням. Нижче описано класичний підхід, який включає зведення (2) до задачі квадратичного програмування. А потім буде обговорено сучасніші підходи, такі як субградієнтний та координатний спуск.
Пряме
Мінімізацію (2) може бути переписано як обмежену задачу оптимізації з диференційовною цільовою функцією наступним чином.
Для кожного ми вводимо змінну . Зверніть увагу, що є найменшим невід'ємним числом, яке задовольняє
Отже, ми можемо переписати задачу оптимізації таким чином:
- мінімізувати
- за умов та для всіх .
Це називається прямою задачею (англ. primal problem).
Двоїсте
Шляхом розв'язання лагранжевої двоїстості наведеної вище задачі отримується спрощена задача:
- максимізувати
- за умов та для всіх .
Це називається двоїстою задачею (англ. dual problem). Оскільки двоїста задача максимізації є квадратичною функцією з лінійними обмеженнями, вона є ефективно розв'язуваною алгоритмами квадратичного програмування.
Тут змінні визначено таким чином, що
- .
Крім того, саме тоді, коли лежить з правильного боку розділення, а коли лежить на межі розділення. З цього випливає, що може бути записано як лінійну комбінацію опорних векторів.
Зсув може бути з'ясовано знаходженням на межі розділення, і розв'язанням
(Зверніть увагу, що , оскільки .)
Ядровий трюк
Припустімо тепер, що ми хотіли би вчитися нелінійного правила класифікації, яке відповідає лінійному правилу класифікації для перетворених точок даних Крім того, в нас є ядрова функція , яка задовольняє .
Ми знаємо, що вектор класифікації у перетвореному просторі задовольняє
де отримуються розв'язанням задачі оптимізації
- мінімізувати
- за умов та для всіх .
Як і раніше, коефіцієнти може бути знайдено розв'язанням задачі квадратичного програмування. Знов-таки, ми можемо знайти такий індекс , що , так що лежить на межі розділення у перетвореному просторі, й тоді розв'язати
Нарешті, нові точки може бути класифіковано обчисленням
Сучасні методи
До сучасних алгоритмів знаходження ОВМ-класифікаторів належать субградієнтний та координатний спуск. Обидві методики довели, що вони пропонують значні переваги над традиційним підходом при роботі з великими, розрідженими наборами даних — субградієнтні методи є особливо дієвими, коли є багато тренувальних зразків, а координатний спуск — коли розмірність простору ознак є високою.
Субградієнтний спуск
Алгоритми субградієнтного спуску для ОВМ працюють безпосередньо з виразом
Зауважте, що є опуклою функцією та . Як такі, традиційні методи градієнтного (або стохастичного градієнтного) спуску може бути адаптовано, коли замість здійснення кроку в напрямку градієнту функції крок здійснюється в напрямку вектора, вибраного з субградієнту функції. Цей підхід має ту перевагу, що, для деяких реалізацій, число ітерацій не масштабується з , числом точок даних.
Координатний спуск
Алгоритми координатного спуску для ОВМ працюють над двоїстою задачею
- максимізувати
- за умов та для всіх .
Для кожного , ітеративно, коефіцієнт коригується в напрямку . Потім робиться проєкція отриманого вектора коефіцієнтів на найближчий вектор коефіцієнтів, який задовольняє задані обмеження. (Зазвичай застосовуються евклідові відстані.) Цей процес повторюється доти, поки не буде отримано вектор коефіцієнтів, близький до оптимального. Отриманий алгоритм є дуже швидким на практиці, хоча доведених гарантій продуктивності мало.
Мінімізація емпіричного ризику
Описана вище опорно-векторна машина з м'яким розділенням є прикладом алгоритму мінімізації емпіричного ризику (англ. empirical risk minimization, ERM) для заві́сних втрат (англ. hinge loss). При розгляді під цим кутом, опорно-векторі машини належать до природного класу алгоритмів статистичного висновування, і багато їхніх унікальних властивостей обумовлено поведінкою заві́сних втрат. Ця точка зору може запропонувати подальше розуміння того, як і чому ОВМ працюють, і дозволити нам краще моделювати їхні статистичні властивості.
Мінімізація ризику
У навчанні з підкріпленням задається набір тренувальних зразків із мітками , і потрібно передбачувати для заданого . Для здійснення цього формують гіпотезу, , таку, що є «добрим» наближенням . «Добре» наближення зазвичай визначається з допомогою функції втрат, , яка характеризує, наскільки поганим є як передбачення . Потім треба обрати гіпотезу, яка мінімізує очікуваний ризик:
В більшості випадків ми не знаємо спільного розподілу безпосередньо. В цих випадках загальною стратегією є обирати гіпотезу, яка мінімізує емпіричний ризик (англ. empirical risk):
За деяких припущень стосовно послідовності випадкових змінних (наприклад, що їх породжено скінченним марковським процесом), якщо множина гіпотез, що розглядаються, є достатньо малою, то мінімізатор емпіричного ризику близько наближуватиме мінімізатор очікуваного ризику зі зростанням . Цей підхід називається мінімізацією емпіричного ризику (англ. empirical risk minimization, ERM).
Регуляризація та стійкість
Щоби задача мінімізації мала добре визначений розв'язок, ми маємо накласти обмеження на множину гіпотез, які розглядаються. Якщо є нормованим простором (як у випадку ОВМ), то особливо дієвою методикою є розглядати лише ті гіпотези , для яких . Це рівнозначне накладенню регуляризаційного штрафу (англ. regularization penalty) , і розв'язанню нової задачі оптимізації
- .
Цей підхід називається регуляризацією Тихонова.
У загальнішому сенсі, може бути деякою мірою складності гіпотези , щоби перевага віддавалася простішим гіпотезам.
ОВМ та завісні втрати
Пригадайте, що ОВМ-класифікатор (із м'яким розділенням) обирається так, щоби мінімізувати наступний вираз.
Зважаючи на вищенаведене, видно, що методика ОВМ є рівнозначною мінімізації емпіричного ризику з регуляризацією Тихонова, де в цьому випадку функцією втрат є заві́сні втрати
З цієї точки зору ОВМ є тісно пов'язаними з іншими фундаментальними алгоритмами класифікації, такими як [en] та логістична регресія. Різниця між цими трьома полягає у виборі функції втрат: регуляризовані найменші квадрати зводяться до мінімізації емпіричного ризику з квадратичними втратами, , а логістична регресія використовує логістичні втрати, .
Цільові функції
Різниця між заві́сними втратами та цими іншими функціями втрат найкраще формулюється в термінах цільових функцій (англ. target functions) — функція, яка мінімізує очікуваний ризик для заданої пари випадкових змінних .
Зокрема, нехай позначає , обумовлений подією, що . У постановці класифікації ми маємо
з імовірністю з імовірністю
Отже, оптимальним класифікатором є
якщо інакше
Для квадратичних втрат цільовою функцією є функція умовного математичного сподівання, ; для логістичних втрат це логістична функція, . І хоча обидві ці функції видають правильний класифікатор, оскільки , вони дають нам більше інформації, ніж ми потребуємо. Фактично, вони дають нам достатньо інформації, щоби повністю описати розподіл .
З іншого боку, можна перевірити, що цільовою функцією заві́сних втрат є саме . Таким чином, у достатньо багатому просторі гіпотез, — або, рівнозначно, для правильно обраного ядра, — ОВМ-класифікатор збігатиметься до найпростішої функції (в термінах ), яка правильно класифікує дані. Це розширює геометричну інтерпретацію ОВМ — для лінійної класифікації емпіричний ризик мінімізується будь-якою функцією, чиї межі лежать між опорними векторами, і найпростішою з них є максимально розділовий класифікатор.
Властивості
ОВМ належать до сімейства узагальнених лінійних класифікаторів, і можуть бути інтерпретовані як розширення перцептрону. Їх також можна розглядати й як окремий випадок регуляризації Тихонова. Особливою властивістю є те, що вони одночасно мінімізують емпіричну похибку класифікації (англ. classification error), й максимізують геометричне розділення (англ. geometric margin); тому вони також відомі й як максимально [en] (англ. maximum margin classifiers).
Маєром, Лішем та Горником було зроблено порівняння ОМВ з іншими класифікаторами.
Вибір параметрів
Ефективність ОВМ залежить від вибору ядра, параметрів ядра та параметра м'якого розділення C. Поширеним вибором є ґаусове ядро, що має єдиний параметр . Найкращу комбінацію C та часто обирають (ґратковим пошуком) з послідовностями C та , які експоненційно зростають, наприклад, ; . Як правило, кожну комбінацію варіантів вибору параметрів перевіряють із застосуванням перехресного затверджування, й обирають параметри з найкращою точністю, показаною перехресним затверджуванням. Як альтернатива, для вибору C та може застосовуватися недавня робота в баєсовій оптимізації, яка часто потребує оцінки набагато меншого числа комбінацій параметрів, ніж ґратковий пошук. Потім остаточна модель, яка використовується для перевірки та класифікації даних, тренується на всьому тренувальному наборі із застосуванням обраних параметрів.
Проблеми
Потенційні недоліки ОВМ включають наступні аспекти:
- Вимагають повністю мічених вхідних даних
- Некалібровані ймовірності приналежності до класів
- ОВМ застосовні напряму лише до двокласових задач. Отже, мають застосовуватися алгоритми, які зводять багатокласову задачу до кількох бінарних задач; див. розділ багатокласові ОВМ.
- Інтерпретувати параметри розв'язаної моделі важко.
Розширення
Опорно-векторне кластерування
Опорно-векторне кластерування (англ. support vector clustering, SVC) — це подібний метод, який також будує ядрові функції, але підходить для некерованого навчання та добування даних. В науці про дані він вважається фундаментальним методом.
Багатокласові ОВМ
Багатокласові ОВМ (англ. multiclass SVM) спрямовані на призначення міток зразкам шляхом застосування опорно-векторних машин, де мітки вибираються зі скінченного набору з декількох елементів.
Панівним підходом до цього є зведення єдиної [en] до кількох задач бінарної класифікації. До поширених методів такого зведення належать:
- Побудова бінарних класифікаторів, що розрізняють (I) між однією з міток та рештою (один-проти-всіх, англ. one-versus-all) або (II) між кожною з пар класів (один-проти-одного, англ. one-versus-one). Класифікація нових зразків для випадку один-проти-всіх здійснюється за стратегією переможець-забирає-все, в якій класифікатор з найвищою вихідною функцією призначає клас (важливо, щоби вихідні функції було відкалібровано, щоби вони видавали порівнянні оцінки). Для підходу один-проти-одного класифікація здійснюється за стратегією голосування максимум-перемагає, в якій кожен з класифікаторів відносить зразок до одного з двох класів, тоді голос за призначений клас збільшується на одиницю, і остаточно клас із більшістю голосів визначає класифікацію зразка.
- ОВМ на орієнтованих ациклічних графах (англ. directed acyclic graph SVM, DAGSVM)
- Вихідні коди з виправленням похибки (англ. error-correcting output codes)
Краммер та Зінгер запропонували багатокласовий метод ОВМ, який зливає задачу багатокласової класифікації в єдину задачу оптимізації, замість розкладати її на кілька задач бінарної класифікації. Див. також Лі, Лін та Вахбу.
Трансдуктивні опорно-векторні машини
Трансдуктивні опорно-векторні машини розширюють ОВМ тим, що вони можуть також обробляти частково мічені дані в напівкерованому навчанні, дотримуючись принципів [en]. Тут, на додачу до тренувального набору , надається також набір
тестових зразків, які потрібно класифікувати. Формально, трансдуктивна опорно-векторна машина визначається наступною прямою задачею оптимізації:
Мінімізувати (за )
за умов (для всіх та всіх )
та
Трансдуктивні опорно-векторні машини було запропоновано Володимиром Вапником 1998 року.
Структурні ОВМ
ОВМ було узагальнено до [en] (англ. structured SVMs), у яких простір міток є структурним, і, можливо, нескінченного розміру.
Регресія
Версію ОВМ для регресії було запропоновано 1996 року Володимиром Вапником, Гаррісом Друкером, Крістофером Бургесом, Ліндою Кауфман та Олександром Смолою. Цей метод називається опорно-векторною регресією (ОВР, англ. support vector regression, SVR). Модель, яка виробляється опорно-векторною класифікацією (як описано вище) залежить лише від підмножини тренувальних даних, оскільки функція втрат для побудови моделі не зважає на тренувальні точки, які лежать за межами розділення. Аналогічно, модель, яка виробляється опорно-векторною регресією, залежить лише від підмножини тренувальних даних, оскільки функція втрат для побудови моделі ігнорує будь-які тренувальні дані, близькі до передбачення моделі. Іншу версію ОВМ, відому як [en] (англ. least squares support vector machine, LS-SVM), було запропоновано Сайкенсом та Вандервалле.
Тренування первинної ОВР означає розв'язання
- мінімізувати
- за умов
де є тренувальним зразком із цільовим значенням . Внутрішній добуток плюс відсікання є передбаченням для цього зразка, а є вільним параметром, що слугує порогом: всі передбачення мають бути в межах відстані від справжніх передбачень. Зазвичай до наведеного вище додають фіктивні змінні, щоби дозволити похибки та наближення в разі, якщо наведена вище задача є нездійсненною.
Реалізація
Параметри максимально розділової гіперплощини виводяться шляхом розв'язання задачі оптимізації. Існує кілька спеціалізованих алгоритмів для швидкого розв'язання задач КП, що виникають в ОВМ, вони здебільшого покладаються на евристики для розбиття задачі на менші підзадачі, з якими легше впоруватися.
Іншим підходом є застосування методу внутрішньої точки, який використовує ньютоно-подібні ітерації для пошуку розв'язку умов Каруша — Куна — Такера прямої та двоїстої задач. Замість розв'язання послідовності розбитих задач, цей підхід безпосередньо розв'язує задачу в цілому. Для уникнення розв'язання лінійної системи з великою ядровою матрицею в ядровому трюку часто використовується низькорангове наближення матриці.
Іншим поширеним методом є алгоритм послідовної мінімальної оптимізації Платта, який розбиває задачу на 2-вимірні підзадачі, які розв'язуються аналітично, усуваючи потребу в алгоритмі числової оптимізації та в зберіганні матриці. Цей алгоритм є простим концептуально, простим у реалізації, зазвичай швидшим, і має кращі властивості масштабування для складних задач ОВМ.
Окремий випадок лінійних опорно-векторних машин може розв'язуватися ефективніше алгоритмами того ж роду, що й використовуються для оптимізації їхнього близького родича, логістичної регресії; цей клас алгоритмів включає субградієнтний спуск (наприклад, PEGASOS) та координатний спуск (наприклад, LIBLINEAR). LIBLINEAR володіє деякими привабливими властивостями часу тренування. Кожна ітерація збіжності займає час, лінійний по відношенню до часу, витраченого на читання тренувальних даних, й ітерації також володіють властивістю Q-лінійної збіжності, що робить цей алгоритм надзвичайно швидким.
Звичайні ядрові ОВМ також можуть розв'язуватися ефективніше при застосуванні субградієнтного спуску (наприклад, P-packSVM), особливо якщо дозволено розпаралелювання.
Ядрові ОВМ доступні в багатьох інструментаріях машинного навчання, включно з LIBSVM, MATLAB, SAS, SVMlight, kernlab, scikit-learn, [en], Weka, Shark, JKernelMachines, OpenCV та іншими.
Див. також
- [en]
- Ядрові машини
- [en]
- [en]
- [en]
- [en]
- [en]
- Доречно-векторна машина, ймовірнісна розріджена ядрова модель, ідентична у функційному вигляді до ОВМ
- Послідовна мінімальна оптимізація
- Методологія картографування
- [en]
Примітки
- Cortes, C.; Vapnik, V. (1995). Support-vector networks. Machine Learning. 20 (3): 273—297. doi:10.1007/BF00994018. (англ.)
- Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137. (англ.)
- *Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, B. P. (2007). Section 16.5. Support Vector Machines. Numerical Recipes: The Art of Scientific Computing (вид. 3). New York: Cambridge University Press. ISBN . (англ.)
- 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. (англ.)
- 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. (англ.)
- Boser, B. E.; Guyon, I. M.; Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. Proceedings of the fifth annual workshop on Computational learning theory – COLT '92. с. 144. doi:10.1145/130385.130401. ISBN . (англ.)
- Why is the SVM margin equal to . Mathematics Stack Exchange. 30 травня 2015.
- Aizerman, Mark A.; Braverman, Emmanuel M.; Rozonoer, Lev I. (1964). Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control. 25: 821—837. (англ.)
- Jin, Chi; Wang, Liwei (2012). Dimensionality dependent PAC-Bayes margin bound. Advances in Neural Information Processing Systems. Архів оригіналу за 2 квітня 2015. Процитовано 29 жовтня 2016. (англ.)
- Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew (16 жовтня 2010). Pegasos: primal estimated sub-gradient solver for SVM. Mathematical Programming. 127 (1): 3—30. doi:10.1007/s10107-010-0420-4. ISSN 0025-5610. Архів оригіналу за 25 серпня 2016. Процитовано 29 жовтня 2016. (англ.)
- Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (1 січня 2008). A Dual Coordinate Descent Method for Large-scale Linear SVM. Proceedings of the 25th International Conference on Machine Learning. ICML '08. New York, NY, USA: ACM: 408—415. doi:10.1145/1390156.1390208. ISBN . (англ.)
- Rosasco, L; Vito, E; Caponnetto, A; Piana, M; Verri, A (1 травня 2004). Are Loss Functions All the Same?. Neural Computation. 16 (5): 1063—1076. doi:10.1162/089976604773135104. ISSN 0899-7667. PMID 15070510. (англ.)
- Meyer, D.; Leisch, F.; Hornik, K. (2003). The support vector machine under test. Neurocomputing. 55: 169. doi:10.1016/S0925-2312(03)00431-4. (англ.)
- Hsu, Chih-Wei; Chang, Chih-Chung; Lin, Chih-Jen (2003). A Practical Guide to Support Vector Classification (PDF) (Технічний звіт). Department of Computer Science and Information Engineering, National Taiwan University. Архів оригіналу (PDF) за 25 червня 2013. Процитовано 29 жовтня 2016.
{{}}
: Проігноровано невідомий параметр|last-author-amp=
() (англ.) - Duan, K. B.; Keerthi, S. S. (2005). Which Is the Best Multiclass SVM Method? An Empirical Study. Multiple Classifier Systems. [en]. Т. 3541. с. 278—285. doi:10.1007/11494683_28. ISBN . (англ.)
- Hsu, Chih-Wei; Lin, Chih-Jen (2002). A Comparison of Methods for Multiclass Support Vector Machines. IEEE Transactions on Neural Networks.
{{}}
: Проігноровано невідомий параметр|last-author-amp=
() (англ.) - Platt, John; [en]; and [en] (2000). Large margin DAGs for multiclass classification. У Solla, Sara A.; Leen, Todd K.; and Müller, Klaus-Robert; eds (ред.). Advances in Neural Information Processing Systems (PDF). MIT Press. с. 547—553. Архів оригіналу (PDF) за 16 червня 2012. Процитовано 29 жовтня 2016. (англ.)
- Dietterich, Thomas G.; and Bakiri, Ghulum; Bakiri (1995). Solving Multiclass Learning Problems via Error-Correcting Output Codes (PDF). Journal of Artificial Intelligence Research. 2: 263—286. arXiv:cs/9501101. Bibcode:1995cs........1101D. Архів оригіналу (PDF) за 9 травня 2013. Процитовано 29 жовтня 2016. (англ.)
- Crammer, Koby; Singer, Yoram (2001). On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines (PDF). Journal of Machine Learning Research. 2: 265—292. Архів оригіналу (PDF) за 29 серпня 2015. Процитовано 29 жовтня 2016.
{{}}
: Проігноровано невідомий параметр|last-author-amp=
() (англ.) - Lee, Y.; Lin, Y.; Wahba, G. (2001). Multicategory Support Vector Machines (PDF). Computing Science and Statistics. 33. Архів оригіналу (PDF) за 17 червня 2013. Процитовано 29 жовтня 2016.
{{}}
: Проігноровано невідомий параметр|last-author-amp=
() (англ.) - Lee, Y.; Lin, Y.; Wahba, G. (2004). Multicategory Support Vector Machines. Journal of the American Statistical Association. 99 (465): 67. doi:10.1198/016214504000000098. (англ.)
- Joachims, Thorsten; "Transductive Inference for Text Classification using Support Vector Machines", Proceedings of the 1999 International Conference on Machine Learning (ICML 1999), pp. 200–209. (англ.)
- Drucker, Harris; Burges, Christopher J. C.; Kaufman, Linda; Smola, Alexander J.; and Vapnik, Vladimir N. (1997); "Support Vector Regression Machines", in Advances in Neural Information Processing Systems 9, NIPS 1996, 155–161, MIT Press. (англ.)
- Suykens, Johan A. K.; Vandewalle, Joos P. L.; Least squares support vector machine classifiers, Neural Processing Letters, vol. 9, no. 3, Jun. 1999, pp. 293–300. (англ.)
- Smola, Alex J.; Schölkopf, Bernhard (2004). A tutorial on support vector regression (PDF). Statistics and Computing. 14 (3): 199—222. Архів оригіналу (PDF) за 31 січня 2012. Процитовано 29 жовтня 2016. (англ.)
- Ferris, M. C.; Munson, T. S. (2002). Interior-Point Methods for Massive Support Vector Machines. SIAM Journal on Optimization. 13 (3): 783. doi:10.1137/S1052623400374379. (англ.)
- John C. Platt (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (PDF). NIPS. Архів оригіналу (PDF) за 2 липня 2015. Процитовано 29 жовтня 2016. (англ.)
- Shai Shalev-Shwartz; Yoram Singer; Nathan Srebro (2007). Pegasos: Primal Estimated sub-GrAdient SOlver for SVM (PDF). ICML. Архів оригіналу (PDF) за 15 грудня 2013. Процитовано 29 жовтня 2016. (англ.)
- R.-E. Fan; K.-W. Chang; C.-J. Hsieh; X.-R. Wang; C.-J. Lin (2008). LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research. 9: 1871—1874. (англ.)
- Zeyuan Allen Zhu та ін. (2009). P-packSVM: Parallel Primal grAdient desCent Kernel SVM (PDF). ICDM. Архів оригіналу (PDF) за 7 квітня 2014. Процитовано 29 жовтня 2016. (англ.)
Література
- Theodoridis, Sergios; and Koutroumbas, Konstantinos; "Pattern Recognition", 4th Edition, Academic Press, 2009, (англ.)
- Nello Cristianini, John Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. — Cambridge University Press, 2000. — . (книга про ОВМ) (англ.)
- 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, (англ.)
- 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. (англ.)
- Schölkopf, Bernhard; Burges, Christopher J. C.; and Smola, Alexander J. (editors); Advances in Kernel Methods: Support Vector Learning, MIT Press, Cambridge, MA, 1999. . (англ.)
- Shawe-Taylor, John; and Cristianini, Nello; Kernel Methods for Pattern Analysis, Cambridge University Press, 2004. (крига про ядрові методи) (англ.)
- Steinwart, Ingo; and Christmann, Andreas; Support Vector Machines, Springer-Verlag, New York, 2008. (книга про ОВМ) (англ.)
- 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. (англ.)
- Vapnik, Vladimir N.; and Kotz, Samuel; Estimation of Dependences Based on Empirical Data, Springer, 2006. , 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. . (англ.)
- Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137. (англ.)
- Владимир Вьюгин. Математические основы машинного обучения и прогнозирования. — МЦМНО, 2014. — 304 с. — . (рос.)
- Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. A Gentle Introduction to Support Vector Machines in Biomedicine: Theory and methods. — World Scientific, 2011. — . (англ.)
- 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 — бібліотека машинного навчання , яка реалізує різні типи ОВМ
- dlib — бібліотека C++ для роботи з ядровими методами та ОВМ
- SVM light — збірка програмних інструментів для навчання та класифікації із застосуванням ОВМ
- SVMJS live demo — ГІК-демонстрація реалізації ОВМ на JavaScript
- Gesture Recognition Toolkit містить зручну для застосування обгортку для libsvm
- Data Mining. 10. Лекция: Методы классификации и прогнозирования. Метод опорных векторов // [ru] (рос.)
- Юрий Лифшиц. Метод опорных векторов (Слайды) — лекция № 7 из курса «Алгоритмы для Интернета» (рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V mashinnomu navchanni me tod opo rnih vektori v ce metod analizu danih dlya klasifikaciyi ta regresijnogo analizu za dopomogoyu modelej z kerovanim navchannyam z pov yazanimi algoritmami navchannya yaki nazivayutsya opo rno ve ktornimi mashi nami OVM angl support vector machines SVM takozh opo rno ve ktornimi mere zhami angl support vector networks 1 Dlya zadanogo naboru trenuvalnih zrazkiv kozhen iz yakih vidmicheno yak nalezhnij do odniyeyi chi inshoyi z dvoh kategorij algoritm trenuvannya OVM buduye model yaka vidnosit novi zrazki do odniyeyi chi inshoyi kategoriyi roblyachi ce nejmovirnisnim binarnim linijnim klasifikatorom Model OVM ye predstavlennyam zrazkiv yak tochok u prostori vidobrazhenih takim chinom sho zrazki z okremih kategorij rozdileno chistoyu progalinoyu yaka ye shonajshirshoyu Novi zrazki todi vidobrazhuyutsya do cogo zh prostoru j robitsya peredbachennya pro yihnyu nalezhnist do kategoriyi na osnovi togo na yakij bik progalini voni potraplyayut Na dodachu do vikonannya linijnoyi klasifikaciyi OVM mozhut efektivno vikonuvati nelinijnu klasifikaciyu pri zastosuvanni tak zvanogo yadrovogo tryuku neyavno vidobrazhuyuchi svoyi vhodi do prostoriv oznak visokoyi vimirnosti Koli dani ne ye michenimi kerovane navchannya ye nemozhlivim i vinikaye neobhidnist u nekerovanomu navchanni yake namagayetsya znajti prirodne klasteruvannya danih na grupi a potim vidobrazhuvati novi dani na ci sformovani grupi Algoritm klasteruvannya yakij zabezpechuye vdoskonalennya oporno vektornim mashinam nazivayetsya opo rno ve ktornim klasteruva nnyam angl support vector clustering 2 i chasto vikoristovuyetsya v promislovih zastosuvannyah koli dani abo ne ye michenimi abo koli lishe deyaki dani ye michenimi yak poperednya obrobka pered prohodom klasifikaciyi Zmist 1 Postanovka zadachi 2 Viznachennya 3 Zastosuvannya 4 Istoriya 5 Linijna OVM 5 1 Zhorstke rozdilennya 5 2 M yake rozdilennya 6 Nelinijna klasifikaciya 7 Obchislennya OVM klasifikatora 7 1 Pryame 7 2 Dvoyiste 7 3 Yadrovij tryuk 7 4 Suchasni metodi 7 4 1 Subgradiyentnij spusk 7 4 2 Koordinatnij spusk 8 Minimizaciya empirichnogo riziku 8 1 Minimizaciya riziku 8 2 Regulyarizaciya ta stijkist 8 3 OVM ta zavisni vtrati 8 3 1 Cilovi funkciyi 9 Vlastivosti 9 1 Vibir parametriv 9 2 Problemi 10 Rozshirennya 10 1 Oporno vektorne klasteruvannya 10 2 Bagatoklasovi OVM 10 3 Transduktivni oporno vektorni mashini 10 4 Strukturni OVM 10 5 Regresiya 11 Realizaciya 12 Div takozh 13 Primitki 14 Literatura 15 PosilannyaPostanovka zadachired nbsp H1 ne rozdilyaye ci klasi H2 rozdilyaye ale lishe z nevelikim rozdilennyam H3 rozdilyaye yih iz maksimalnim rozdilennyam V mashinnomu navchanni poshirenoyu zadacheyu ye klasifikaciya danih Rozglyanmo deyaki zadani tochki danih kozhna z yakih nalezhit do odnogo z dvoh klasiv a metoyu ye virishuvati v yakomu klasi bude nova tochka danih U vipadku oporno vektornih mashin tochku danih rozglyadayut yak p displaystyle p nbsp vimirnij vektor spisok p displaystyle p nbsp chisel i hochut diznatisya chi mozhlivo rozdiliti taki tochki p 1 displaystyle p 1 nbsp vimirnoyu giperploshinoyu Ce nazivayetsya linijnim klasifikatorom Isnuye bagato giperploshin yaki mogli bi rozdilyati odni j ti zh dani Odnim iz variantiv rozumnogo viboru najkrashoyi giperploshini ye takij yakij proponuye najbilshij promizhok abo rozdilennya angl margin mizh dvoma klasami Tozh mi obirayemo giperploshinu takim chinom shobi vidstan vid neyi do najblizhchih tochok danih z kozhnogo boku bula maksimalnoyu Taka giperploshina yaksho vona isnuye vidoma yak maksimalno rozdilova giperploshina angl maximum margin hyperplane a linijnij klasifikator sho vona jogo viznachaye yak maksimalno rozdilovij klasifikator en angl maximum margin classifier abo rivnoznachno yak perceptron optimalnoyi stabilnosti angl perceptron of optimal stability dzherelo Viznachennyared Formalnishe oporno vektorna mashina buduye giperploshinu abo nabir giperploshin u prostori visokoyi abo neskinchennoyi vimirnosti yaki mozhna vikoristovuvati dlya klasifikaciyi regresiyi ta inshih zadach Intuyitivno dobre rozdilennya dosyagayetsya giperploshinoyu yaka maye najbilshu vidstan do najblizhchih tochok trenuvalnih danih bud yakogo z klasiv tak zvane funkcijne rozdilennya oskilki v zagalnomu vipadku sho bilshim ye rozdilennya to nizhchoyu ye pohibka uzagalnennya klasifikatora nbsp Yadrova mashina V toj chas yak pervinnu zadachu mozhe buti sformulovano u skinchennovimirnomu prostori chasto traplyayetsya tak sho mnozhini yaki treba rozriznyuvati ne ye linijno rozdilnimi v nomu Z ciyeyi prichini bulo zaproponovano vidobrazhuvati pervinnij skinchennovimirnij prostir do prostoru nabagato vishoyi vimirnosti zdogadno roblyachi rozdilennya prostishim u tomu prostori Dlya zberezhennya pomirnogo obchislyuvalnogo navantazhennya vidobrazhennya yaki vikoristovuyutsya metodom opornih vektoriv rozroblyayut takimi shobi zabezpechuvati mozhlivist prostogo obchislennya skalyarnih dobutkiv u terminah zminnih pervinnogo prostoru viznachayuchi yih u terminah yadrovih funkcij en k x y displaystyle k x y nbsp sho yih obirayut vidpovidno do zadachi 3 Giperploshini v prostori vishoyi vimirnosti viznachayutsya yak geometrichne misce tochok chiyi skalyarni dobutki z vektorom u comu prostori ye stalimi Vektori yaki viznachayut giperploshini mozhut obiratisya yak linijni kombinaciyi z parametrami a i displaystyle alpha i nbsp vidobrazhen vektoriv oznak x i displaystyle x i nbsp yaki traplyayutsya v bazi danih Za takogo viboru giperploshini tochki x displaystyle x nbsp prostoru oznak yaki vidobrazhayutsya na giperploshinu viznachayutsya vidnoshennyam i a i k x i x c o n s t a n t displaystyle textstyle sum i alpha i k x i x mathrm constant nbsp Zauvazhte sho yaksho k x y displaystyle k x y nbsp staye maloyu z viddalennyam y displaystyle y nbsp vid x displaystyle x nbsp to kozhen chlen ciyeyi sumi vimiryuye stupin blizkosti probnoyi tochki x displaystyle x nbsp do vidpovidnih osnovnih tochok danih x i displaystyle x i nbsp Takim chinom navedena vishe suma yader mozhe vikoristovuvatisya dlya vimiryuvannya vidnosnoyi blizkosti kozhnoyi probnoyi tochki do tochok danih yaki pohodyat z odniyeyi abo inshoyi z mnozhin yaki treba rozriznyuvati Zvernit uvagu na toj fakt sho mnozhina tochok x displaystyle x nbsp vidobrazhena na bud yaku giperploshinu mozhe buti v rezultati dovoli vignutoyu umozhlivlyuyuchi nabagato skladnishe rozriznyuvannya mizh mnozhinami yaki vzagali ne ye opuklimi v pervinnomu prostori Zastosuvannyared OVM mozhut zastosovuvatisya dlya rozv yazannya riznomanitnih praktichnih zadach OVM ye korisnimi dlya kategorizaciyi tekstiv ta gipertekstiv oskilki yihnye zastosuvannya mozhe znachno znizhuvati potrebu v michenih trenuvalnih zrazkah yak u standartnij induktivnij tak i v transduktivnij en postanovkah Iz zastosuvannyam OVM mozhe vikonuvatisya j klasifikaciya zobrazhen Eksperimentalni rezultati pokazuyut sho OVM mozhut dosyagati znachno vishoyi tochnosti poshuku nizh tradicijni shemi utochnennya zapitu vsogo lishe pislya troh chotiroh raundiv zvorotnogo zv yazku pro vidpovidnist Ce ye virnim i dlya sistem segmentuvannya zobrazhen vklyuchno z timi yaki vikoristovuyut vidozminenu versiyu OVM yaka zastosovuye privilejovanij pidhid zaproponovanij Vapnikom 4 5 Za dopomogoyu OVM mozhe zdijsnyuvatisya rozpiznavannya rukopisnih simvoliv Algoritm OVM shiroko zastosovuyetsya v biologichnih ta inshih naukah Yih bulo vikoristano dlya klasifikaciyi bilkiv z pravilnoyu klasifikaciyeyu do 90 skladu Yak mehanizm interpretuvannya modelej OVM bulo zaproponovano permutacijnij test na osnovi vagovih koeficiyentiv OVM 6 7 Vagovi koeficiyenti oporno vektornih mashin vikoristovuvalisya dlya interpretuvannya modelej OVM i v minulomu 8 Retrospektivne interpretuvannya modelej oporno vektornih mashin z metoyu identifikuvannya oznak yaki vikoristovuye model dlya zdijsnennya peredbachen ye vidnosno novoyu oblastyu doslidzhen z osoblivim znachennyam u biologichnih naukah Istoriyared Pervinnij algoritm OVM bulo vinajdeno Volodimirom Vapnikom ta Oleksiyem Chervonenkisom en 1963 roku 1992 roku Bernhard Boser Izabel Gijon ta Volodimir Vapnik zaproponuvali sposib stvoryuvati nelinijni klasifikatori shlyahom zastosuvannya do maksimalno rozdilovih giperploshin yadrovogo tryuku 9 Potochne standartne vtilennya m yake rozdilennya bulo zaproponovano Korinnoyu Kortes ta Volodimirom Vapnikom 1993 roku j opublikovano 1995 roku 1 Linijna OVMred V nas ye trenuvalnij nabir danih z n displaystyle n nbsp tochok viglyadu x 1 y 1 x n y n displaystyle vec x 1 y 1 ldots vec x n y n nbsp de y i displaystyle y i nbsp ye abo 1 abo 1 i kozhen z nih vkazuye klas do yakogo nalezhit tochka x i displaystyle vec x i nbsp Kozhen x i displaystyle vec x i nbsp ye p displaystyle p nbsp vimirnim dijsnim vektorom Nam treba znajti maksimalno rozdilovu giperploshinu yaka viddilyaye grupu tochok x i displaystyle vec x i nbsp dlya yakih y i 1 displaystyle y i 1 nbsp vid grupi tochok dlya yakih y i 1 displaystyle y i 1 nbsp i viznachayetsya takim chinom sho vidstan mizh ciyeyu giperploshinoyu ta najblizhchoyu tochkoyu x i displaystyle vec x i nbsp z kozhnoyi z grup ye maksimalnoyu Bud yaku giperploshinu mozhe buti zapisano yak mnozhinu tochok x displaystyle vec x nbsp yaki zadovolnyayut w x b 0 displaystyle vec w cdot vec x b 0 nbsp de w displaystyle vec w nbsp ye ne obov yazkovo normalizovanim vektorom normali do ciyeyi giperploshini Parametr b w displaystyle tfrac b vec w nbsp viznachaye zsuv giperploshini vid pochatku koordinat vzdovzh vektora normali w displaystyle vec w nbsp Zhorstke rozdilennyared nbsp Maksimalno rozdilova giperploshina ta mezhi dlya OVM natrenovanoyi zrazkami z dvoh klasiv Zrazki na mezhah nazivayutsya opornimi vektorami Yaksho trenuvalni dani linijno rozdilni to mi mozhemo obrati dvi paralelni giperploshini yaki rozdilyayut dva klasi danih tak sho vidstan mizh nimi yakomoga bilsha Oblast obmezhena cimi dvoma giperploshinami nazivayetsya rozdilennyam angl margin a maksimalno rozdilova giperploshina ce giperploshina yaka lezhit poseredini mizh cimi dvoma Ci giperploshini mozhe buti opisano rivnyannyami w x b 1 displaystyle vec w cdot vec x b 1 nbsp bud sho na abo vishe ciyeyi mezhi nalezhit do klasu z mitkoyu 1 ta w x b 1 displaystyle vec w cdot vec x b 1 nbsp bud sho na abo nizhche ciyeyi mezhi nalezhit do klasu z mitkoyu 1 Z geometrichnoyi tochki zoru vidstannyu mizh cimi dvoma giperploshinami ye 2 w displaystyle tfrac 2 vec w nbsp 10 tozh dlya maksimizaciyi vidstani mizh nimi nam treba minimizuvati w displaystyle vec w nbsp Oskilki mi takozh mayemo zavaditi potraplyannyu tochok danih do rozdilennya mi dodayemo take obmezhennya dlya kozhnogo i displaystyle i nbsp abo w x i b 1 displaystyle vec w cdot vec x i b geqslant 1 nbsp yaksho y i 1 displaystyle y i 1 nbsp abo w x i b 1 displaystyle vec w cdot vec x i b leqslant 1 nbsp yaksho y i 1 displaystyle y i 1 nbsp Ci obmezhennya stverdzhuyut sho kozhna tochka danih musit lezhati z pravilnogo boku rozdilennya Ci dvi nerivnosti mozhna zapisati yak odnu y i w x i b 1 displaystyle y i vec w cdot vec x i b geqslant 1 quad nbsp dlya vsih 1 i n 1 displaystyle 1 geqslant i geqslant n qquad qquad 1 nbsp Mi mozhemo zibrati ce dokupi shobi otrimati zadachu optimizaciyi Minimizuvati w displaystyle vec w nbsp za umovi y i w x i b 1 displaystyle y i vec w cdot vec x i b geqslant 1 nbsp dlya i 1 n displaystyle i 1 ldots n nbsp w displaystyle vec w nbsp ta b displaystyle b nbsp yaki rozv yazuyut cyu zadachu viznachayut nash klasifikator x sgn w x b displaystyle vec x mapsto operatorname sgn vec w cdot vec x b nbsp Ochevidnim ale vazhlivim naslidkom cogo geometrichnogo opisu ye te sho maksimalno rozdilova giperploshina povnistyu viznachayetsya timi x i displaystyle vec x i nbsp yaki lezhat najblizhche do neyi Ci x i displaystyle vec x i nbsp nazivayut opornimi vektorami angl support vectors M yake rozdilennyared Dlya rozshirennya OVM na vipadki v yakih dani ne ye linijno rozdilnimi mi vvodimo zavi snu funkciyu vtrat angl hinge loss function max 0 1 y i w x i b displaystyle max left 0 1 y i vec w cdot vec x i b right nbsp Zauvazhimo sho y i displaystyle y i nbsp ye i yu cilyu angl target tobto v nashomu vipadku 1 abo 1 ta w x i b displaystyle vec w cdot vec x i b nbsp potochnij rezultat Cya funkciya ye nulovoyu yaksho obmezhennya v 1 zadovolnyayetsya inshimi slovami yaksho x i displaystyle vec x i nbsp lezhit iz pravilnogo boku rozdilennya Dlya danih iz nepravilnogo boku rozdilennya znachennya ciyeyi funkciyi ye proporcijnim do vidstani vid rozdilennya Todi nam treba minimizuvati 1 n i 1 n max 0 1 y i w x i b l w 2 displaystyle 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 nbsp de parametr l displaystyle lambda nbsp viznachaye kompromis mizh zbilshennyam rozmiru rozdilennya ta zabezpechennyam togo sho x i displaystyle vec x i nbsp lezhit iz pravilnogo boku rozdilennya Takim chinom dlya dostatno malih znachen l displaystyle lambda nbsp OVM iz m yakim rozdilennyam angl soft margin SVM povoditimetsya odnakovo z OVM iz zhorstkim rozdilennyam angl hard margin SVM yaksho vhidni dani ye linijno klasifikovnimi ale tim ne menshe vchitimetsya zhittyezdatnogo pravila klasifikaciyi yaksho ni Nelinijna klasifikaciyared nbsp Yadrova mashina Pervinnij algoritm maksimalno rozdilovoyi giperploshini zaproponovanij Volodimirom Vapnikom u 1963 roci buduvav linijnij klasifikator Prote 1992 roku Bernhard Boser Izabel Gijon ta Volodimir Vapnik zaproponuvali sposib stvoryuvati nelinijni klasifikatori shlyahom zastosuvannya do maksimalno rozdilovih giperploshin yadrovogo tryuku pervinno zaproponovanogo Ajzermanom ta in 11 9 Otrimanij algoritm ye formalno analogichnim za vinyatkom togo sho kozhen skalyarnij dobutok zamineno nelinijnoyu yadrovoyu funkciyeyu Ce dozvolyaye algoritmovi uzgodzhuvati maksimalno rozdilovu giperploshinu v peretvorenomu prostori oznak Peretvorennya mozhe buti nelinijnim a peretvorenij prostir velikoyi vimirnosti hoch klasifikator i ye giperploshinoyu v peretvorenomu prostori oznak u pervinnomu vhidnomu prostori vin mozhe buti nelinijnim Slid zaznachiti sho robota v prostori oznak visokoyi vimirnosti zbilshuye pohibku uzagalnennya oporno vektornih mashin hocha za dostatnoyi kilkosti zrazkiv cej algoritm vse odno pracyuye dobre 12 Do deyakih najposhirenishih yader nalezhat Polinomialne odnoridne k x i x j x i x j d displaystyle k left vec x i vec x j right left vec x i cdot vec x j right d nbsp Polinomialne en neodnoridne k x i x j x i x j 1 d displaystyle k left vec x i vec x j right left vec x i cdot vec x j 1 right d nbsp Gausova radialno bazisna funkciya k x i x j exp g x i x j 2 displaystyle k left vec x i vec x j right exp left gamma left vec x i vec x j right 2 right nbsp dlya g gt 0 displaystyle gamma gt 0 nbsp Inodi vikoristovuyut g 1 2 s 2 displaystyle gamma dfrac 1 2 sigma 2 nbsp ale chastishe cej giperparametr pidbirayut z dopomogoyu perehresnogo zatverdzhuvannya Sigmoyidne giperbolichnij tangens k x i x j tanh k x i x j c displaystyle k left vec x i vec x j right tanh left kappa vec x i cdot vec x j c right nbsp dlya deyakih ne vsih k gt 0 displaystyle kappa gt 0 nbsp ta c lt 0 displaystyle c lt 0 nbsp Yadro pov yazano z peretvorennyam f x i displaystyle varphi left vec x i right nbsp cherez rivnyannya k x i x j f x i f x j displaystyle k left vec x i vec x j right varphi left vec x i right cdot varphi left vec x j right nbsp Znachennya w takozh znahoditsya v peretvorenomu prostori z w i a i y i f x i displaystyle textstyle vec w displaystyle sum limits i alpha i y i varphi left vec x i right nbsp Skalyarni dobutki z w dlya klasifikaciyi znov taki mozhe buti obchislyuvano za dopomogoyu yadrovogo tryuku tobto w f x i a i y i k x i x displaystyle 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 nbsp Obchislennya OVM klasifikatorared Obchislennya OVM klasifikatora z m yakim rozdilennyam stanovit minimizaciyu virazu viglyadu 1 n i 1 n max 0 1 y i w x i b l w 2 2 displaystyle 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 nbsp Mi zoseredzhuyemosya na klasifikatori z m yakim rozdilennyam oskilki yak zauvazheno vishe vibir dostatno malogo znachennya l displaystyle lambda nbsp dlya linijno rozdilnih vhidnih danih daye klasifikator iz zhorstkim rozdilennyam Nizhche opisano klasichnij pidhid yakij vklyuchaye zvedennya 2 do zadachi kvadratichnogo programuvannya A potim bude obgovoreno suchasnishi pidhodi taki yak subgradiyentnij ta koordinatnij spusk Pryamered Minimizaciyu 2 mozhe buti perepisano yak obmezhenu zadachu optimizaciyi z diferencijovnoyu cilovoyu funkciyeyu nastupnim chinom Dlya kozhnogo i 1 n displaystyle i in 1 ldots n nbsp mi vvodimo zminnu z i max 0 1 y i w x i b displaystyle zeta i max left 0 1 y i w cdot x i b right nbsp Zvernit uvagu sho z i displaystyle zeta i nbsp ye najmenshim nevid yemnim chislom yake zadovolnyaye y i w x i b 1 z i displaystyle y i w cdot x i b geq 1 zeta i nbsp Otzhe mi mozhemo perepisati zadachu optimizaciyi takim chinom minimizuvati 1 n i 1 n z i l w 2 displaystyle frac 1 n sum i 1 n zeta i lambda w 2 nbsp za umov y i x i w b 1 z i displaystyle y i x i cdot w b geq 1 zeta i nbsp ta z i 0 displaystyle zeta i geq 0 nbsp dlya vsih i displaystyle i nbsp Ce nazivayetsya pryamoyu zadacheyu angl primal problem Dvoyistered Shlyahom rozv yazannya lagranzhevoyi dvoyistosti navedenoyi vishe zadachi otrimuyetsya sproshena zadacha maksimizuvati f c 1 c n i 1 n c i 1 2 i 1 n j 1 n y i c i x i x j y j c j displaystyle 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 nbsp za umov i 1 n c i y i 0 displaystyle sum i 1 n c i y i 0 nbsp ta 0 c i 1 2 n l displaystyle 0 leq c i leq frac 1 2n lambda nbsp dlya vsih i displaystyle i nbsp Ce nazivayetsya dvoyistoyu zadacheyu angl dual problem Oskilki dvoyista zadacha maksimizaciyi ye kvadratichnoyu funkciyeyu c i displaystyle c i nbsp z linijnimi obmezhennyami vona ye efektivno rozv yazuvanoyu algoritmami kvadratichnogo programuvannya Tut zminni c i displaystyle c i nbsp viznacheno takim chinom sho w i 1 n c i y i x i displaystyle vec w sum i 1 n c i y i vec x i nbsp Krim togo c i 0 displaystyle c i 0 nbsp same todi koli x i displaystyle vec x i nbsp lezhit z pravilnogo boku rozdilennya a 0 lt c i lt 2 n l 1 displaystyle 0 lt c i lt 2n lambda 1 nbsp koli x i displaystyle vec x i nbsp lezhit na mezhi rozdilennya Z cogo viplivaye sho w displaystyle vec w nbsp mozhe buti zapisano yak linijnu kombinaciyu opornih vektoriv Zsuv b displaystyle b nbsp mozhe buti z yasovano znahodzhennyam x i displaystyle vec x i nbsp na mezhi rozdilennya i rozv yazannyam y i w x i b 1 b y i w x i displaystyle y i vec w cdot vec x i b 1 iff b y i vec w cdot vec x i nbsp Zvernit uvagu sho y i 1 y i displaystyle y i 1 y i nbsp oskilki y i 1 displaystyle y i pm 1 nbsp Yadrovij tryukred Pripustimo teper sho mi hotili bi vchitisya nelinijnogo pravila klasifikaciyi yake vidpovidaye linijnomu pravilu klasifikaciyi dlya peretvorenih tochok danih f x i displaystyle varphi vec x i nbsp Krim togo v nas ye yadrova funkciya k displaystyle k nbsp yaka zadovolnyaye k x i x j f x i f x j displaystyle k vec x i vec x j varphi vec x i cdot varphi vec x j nbsp Mi znayemo sho vektor klasifikaciyi w displaystyle vec w nbsp u peretvorenomu prostori zadovolnyaye w i 1 n c i y i f x i displaystyle vec w sum i 1 n c i y i varphi vec x i nbsp de c i displaystyle c i nbsp otrimuyutsya rozv yazannyam zadachi optimizaciyi minimizuvati f c 1 c n i 1 n c i 1 2 i 1 n j 1 n y i c i f x i f x j y j c j i 1 n c i 1 2 i 1 n j 1 n y i c i k x i x j y j c j displaystyle begin aligned f c 1 ldots c n amp 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 amp 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 nbsp za umov i 1 n c i y i 0 displaystyle sum i 1 n c i y i 0 nbsp ta 0 c i 1 2 n l displaystyle 0 leq c i leq frac 1 2n lambda nbsp dlya vsih i displaystyle i nbsp Yak i ranishe koeficiyenti c i displaystyle c i nbsp mozhe buti znajdeno rozv yazannyam zadachi kvadratichnogo programuvannya Znov taki mi mozhemo znajti takij indeks i displaystyle i nbsp sho 0 lt c i lt 2 n l 1 displaystyle 0 lt c i lt 2n lambda 1 nbsp tak sho f x i displaystyle varphi vec x i nbsp lezhit na mezhi rozdilennya u peretvorenomu prostori j todi rozv yazati b w f x i y i k 1 n c k y k f x k f x i y i k 1 n c k y k k x k x i y i displaystyle begin aligned b vec w cdot varphi vec x i y i amp left sum k 1 n c k y k varphi vec x k cdot varphi vec x i right y i amp left sum k 1 n c k y k k vec x k vec x i right y i end aligned nbsp Nareshti novi tochki mozhe buti klasifikovano obchislennyam z sgn w f z b sgn i 1 n c i y i k x i z b displaystyle 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 nbsp Suchasni metodired Do suchasnih algoritmiv znahodzhennya OVM klasifikatoriv nalezhat subgradiyentnij ta koordinatnij spusk Obidvi metodiki doveli sho voni proponuyut znachni perevagi nad tradicijnim pidhodom pri roboti z velikimi rozridzhenimi naborami danih subgradiyentni metodi ye osoblivo diyevimi koli ye bagato trenuvalnih zrazkiv a koordinatnij spusk koli rozmirnist prostoru oznak ye visokoyu Subgradiyentnij spuskred Algoritmi subgradiyentnogo spusku dlya OVM pracyuyut bezposeredno z virazom f w b 1 n i 1 n max 0 1 y i w x i b l w 2 displaystyle 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 nbsp Zauvazhte sho f displaystyle f nbsp ye opukloyu funkciyeyu w displaystyle vec w nbsp ta b displaystyle b nbsp Yak taki tradicijni metodi gradiyentnogo abo stohastichnogo gradiyentnogo spusku mozhe buti adaptovano koli zamist zdijsnennya kroku v napryamku gradiyentu funkciyi krok zdijsnyuyetsya v napryamku vektora vibranogo z subgradiyentu funkciyi Cej pidhid maye tu perevagu sho dlya deyakih realizacij chislo iteracij ne masshtabuyetsya z n displaystyle n nbsp chislom tochok danih 13 Koordinatnij spuskred Algoritmi koordinatnogo spusku dlya OVM pracyuyut nad dvoyistoyu zadacheyu maksimizuvati f c 1 c n i 1 n c i 1 2 i 1 n j 1 n y i c i x i x j y j c j displaystyle 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 nbsp za umov i 1 n c i y i 0 displaystyle sum i 1 n c i y i 0 nbsp ta 0 c i 1 2 n l displaystyle 0 leq c i leq frac 1 2n lambda nbsp dlya vsih i displaystyle i nbsp Dlya kozhnogo i 1 n displaystyle i in 1 ldots n nbsp iterativno koeficiyent c i displaystyle c i nbsp koriguyetsya v napryamku f c i displaystyle partial f partial c i nbsp Potim robitsya proyekciya otrimanogo vektora koeficiyentiv c 1 c n displaystyle c 1 ldots c n nbsp na najblizhchij vektor koeficiyentiv yakij zadovolnyaye zadani obmezhennya Zazvichaj zastosovuyutsya evklidovi vidstani Cej proces povtoryuyetsya doti poki ne bude otrimano vektor koeficiyentiv blizkij do optimalnogo Otrimanij algoritm ye duzhe shvidkim na praktici hocha dovedenih garantij produktivnosti malo 14 Minimizaciya empirichnogo rizikured Opisana vishe oporno vektorna mashina z m yakim rozdilennyam ye prikladom algoritmu minimizaciyi empirichnogo riziku angl empirical risk minimization ERM dlya zavi snih vtrat angl hinge loss Pri rozglyadi pid cim kutom oporno vektori mashini nalezhat do prirodnogo klasu algoritmiv statistichnogo visnovuvannya i bagato yihnih unikalnih vlastivostej obumovleno povedinkoyu zavi snih vtrat Cya tochka zoru mozhe zaproponuvati podalshe rozuminnya togo yak i chomu OVM pracyuyut i dozvoliti nam krashe modelyuvati yihni statistichni vlastivosti Minimizaciya rizikured U navchanni z pidkriplennyam zadayetsya nabir trenuvalnih zrazkiv X 1 X n displaystyle X 1 ldots X n nbsp iz mitkami y 1 y n displaystyle y 1 ldots y n nbsp i potribno peredbachuvati y n 1 displaystyle y n 1 nbsp dlya zadanogo X n 1 displaystyle X n 1 nbsp Dlya zdijsnennya cogo formuyut gipotezu f displaystyle f nbsp taku sho f X n 1 displaystyle f X n 1 nbsp ye dobrim nablizhennyam y n 1 displaystyle y n 1 nbsp Dobre nablizhennya zazvichaj viznachayetsya z dopomogoyu funkciyi vtrat ℓ y z displaystyle ell y z nbsp yaka harakterizuye naskilki poganim ye z displaystyle z nbsp yak peredbachennya y displaystyle y nbsp Potim treba obrati gipotezu yaka minimizuye ochikuvanij rizik e f E ℓ y n 1 f X n 1 displaystyle varepsilon f mathbb E left ell y n 1 f X n 1 right nbsp V bilshosti vipadkiv mi ne znayemo spilnogo rozpodilu X n 1 y n 1 displaystyle X n 1 y n 1 nbsp bezposeredno V cih vipadkah zagalnoyu strategiyeyu ye obirati gipotezu yaka minimizuye empirichnij rizik angl empirical risk e f 1 n k 1 n ℓ y k f X k displaystyle hat varepsilon f frac 1 n sum k 1 n ell y k f X k nbsp Za deyakih pripushen stosovno poslidovnosti vipadkovih zminnih X k y k displaystyle X k y k nbsp napriklad sho yih porodzheno skinchennim markovskim procesom yaksho mnozhina gipotez sho rozglyadayutsya ye dostatno maloyu to minimizator empirichnogo riziku blizko nablizhuvatime minimizator ochikuvanogo riziku zi zrostannyam n displaystyle n nbsp Cej pidhid nazivayetsya minimizaciyeyu empirichnogo riziku angl empirical risk minimization ERM Regulyarizaciya ta stijkistred Shobi zadacha minimizaciyi mala dobre viznachenij rozv yazok mi mayemo naklasti obmezhennya na mnozhinu H displaystyle mathcal H nbsp gipotez yaki rozglyadayutsya Yaksho H displaystyle mathcal H nbsp ye normovanim prostorom yak u vipadku OVM to osoblivo diyevoyu metodikoyu ye rozglyadati lishe ti gipotezi f displaystyle f nbsp dlya yakih f H lt k displaystyle lVert f rVert mathcal H lt k nbsp Ce rivnoznachne nakladennyu regulyarizacijnogo shtrafu angl regularization penalty R f l k f H displaystyle mathcal R f lambda k lVert f rVert mathcal H nbsp i rozv yazannyu novoyi zadachi optimizaciyi f a r g min f H e f R f displaystyle hat f mathrm arg min f in mathcal H hat varepsilon f mathcal R f nbsp Cej pidhid nazivayetsya regulyarizaciyeyu Tihonova U zagalnishomu sensi R f displaystyle mathcal R f nbsp mozhe buti deyakoyu miroyu skladnosti gipotezi f displaystyle f nbsp shobi perevaga viddavalasya prostishim gipotezam OVM ta zavisni vtratired Prigadajte sho OVM klasifikator iz m yakim rozdilennyam w b x sgn w x b displaystyle hat w b x mapsto operatorname sgn hat w cdot x b nbsp obirayetsya tak shobi minimizuvati nastupnij viraz 1 n i 1 n max 0 1 y i w x i b l w 2 displaystyle 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 nbsp Zvazhayuchi na vishenavedene vidno sho metodika OVM ye rivnoznachnoyu minimizaciyi empirichnogo riziku z regulyarizaciyeyu Tihonova de v comu vipadku funkciyeyu vtrat ye zavi sni vtrati ℓ y z max 0 1 y z displaystyle ell y z max left 0 1 yz right nbsp Z ciyeyi tochki zoru OVM ye tisno pov yazanimi z inshimi fundamentalnimi algoritmami klasifikaciyi takimi yak regulyarizovani najmenshi kvadrati en ta logistichna regresiya Riznicya mizh cimi troma polyagaye u vibori funkciyi vtrat regulyarizovani najmenshi kvadrati zvodyatsya do minimizaciyi empirichnogo riziku z kvadratichnimi vtratami ℓ s q y z y z 2 displaystyle ell sq y z y z 2 nbsp a logistichna regresiya vikoristovuye logistichni vtrati ℓ log y z ln 1 e y z displaystyle ell log y z ln 1 e yz nbsp Cilovi funkciyired Riznicya mizh zavi snimi vtratami ta cimi inshimi funkciyami vtrat najkrashe formulyuyetsya v terminah cilovih funkcij angl target functions funkciya yaka minimizuye ochikuvanij rizik dlya zadanoyi pari vipadkovih zminnih X y displaystyle X y nbsp Zokrema nehaj y x displaystyle y x nbsp poznachaye y displaystyle y nbsp obumovlenij podiyeyu sho X x displaystyle X x nbsp U postanovci klasifikaciyi mi mayemo y x 1 1 displaystyle y x begin cases 1 1 end cases nbsp z imovirnistyu p x displaystyle p x nbsp z imovirnistyu 1 p x displaystyle 1 p x nbsp Otzhe optimalnim klasifikatorom ye f x 1 1 displaystyle f x begin cases 1 1 end cases nbsp yaksho p x 1 2 displaystyle p x geq 1 2 nbsp inakshe Dlya kvadratichnih vtrat cilovoyu funkciyeyu ye funkciya umovnogo matematichnogo spodivannya f s q x E y x displaystyle f sq x mathbb E left y x right nbsp dlya logistichnih vtrat ce logistichna funkciya f log x ln p x 1 p x displaystyle f log x ln left p x 1 p x right nbsp I hocha obidvi ci funkciyi vidayut pravilnij klasifikator oskilki sgn f s q sgn f log f displaystyle operatorname sgn f sq operatorname sgn f log f nbsp voni dayut nam bilshe informaciyi nizh mi potrebuyemo Faktichno voni dayut nam dostatno informaciyi shobi povnistyu opisati rozpodil y x displaystyle y x nbsp Z inshogo boku mozhna pereviriti sho cilovoyu funkciyeyu zavi snih vtrat ye same f displaystyle f nbsp Takim chinom u dostatno bagatomu prostori gipotez abo rivnoznachno dlya pravilno obranogo yadra OVM klasifikator zbigatimetsya do najprostishoyi funkciyi v terminah R displaystyle mathcal R nbsp yaka pravilno klasifikuye dani Ce rozshiryuye geometrichnu interpretaciyu OVM dlya linijnoyi klasifikaciyi empirichnij rizik minimizuyetsya bud yakoyu funkciyeyu chiyi mezhi lezhat mizh opornimi vektorami i najprostishoyu z nih ye maksimalno rozdilovij klasifikator 15 Vlastivostired OVM nalezhat do simejstva uzagalnenih linijnih klasifikatoriv i mozhut buti interpretovani yak rozshirennya perceptronu Yih takozh mozhna rozglyadati j yak okremij vipadok regulyarizaciyi Tihonova Osoblivoyu vlastivistyu ye te sho voni odnochasno minimizuyut empirichnu pohibku klasifikaciyi angl classification error j maksimizuyut geometrichne rozdilennya angl geometric margin tomu voni takozh vidomi j yak maksimalno rozdilovi klasifikatori en angl maximum margin classifiers Mayerom Lishem ta Gornikom bulo zrobleno porivnyannya OMV z inshimi klasifikatorami 16 Vibir parametrivred Efektivnist OVM zalezhit vid viboru yadra parametriv yadra ta parametra m yakogo rozdilennya C Poshirenim viborom ye gausove yadro sho maye yedinij parametr g displaystyle gamma nbsp Najkrashu kombinaciyu C ta g displaystyle gamma nbsp chasto obirayut gratkovim poshukom z poslidovnostyami C ta g displaystyle gamma nbsp yaki eksponencijno zrostayut napriklad C 2 5 2 3 2 13 2 15 displaystyle C in 2 5 2 3 dots 2 13 2 15 nbsp g 2 15 2 13 2 1 2 3 displaystyle gamma in 2 15 2 13 dots 2 1 2 3 nbsp Yak pravilo kozhnu kombinaciyu variantiv viboru parametriv pereviryayut iz zastosuvannyam perehresnogo zatverdzhuvannya j obirayut parametri z najkrashoyu tochnistyu pokazanoyu perehresnim zatverdzhuvannyam Yak alternativa dlya viboru C ta g displaystyle gamma nbsp mozhe zastosovuvatisya nedavnya robota v bayesovij optimizaciyi yaka chasto potrebuye ocinki nabagato menshogo chisla kombinacij parametriv nizh gratkovij poshuk Potim ostatochna model yaka vikoristovuyetsya dlya perevirki ta klasifikaciyi danih trenuyetsya na vsomu trenuvalnomu nabori iz zastosuvannyam obranih parametriv 17 Problemired Potencijni nedoliki OVM vklyuchayut nastupni aspekti Vimagayut povnistyu michenih vhidnih danih Nekalibrovani jmovirnosti prinalezhnosti do klasiv OVM zastosovni napryamu lishe do dvoklasovih zadach Otzhe mayut zastosovuvatisya algoritmi yaki zvodyat bagatoklasovu zadachu do kilkoh binarnih zadach div rozdil bagatoklasovi OVM Interpretuvati parametri rozv yazanoyi modeli vazhko Rozshirennyared Oporno vektorne klasteruvannyared Oporno vektorne klasteruvannya angl support vector clustering SVC ce podibnij metod yakij takozh buduye yadrovi funkciyi ale pidhodit dlya nekerovanogo navchannya ta dobuvannya danih V nauci pro dani vin vvazhayetsya fundamentalnim metodom Bagatoklasovi OVMred Bagatoklasovi OVM angl multiclass SVM spryamovani na priznachennya mitok zrazkam shlyahom zastosuvannya oporno vektornih mashin de mitki vibirayutsya zi skinchennogo naboru z dekilkoh elementiv Panivnim pidhodom do cogo ye zvedennya yedinoyi bagatoklasovoyi zadachi en do kilkoh zadach binarnoyi klasifikaciyi 18 Do poshirenih metodiv takogo zvedennya nalezhat 18 19 Pobudova binarnih klasifikatoriv sho rozriznyayut I mizh odniyeyu z mitok ta reshtoyu odin proti vsih angl one versus all abo II mizh kozhnoyu z par klasiv odin proti odnogo angl one versus one Klasifikaciya novih zrazkiv dlya vipadku odin proti vsih zdijsnyuyetsya za strategiyeyu peremozhec zabiraye vse v yakij klasifikator z najvishoyu vihidnoyu funkciyeyu priznachaye klas vazhlivo shobi vihidni funkciyi bulo vidkalibrovano shobi voni vidavali porivnyanni ocinki Dlya pidhodu odin proti odnogo klasifikaciya zdijsnyuyetsya za strategiyeyu golosuvannya maksimum peremagaye v yakij kozhen z klasifikatoriv vidnosit zrazok do odnogo z dvoh klasiv todi golos za priznachenij klas zbilshuyetsya na odinicyu i ostatochno klas iz bilshistyu golosiv viznachaye klasifikaciyu zrazka OVM na oriyentovanih aciklichnih grafah angl directed acyclic graph SVM DAGSVM 20 Vihidni kodi z vipravlennyam pohibki angl error correcting output codes 21 Krammer ta Zinger zaproponuvali bagatoklasovij metod OVM yakij zlivaye zadachu bagatoklasovoyi klasifikaciyi v yedinu zadachu optimizaciyi zamist rozkladati yiyi na kilka zadach binarnoyi klasifikaciyi 22 Div takozh Li Lin ta Vahbu 23 24 Transduktivni oporno vektorni mashinired Transduktivni oporno vektorni mashini rozshiryuyut OVM tim sho voni mozhut takozh obroblyati chastkovo micheni dani v napivkerovanomu navchanni dotrimuyuchis principiv transdukciyi en Tut na dodachu do trenuvalnogo naboru D displaystyle mathcal D nbsp nadayetsya takozh nabir D x i x i R p i 1 k displaystyle mathcal D star vec x i star mid vec x i star in mathbb R p i 1 k nbsp testovih zrazkiv yaki potribno klasifikuvati Formalno transduktivna oporno vektorna mashina viznachayetsya nastupnoyu pryamoyu zadacheyu optimizaciyi 25 Minimizuvati za w b y displaystyle vec w b vec y star nbsp 1 2 w 2 displaystyle frac 1 2 vec w 2 nbsp za umov dlya vsih i 1 n displaystyle i 1 dots n nbsp ta vsih j 1 k displaystyle j 1 dots k nbsp y i w x i b 1 displaystyle y i vec w cdot vec x i b geq 1 nbsp y j w x j b 1 displaystyle y j star vec w cdot vec x j star b geq 1 nbsp ta y j 1 1 displaystyle y j star in 1 1 nbsp Transduktivni oporno vektorni mashini bulo zaproponovano Volodimirom Vapnikom 1998 roku Strukturni OVMred OVM bulo uzagalneno do strukturnih OVM en angl structured SVMs u yakih prostir mitok ye strukturnim i mozhlivo neskinchennogo rozmiru Regresiyared Versiyu OVM dlya regresiyi bulo zaproponovano 1996 roku Volodimirom Vapnikom Garrisom Drukerom Kristoferom Burgesom Lindoyu Kaufman ta Oleksandrom Smoloyu 26 Cej metod nazivayetsya oporno vektornoyu regresiyeyu OVR angl support vector regression SVR Model yaka viroblyayetsya oporno vektornoyu klasifikaciyeyu yak opisano vishe zalezhit lishe vid pidmnozhini trenuvalnih danih oskilki funkciya vtrat dlya pobudovi modeli ne zvazhaye na trenuvalni tochki yaki lezhat za mezhami rozdilennya Analogichno model yaka viroblyayetsya oporno vektornoyu regresiyeyu zalezhit lishe vid pidmnozhini trenuvalnih danih oskilki funkciya vtrat dlya pobudovi modeli ignoruye bud yaki trenuvalni dani blizki do peredbachennya modeli Inshu versiyu OVM vidomu yak oporno vektorna mashina najmenshih kvadrativ en angl least squares support vector machine LS SVM bulo zaproponovano Sajkensom ta Vandervalle 27 Trenuvannya pervinnoyi OVR oznachaye rozv yazannya 28 minimizuvati 1 2 w 2 displaystyle frac 1 2 w 2 nbsp za umov y i w x i b e w x i b y i e displaystyle begin cases y i langle w x i rangle b leq varepsilon langle w x i rangle b y i leq varepsilon end cases nbsp de x i displaystyle x i nbsp ye trenuvalnim zrazkom iz cilovim znachennyam y i displaystyle y i nbsp Vnutrishnij dobutok plyus vidsikannya w x i b displaystyle langle w x i rangle b nbsp ye peredbachennyam dlya cogo zrazka a e displaystyle varepsilon nbsp ye vilnim parametrom sho sluguye porogom vsi peredbachennya mayut buti v mezhah vidstani e displaystyle varepsilon nbsp vid spravzhnih peredbachen Zazvichaj do navedenogo vishe dodayut fiktivni zminni shobi dozvoliti pohibki ta nablizhennya v razi yaksho navedena vishe zadacha ye nezdijsnennoyu Realizaciyared Parametri maksimalno rozdilovoyi giperploshini vivodyatsya shlyahom rozv yazannya zadachi optimizaciyi Isnuye kilka specializovanih algoritmiv dlya shvidkogo rozv yazannya zadach KP sho vinikayut v OVM voni zdebilshogo pokladayutsya na evristiki dlya rozbittya zadachi na menshi pidzadachi z yakimi legshe vporuvatisya Inshim pidhodom ye zastosuvannya metodu vnutrishnoyi tochki yakij vikoristovuye nyutono podibni iteraciyi dlya poshuku rozv yazku umov Karusha Kuna Takera pryamoyi ta dvoyistoyi zadach 29 Zamist rozv yazannya poslidovnosti rozbitih zadach cej pidhid bezposeredno rozv yazuye zadachu v cilomu Dlya uniknennya rozv yazannya linijnoyi sistemi z velikoyu yadrovoyu matriceyu v yadrovomu tryuku chasto vikoristovuyetsya nizkorangove nablizhennya matrici Inshim poshirenim metodom ye algoritm poslidovnoyi minimalnoyi optimizaciyi Platta yakij rozbivaye zadachu na 2 vimirni pidzadachi yaki rozv yazuyutsya analitichno usuvayuchi potrebu v algoritmi chislovoyi optimizaciyi ta v zberiganni matrici Cej algoritm ye prostim konceptualno prostim u realizaciyi zazvichaj shvidshim i maye krashi vlastivosti masshtabuvannya dlya skladnih zadach OVM 30 Okremij vipadok linijnih oporno vektornih mashin mozhe rozv yazuvatisya efektivnishe algoritmami togo zh rodu sho j vikoristovuyutsya dlya optimizaciyi yihnogo blizkogo rodicha logistichnoyi regresiyi cej klas algoritmiv vklyuchaye subgradiyentnij spusk napriklad PEGASOS 31 ta koordinatnij spusk napriklad LIBLINEAR 32 LIBLINEAR volodiye deyakimi privablivimi vlastivostyami chasu trenuvannya Kozhna iteraciya zbizhnosti zajmaye chas linijnij po vidnoshennyu do chasu vitrachenogo na chitannya trenuvalnih danih j iteraciyi takozh volodiyut vlastivistyu Q linijnoyi zbizhnosti sho robit cej algoritm nadzvichajno shvidkim Zvichajni yadrovi OVM takozh mozhut rozv yazuvatisya efektivnishe pri zastosuvanni subgradiyentnogo spusku napriklad P packSVM 33 osoblivo yaksho dozvoleno rozparalelyuvannya Yadrovi OVM dostupni v bagatoh instrumentariyah mashinnogo navchannya vklyuchno z LIBSVM MATLAB SAS SVMlight kernlab scikit learn Shogun en Weka Shark JKernelMachines OpenCV ta inshimi Div takozhred Adaptivne tabulyuvannya na misci en Yadrovi mashini Yadro Fishera en Masshtabuvannya Platta en Polinomialne yadro en Peredbachuvalna analitika en Perspektivi regulyarizaciyi na oporno vektornih mashinah en Dorechno vektorna mashina jmovirnisna rozridzhena yadrova model identichna u funkcijnomu viglyadi do OVM Poslidovna minimalna optimizaciya Metodologiya kartografuvannya Winnow algoritm en Primitkired a b Cortes C Vapnik V 1995 Support vector networks Machine Learning 20 3 273 297 doi 10 1007 BF00994018 angl Ben Hur Asa Horn David Siegelmann Hava and Vapnik Vladimir Support vector clustering 2001 Journal of Machine Learning Research 2 125 137 angl Press William H Teukolsky Saul A Vetterling William T Flannery B P 2007 Section 16 5 Support Vector Machines Numerical Recipes The Art of Scientific Computing vid 3 New York Cambridge University Press ISBN 978 0 521 88068 8 angl Vapnik V Invited Speaker IPMU Information Processing and Management 2014 angl 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 angl Bilwaj Gaonkar Christos Davatzikos Analytic estimation of statistical significance maps for support vector machine based multi variate image analysis and classification angl R Cuingnet C Rosso M Chupin S Lehericy 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 angl Statnikov A Hardin D amp Aliferis C 2006 Using SVM weight based methods to identify causally relevant and non causally relevant variables sign 1 4 angl a b Boser B E Guyon I M Vapnik V N 1992 A training algorithm for optimal margin classifiers Proceedings of the fifth annual workshop on Computational learning theory COLT 92 s 144 doi 10 1145 130385 130401 ISBN 089791497X angl Why is the SVM margin equal to 2 w displaystyle frac 2 mathbf w nbsp Mathematics Stack Exchange 30 travnya 2015 Aizerman Mark A Braverman Emmanuel M Rozonoer Lev I 1964 Theoretical foundations of the potential function method in pattern recognition learning Automation and Remote Control 25 821 837 angl Jin Chi Wang Liwei 2012 Dimensionality dependent PAC Bayes margin bound Advances in Neural Information Processing Systems Arhiv originalu za 2 kvitnya 2015 Procitovano 29 zhovtnya 2016 angl Shalev Shwartz Shai Singer Yoram Srebro Nathan Cotter Andrew 16 zhovtnya 2010 Pegasos primal estimated sub gradient solver for SVM Mathematical Programming 127 1 3 30 doi 10 1007 s10107 010 0420 4 ISSN 0025 5610 Arhiv originalu za 25 serpnya 2016 Procitovano 29 zhovtnya 2016 angl Hsieh Cho Jui Chang Kai Wei Lin Chih Jen Keerthi S Sathiya Sundararajan S 1 sichnya 2008 A Dual Coordinate Descent Method for Large scale Linear SVM Proceedings of the 25th International Conference on Machine Learning ICML 08 New York NY USA ACM 408 415 doi 10 1145 1390156 1390208 ISBN 978 1 60558 205 4 angl Rosasco L Vito E Caponnetto A Piana M Verri A 1 travnya 2004 Are Loss Functions All the Same Neural Computation 16 5 1063 1076 doi 10 1162 089976604773135104 ISSN 0899 7667 PMID 15070510 angl Meyer D Leisch F Hornik K 2003 The support vector machine under test Neurocomputing 55 169 doi 10 1016 S0925 2312 03 00431 4 angl Hsu Chih Wei Chang Chih Chung Lin Chih Jen 2003 A Practical Guide to Support Vector Classification PDF Tehnichnij zvit Department of Computer Science and Information Engineering National Taiwan University Arhiv originalu PDF za 25 chervnya 2013 Procitovano 29 zhovtnya 2016 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite tech report title Shablon Cite tech report cite tech report a Proignorovano nevidomij parametr last author amp dovidka angl a b Duan K B Keerthi S S 2005 Which Is the Best Multiclass SVM Method An Empirical Study Multiple Classifier Systems LNCS en T 3541 s 278 285 doi 10 1007 11494683 28 ISBN 978 3 540 26306 7 angl Hsu Chih Wei Lin Chih Jen 2002 A Comparison of Methods for Multiclass Support Vector Machines IEEE Transactions on Neural Networks a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Proignorovano nevidomij parametr last author amp dovidka angl Platt John Cristianini N en and Shawe Taylor J en 2000 Large margin DAGs for multiclass classification U Solla Sara A Leen Todd K and Muller Klaus Robert eds red Advances in Neural Information Processing Systems PDF MIT Press s 547 553 Arhiv originalu PDF za 16 chervnya 2012 Procitovano 29 zhovtnya 2016 angl Dietterich Thomas G and Bakiri Ghulum Bakiri 1995 Solving Multiclass Learning Problems via Error Correcting Output Codes PDF Journal of Artificial Intelligence Research 2 263 286 arXiv cs 9501101 Bibcode 1995cs 1101D Arhiv originalu PDF za 9 travnya 2013 Procitovano 29 zhovtnya 2016 angl Crammer Koby Singer Yoram 2001 On the Algorithmic Implementation of Multiclass Kernel based Vector Machines PDF Journal of Machine Learning Research 2 265 292 Arhiv originalu PDF za 29 serpnya 2015 Procitovano 29 zhovtnya 2016 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Proignorovano nevidomij parametr last author amp dovidka angl Lee Y Lin Y Wahba G 2001 Multicategory Support Vector Machines PDF Computing Science and Statistics 33 Arhiv originalu PDF za 17 chervnya 2013 Procitovano 29 zhovtnya 2016 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Proignorovano nevidomij parametr last author amp dovidka angl Lee Y Lin Y Wahba G 2004 Multicategory Support Vector Machines Journal of the American Statistical Association 99 465 67 doi 10 1198 016214504000000098 angl Joachims Thorsten Transductive Inference for Text Classification using Support Vector Machines Proceedings of the 1999 International Conference on Machine Learning ICML 1999 pp 200 209 angl Drucker Harris Burges Christopher J C Kaufman Linda Smola Alexander J and Vapnik Vladimir N 1997 Support Vector Regression Machines in Advances in Neural Information Processing Systems 9 NIPS 1996 155 161 MIT Press angl Suykens Johan A K Vandewalle Joos P L Least squares support vector machine classifiers Neural Processing Letters vol 9 no 3 Jun 1999 pp 293 300 angl Smola Alex J Scholkopf Bernhard 2004 A tutorial on support vector regression PDF Statistics and Computing 14 3 199 222 Arhiv originalu PDF za 31 sichnya 2012 Procitovano 29 zhovtnya 2016 angl Ferris M C Munson T S 2002 Interior Point Methods for Massive Support Vector Machines SIAM Journal on Optimization 13 3 783 doi 10 1137 S1052623400374379 angl John C Platt 1998 Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines PDF NIPS Arhiv originalu PDF za 2 lipnya 2015 Procitovano 29 zhovtnya 2016 angl Shai Shalev Shwartz Yoram Singer Nathan Srebro 2007 Pegasos Primal Estimated sub GrAdient SOlver for SVM PDF ICML Arhiv originalu PDF za 15 grudnya 2013 Procitovano 29 zhovtnya 2016 angl R E Fan K W Chang C J Hsieh X R Wang C J Lin 2008 LIBLINEAR A library for large linear classification Journal of Machine Learning Research 9 1871 1874 angl Zeyuan Allen Zhu ta in 2009 P packSVM Parallel Primal grAdient desCent Kernel SVM PDF ICDM Arhiv originalu PDF za 7 kvitnya 2014 Procitovano 29 zhovtnya 2016 angl Literaturared Theodoridis Sergios and Koutroumbas Konstantinos Pattern Recognition 4th Edition Academic Press 2009 ISBN 978 1 59749 272 0 angl 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 kniga pro OVM angl 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 angl Kecman Vojislav Learning and Soft Computing Support Vector Machines Neural Networks Fuzzy Logic Systems The MIT Press Cambridge MA 2001 angl Scholkopf Bernhard and Smola Alexander J Learning with Kernels MIT Press Cambridge MA 2002 ISBN 0 262 19475 9 angl Scholkopf 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 angl Shawe Taylor John and Cristianini Nello Kernel Methods for Pattern Analysis Cambridge University Press 2004 ISBN 0 521 81397 2 kriga pro yadrovi metodi angl Steinwart Ingo and Christmann Andreas Support Vector Machines Springer Verlag New York 2008 ISBN 978 0 387 77241 7 kniga pro OVM angl 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 Cya pracya vikoristovuye minimalnu dovzhinu povidomlennya i faktichno vklyuchaye jmovirnisni oporno vektorni mashini v listkah derev rishen angl Vapnik Vladimir N The Nature of Statistical Learning Theory Springer Verlag 1995 ISBN 0 387 98780 0 angl Vapnik Vladimir N and Kotz Samuel Estimation of Dependences Based on Empirical Data Springer 2006 ISBN 0 387 30865 2 510 pages ce ye peredrukom rannoyi krigi Vapnika yaka opisuye filosofiyu sho stoyit za pidhodom OVM Dopovnennya 2006 roku opisuye novi vdoskonalennya angl 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 Stislo opisuye teoretichni ideyi sho lezhat v osnovi OVM angl Bennett Kristin P and Campbell Colin Support Vector Machines Hype or Hallelujah SIGKDD Explorations 2 2 2000 1 13 Vidminne vvedennya do OVM iz korisnimi malyunkami angl Ivanciuc Ovidiu Applications of Support Vector Machines in Chemistry in Reviews in Computational Chemistry Volume 23 2007 pp 291 400 angl Catanzaro Bryan Sundaram Narayanan and Keutzer Kurt Fast Support Vector Machine Training and Classification on Graphics Processors in International Conference on Machine Learning 2008 angl Campbell Colin and Ying Yiming Learning with Support Vector Machines 2011 Morgan and Claypool ISBN 978 1 60845 616 1 angl Ben Hur Asa Horn David Siegelmann Hava and Vapnik Vladimir Support vector clustering 2001 Journal of Machine Learning Research 2 125 137 angl Vladimir Vyugin Matematicheskie osnovy mashinnogo obucheniya i prognozirovaniya MCMNO 2014 304 s ISBN 978 5 457 71889 0 ros 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 angl Alexey Nefedov Support Vector Machines A Simple Tutorial 2016 angl A A Shumejko S L Sotnik M V Lysak Ispolzovanie geneticheskih algoritmov v zadachah klassifikacii tekstov ros Yu Lifshic Metod opornih vektorov ros Andrew Ng 2016 Support Vector Machines PDF CS229 Course Machine Learning Stanford University angl Dudin V D 2013 Sravnenie i testirovanie realizacij algoritma SVM dlya zadach klassifikacii PDF Kursovaya rabota Sankt Peterburgskij gosudarstvennyj universitet chastkovij rosijskomovnij plagiat ros Posilannyared www support vector net Klyuchova kniga pro cej metod An Introduction to Support Vector Machines z dostupnim onlajn programnim zabezpechennyam angl Burges Christopher J C A Tutorial on Support Vector Machines for Pattern Recognition Data Mining and Knowledge Discovery 2 121 167 1998 angl www kernel machines org zagalna informaciya ta zbirka doslidnickih prac angl www support vector machines org literatura oglyadi programne zabezpechennya posilannya pov yazani z oporno vektornimi mashinami akademichnij sajt angl svmtutorial online Proste vvedennya do OVM legko dostupne bud komu z bazovimi znannyami v matematici angl videolectures net video lekciyi pov yazani z OVM angl Karatzoglou Alexandros et al Support Vector Machines in R Journal of Statistical Software April 2006 Volume 15 Issue 9 angl libsvm LIBSVM populyarna biblioteka dlya sistem navchannya OVM liblinear biblioteka dlya velikoyi linijnoyi klasifikaciyi vklyuchno z deyakimi OVM Shark biblioteka mashinnogo navchannya C yaka realizuye rizni tipi OVM dlib biblioteka C dlya roboti z yadrovimi metodami ta OVM SVM light zbirka programnih instrumentiv dlya navchannya ta klasifikaciyi iz zastosuvannyam OVM SVMJS live demo GIK demonstraciya realizaciyi OVM na JavaScript Gesture Recognition Toolkit mistit zruchnu dlya zastosuvannya obgortku dlya libsvm Data Mining 10 Lekciya Metody klassifikacii i prognozirovaniya Metod opornyh vektorov Intuit ru ru ros Yurij Lifshic Metod opornyh vektorov Slajdy lekciya 7 iz kursa Algoritmy dlya Interneta ros Otrimano z https uk wikipedia org w index php title Metod opornih vektoriv amp oldid 42095659