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

Розгляньмо задачу бінарної класифікації з набором даних (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}}$ .

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

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

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

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