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

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

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

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

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

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

[ред. | ред. код]
H1 не розділяє ці класи. H2 розділяє, але лише з невеликим розділенням. H3 розділяє їх із максимальним розділенням.

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

Визначення

[ред. | ред. код]

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

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

В той час, як первинну задачу може бути сформульовано у скінченновимірному просторі, часто трапляється так, що множини, які треба розрізнювати, не є лінійно роздільними в ньому. З цієї причини було запропоновано відображувати первинний скінченновимірний простір до простору набагато вищої вимірності, здогадно роблячи розділення простішим у тому просторі. Для збереження помірного обчислювального навантаження, відображення, які використовуються методом опорних векторів, розробляють такими, щоби забезпечувати можливість простого обчислення скалярних добутків у термінах змінних первинного простору, визначаючи їх у термінах ядрових функцій[en] , що їх обирають відповідно до задачі.[3] Гіперплощини в просторі вищої вимірності визначаються як геометричне місце точок, чиї скалярні добутки з вектором у цьому просторі є сталими. Вектори, які визначають гіперплощини, можуть обиратися як лінійні комбінації з параметрами відображень векторів ознак , які трапляються в базі даних. За такого вибору гіперплощини, точки простору ознак, які відображаються на гіперплощину, визначаються відношенням Зауважте, що якщо стає малою з віддаленням від , то кожен член цієї суми вимірює ступінь близькості пробної точки до відповідних основних точок даних . Таким чином, наведена вище сума ядер може використовуватися для вимірювання відносної близькості кожної пробної точки до точок даних, які походять з однієї або іншої з множин, які треба розрізнювати. Зверніть увагу на той факт, що множина точок , відображена на будь-яку гіперплощину, може бути в результаті доволі вигнутою, уможливлюючи набагато складніше розрізнювання між множинами, які взагалі не є опуклими в первинному просторі.

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

[ред. | ред. код]

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

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

Історія

[ред. | ред. код]

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

Лінійна ОВМ

[ред. | ред. код]

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

де є або 1, або -1, і кожен з них вказує клас, до якого належить точка . Кожен є -вимірним дійсним вектором. Нам треба знайти «максимально розділову гіперплощину», яка відділяє групу точок , для яких , від групи точок, для яких , і визначається таким чином, що відстань між цією гіперплощиною та найближчою точкою з кожної з груп є максимальною.

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

