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

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

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

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

Задача оптимізації

Докладніше: Метод опорних векторів

Розгляньмо задачу бінарної класифікації з набором даних (x₁, y₁), …, (x_n, y_n), де x_i є вхідним вектором, а y_i ∈ {-1, +1} є відповідною бінарною міткою. Опорно-векторна машина з м'яким проміжком тренується розв'язанням задачі квадратичного програмування, яка виражається в двоїстому вигляді наступним чином:

${\displaystyle \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j}}$

за умов

${\displaystyle 0\leq \alpha _{i}\leq C,\quad }$ для ${\displaystyle i=1,2,\ldots ,n,}$

${\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0}$

де C є гіперпараметром ОВМ, а K(x_i, x_j) є ^[en], обидва надані користувачем; а змінні ${\displaystyle \alpha _{i}}$ є множниками Лагранжа.

Алгоритм

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

${\displaystyle 0\leq \alpha _{1},\alpha _{2}\leq C,}$

${\displaystyle y_{1}\alpha _{1}+y_{2}\alpha _{2}=k,}$

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

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

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

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

Пов'язані праці

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

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

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

Див. також

• ^[en]

Примітки

1. Platt, John (1998), (PDF), (CiteSeerX): 10.1.1.43.4376, архів оригіналу (PDF) за 13 листопада 2016, процитовано 23 жовтня 2016 (англ.)
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 [ 18 липня 2011 у Wayback Machine.]. (англ.)
4. Rifkin, Ryan (2002), , Ph.D. thesis: 18, архів оригіналу за 14 березня 2012, процитовано 23 жовтня 2016 (англ.)
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. doi:10.1145/130385.130401. ISBN . (англ.)
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. doi:10.1109/NNSP.1997.622408. ISBN . (англ.)