Алгоритм INCAS
Материал из MachineLearning.
(Новая: {{Задание|Михаил|Константин Воронцов|7 января 2010}} '''Алгоритм INCAS''' (INCremental Active Set method) - алгоритм настройк...) |
|||
Строка 1: | Строка 1: | ||
- | {{Задание|Михаил|Константин Воронцов|7 января 2010}} | + | Ž{{Задание|Михаил|Константин Воронцов|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:50, 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.
- К.В. Воронцов, Машинное обучение (курс лекций)