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

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

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

Последовательная минимальная оптимизация ( SMO ) - это алгоритм решения задачи квадратичного программирования (QP), возникающей во время обучения машин с опорными векторами (SVM). Он был изобретен Джоном Платтом в 1998 году в Microsoft Research . SMO широко используется для обучения опорных векторных машин и реализуется популярным инструментом LIBSVM . Публикация алгоритма SMO в 1998 году вызвала большой ажиотаж в сообществе SVM, так как ранее доступные методы обучения SVM были намного сложнее и требовали дорогостоящих сторонних решателей QP.

Проблема оптимизации

Рассмотрим задачу двоичной классификации с набором данных ( 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 {\ mbox {for}} i = 1,2, \ ldots, n,}$

${\ Displaystyle \ сумма _ {я = 1} ^ {п} у_ {я} \ альфа _ {я} = 0}$

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

Алгоритм

SMO - это итерационный алгоритм для решения описанной выше задачи оптимизации. SMO разбивает эту проблему на ряд минимально возможных подзадач, которые затем решаются аналитически. Из-за ограничения линейного равенства, включающего множители Лагранжа , наименьшая возможная проблема включает два таких множителя. Затем для любых двух множителей и ограничения уменьшаются до: ${\ displaystyle \ alpha _ {я}}$${\ 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. Найдите множитель Лагранжа, который нарушает условия Каруша – Куна – Таккера (KKT) для задачи оптимизации.${\ displaystyle \ alpha _ {1}}$
2. Выберите второй множитель и оптимизируйте пару .${\ displaystyle \ alpha _ {2}}$${\ Displaystyle (\ альфа _ {1}, \ альфа _ {2})}$
3. Повторяйте шаги 1 и 2 до схождения.

Когда все множители Лагранжа удовлетворяют условиям KKT (в пределах заданного пользователем допуска), проблема решена. Хотя этот алгоритм гарантирует сходимость, эвристика используется для выбора пары множителей, чтобы ускорить скорость сходимости. Это очень важно для больших наборов данных, поскольку есть возможные варианты для и . ${\ Displaystyle п (п-1) / 2}$${\ displaystyle \ alpha _ {я}}$${\ displaystyle \ alpha _ {j}}$

Связанных с работой

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

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

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

Смотрите также

• Перцептрон ядра

Ссылки