Метод опорных векторов (англ. support vector machine, SVM) — один из наиболее популярных методов обучения, который применяется для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки оптимальным способом. Алгоритм работает в предположении, что чем больше расстояние (зазор) между разделяющей гиперплоскостью и объектами разделяемых классов, тем меньше будет средняя ошибка классификатора.
Содержание
Метод опорных векторов в задаче классификации [ править ]
Разделяющая гиперплоскость [ править ]
Линейно разделимая выборка [ править ]
Но для двух линейно разделимых классов возможны различные варианты построения разделяющих гиперплоскостей. Метод опорных векторов выбирает ту гиперплоскость, которая максимизирует отступ между классами:
Если выборка линейно разделима, то существует такая гиперплоскость, отступ от которой до каждого объекта положителен:
Мы хотим построить такую разделяющую гиперплоскость, чтобы объекты обучающей выборки находились на наибольшем расстоянии от неё.
Заметим, что мы можем упростить постановку задачи:
Краткий обзор алгоритма машинного обучения Метод Опорных Векторов (SVM)
Предисловие
В данной статье мы изучим несколько аспектов SVM:
Как известно, задачи машинного обучения разделены на две основные категории — классификация и регрессия. В зависимости от того, какая из этих задач перед нами стоит, и какой у нас имеется датасет для этой задачи, мы выбираем какой именно алгоритм использовать.
Метод Опорных Векторов или SVM (от англ. Support Vector Machines) — это линейный алгоритм используемый в задачах классификации и регрессии. Данный алгоритм имеет широкое применение на практике и может решать как линейные так и нелинейные задачи. Суть работы “Машин” Опорных Векторов проста: алгоритм создает линию или гиперплоскость, которая разделяет данные на классы.
Теория
Основной задачей алгоритма является найти наиболее правильную линию, или гиперплоскость разделяющую данные на два класса. SVM это алгоритм, который получает на входе данные, и возвращает такую разделяющую линию.
Рассмотрим следующий пример. Допустим у нас есть набор данных, и мы хотим классифицировать и разделить красные квадраты от синих кругов (допустим позитивное и отрицательное). Основной целью в данной задаче будет найти “идеальную” линию которая разделит эти два класса.
Найдите идеальную линию, или гиперплоскость, которая разделит набор данных на синий и красный классы.
На первый взгляд, не так уж и сложно, правда?
Но, как вы можете заметить, нет одной, уникальной, линии, которая бы решала такую задачу. Мы можем подобрать бесконечное множество таких линий, которые могут разделить эти два класса. Как же именно SVM находит “идеальную” линию, и что в его понимании “идеальная”?
Взгляните на пример ниже, и подумайте какая из двух линий (желтая или зеленая) лучше всего разделяет два класса, и подходит под описаниие “идеальной”?
Какая линия лучше разделяет набор данных по вашему мнению?
Если вы выбрали желтую прямую, я вас поздравляю: это та самая линия, которую бы выбрал алгоритм. В данном примере мы можем интуитивно понять что желтая линия разделяет и соответственно классифицирует два класса лучше зеленой.
В случае с зеленой линией — она расположена слишком близко к красному классу. Несмотря на то, что она верно классифицировала все объекты текущего набора данных, такая линия не будет генерализованной — не будет так же хорошо вести себя с незнакомым набором данных. Задача нахождения генерализованной разделяющей двух классов является одной из основных задач в машинном обучении.
Как SVM находит лучшую линию
Алгоритм SVM устроен таким образом, что он ищет точки на графике, которые расположены непосредственно к линии разделения ближе всего. Эти точки называются опорными векторами. Затем, алгоритм вычисляет расстояние между опорными векторами и разделяющей плоскостью. Это расстояние которое называется зазором. Основная цель алгоритма — максимизировать расстояние зазора. Лучшей гиперплоскостью считается такая гиперплоскость, для которой этот зазор является максимально большим.
Довольно просто, не так ли? Рассмотрим следующий пример, с более сложным датасетом, который нельзя разделить линейно.
Очевидно, что этот набор данных нельзя разделить линейно. Мы не можем начертить прямую линию, которая бы классифицировала эти данные. Но, этот датасет можно разделить линейно, добавив дополнительное измерение, которое мы назовем осью Z. Представим, что координаты на оси Z регулируются следующим ограничением:
Таким образом, ордината Z представлена из квадрата расстояния точки до начала оси. Ниже приведена визуализация того же набора данных, на оси Z.
Теперь данные можно разделить линейно. Допустим пурпурная линия разделяющая данные z=k, где k константа. Если
, то следовательно и
— формула окружности. Таким образом, мы можем спроэцировать наш линейный разделитель, обратно к исходному количеству измерений выборки, используя эту трансформацию.
В результате, мы можем классифицировать нелинейный набор данных добавив к нему дополнительное измерение, а затем, привести обратно к исходному виду используя математическую трансформацию. Однако, не со всеми наборами данных можно с такой же легкостью провернуть такую трансформацию. К счастью, имплементация этого алгоритма в библиотеке sklearn решает эту задачу за нас.
Гиперплоскость
Теперь, когда мы ознакомились с логикой алгоритма, перейдем к формальному определению гиперплоскости
Гиперплоскость — это n-1 мерная подплоскость в n-мерном Евклидовом пространстве, которая разделяет пространство на две отдельные части.
Например, представим что наша линия представлена в виде одномерного Евклидова пространства (т.е. наш набор данных лежит на прямой). Выберите точку на этой линии. Эта точка разделит набор данных, в нашем случае линию, на две части. У линии есть одна мера, а у точки 0 мер. Следовательно, точка — это гиперплоскость линии.
Для двумерного датасета, с которым мы познакомились ранее, разделяющая прямая была той самой гиперплоскостью. Проще говоря, для n-мерного пространства существует n-1 мерная гиперплоскость, разделяющая это пространство на две части.
Точки представлены в виде массива X, а классы к которому они принадлежат в виде массива y. Теперь мы обучим нашу модель этой выборкой. Для данного примера я задал линейный параметр “ядра” классификатора (kernel).
Предсказание класса нового объекта
Настройка параметров
Параметры — это аргументы которые вы передаете при создании классификатора. Ниже я привел несколько самых важных настраиваемых параметров SVM:
Данный параметр помогает отрегулировать ту тонкую грань между “гладкостью” и точностью классификации объектов обучающей выборки. Чем больше значение “С” тем больше объектов обучающей выборки будут правильно классифицированы.
В данном примере есть несколько порогов принятия решений, которые мы можем определить для этой конкретной выборки. Обратите внимание на прямую (представлена на графике в виде зеленой линии) порога решений. Она довольно таки проста, и по этой причине, несколько объектов были классифицированы неверно. Эти точки, которые были классифицированы неправильно называются выбросами в данных.
Мы также можем настроить параметры таким образом, что в конечном итоге получим более изогнутую линию (светло-голубой порог решений), которая будет классфицировать асболютно все данные обучающей выборки правильно. Конечно, в таком случае, шансы того, что наша модель сможет генерализовать и показать столь же хорошие результаты на новых данных, катастрофически мала. Следовательно, если вы пытаетесь достигнуть точности при обучении модели, вам стоит нацелиться на что-то более ровное, прямое. Чем выше число “С” тем более запутанная гиперплоскость будет в вашей модели, но и выше число верно-классифицированных объектов обучающей выборки. Поэтому, важно “подкручивать” параметры модели под конкретный набор данных, чтобы избежать переобучения но, в то же время достигнуть высокой точности.
В официальной документации библиотека SciKit Learn говорится, что гамма определяет насколько далеко каждый из элементов в наборе данных имеет влияние при определении “идеальной линии”. Чем ниже гамма, тем больше элементов, даже тех, которые достаточно далеки от разделяющей линии, принимают участие в процессе выбора этой самой линии. Если же, гамма высокая, тогда алгоритм будет “опираться” только на тех элементах, которые наиболее близки к самой линии. Если задать уровень гаммы слишком высоким, тогда в процессе принятия решения о расположении линии будут учавствовать только самые близкие к линии элементы. Это поможет игнорировать выбросы в данных. Алгоритм SVM устроен таким образом, что точки расположенные наиболее близко относительно друг друга имеют больший вес при принятии решения. Однако при правильной настройке «C» и «gamma» можно добиться оптимального результата, который построит более линейную гиперплоскость игнорирующую выбросы, и следовательно, более генерализуемую.
Заключение
Я искренне надеюсь, что эта статья помогла вам разобраться в сути работы SVM или Метода Опорных Векторов. Я жду от вас любых комментариев и советов. В последующих публикациях я расскажу о математической составляющей SVM и о проблемах оптимизации.
В данной статье я хочу рассказать о проблеме классификации данных методом опорных векторов (Support Vector Machine, SVM). Такая классификация имеет довольно широкое применение: от распознавания образов или создания спам-фильтров до вычисления распределения горячих аллюминиевых частиц в ракетных выхлопах.
Сначала несколько слов об исходной задаче. Задача классификации состоит в определении к какому классу из, как минимум, двух изначально известных относится данный объект. Обычно таким объектом является вектор в n-мерном вещественном пространстве . Координаты вектора описывают отдельные аттрибуты объекта. Например, цвет c, заданный в модели RGB, является вектором в трехмерном пространстве: c=(red, green, blue).
Если классов всего два («спам / не спам», «давать кредит / не давать кредит», «красное / черное»), то задача называется бинарной классификацией. Если классов несколько — многоклассовая (мультиклассовая) классификация. Также могут иметься образцы каждого класса — объекты, про которые заранее известно к какому классу они принадлежат. Такие задачи называют обучением с учителем, а известные данные называются обучающей выборкой. (Примечание: если классы изначально не заданы, то перед нами задача кластеризации.)
Метод опорных векторов, рассматриваемый в данной статье, относится к обучению с учителем.
Итак, математическая формулировка задачи классификации такова: пусть X — пространство объектов (например, ), Y — наши классы (например, Y = <-1,1>). Дана обучающая выборка: . Требуется построить функцию (классификатор), сопоставляющий класс y произвольному объекту x.
Метод опорных векторов
Данный метод изначально относится к бинарным классификаторам, хотя существуют способы заставить его работать и для задач мультиклассификации.
Идея метода
Идею метода удобно проиллюстрировать на следующем простом примере: даны точки на плоскости, разбитые на два класса (рис. 1). Проведем линию, разделяющую эти два класса (красная линия на рис. 1). Далее, все новые точки (не из обучающей выборки) автоматически классифицируются следующим образом:
точка выше прямой попадает в класс A, точка ниже прямой — в класс B.
Такую прямую назовем разделяющей прямой. Однако, в пространствах высоких размерностей прямая уже не будет разделять наши классы, так как понятие «ниже прямой» или «выше прямой» теряет всякий смысл. Поэтому вместо прямых необходимо рассматривать гиперплоскости — пространства, размерность которых на единицу меньше, чем размерность исходного пространства. В , например, гиперплоскость — это обычная двумерная плоскость.
В нашем примере существует несколько прямых, разделяющих два класса (рис. 2):
С точки зрения точности классификации лучше всего выбрать прямую, расстояние от которой до каждого класса максимально. Другими словами, выберем ту прямую, которая разделяет классы наилучшим образом (красная прямая на рис.2). Такая прямая, а в общем случае — гиперплоскость, называется оптимальной разделяющей гиперплоскостью.
Вектора, лежащие ближе всех к разделяющей гиперплоскости, называются опорными векторами (support vectors). На рисунке 2 они помечены красным.
Немного математики
Пусть имеется обучающая выборка: .
Далее, мы хотим выбрать такие w и b которые максимизируют расстояние до каждого класса. Можно подсчитать, что данное расстояние равно . Проблема нахождения максимума эквивалентна проблеме нахождения минимума . Запишем все это в виде задачи оптимизации:
которая является стандартной задачей квадратичного программирования и решается с помощью множителей Лагранжа. Описание данного метода можно найти в Википедии.
Линейная неразделимость
На практике случаи, когда данные можно разделить гиперплоскостью, или, как еще говорят, линейно, довольно редки. Пример линейной неразделимости можно видеть на рисунке 3:
В этом случае поступают так: все элементы обучающей выборки вкладываются в пространство X более высокой размерности с помощью специального отображения . При этом отображение выбирается так, чтобы в новом пространстве X выборка была линейно разделима.
Классифицирующая функция F принимает вид . Выражение называется ядром классификатора. С математической точки зрения ядром может служить любая положительно определенная симметричная функция двух переменных. Положительная определенность необходимо для того, чтобы соответствующая функция Лагранжа в задаче оптимизации была ограничена снизу, т.е. задача оптимизации была бы корректно определена.
Точность классификатора зависит, в частности, от выбора ядра. На видео можно увидеть иллюстрирацию классификации при помощи полиномиального ядра:
Чаще всего на практике встречаются следующие ядра:
Полиномиальное:
Радиальная базисная функция:
Гауссова радиальная базисная функция:
Сигмоид:
Заключение и литература
Среди других классификаторов хочу отметить также метод релевантных векторов (Relevance Vector Machine, RVM). В отличие от SVM данный метод дает вероятности, с которыми объект принадлежит данному классу. Т.е. если SVM говорит «x пирнадлежит классу А», то RVM скажет «x принадлежит классу А с вероятностью p и классу B с вероятностью 1-p«.
1. Christopher M. Bishop.Pattern recognition and machine learning, 2006.
К недостаткам опорных векторных машин можно отнести:
1.4.1. Классификация
После установки модель может быть использована для прогнозирования новых значений:
1.4.1.1. Мультиклассовая классификация
С другой стороны, LinearSVC реализует мультиклассовую стратегию «один против остальных», таким образом обучая n_classes модели.
См. « Математическая формулировка» для полного описания решающей функции.
Для «один против остальных» LinearSVC атрибуты coef_ и intercept_ имеют форму (n_classes, n_features) и (n_classes, ) соответственно. Каждая строка коэффициентов соответствует одному из классификаторов n_classes «один против остальных» и аналогичных для перехватов в порядке класса «один».
Форма dual_coef_ является (n_classes-1, n_SV) с довольно трудно макетом обхвата. Столбцы соответствуют опорным векторам, включенным в любой из n_classes * (n_classes — 1) / 2 классификаторов «один на один». Каждый из опорных векторов используется в n_classes — 1 классификаторах. Эти n_classes — 1 записи в каждой строке соответствует двойственным коэффициентам для этих классификаторов.
$\alpha^<0>_<0,1>$
$\alpha^<0>_<0,2>$
Коэффициенты для КА класса 0
$\alpha^<1>_<0,1>$
$\alpha^<1>_<0,2>$
Коэффициенты для КА класса 0
$\alpha^<2>_<0,1>$
$\alpha^<2>_<0,2>$
Коэффициенты для КА класса 0
$\alpha^<0>_<1,0>$
$\alpha^<0>_<1,2>$
Коэффициенты для КА класса 1
$\alpha^<1>_<1,0>$
$\alpha^<1>_<1,2>$
Коэффициенты для КА класса 1
$\alpha^<0>_<2,0>$
$\alpha^<0>_<2,1>$
Коэффициенты для КА 2 класса
$\alpha^<1>_<2,0>$
$\alpha^<1>_<2,1>$
Коэффициенты для КА 2 класса
1.4.1.2. Результаты и вероятности
Перекрестная проверка, связанная с масштабированием Platt, — дорогостоящая операция для больших наборов данных. Кроме того, оценки вероятности могут не соответствовать оценкам:
1.4.1.3. Несбалансированные проблемы
SVC (но не NuSVC ) реализует параметр class_weight в fit методе. Это словарь формы , где значение — это число с плавающей точкой number > 0, которое устанавливает С для параметра класса class_label значение C * value. На рисунке ниже показана граница решения несбалансированной проблемы с поправкой на вес и без нее.
1.4.2. Регрессия
Метод классификации опорных векторов может быть расширен для решения задач регрессии. Этот метод называется регрессией опорных векторов.
Модель, созданная с помощью классификации опорных векторов (как описано выше), зависит только от подмножества обучающих данных, потому что функция затрат для построения модели не заботится о точках обучения, которые лежат за пределами поля. Аналогичным образом модель, созданная с помощью регрессии опорных векторов, зависит только от подмножества обучающих данных, поскольку функция стоимости игнорирует образцы, прогноз которых близок к их целевому значению.
Как и в случае с классами классификации, метод соответствия будет принимать в качестве аргументов векторы X, y, только в этом случае ожидается, что y будет иметь значения с плавающей запятой вместо целочисленных значений:
1.4.3. Оценка плотности, обнаружение новизны
Класс OneClassSVM реализует одноклассную SVM, которая используется для обнаружения выбросов.
См. Раздел Обнаружение новинок и выбросов для описания и использования OneClassSVM.
1.4.4. Сложность
1.4.5. Советы по практическому использованию
См. Раздел « Предварительная обработка данных» для получения более подробной информации о масштабировании и нормализации.
1.4.6. Функции ядра
Функция ядра может быть любой из следующих:
Разные ядра задаются kernel параметром:
1.4.6.1. Параметры ядра RBF
Правильный выбор C и gamma имеет решающее значение для производительности SVM. Рекомендуется использовать GridSearchCV с C и gamma экспоненциально далеко друг от друга, чтобы выбрать хорошие значения.
1.4.6.2. Пользовательские ядра
Вы можете определить свои собственные ядра, указав ядро как функцию Python или предварительно вычислив матрицу Грама.
Классификаторы с пользовательскими ядрами ведут себя так же, как и любые другие классификаторы, за исключением того, что:
1.4.6.2.1. Использование функций Python в качестве ядер
Вы можете использовать собственные определенные ядра, передав функцию kernel параметру.
Ваше ядро должно принимать в качестве аргументов две матрицы формы (n_samples_1, n_features), (n_samples_2, n_features) и возвращает матрицу ядра в форме (n_samples_1, n_samples_2)
Следующий код определяет линейное ядро и создает экземпляр классификатора, который будет использовать это ядро:
1.4.6.2.2. Используя матрицу Грама
Вы можете передать предварительно вычисленные ядра, используя kernel=’precomputed’ параметр. Затем вы должны передать матрицу Грама вместо X к fit и predict методам. Должны быть предоставлены значения ядра между всеми обучающими векторами и тестовыми векторами:
1.4.7. Математическая постановка
Машина опорных векторов конструирует гиперплоскость или набор гиперплоскостей в пространстве большой или бесконечной размерности, которые можно использовать для классификации, регрессии или других задач. Интуитивно хорошее разделение достигается за счет гиперплоскости, которая имеет наибольшее расстояние до ближайших точек обучающих данных любого класса (так называемый функциональный запас), поскольку, как правило, чем больше запас, тем ниже ошибка обобщения классификатора. На рисунке ниже показана функция решения для линейно разделяемой задачи с тремя образцами на границах запаса, называемыми «векторами поддержки»:
В общем, когда проблема не является линейно разделимой, опорные векторы являются выборками в пределах границ поля.
Мы рекомендуем 13 и 14 как хорошие справочные материалы по теории и практике SVM.
1.4.7.1. SVC
SVC решает следующую основную проблему: $$\min_ \frac<1> <2>w^T w + C \sum_^ \zeta_i$$ $$\textrm y_i (w^T \phi (x_i) + b) \geq 1 — \zeta_i,$$ $$\zeta_i \geq 0, i=1, …, n$$
Первичную задачу можно эквивалентно сформулировать как $$\min_ \frac<1> <2>w^T w + C \sum_\max(0, |y_i — (w^T \phi(x_i) + b)| — \varepsilon),$$
1.4.8. Детали реализации
Внутри мы используем libsvm 12 и liblinear 11 для обработки всех вычислений. Эти библиотеки обернуты с использованием C и Cython. Описание реализации и детали используемых алгоритмов см. В соответствующих документах.
