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

Шаблон:Infobox Algorithm Послідо́вна мініма́льна оптиміза́ція (ПМО, Шаблон:Lang-en) — це алгоритм розв'язання задачі квадратичного програмування (КП), яка постає при тренуванні опорно-векторних машин (ОВМ, Шаблон:Lang-en). Його було винайдено Шаблон:Нп 1998 року в Microsoft Research. ПМО широко використовується для тренування опорно-векторних машин, і втілюється популярним інструментом LIBSVM. Публікація алгоритму ПМО 1998 року викликала велике збудження в спільноті ОВМ, оскільки доступні раніше методи тренування опорно-векторних машин були набагато складнішими, й вимагали дорогих сторонніх інструментів розв'язання задач КП.

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

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

$\underset{\alpha }{\max }\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\le {\alpha }_i\le C,$ для $i=1,2,\dots ,n,$

$\sum _{i=1}^n{y}_i{\alpha }_i=0$

де C є гіперпараметром ОВМ, а K(x_i, x_j) є Шаблон:Нп, обидва надані користувачем; а змінні ${\alpha }_i$ є множниками Лагранжа.

Алгоритм

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

$0\le {\alpha }_1,{\alpha }_2\le C,$

$y_1{\alpha }_1+y_2{\alpha }_2=k,$

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

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

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

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

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

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

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

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

Див. також

• Шаблон:Нп