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

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

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

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

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

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

\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}

за умов

0\leq \alpha _{i}\leq C,\quad

для

i=1,2,\ldots ,n,

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

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

Алгоритм ред.

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

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

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

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

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

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

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

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

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

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

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

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

Ядровий перцептрон^[en]

Примітки ред.

↑ ^а ^б ^в ^г ^д Platt, John (1998), Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (PDF), CiteSeerX: 10.1.1.43.4376, архів оригіналу (PDF) за 13 листопада 2016, процитовано 23 жовтня 2016 (англ.)
↑ Chang, Chih-Chung; Lin, Chih-Jen (2011). LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology. 2 (3). (англ.)
↑ Luca Zanni (2006). Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems [Архівовано 18 липня 2011 у Wayback Machine.]. (англ.)
↑ Rifkin, Ryan (2002), Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning, Ph.D. thesis: 18, архів оригіналу за 14 березня 2012, процитовано 23 жовтня 2016 (англ.)
↑ 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. (англ.)
↑ 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 0-7803-4256-9. (англ.)

[Platt-1] а ^б ^в ^г ^д Platt, John (1998), Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (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), Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning, Ph.D. thesis: 18, архів оригіналу за 14 березня 2012, процитовано 23 жовтня 2016 (англ.)

[ReferenceA-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 089791497X. (англ.)

[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 0-7803-4256-9. (англ.)

[1]

[2]

[3]

[4]

[5]

[6]