Алгоритм INCAS
Материал из MachineLearning.
Строка 1: | Строка 1: | ||
- | + | {{Задание|Михаил|Константин Воронцов|7 января 2010}} | |
'''Алгоритм INCAS''' (INCremental Active Set method) - алгоритм настройки [[SVM]].<br><br> | '''Алгоритм INCAS''' (INCremental Active Set method) - алгоритм настройки [[SVM]].<br><br> | ||
Рассматривается задача классификации на два непересекающихся класса, <tex>Y = \{-1, 1\}</tex>, а <tex>X = R^n</tex>. '''Алгоритм INCAS''' позволяет уменьшить число вычислений при построении [[SVM]]. | Рассматривается задача классификации на два непересекающихся класса, <tex>Y = \{-1, 1\}</tex>, а <tex>X = R^n</tex>. '''Алгоритм INCAS''' позволяет уменьшить число вычислений при построении [[SVM]]. | ||
Строка 39: | Строка 39: | ||
:параметры линейного классификатора <tex>$\omega$</tex> и <tex>$\omega_0$</tex>. | :параметры линейного классификатора <tex>$\omega$</tex> и <tex>$\omega_0$</tex>. | ||
---- | ---- | ||
- | |||
#начальное приближение: | #начальное приближение: | ||
#:<tex>I_S</tex> = две ближайшие точки из разных классов; | #:<tex>I_S</tex> = две ближайшие точки из разных классов; |
Версия 19:51, 4 января 2010
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм INCAS (INCremental Active Set method) - алгоритм настройки SVM.
Рассматривается задача классификации на два непересекающихся класса, , а . Алгоритм INCAS позволяет уменьшить число вычислений при построении SVM.
Содержание |
Двойственная задача
При построении SVM приходится решать двойственную задачу:
Здесь - вектор двойственных переменных, - параметр алгоритма.
Если решение задачи известно, то возможно найти параметры линейного классификатора и .
Задача является задачей квадратичного программирования. Методы решения подобных задач известны, но они трудоемки. Поэтому для обучения SVM применяют алгоритмы, которые учитывают его специфические особенности. Один из них - последовательный метод активных ограничений, INCAS.
Преобразованная двойственная задача
Двойственную задачу преобразовывают следующим образом. Вводятся матрица и вектор-столбцы: вектор ответов , вектор двойственных переменных и вектор из единиц .
Тогда систему можно переписать в виде:
Предполагают, что известно разбиение множества объектов на непересекающиеся подмножества :
- - периферийные объекты, у которых отступ ;
- - опорные объекты, у которых отступ ;
- - объекты-нарушители, у которых отступ .
На подмножествах и значения равны и , соответственно. Матрицу и векторы записывают в блочном виде:
А система принимает вид:
Это задача минимизации квадратичного функционала с линейным ограничением типа равенства. Ее решение сводится к обращению симметричной положительно определенной матрицы . Решение ее даст вектор , которые позволит найти параметры алгоритма и . После этого проверяют правильность разбиения .
Алгоритм INCAS
Вход
- - обучающая выборка;
- - параметр двойственной задачи.
Выход
- параметры линейного классификатора и .
- начальное приближение:
- = две ближайшие точки из разных классов;
- = остальные точки;
- = .
- повторять
- повторять
- решить оптимизационную задачу
- если и и , то перевести в
- если и и , то перевести в
- пока существует , который нужно перевести в или в
- вычислить параметры и
- вычислить отступы
- если и , то перевести в
- если и , то перевести в
- пока существует , который нужно перевести в
Начальное приближение
Количество итераций зависит от того, насколько удачно выбрано начальное приближение. "Угадать" множество можно несколькими способами, например:
- Берется произвольная точка выборки. Ищется ближайшая к ней точка из другого класса. Для нее находится ближайшая точка из первого класса и так далее. Процесс, как правило, быстро сходится к паре пограничных точек. Они и принимаются за начальное приближение .
- Строятся несколько "грубых" линейных классификаторов. Для каждой разделяющей поверхности находят несколько ближайших к ней точек из разных классов, которыми инициализируют .
Эффективность
- Оптимизационная задача зависит только от матриц . Следовательно, скалярные произведения надо вычислять только для пар "опорный-опорный" и "опорный-нарушитель".
- На каждой итерации к множеству добавляется только один объект. Значит, для пересчета обратной матрицы требуется операций, а не операций.
Преимущества и недостатки
Преимущества
- Метод позволяет решать задачи, где нет линейной разделимости
- Алгоритм особенно эффективен, если число опорных векторов невелико
- Данные могут поступать в режиме реального времени
Недостатки
- Алгоритм становится неэффективным, если число опорных векторов велико. В этом случае либо меняют ядро , либо саму постановку задачи.
Литература
- S. Fine, K. Scheinberg, INCAS: An incremental active set method for SVM, 2002.
- K. Scheinberg, An efficient implementation of an active set method for svms, 2006.
- К.В. Воронцов, Машинное обучение (курс лекций)