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

Последовательная минимальная оптимизация
Сорт	Алгоритм оптимизации обучения машин опорных векторов
Худшая производительность	О( п ³)

Последовательная минимальная оптимизация ( SMO ) — это алгоритм решения задачи квадратичного программирования (QP), возникающий при обучении машин опорных векторов (SVM). Его изобрел Джон Платт в 1998 году в Microsoft Research . ^[1] SMO широко используется для обучения машин опорных векторов и реализуется с помощью популярного инструмента LIBSVM . ^[2]^[3] Публикация алгоритма SMO в 1998 году вызвала большой ажиотаж в сообществе SVM, поскольку ранее доступные методы обучения SVM были гораздо более сложными и требовали дорогостоящих сторонних решателей QP. ^[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 {\mbox{ for }}i=1,2,\ldots ,n,

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

где C — гиперпараметр SVM, а K ( xi _{, оба} , x _j ) — функция ядра предоставляются пользователем; и переменные $\alpha _{i}$ являются множителями Лагранжа .

Алгоритм

SMO — это итерационный алгоритм решения описанной выше задачи оптимизации. SMO разбивает эту проблему на ряд наименьших возможных подзадач, которые затем решаются аналитически. Из-за ограничения линейного равенства, включающего множители Лагранжа $\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)/2$ возможные варианты для $\alpha _{i}$ и $\alpha _{j}$ .

Связанные работы

Первый подход к разбиению больших задач обучения SVM на ряд более мелких задач оптимизации был предложен Бернхардом Бозером , Изабель Гийон , Владимиром Вапником . ^[5] Он известен как «алгоритм фрагментации». Алгоритм начинается со случайного подмножества данных, решает эту проблему и итеративно добавляет примеры, нарушающие условия оптимальности. Недостатком данного алгоритма является необходимость решения QP-задач масштабирования с количеством СВ. В реальных наборах данных с разреженными данными SMO может быть более чем в 1000 раз быстрее, чем алгоритм фрагментации. ^[1]

В 1997 году Э. Осуна , Р. Фрейнд и Ф. Гироси доказали теорему, которая предлагает совершенно новый набор QP-алгоритмов для SVM. ^[6] В силу этой теоремы большую проблему QP можно разбить на ряд более мелких подзадач QP. Последовательность подзадач QP, которая всегда добавляет хотя бы одного нарушителя условий Каруша – Куна – Такера (ККТ), гарантированно сходится. Алгоритм разбиения подчиняется условиям теоремы и, следовательно, будет сходиться. ^[1] Алгоритм SMO можно рассматривать как частный случай алгоритма Осуна, где размер оптимизации равен двум и оба множителя Лагранжа заменяются на каждом шаге новыми множителями, выбранными с помощью хорошей эвристики. ^[1]

Алгоритм SMO тесно связан с семейством алгоритмов оптимизации, называемых методами Брегмана или методами действия строк. Эти методы решают задачи выпуклого программирования с линейными ограничениями. Это итеративные методы, в которых каждый шаг проецирует текущую исходную точку на каждое ограничение. ^[1]

См. также

Ядро персептрона

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Платт, Джон (1998). «Последовательная минимальная оптимизация: быстрый алгоритм обучения машин опорных векторов» (PDF) . CiteSeerX 10.1.1.43.4376 .
^ Чанг, Чи-Чунг; Линь, Чи-Джен (2011). «LIBSVM: библиотека для машин опорных векторов». Транзакции ACM в интеллектуальных системах и технологиях . 2 (3). дои : 10.1145/1961189.1961199 . S2CID 961425 .
^ Занни, Лука (2006). «Параллельное программное обеспечение для обучения крупномасштабных машин опорных векторов в многопроцессорных системах» (PDF) .
^ Рифкин, Райан (2002). Все старое снова новое: свежий взгляд на исторические подходы в машинном обучении (кандидатская диссертация). Массачусетский технологический институт. п. 18. HDL : 1721,1/17549 .
^ Бозер, Бельгия; Гийон, И.М.; Вапник, В. Н. (1992). «Алгоритм обучения оптимальных классификаторов маржи». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . п. 144. CiteSeerX 10.1.1.21.3818 . дои : 10.1145/130385.130401 . ISBN 978-0897914970 . S2CID 207165665 .
^ Осуна, Э.; Фройнд, Р.; Гироси, Ф. (1997). «Улучшенный алгоритм обучения машин опорных векторов». Нейронные сети для обработки сигналов [1997] VII. Материалы семинара IEEE 1997 года . стр. 276–285. CiteSeerX 10.1.1.392.7405 . дои : 10.1109/NNSP.1997.622408 . ISBN 978-0-7803-4256-9 . S2CID 5667586 .

[Platt-1] Jump up to: ^а ^б ^с ^д ^и Платт, Джон (1998). «Последовательная минимальная оптимизация: быстрый алгоритм обучения машин опорных векторов» (PDF) . CiteSeerX 10.1.1.43.4376 .

[2] Чанг, Чи-Чунг; Линь, Чи-Джен (2011). «LIBSVM: библиотека для машин опорных векторов». Транзакции ACM в интеллектуальных системах и технологиях . 2 (3). дои : 10.1145/1961189.1961199 . S2CID 961425 .

[3] Занни, Лука (2006). «Параллельное программное обеспечение для обучения крупномасштабных машин опорных векторов в многопроцессорных системах» (PDF) .

[4] Рифкин, Райан (2002). Все старое снова новое: свежий взгляд на исторические подходы в машинном обучении (кандидатская диссертация). Массачусетский технологический институт. п. 18. HDL : 1721,1/17549 .

[ReferenceA-5] Бозер, Бельгия; Гийон, И.М.; Вапник, В. Н. (1992). «Алгоритм обучения оптимальных классификаторов маржи». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . п. 144. CiteSeerX 10.1.1.21.3818 . дои : 10.1145/130385.130401 . ISBN 978-0897914970 . S2CID 207165665 .

[6] Осуна, Э.; Фройнд, Р.; Гироси, Ф. (1997). «Улучшенный алгоритм обучения машин опорных векторов». Нейронные сети для обработки сигналов [1997] VII. Материалы семинара IEEE 1997 года . стр. 276–285. CiteSeerX 10.1.1.392.7405 . дои : 10.1109/NNSP.1997.622408 . ISBN 978-0-7803-4256-9 . S2CID 5667586 .

[1]

[2]

[3]

[4]

[5]

[6]