Алгоритм INCAS

Материал из MachineLearning.

Перейти к: навигация, поиск

Ž

Данная статья является непроверенным учебным заданием.
Студент: Участник:Михаил
Преподаватель: Участник:Константин Воронцов
Срок: 7 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Алгоритм INCAS (INCremental Active Set method) - алгоритм настройки SVM.

Рассматривается задача классификации на два непересекающихся класса, Y = \{-1, 1\}, а X = R^n. Алгоритм INCAS позволяет уменьшить число вычислений при построении SVM.

Содержание

Двойственная задача

При построении SVM приходится решать двойственную задачу:

\(1\) \left{\begin{array}{lcl}
-\mathscr{L}\(\lambda\) = - \sum_{i=1}^l \lambda_i + \frac{1}{2} \sum_{i=1}^l \sum_{j=1}^l \lambda_i \lambda_j y_i y_j
\<x_i,x_j\> \to \min_{\lambda};\\
0 \leq \lambda_i \leq C, i = 1,...,l;\\
\sum_{i=1}^l \lambda_i y_i = 0.
\end{array}

Здесь \lambda = \(\lambda_1,...,\lambda_l\) - вектор двойственных переменных, C - параметр алгоритма.
Если решение задачи известно, то возможно найти параметры линейного классификатора $\omega$ и $\omega_0$.
Задача \(1\) является задачей квадратичного программирования. Методы решения подобных задач известны, но они трудоемки. Поэтому для обучения SVM применяют алгоритмы, которые учитывают его специфические особенности. Один из них - последовательный метод активных ограничений, INCAS.

Преобразованная двойственная задача

Двойственную задачу преобразовывают следующим образом. Вводятся матрица $Q = \(y_i y_j K\(x_i,x_j\)\)_{i=1,l}^{j=1,l}$ и вектор-столбцы: вектор ответов $y = \(y_i\)_{i=1,l}$, вектор двойственных переменных $\lambda = \(\lambda_i\)_{i=1,l}$ и вектор из единиц $e = \(1\)_{i=1,l}$.
Тогда систему \(1\) можно переписать в виде:

\(2\) \left{\begin{array}{lcl}
\frac{1}{2} \lambda^T Q  \lambda - e^T \lambda \to \min_{\lambda};\\
0 \leq \lambda \leq C e;\\
y^T \lambda = 0.\end{array}

Предполагают, что известно разбиение множества объектов на непересекающиеся подмножества \{1,...,l\} = I_O \cup I_C \cup I_S\:

  • I_O = \{i:\ \lambda_i = 0\} - периферийные объекты, у которых отступ M_i \g 1;
  • I_S = \{i:\ 0 \leq \lambda_i \leq C\} - опорные объекты, у которых отступ M_i = 1;
  • I_C = \{i:\ \lambda_i = C\} - объекты-нарушители, у которых отступ M_i < 1.

На подмножествах I_O и I_C значения \lambda_i равны 0 и C, соответственно. Матрицу Q и векторы y, e, \lambda записывают в блочном виде:
$$Q = \left(\begin{matrix}Q_{SS} & Q_{SO} & Q_{SC}\\Q_{OS} & Q_{OO} & Q_{OC}\\Q_{CS} & Q_{CO} & Q_{CC}\end{matrix}\right);\ y = \left(\begin{matrix}y_S\\y_O\\y_C\end{matrix}\right);\ e = \left(\begin{matrix}e_S\\e_O\\e_C\end{matrix}\right);\ \lambda = \left(\begin{matrix}\lambda_S\\0\\Ce_C\end{matrix}\right).$$
А система \(2\) принимает вид:

\(3\) \left{\begin{array}{lcl}
\frac{1}{2} \lambda_S^T Q_{SS} \lambda_S + C e_C^T Q_{CS} \lambda_S - e_S^T \lambda_S \to \min_{\lambda_S};\\
y_S^T \lambda_S + C e_C^T y_C = 0.\end{array}

Это задача минимизации квадратичного функционала с линейным ограничением типа равенства. Ее решение сводится к обращению симметричной положительно определенной матрицы Q_{SS}. Решение ее даст вектор \lambda, которые позволит найти параметры алгоритма $\omega$ и $\omega_0$. После этого проверяют правильность разбиения I_O \cup I_C \cup I_S\.

Алгоритм INCAS

Вход

X^l - обучающая выборка;
C - параметр двойственной задачи.

Выход

параметры линейного классификатора $\omega$ и $\omega_0$.

==

  1. начальное приближение:
    I_S = две ближайшие точки из разных классов;
    I_O = остальные точки;
    I_C = $\emptyset$.
  2. повторять
  3. повторять
  4. решить оптимизационную задачу \(3\)
  5. если |I_S| > 2 и \exists i:\ i \in I_S и \lambda_i \leq 0, то перевести i в I_O
  6. если |I_S| > 2 и \exists i:\ i \in I_S и \lambda_i \geq C, то перевести i в I_C
  7. пока существует i \in I_S, который нужно перевести в I_O или в I_C
  8. вычислить параметры $\omega$ и $\omega_0$
  9. вычислить отступы M_i, i \in I_O \cup I_C
  10. если \exists i:\ i \in I_O и M_i \leq 1, то перевести i в I_S
  11. если \exists i:\ i \in I_S и M_i \geq 1, то перевести i в I_S
  12. пока существует i \in I_O \cup I_C, который нужно перевести в I_S

Начальное приближение

Количество итераций зависит от того, насколько удачно выбрано начальное приближение. "Угадать" множество I_S можно несколькими способами, например:

  • Берется произвольная точка выборки. Ищется ближайшая к ней точка из другого класса. Для нее находится ближайшая точка из первого класса и так далее. Процесс, как правило, быстро сходится к паре пограничных точек. Они и принимаются за начальное приближение I_S.
  • Строятся несколько "грубых" линейных классификаторов. Для каждой разделяющей поверхности находят несколько ближайших к ней точек из разных классов, которыми инициализируют I_S.

Эффективность

  • Оптимизационная задача \(3\) зависит только от матриц Q_{SS}, Q{CS}. Следовательно, скалярные произведения надо вычислять только для пар "опорный-опорный" и "опорный-нарушитель".
  • На каждой итерации к множеству I_S добавляется только один объект. Значит, для пересчета обратной матрицы Q_{SS}^{-1} требуется O\(h^2\) операций, а не O\(h^3\) операций.

Преимущества и недостатки

Преимущества

  • Метод позволяет решать задачи, где нет линейной разделимости
  • Алгоритм особенно эффективен, если число опорных векторов невелико
  • Данные могут поступать в режиме реального времени

Недостатки

  • Алгоритм становится неэффективным, если число опорных векторов велико. В этом случае либо меняют ядро K\(x,x'\), либо саму постановку задачи.

Литература

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_INCAS»
Личные инструменты