Послідо́вна мініма́льна оптиміза́ція (ПМО, ) — це алгоритм розв'язання задачі квадратичного програмування (КП), яка постає при тренуванні опорно-векторних машин (ОВМ, ). Його було винайдено 1998 року в Microsoft Research. ПМО широко використовується для тренування опорно-векторних машин, і втілюється популярним інструментом LIBSVM. Luca Zanni (2006). Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems . Публікація алгоритму ПМО 1998 року викликала велике збудження в спільноті ОВМ, оскільки доступні раніше методи тренування опорно-векторних машин були набагато складнішими, й вимагали дорогих сторонніх інструментів розв'язання задач КП.
Задача оптимізації
Розгляньмо задачу бінарної класифікації з набором даних (x1, y1), …, (xn, yn), де xi є вхідним вектором, а є відповідною бінарною міткою. Опорно-векторна машина з м'яким проміжком тренується розв'язанням задачі квадратичного програмування, яка виражається в двоїстому вигляді наступним чином:
за умов для
де C є гіперпараметром ОВМ, а K(xi, xj) є , обидва надані користувачем; а змінні є множниками Лагранжа.
Алгоритм
ПМО є ітеративним алгоритмом розв'язання описаної вище задачі оптимізації. ПМО розбиває цю задачу на ряд найменших можливих підзадач, які потім розв'язуються аналітично. Через лінійну рівність в обмеженнях, яка включає лагранжеві множники , найменша можлива задача включає два такі множники. Тоді для будь-яких двох множників і обмеження зводяться до
і цю звужену задачу можливо розв'язувати аналітично: потрібно знаходити мінімум одновимірної квадратичної функції. є сумою решти членів у обмеженні-рівнянні з протилежним знаком, яка є незмінною на кожній ітерації.
Алгоритм діє наступним чином:
Знайти лагранжів множник , який порушує умови Каруша — Куна — Такера (ККТ) для задачі оптимізації. Вибрати другий множник , й оптимізувати пару . Повторювати кроки 1 та 2 до збігання.
Коли всі лагранжеві множники задовольняють умови ККТ (в межах визначеного користувачем допуску), задачу розв'язано. Хоч цей алгоритм і збігається гарантовано, для вибору пар множників застосовується евристика, щоби прискорити темп збігання. Це є критичним для великих наборів даних, оскільки існує n(n − 1) можливих варіантів вибору та .
Пов'язані праці
Перший підхід до розділення великих задач навчання ОВМ на ряд менших оптимізаційних завдань було запропоновано , та Володимиром Вапником. Він відомий як «кусеневий алгоритм» (). Цей алгоритм починається з випадкового піднабору даних, розв'язує цю задачу, й ітеративно додає зразки, які порушують умови оптимальності. Одним із недоліків цього алгоритму є необхідність розв'язання задач КП, які масштабуються з числом опорних векторів. На реальних розріджених наборах даних ПМО може бути швидшою за кусеневий алгоритм в понад 1000 разів.
1997 року , та довели теорему, яка пропонує цілий ряд нових алгоритмів КП для ОВМ. В силу цієї теореми велику задачу КП може бути розбито на ряд менших підзадач КП. Послідовність підзадач КП, яка завжди додає щонайменше одного порушника умов Каруша — Куна — Такера (ККТ), гарантовано збігається. Кусеневий алгоритм задовольняє умови цієї теореми і, отже, збігатиметься. Алгоритм ПМО можна розглядати як окремий випадок алгоритму Осуни, де розміром оптимізації є два, й обидва лагранжеві множники замінюються на кожному кроці новими множниками, які обираються за допомогою доброї евристики.
Алгоритм ПМО тісно пов'язаний із сімейством алгоритмів оптимізації, що зветься , або рядково-активаційними методами. Ці методи розв'язують задачі опуклого програмування з лінійними обмеженнями. Вони є ітеративними методами, де кожен крок робить проєкцію поточної прямої точки на кожне з обмежень.
Див. також
Примітки