де є (не обов'язково нормалізованим) вектором нормалі до цієї гіперплощини. Параметр визначає зсув гіперплощини від початку координат вздовж вектора нормалі .

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

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

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

(будь-що на або вище цієї межі належить до класу з міткою 1)

та

(будь-що на або нижче цієї межі належить до класу з міткою -1)

З геометричної точки зору, відстанню між цими двома гіперплощинами є ,[10] тож для максимізації відстані між ними нам треба мінімізувати . Оскільки ми також маємо завадити потраплянню точок даних до розділення, ми додаємо таке обмеження: для кожного , або

якщо

або

якщо

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

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

для всіх

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

«Мінімізувати за умови для »

та , які розв'язують цю задачу, визначають наш класифікатор, .

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

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

[ред. | ред. код]

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

Зауважимо, що є i-ю цілю (англ. target) (тобто, в нашому випадку, 1 або -1) та - поточний результат.

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

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

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

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

[ред. | ред. код]
Ядрова машина

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

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

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

  • Поліноміальне (однорідне):
  • Поліноміальне[en] (неоднорідне):
  • Ґаусова радіально-базисна функція: для . Іноді використовують , але частіше цей гіперпараметр підбирають з допомогою перехресного затверджування
  • Сигмоїдне (гіперболічний тангенс): для деяких (не всіх) та

Ядро пов'язано з перетворенням через рівняння . Значення w також знаходиться в перетвореному просторі, з . Скалярні добутки з w для класифікації, знов-таки, може бути обчислювано за допомогою ядрового трюку, тобто, .

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

[ред. | ред. код]

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

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

Пряме

[ред. | ред. код]

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

Для кожного ми вводимо змінну . Зверніть увагу, що є найменшим невід'ємним числом, яке задовольняє

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

мінімізувати
за умов та для всіх .

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

Двоїсте

[ред. | ред. код]

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

максимізувати
за умов та для всіх .

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

Тут змінні визначено таким чином, що

.

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

Зсув може бути з'ясовано знаходженням на межі розділення, і розв'язанням

(Зверніть увагу, що , оскільки .)

Ядровий трюк

[ред. | ред. код]

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

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

де отримуються розв'язанням задачі оптимізації

мінімізувати
за умов та для всіх .

Як і раніше, коефіцієнти може бути знайдено розв'язанням задачі квадратичного програмування. Знов-таки, ми можемо знайти такий індекс , що , так що лежить на межі розділення у перетвореному просторі, й тоді розв'язати

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

максимізувати
за умов та для всіх .

Для кожного , ітеративно, коефіцієнт коригується в напрямку . Потім робиться проєкція отриманого вектора коефіцієнтів на найближчий вектор коефіцієнтів, який задовольняє задані обмеження. (Зазвичай застосовуються евклідові відстані.) Цей процес повторюється доти, поки не буде отримано вектор коефіцієнтів, близький до оптимального. Отриманий алгоритм є дуже швидким на практиці, хоча доведених гарантій продуктивності мало.[14]

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

[ред. | ред. код]

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

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

[ред. | ред. код]

У навчанні з підкріпленням задається набір тренувальних зразків із мітками , і потрібно передбачувати для заданого . Для здійснення цього формують гіпотезу, , таку, що є «добрим» наближенням . «Добре» наближення зазвичай визначається з допомогою функції втрат, , яка характеризує, наскільки поганим є як передбачення . Потім треба обрати гіпотезу, яка мінімізує очікуваний ризик:

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

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

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

[ред. | ред. код]

Щоби задача мінімізації мала добре визначений розв'язок, ми маємо накласти обмеження на множину гіпотез, які розглядаються. Якщо є нормованим простором (як у випадку ОВМ), то особливо дієвою методикою є розглядати лише ті гіпотези , для яких . Це рівнозначне накладенню регуляризаційного штрафу (англ. regularization penalty) , і розв'язанню нової задачі оптимізації

.

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

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

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

[ред. | ред. код]

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

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

З цієї точки зору ОВМ є тісно пов'язаними з іншими фундаментальними алгоритмами класифікації, такими як регуляризовані найменші квадрати[en] та логістична регресія. Різниця між цими трьома полягає у виборі функції втрат: регуляризовані найменші квадрати зводяться до мінімізації емпіричного ризику з квадратичними втратами, , а логістична регресія використовує логістичні втрати, .

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

[ред. | ред. код]

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

Зокрема, нехай позначає , обумовлений подією, що . У постановці класифікації ми маємо

з імовірністю
з імовірністю

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

якщо
інакше

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

З іншого боку, можна перевірити, що цільовою функцією заві́сних втрат є саме . Таким чином, у достатньо багатому просторі гіпотез, — або, рівнозначно, для правильно обраного ядра, — ОВМ-класифікатор збігатиметься до найпростішої функції (в термінах ), яка правильно класифікує дані. Це розширює геометричну інтерпретацію ОВМ — для лінійної класифікації емпіричний ризик мінімізується будь-якою функцією, чиї межі лежать між опорними векторами, і найпростішою з них є максимально розділовий класифікатор.[15]

Властивості

[ред. | ред. код]

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

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

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

[ред. | ред. код]

Ефективність ОВМ залежить від вибору ядра, параметрів ядра та параметра м'якого розділення C. Поширеним вибором є ґаусове ядро, що має єдиний параметр . Найкращу комбінацію C та часто обирають ґратковим пошуком з послідовностями C та , які експоненційно зростають, наприклад, ; . Як правило, кожну комбінацію варіантів вибору параметрів перевіряють із застосуванням перехресного затверджування, й обирають параметри з найкращою точністю, показаною перехресним затверджуванням. Як альтернатива, для вибору C та може застосовуватися недавня робота в баєсовій оптимізації, яка часто потребує оцінки набагато меншого числа комбінацій параметрів, ніж ґратковий пошук. Потім остаточна модель, яка використовується для перевірки та класифікації даних, тренується на всьому тренувальному наборі із застосуванням обраних параметрів.[17]

Проблеми

[ред. | ред. код]

Потенційні недоліки ОВМ включають наступні аспекти:

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

Розширення

[ред. | ред. код]

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

Трансдуктивні опорно-векторні машини розширюють ОВМ тим, що вони можуть також обробляти частково мічені дані в напівкерованому навчанні, дотримуючись принципів трансдукції[en]. Тут, на додачу до тренувального набору , надається також набір

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

Мінімізувати (за )

за умов (для всіх та всіх )

та

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

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

[ред. | ред. код]

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

Регресія

[ред. | ред. код]

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

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

мінімізувати
за умов

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

Реалізація

[ред. | ред. код]

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

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

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

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

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

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

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. а б Cortes, C.; Vapnik, V. (1995). Support-vector networks. Machine Learning. 20 (3): 273—297. doi:10.1007/BF00994018. (англ.)
  2. Ben-Hur, Asa, Horn, David, Siegelmann, Hava, and Vapnik, Vladimir; "Support vector clustering" (2001) Journal of Machine Learning Research, 2: 125–137. (англ.)
  3. *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 978-0-521-88068-8. (англ.)
  4. Vapnik, V.: Invited Speaker. IPMU Information Processing and Management 2014) (англ.)
  5. 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. (англ.)
  6. Bilwaj Gaonkar, Christos Davatzikos Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification (англ.)
  7. 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 (англ.)
  8. Statnikov, A., Hardin, D., & Aliferis, C. (2006). Using SVM weight-based methods to identify causally relevant and non-causally relevant variables. sign, 1, 4. (англ.)
  9. а б 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 089791497X. (англ.)
  10. Why is the SVM margin equal to . Mathematics Stack Exchange. 30 травня 2015.
  11. 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. (англ.)
  12. Jin, Chi; Wang, Liwei (2012). Dimensionality dependent PAC-Bayes margin bound. Advances in Neural Information Processing Systems. Архів оригіналу за 2 квітня 2015. Процитовано 29 жовтня 2016. (англ.)
  13. 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. (англ.)
  14. 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 978-1-60558-205-4. (англ.)
  15. 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. (англ.)
  16. Meyer, D.; Leisch, F.; Hornik, K. (2003). The support vector machine under test. Neurocomputing. 55: 169. doi:10.1016/S0925-2312(03)00431-4. (англ.)
  17. 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. {{cite tech report}}: Проігноровано невідомий параметр |last-author-amp= (довідка) (англ.)
  18. а б Duan, K. B.; Keerthi, S. S. (2005). Which Is the Best Multiclass SVM Method? An Empirical Study. Multiple Classifier Systems. LNCS[en]. Т. 3541. с. 278—285. doi:10.1007/11494683_28. ISBN 978-3-540-26306-7. (англ.)
  19. Hsu, Chih-Wei; Lin, Chih-Jen (2002). A Comparison of Methods for Multiclass Support Vector Machines. IEEE Transactions on Neural Networks. {{cite journal}}: Проігноровано невідомий параметр |last-author-amp= (довідка) (англ.)
  20. Platt, John; Cristianini, N.[en]; and Shawe-Taylor, J.[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. (англ.)
  21. 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. (англ.)
  22. 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. {{cite journal}}: Проігноровано невідомий параметр |last-author-amp= (довідка) (англ.)
  23. Lee, Y.; Lin, Y.; Wahba, G. (2001). Multicategory Support Vector Machines (PDF). Computing Science and Statistics. 33. Архів оригіналу (PDF) за 17 червня 2013. Процитовано 29 жовтня 2016. {{cite journal}}: Проігноровано невідомий параметр |last-author-amp= (довідка) (англ.)
  24. Lee, Y.; Lin, Y.; Wahba, G. (2004). Multicategory Support Vector Machines. Journal of the American Statistical Association. 99 (465): 67. doi:10.1198/016214504000000098. (англ.)
  25. 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. (англ.)
  26. 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. (англ.)
  27. 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. (англ.)
  28. 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. (англ.)
  29. 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. (англ.)
  30. John C. Platt (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (PDF). NIPS. Архів оригіналу (PDF) за 2 липня 2015. Процитовано 29 жовтня 2016. (англ.)
  31. Shai Shalev-Shwartz; Yoram Singer; Nathan Srebro (2007). Pegasos: Primal Estimated sub-GrAdient SOlver for SVM (PDF). ICML. Архів оригіналу (PDF) за 15 грудня 2013. Процитовано 29 жовтня 2016. (англ.)
  32. 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. (англ.)
  33. Zeyuan Allen Zhu та ін. (2009). P-packSVM: Parallel Primal grAdient desCent Kernel SVM (PDF). ICDM. Архів оригіналу (PDF) за 7 квітня 2014. Процитовано 29 жовтня 2016. (англ.)

Література

[ред. | ред. код]

Посилання

[ред. | ред. код]