Послідовна мінімальна оптимізація

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Послідовна мінімальна оптимізація
Клас Алгоритм оптимізації для тренування опорно-векторних машин
Найгірша швидкодія O(n³)

Послідо́вна мініма́льна оптиміза́ція (ПМО, англ. sequential minimal optimization, SMO) — це алгоритм розв'язання задачі квадратичного програмування (КП), яка постає при тренуванні опорно-векторних машин (ОВМ, англ. support vector machines, SVM). Його було винайдено Джоном Платтом[en] 1998 року в Microsoft Research.[1] ПМО широко використовується для тренування опорно-векторних машин, і втілюється популярним інструментом LIBSVM.[2][3] Публікація алгоритму ПМО 1998 року викликала велике збудження в спільноті ОВМ, оскільки доступні раніше методи тренування опорно-векторних машин були набагато складнішими, й вимагали дорогих сторонніх інструментів розв'язання задач КП.[4]

Задача оптимізації[ред. | ред. код]

Розгляньмо задачу бінарної класифікації з набором даних (x1, y1), …, (xn, yn), де xi є вхідним вектором, а yi ∈ {-1, +1} є відповідною бінарною міткою. Опорно-векторна машина з м'яким проміжком тренується розв'язанням задачі квадратичного програмування, яка виражається в двоїстому вигляді[en] наступним чином:

за умов
для

де C є гіперпараметром ОВМ, а K(xi, xj) є ядровою функцією[en], обидва надані користувачем; а змінні є множниками Лагранжа.

Алгоритм[ред. | ред. код]

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

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

Алгоритм діє наступним чином:

  1. Знайти лагранжів множник , який порушує умови Каруша — Куна — Такера (ККТ) для задачі оптимізації.
  2. Вибрати другий множник , й оптимізувати пару .
  3. Повторювати кроки 1 та 2 до збігання.

Коли всі лагранжеві множники задовольняють умови ККТ (в межах визначеного користувачем допуску), задачу розв'язано. Хоч цей алгоритм і збігається гарантовано, для вибору пар множників застосовується евристика, щоби прискорити темп збігання. Це є критичним для великих наборів даних, оскільки існує n(n − 1) можливих варіантів вибору та .

Пов'язані праці[ред. | ред. код]

Перший підхід до розділення великих задач навчання ОВМ на ряд менших оптимізаційних завдань було запропоновано Бернхардом Босером, Ізабель Гійон та Володимиром Вапником.[5] Він відомий як «кусеневий алгоритм» (англ. "chunking algorithm"). Цей алгоритм починається з випадкового піднабору даних, розв'язує цю задачу, й ітеративно додає зразки, які порушують умови оптимальності. Одним із недоліків цього алгоритму є необхідність розв'язання задач КП, які масштабуються з числом опорних векторів. На реальних розріджених наборах даних ПМО може бути швидшою за кусеневий алгоритм в понад 1000 разів.[1]

1997 року Е. Осуна, Р. Фройнд та Ф. Гіросі довели теорему, яка пропонує цілий ряд нових алгоритмів КП для ОВМ.[6] В силу цієї теореми велику задачу КП може бути розбито на ряд менших підзадач КП. Послідовність підзадач КП, яка завжди додає щонайменше одного порушника умов Каруша — Куна — Такера (ККТ), гарантовано збігається. Кусеневий алгоритм задовольняє умови цієї теореми і, отже, збігатиметься.[1] Алгоритм ПМО можна розглядати як окремий випадок алгоритму Осуни, де розміром оптимізації є два, й обидва лагранжеві множники замінюються на кожному кроці новими множниками, які обираються за допомогою доброї евристики.[1]

Алгоритм ПМО тісно пов'язаний із сімейством алгоритмів оптимізації, що зветься методами Бреґмана[en], або рядково-активаційними методами. Ці методи розв'язують задачі опуклого програмування з лінійними обмеженнями. Вони є ітеративними методами, де кожен крок робить проекцію поточної прямої точки на кожне з обмежень.[1]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. а б в г д Platt, John (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. CiteSeerX: 10.1.1.43.4376.  (англ.)
  2. Chang, Chih-Chung; Lin, Chih-Jen (2011). LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2 (3).  (англ.)
  3. Luca Zanni (2006). Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems. (англ.)
  4. Rifkin, Ryan (2002). Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning. Ph.D. thesis: 18.  (англ.)
  5. 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. ISBN 089791497X. doi:10.1145/130385.130401.  (англ.)
  6. Osuna, E.; Freund, R.; Girosi, F. (1997). An improved training algorithm for support vector machines. Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop. с. 276 – 285. ISBN 0-7803-4256-9. doi:10.1109/NNSP.1997.622408.  (англ.)