Метод Support Vector Machine для решения задач классификации

Постановка задачи

Классификация – распределение объектов по заранее заданным классам в зависи-мости от общих признаков. В литературе часто употребляются синонимы термина «клас-сификация», например, «распознавание образов» (Pattern Recognition) или «категориза-ция текстов» (Text Categorization) в зависимости от прикладной области.
Приведем формальную постановку задачи классификации. Для простоты будем считать, что имеется всего два класса. Пусть заданы:
• множество Х обучающих объектов, заданных векторами признаков: X={X1, X2, ..., XN}, ХRd (Х является подмножеством евклидова пространства размерности d);
• множество Y ответов для обучающих объектов: Y={y1, y2, ..., yN}, yi{–1, +1} (два класса).
Тогда задача классификации состоит в построении такого алгоритма А (решающе-го правила, функции), который каждому вектору Xi (i=1..N) сопоставляет правильный ответ yi, то есть А: Х → Y. В дальнейшем построенный алгоритм должен применяться для классификации произвольного вектора Х, о классовой принадлежности которого ни-чего неизвестно.

Алгоритмы обучения

Обучение SVM сводится к решению задачи квадратичной оптимизации с предель-ными ограничивающими условиями и одним ограничением линейного равенства. Не-смотря на то, что существуют успешные методы решения подобных задач, при обучении SVM следует учитывать множество факторов. В частности, многие стандартные методы решения задач квадратичного программирования технически непригодны для задач обу-чения текстовых SVM-классификаторов, поскольку требуют слишком длительного вре-мени обучения и больших объемов памяти для вычислений.
Привести четкую классификацию алгоритмов обучения SVM достаточно сложно, ввиду большого количества различных подходов. Можно выделить несколько больших групп методов.
Первую группу составляют традиционные методы решения оптимизационных за-дач, которые применяются в общем случае и для обучения искусственных нейронных се-тей. Применительно к SVM данные методы используются, когда количество обучающих примеров относительно невелико (до 4000 – 5000). К этой группе относятся различные методы поиска седловой точки функции Лагранжа – методы Ньютона, квазиньютонов-ские методы, методы сопряженных направлений и др. (первым для обучения SVM был предложен метод сопряженных градиентов [10]). В настоящее время достаточно популя-рен градиентный алгоритм Kernel-Adatron [11].
Вторую большую группу составляют методы обучения SVM, идея которых осно-вана на разбиении одной большой задачу на ряд подзадач. Первый подход по разбиению больших задач обучения SVM на серии меньших задач оптимизации был предложен в [3]. Он известен как алгоритм «образования фрагментов» (chunking). Алгоритм начинает со случайного подмножества обучающих данных, решает эту задачу и многократно до-бавляет примеры, которые нарушают условия оптимальности. В [12] был предложен ме-тод декомпозиции, который разбивает оптимизационную задачу на неактивную и актив-ную части (так называемый «рабочий набор»). Главным преимуществом данного метода является то, что он предлагает алгоритмы с требованиями памяти, которые линейны от-носительно количества обучающих примеров и количества опорных векторов. Данный алгоритм, усовершенствованный в части оптимизации выбора рабочего набора и кэши-рования данных применяется в популярной программе SVMLight [13]. В группе методов декомпозиции наиболее эффективен на сегодняшний день алгоритм последовательной минимальной оптимизации (Sequential Minimal Optimization, SMO), предложенный Плат-том [14]. Его можно рассматривать как предельный случай алгоритма декомпозиции, размер рабочего набора в котором всегда равен 2, а для поиска оптимального рабочего набора используется набор эвристик.
Ко второй группе можно отнести и методы, основанные на аппроксимации гессен-ской матрицы (матрицы частных производных функции Лагранжа) с помощью более мелких матриц, используя или низкоуровневое представление ([15]) или выбор-ку/дискретизацию ([16, 17]), тем самым уменьшая размер задачи оптимизации и ускоряя процесс обучения.
Третью группу составляют методы обучения, основанные на вычленении из боль-шого набора входных данных тех векторов, которые являются опорными, поскольку только они определяют оптимальное решение оптимизационной задачи для SVM. Такой подход используется, например, в [18, 19, 20]. Сюда же можно отнести и так называемые инкрементные методы обучения, которые предполагают последовательное обучение SVM на новых данных при удалении всех предыдущих данных за исключением их опор-ных векторов [21], [22]. Преимуществом инкрементных методов является возможность быстрого переобучения SVM при появлении новых данных.
Приведенная выше классификация методов обучения SVM является достаточно условной и, возможно, неполной, поскольку существуют и другие алгоритмы (например вероятностный SVM [23]). В то же время она дает представление о многообразии мето-дов обучения SVM, которые постоянно совершенствуются и развиваются.
Среди указанных методов не существует наилучшего. Каждый из них имеет «свой» набор данных, на котором он показывает оптимальные результаты. Задача исследователя или разработчика – выбрать из имеющихся методов наилучший для данной области.

Применение

В заключение укажем несколько наиболее распространенных областей применения метода SVM и его модификаций.
1) Машинное зрение – распознавание лиц и других объектов на фотографиях и ви-деоизображении, задачи идентификации.
2) Классификация текстов – тематическая классификация веб-страниц, поиск в Интернете, фильтрация электронной почты от спама.
3) Распознавание рукописных символов – на тестовом наборе из 60000 рукопис-ных цифр, созданном в американском институте NIST (National Institute of Standards and Technology), метод SVM показал наименьшее число ошибок (0,56%) по сравнению с нейронными сетями и статистическими методами.
4) Биоинформатика – анализ генетических цепочек, определение аминокислотной последовательности белков и др.
5) Анализ временных последовательностей – распознавание аномального трафика в компьютерных сетях.
Таким образом, метод SVM в настоящее время находит применение в актуальных сферах Computer Science и смежных областей. В то же время метод продолжает привле-кать внимание исследователей, особенно в таких аспектах как разработка новых алго-ритмов обучения, построение правил выбора ядерных функций и их параметров, созда-ние методов многоклассового SVM.