Алгоритм INCAS
Материал из MachineLearning.
(→Алгоритм INCAS) |
|||
Строка 77: | Строка 77: | ||
*[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956 citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956] | *[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956 citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956] | ||
*[http://en.wikipedia.org/wiki/Support_vector_machine en.wikipedia.org/wiki/Support_vector_machine] | *[http://en.wikipedia.org/wiki/Support_vector_machine en.wikipedia.org/wiki/Support_vector_machine] | ||
+ | [[Категория:Классификация]] [[Категория: Линейные классификаторы]] |
Версия 19:54, 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.
- К.В. Воронцов, Машинное обучение (курс лекций)