Метод опорных векторов для чайников в excel
Обновлено: 04.07.2024
- Эффективен в пространствах больших размеров.
- По-прежнему эффективен в случаях, когда количество измерений превышает количество образцов.
- Использует подмножество обучающих точек в функции принятия решений (называемых опорными векторами), поэтому это также эффективно с точки зрения памяти.
- Универсальность: для функции принятия решения могут быть указаны различные функции ядра . Предоставляются общие ядра, но также можно указать собственные ядра.
К недостаткам опорных векторных машин можно отнести:
- Если количество функций намного превышает количество выборок, избегайте чрезмерной подгонки при выборе функций ядра, и термин регуляризации имеет решающее значение.
- SVM не предоставляют напрямую оценки вероятностей, они рассчитываются с использованием дорогостоящей пятикратной перекрестной проверки (см. Оценки и вероятности ниже).
Метод опорных векторов в scikit-learn поддерживают как плотные ( numpy.ndarray и конвертируемые в это numpy.asarray ), так и разреженные (любые scipy.sparse ) выборочные векторы в качестве входных данных. Однако, чтобы использовать SVM для прогнозирования разреженных данных, он должен соответствовать этим данным. Для оптимальной производительности используйте C-порядковый numpy.ndarray (плотный) или scipy.sparse.csr_matrix (разреженный) с dtype=float64 .
1.4.1. Классификация
SVC , NuSVC и LinearSVC являются классами, способными выполнять двоичную и мультиклассовую классификацию набора данных.
SVC и NuSVC являются аналогичными методами, но принимают несколько разные наборы параметров и имеют разные математические формулировки (см. раздел Математическая формулировка ). С другой стороны, LinearSVC это еще одна (более быстрая) реализация классификации опорных векторов для случая линейного ядра. Обратите внимание, что LinearSVC параметр не принимает kernel , так как предполагается, что он линейный. Ему также не хватает некоторых атрибутов SVC и NuSVC , например support_ .
Как и другие классификаторы SVC , NuSVC и LinearSVC в качестве входных двух массивов: массив X формы (n_samples, n_features), проведение обучающих выборок, и массив y из класса меток (строки или целые числа), в форме (n_samples):
После установки модель может быть использована для прогнозирования новых значений:
Функция принятия решения SVM (подробно описанная в математической формулировке ) зависит от некоторого подмножества обучающих данных, называемых опорными векторами. Некоторые свойства этих опорных векторов можно найти в атрибутах support_vectors_ , support_ а также n_support_ :
1.4.1.1. Мультиклассовая классификация
С другой стороны, LinearSVC реализует мультиклассовую стратегию «один против остальных», таким образом обучая n_classes модели.
См. « Математическая формулировка» для полного описания решающей функции.
Обратите внимание, что LinearSVC также реализуется альтернативная мультиклассовая стратегия, так называемая мультиклассовая SVM, сформулированная Краммером и Зингером 16 , с использованием этой опции multi_class='crammer_singer' . На практике обычно предпочтительнее использовать классификацию «один против остальных», поскольку результаты в основном схожи, но время выполнения значительно меньше.
Для «один против остальных» LinearSVC атрибуты coef_ и intercept_ имеют форму (n_classes, n_features) и (n_classes, ) соответственно. Каждая строка коэффициентов соответствует одному из классификаторов n_classes «один против остальных» и аналогичных для перехватов в порядке класса «один».
Это может быть яснее на примере: рассмотрим проблему трех классов с классом 0, имеющим три опорных вектора. $v_0^0$,$v_0^1$,$v_0^2$ и классы 1 и 2, имеющие два опорных вектора $v_1^0$,$v_1^1$ а также $v_2^0$,$v_2^1$ соответственно. Для каждого опорного вектора $v_i^j$, есть два двойственных коэффициента. Назовем коэффициент опоры вектором $v_i^j$ в классификаторе между классами $i$ а также $k$ $\alpha^_$. Тогда dual_coef_ выглядит так:
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА класса 0 |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА класса 0 |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА класса 0 |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА класса 1 |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА класса 1 |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА 2 класса |
| $\alpha^_$ | $\alpha^_$ | Коэффициенты для КА 2 класса |
1.4.1.2. Результаты и вероятности
Метод decision_function из SVC и NuSVC дает по классам баллов для каждого образца (или единого показателя на образец в двоичном случае). Если для параметра конструктора probability установлено значение True , включаются оценки вероятности членства в классе (из методов predict_proba и predict_log_proba ). В двоичном случае вероятности калибруются с использованием шкалы Платта 9 : логистическая регрессия по оценкам SVM, согласованная с помощью дополнительной перекрестной проверки данных обучения. В случае мультикласса это расширяется в соответствии с 10 .
Та же процедура калибровки вероятности доступна для всех оценщиков через CalibratedClassifierCV (см. Калибровка вероятности ). В случае SVC и NuSVC эта процедура встроена в libsvm, которая используется под капотом, поэтому она не полагается на scikit-learn CalibratedClassifierCV .
Известно также, что метод Платта имеет теоретические проблемы. Если требуются оценки достоверности, но они не обязательно должны быть вероятностями, то рекомендуется установить probability=False и использовать decision_function вместо predict_proba .
1.4.1.3. Несбалансированные проблемы
В задачах, где желательно придать большее значение определенным классам или определенным отдельным образцам, можно использовать параметры class_weight и sample_weight .
SVC , NuSVC , SVR , NuSVR , LinearSVC , LinearSVR и OneClassSVM осуществить также веса для отдельных образцов в fit методе через sample_weight параметр. Подобно тому class_weight , это устанавливает параметр C для i-го примера равным C * sample_weight[i], что побуждает классификатор правильно определять эти образцы. На рисунке ниже показано влияние взвешивания выборки на границу принятия решения. Размер кружков пропорционален весу образца:
1.4.2. Регрессия
Метод классификации опорных векторов может быть расширен для решения задач регрессии. Этот метод называется регрессией опорных векторов.
Модель, созданная с помощью классификации опорных векторов (как описано выше), зависит только от подмножества обучающих данных, потому что функция затрат для построения модели не заботится о точках обучения, которые лежат за пределами поля. Аналогичным образом модель, созданная с помощью регрессии опорных векторов, зависит только от подмножества обучающих данных, поскольку функция стоимости игнорирует образцы, прогноз которых близок к их целевому значению.
Есть три различных реализаций опорных векторов регрессии: SVR , NuSVR и LinearSVR . LinearSVR обеспечивает более быструю реализацию, чем, SVR но учитывает только линейное ядро, но NuSVR реализует несколько иную формулировку, чем SVR и LinearSVR . См. Подробности реализации для получения дополнительной информации.
Как и в случае с классами классификации, метод соответствия будет принимать в качестве аргументов векторы X, y, только в этом случае ожидается, что y будет иметь значения с плавающей запятой вместо целочисленных значений:
1.4.3. Оценка плотности, обнаружение новизны
Класс OneClassSVM реализует одноклассную SVM, которая используется для обнаружения выбросов.
См. Раздел Обнаружение новинок и выбросов для описания и использования OneClassSVM.
1.4.4. Сложность
Для линейного случая, алгоритм , используемый в LinearSVC по liblinear реализации является гораздо более эффективным , чем его libsvm SVC аналог и может масштабироваться почти линейно миллионы образцов и/или функций.
1.4.5. Советы по практическому использованию
- Избегая копирования данных : Для SVC , SVR , NuSVC и NuSVR если данные , передаваемые в некоторых методов не C упорядоченный непрерывный и двойной точности, то он будет скопирован перед вызовом основной реализации C. Вы можете проверить, является ли данный массив numpy непрерывным, проверив его flags атрибут.
См. Раздел « Предварительная обработка данных» для получения более подробной информации о масштабировании и нормализации.
- Что касается shrinking параметра, цитируя 12 : мы обнаружили, что если количество итераций велико, то сжатие может сократить время обучения. Однако, если мы решим проблему оптимизации слабо (например, используя большой допуск остановки), код без использования сжатия может быть намного быстрее.
- Параметр nu в NuSVC / OneClassSVM / NuSVR приближает долю ошибок обучения и опорных векторов.
- В SVC случае, если данные несбалансированы (например, много положительных и мало отрицательных), установите class_weight='balanced' и/или попробуйте разные параметры штрафа C .
- Случайность базовых реализаций : базовые реализации SVC и NuSVC используют генератор случайных чисел только для перетасовки данных для оценки вероятности (когда probability установлено значение True ). Этой случайностью можно управлять с помощью random_state параметра. Если probability установлено значение, False эти оценки не являются случайными и random_state не влияют на результаты. Базовая OneClassSVM реализация аналогична реализациям SVC и NuSVC . Поскольку оценка вероятности не предусмотрена OneClassSVM , она не является случайной.
1.4.6. Функции ядра
Функция ядра может быть любой из следующих:
Разные ядра задаются kernel параметром:
1.4.6.1. Параметры ядра RBF
Правильный выбор C и gamma имеет решающее значение для производительности SVM. Рекомендуется использовать GridSearchCV с C и gamma экспоненциально далеко друг от друга, чтобы выбрать хорошие значения.
1.4.6.2. Пользовательские ядра
Вы можете определить свои собственные ядра, указав ядро как функцию Python или предварительно вычислив матрицу Грама.
Классификаторы с пользовательскими ядрами ведут себя так же, как и любые другие классификаторы, за исключением того, что:
- Поле support_vectors_ теперь пустое, в нем хранятся только индексы опорных векторов support_
- Ссылка (а не копия) первого аргумента fit() метода сохраняется для использования в будущем. Если этот массив изменится между использованием fit() и predict() вы получите неожиданные результаты.
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
Данные обучающие векторы $x_i \in \mathbb^p$, i = 1,…, n, в двух классах, и вектор $y \in \left\^n$ наша цель найти $w \in\mathbb^p$ а также $b \in \mathbb$ такой, что предсказание, данное $\text (w^T\phi(x) + b)$ подходит для большинства образцов.
Интуитивно мы пытаемся максимизировать маржу (минимизируя $||w||^2 = w^Tw$), при этом налагается штраф, если образец неправильно классифицирован или находится в пределах границ маржи. В идеале значение $y_i(w^T \phi (x_i) + b)$ было бы $\geq 1$ для всех образцов, что указывает на идеальный прогноз. Но обычно проблемы не всегда можно идеально отделить с помощью гиперплоскости, поэтому мы позволяем некоторым образцам находиться на расстоянии $\zeta_i$ от их правильной границы поля. Срок штрафа C контролирует силу этого штрафа и, как результат, действует как параметр обратной регуляризации (см. Примечание ниже).
где e вектор всех единиц, а $Q$ является n от n положительно полуопределенная матрица, $Q_ \equiv y_i y_j K(x_i, x_j)$, где $K(x_i, x_j) = \phi (x_i)^T \phi (x_j)$ это ядро. Условияαi называются двойственными коэффициентами, и они ограничены сверху величиной $C$. Это двойное представление подчеркивает тот факт, что обучающие векторы неявно отображаются в более высокое (возможно, бесконечное) пространство с помощью функции $\phi$: см. трюк с ядром .
Как только проблема оптимизации решена, выходные данные функции решения для данной выборкиx становится:
$$\sum_
и предсказанный класс соответствуют его знаку. Нам нужно только просуммировать по опорным векторам (то есть выборкам, которые лежат в пределах поля), потому что двойные коэффициенты $\alpha_i$ равны нулю для остальных образцов.
Доступ к этим параметрам можно получить через атрибуты, dual_coef_ содержащие продукт.yiαi, support_vectors_ который содержит опорные векторы и intercept_ независимый член $b$
В то время как модели SVM, полученные из libsvm и liblinear, используют в C качестве параметра регуляризации, большинство других оценщиков используют alpha . Точная эквивалентность между степенью регуляризации двух моделей зависит от точной целевой функции, оптимизированной моделью. Например, когда используется оценка Ridge регрессии, связь между ними задается как $C = \frac$
1.4.7.2. LinearSVC
Первичную задачу можно эквивалентно сформулировать как
$$\min_ \frac w^T w + C \sum_\max(0, y_i (w^T \phi(x_i) + b)),$$
1.4.7.3. NuSVC
В ν-SVC рецептура 15 представляет собой повторную параметризацию $C$-SVC и, следовательно, математически эквивалентен.
1.4.7.4. SVR
Здесь мы штрафуем образцы, прогноз которых не ниже εподальше от их истинной цели. Эти образцы штрафуют цель на $\zeta_i$ или $\zeta_i^*$, в зависимости от того, лежат ли их прогнозы выше или ниже $\varepsilon$ диапазона.
где $e$ вектор всех единиц, $Q$ является $n$ от $n$ положительно полуопределенная матрица, $Q_ \equiv K(x_i, x_j) = \phi (x_i)^T \phi (x_j)$ это ядро. Здесь обучающие векторы неявно отображаются в более высокое (возможно, бесконечное) пространство с помощью функции $\phi$.
1.4.7.5. LinearSVR
где мы используем нечувствительные к эпсилону потери, т. е. ошибки менее $\varepsilon$ игнорируются. Это форма, которая напрямую оптимизируется LinearSVR .
1.4.8. Детали реализации
Внутри мы используем libsvm 12 и liblinear 11 для обработки всех вычислений. Эти библиотеки обернуты с использованием C и Cython. Описание реализации и детали используемых алгоритмов см. В соответствующих документах.
Метод опорных векторов (далее МОВ) — это техника машинного обучения с учителем. Она используется в классификации, может быть применена к регрессионным задачам.
Метод определяет границу принятия решения (далее ГПР) вместе с максимальным зазором, который разделяет почти все точки на два класса, оставляя место для неправильной классификации.
МОВ — улучшенная версия алгоритмов максимального зазора. Его преимущество заключается в том, что он может определять как линейную, так и нелинейную границу с помощью функций ядра, поэтому он подходит для реальных задач, где данные не всегда полностью разделимы прямой линией.
Разделяющие гиперплоскости
Цель МОВ — определить гиперплоскость (также называется “разделяющей” или “ГПР”), которая разделяет точки на два класса.
Для ее визуализации представим двумерный набор данных:
Гиперплоскость, которая полностью разделяет точки на два класса. Гиперплоскость, которая полностью разделяет точки на два класса.Гиперплоскостей, разделяющих точки, будет бесконечное множество, но поскольку мы работаем в двумерном пространстве, любая гиперплоскость всегда будет иметь (2–1) = 1 измерение (можно представить её простой линией регрессии).
В свою очередь, точки можно классифицировать, основываясь на том, где они находятся по отношению к ГПР:
Если вы работаете с более чем двумя измерениями, например вектор объектов X имеет более чем два объекта, вы классифицируете сами векторы, а не точки.
Все векторы, которые падают ниже ГПР, принадлежат классу -1, а если выше, то 1.
Зазоры для повышения достоверности прогноза
Мы использовали обучающие данные для определения ГПР. А что насчет качества предсказаний?
Если вектор находится далеко от границы, то можно быть уверенным в его классе, даже если модель в чем-то ошибочна. Но какой класс назначить в ином случае?
МОВ также рисует границу зазора вокруг ГПР. Цель — максимально отделить векторы от нее. Зазор дает больше уверенности в прогнозах: векторы находятся как минимум на расстоянии длины этого зазора от границы, поэтому картина становится более ясной.
Положение зазора определяется с помощью векторов, наиболее близких к границам. Поэтому те из них, что лежат на зазоре, являются опорными векторами .
С зазором в качестве буфера вектор можно классифицировать по его местонахождению относительно зазора, длина которого представлена M.
Классификация на основе местонахождения вектора относительно зазора. Классификация на основе местонахождения вектора относительно зазора.Пространство для неправильной классификации
Добавление зазора улучшает качество предсказаний, но этого недостаточно для реальных задач.
МОВ, как и классификаторы опорных векторов, использует важную характеристику, которая позволяет ошибаться и присваивать неверный класс некоторым векторам.
ГПР и зазор для классификаторов, а также соответствующие опорные векторы. ГПР и зазор для классификаторов, а также соответствующие опорные векторы.Вместо разделения векторов на два класса МОВ идет на компромисс, позволяя некоторым векторам попадать внутрь зазора и на неправильную сторону границы.
МОВ допускает неправильную классификацию в процессе обучения. Он лучше работает с большинством векторов в тестовом наборе.
Помимо зазора, модель теперь включает в себя слабые переменные, которые сообщат:
• классифицировано ли тестовое наблюдение правильно или нет;
• где наблюдение находится относительно ГПР и зазора.
Они могут иметь три возможных значения:
- 0 — классифицировано верно;
- >0 — неверная сторона границы зазора;
- >1 — неверная сторона гиперплоскости.
Число неправильно классифицированных векторов ограничено параметром C:
Классификация на основе местонахождения вектора относительно зазора, включающая слабые переменные. Классификация на основе местонахождения вектора относительно зазора, включающая слабые переменные.Эта модель точнее, но она все еще построена поверх классификаторов максимального зазора. Например, если C = 0 (то есть слабые переменные могут быть равны 0), модель возвращается к такому классификатору. Таким образом, есть линейная граница решения и максимально большой зазор, внутри которого не могут находиться векторы.
Рост числа слабых переменных влияет на количество допустимых ошибок, что, в свою очередь, затрагивает ширину зазора из-за выбора различных опорных векторов. Также он контролирует компромисс между смещением и дисперсией модели.
Зависимость смещения и дисперсии от числа слабых переменных. Зависимость смещения и дисперсии от числа слабых переменных.Большое число слабых переменных:
- Большой зазор.
- Низкий уровень дисперсии.
- Большое смещение.
- Больше опорных векторов.
Малое число слабых переменных:
- Малый зазор.
- Высокий уровень дисперсии.
- Низкое смещение.
- Меньше опорных векторов.
Наличие некоторого пространства для ошибок делает МОВ более гибким, но подход применим к ограниченному набору проблем.
В реальных задачах трудно разделить данные на два класса линейной границей.
Метод опорных векторов
Этот метод разделяет характеристики классификаторов запаса. Уникальность его в том, что он может определять как линейные, так и нелинейные ГПР.
Для второго МОВ использует функции для преобразования исходного пространства объектов в новое, которое может представлять эти нелинейные отношения.
Предположим, вы увеличиваете исходное пространство объектов возведением во вторую степень. Вы применили квадратичную функцию к исходному набору объектов. Теперь в этом расширенном пространстве есть оригинальная функция и ее квадратичная версия. Здесь неявно существует функция, которая сопоставляет эти два пространственных объекта.
Расширение пространства объектов с помощью квадратичной версии исходных. Расширение пространства объектов с помощью квадратичной версии исходных.Если вы попытаетесь нарисовать границу решения в исходном пространстве объектов, она будет иметь квадратичную форму. Но если вы тренируете модель в расширенном пространстве, то обнаружите линейную границу, которая разделяет два класса. Поскольку это является преобразованием, квадратичная граница в исходном пространстве объектов соответствует линейной в расширенном.
Функции выше называются ядрами . Они работают как функции сходства между наблюдениями в обучающих и тестовых наборах.
Граница решения и запасдля МОВ, наряду с соответствующими опорными векторами, используют линейное (справа) и полиномиальное ядро (слева). Граница решения и запасдля МОВ, наряду с соответствующими опорными векторами, используют линейное (справа) и полиномиальное ядро (слева).Когда есть модель, представленная внутренними результатами, можно подключить функцию ядра. Линейное ядро — это аналог применения линейных преобразований к пространству объектов. И в этом случае это то же, что и классификатор опорных векторов, потому что ГПР линейна.
С полиномиальными ядрами вы проецируете исходное пространство объектов в полиномиальное. Граница, разделяющая классы, определяется полиномом более высокого порядка.
Использование ядер отличает классификаторы от метода опорных векторов, что открывает путь к решению более сложных задач. Но увеличение пространства признаков означает рост вычислительных требований. При большомпространстве функций подгонка модели станет дорогостоящей с точки зрения времени и ресурсов.
Ядра добавляют преимущество. МОВ не вычисляет преобразование каждого наблюдения в расширенное пространство. Используется трюк с ядром — вычисляется внутреннийрезультат наблюдений в этом пространстве. Этот трюкгораздо менее требователен.
МОВ делает два важных допущения:
- Данные линейно разделимы. Даже если линейная граница находится в расширенном пространстве.
- Модель представлена с использованием внутренних результатов , что допускает применение ядер.
Примеры
Я сгенерировал случайный набор данных и разделил его на два разных класса:
Метод опорных векторов(SVM - support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову.
SVM используется как для линейно разделяемых данных, так и для нелинейных разделяемых данных.
Для нелинейных данных используются функции ядра.
Давайте узнаем о SVC (классификатор опорных векторов) в линейных разделяемых данных, который используется для задач классификации в этой статье.
Темы, затронутые в статье.
Линейно разделяемые данные
- SVM в линейно разделимых данных
- Что такое гиперплоскость?
- Что делает SVM?
- Важные термины, используемые в SVM
- Почему он назван машинами опорных векторов?
- Математика SVM
- Как найти лучшую гиперплоскость?
Линейно разделяемые данные
1. Одномерное пространство
Предположим, у нас есть два класса, красный и зеленый, и если мы можем найти границу, которая разделяет два класса, это называется линейно разделяемыми данными.
Здесь мы могли бы выделить одну точку, которая действует как граница между двумя классами. Точки данных ниже конкретной точки относятся к красному классу, а выше этой конкретной точки относятся к зеленому классу.
2. Двумерное пространство
Точно так же в двухмерном пространстве мы можем нарисовать линию, которая действует как граница между двумя классами.
Здесь точки данных так же линейно разделяются в данном измерении.
Основная идея метода — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.
Гиперплоскости - это границы решений, которые классифицируют данные
Постановка задачи
Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представляется как вектор (точка) в p-мерном пространстве (упорядоченный набор p чисел). Каждая из этих точек принадлежит только одному из двух классов. Вопрос состоит в том, можно ли разделить точки гиперплоскостью размерности ). Это — типичный случай линейной разделимости. Искомых гиперплоскостей может быть много, поэтому полагают, что максимизация зазора между классами способствует более уверенной классификации. То есть, можно ли найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это эквивалентно тому, что сумма расстояний до гиперплоскости от двух ближайших к ней точек, лежащих по разные стороны от неё, максимальна. Если такая гиперплоскость существует, она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.
Алгоритм SVM находит лучшую гиперплоскость, которая находится посередине двух классов с максимальным отсупом с обеих сторон.
Точки данных, ближайшие к гиперплоскости в обоих классах, известны как опорные векторы.
Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Если точка данных, не являющаяся опорным вектором, удаляется, это не влияет на модель.
Почему метод назван метод опорных векторов?
Гиперплоскость определяется опорными векторами. Если мы удалим точки данных, кроме опорных векторов, гиперплоскость не изменится. Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Теперь перейдем к важным моментам.
Как найти лучшую гиперплоскость?
Как нам увеличить маржу?
Сначала давайте разберемся с математикой, лежащей в основе SVM, а затем мы перейдем к двум приведенным выше вопросам.
Математика SVM
Основной принцип SVM заключается в том, что мы хотим нарисовать гиперплоскость с максимальным отступом, разделяющим два класса. Предположим, мы хотим разделить два класса C1 и C2 с помощью SVC в двумерном пространстве. Затем мы хотим предсказать класс неизвестного вектора признаков X как класс C1 или класс C2.
Мы можем использовать линейное уравнение
w → обозначает вектор веса, перпендикулярный гиперплоскости. Он представляет ориентацию гиперплоскости в d-мерном пространстве, где d - размерность вектора признаков.
b → Он представляет положение гиперплоскости в d-мерном пространстве.
Это линейное уравнение в двух измерениях представляет собой прямую линию. Оно представляет собой плоскость в трехмерном пространстве и гиперплоскость в более чем трех измерениях.
Переходя к проблеме классификации. Для каждого вектора признаков мы должны вычислить линейную функцию таким образом, чтобы
1 Если вектор признаков лежит на положительной стороне гиперплоскости,
В данной статье я хочу рассказать о проблеме классификации данных методом опорных векторов (Support Vector Machine, SVM). Такая классификация имеет довольно широкое применение: от распознавания образов или создания спам-фильтров до вычисления распределения горячих аллюминиевых частиц в ракетных выхлопах.
Сначала несколько слов об исходной задаче. Задача классификации состоит в определении к какому классу из, как минимум, двух изначально известных относится данный объект. Обычно таким объектом является вектор в n-мерном вещественном пространстве . Координаты вектора описывают отдельные аттрибуты объекта. Например, цвет c, заданный в модели RGB, является вектором в трехмерном пространстве: c=(red, green, blue).
Если классов всего два («спам / не спам», «давать кредит / не давать кредит», «красное / черное»), то задача называется бинарной классификацией. Если классов несколько — многоклассовая (мультиклассовая) классификация. Также могут иметься образцы каждого класса — объекты, про которые заранее известно к какому классу они принадлежат. Такие задачи называют обучением с учителем, а известные данные называются обучающей выборкой. (Примечание: если классы изначально не заданы, то перед нами задача кластеризации.)
Метод опорных векторов, рассматриваемый в данной статье, относится к обучению с учителем.
Итак, математическая формулировка задачи классификации такова: пусть X — пространство объектов (например, ), Y — наши классы (например, Y = ). Дана обучающая выборка: . Требуется построить функцию (классификатор), сопоставляющий класс y произвольному объекту x.
Метод опорных векторов
Данный метод изначально относится к бинарным классификаторам, хотя существуют способы заставить его работать и для задач мультиклассификации.
Идея метода
Идею метода удобно проиллюстрировать на следующем простом примере: даны точки на плоскости, разбитые на два класса (рис. 1). Проведем линию, разделяющую эти два класса (красная линия на рис. 1). Далее, все новые точки (не из обучающей выборки) автоматически классифицируются следующим образом:
точка выше прямой попадает в класс A,
точка ниже прямой — в класс B.
Такую прямую назовем разделяющей прямой. Однако, в пространствах высоких размерностей прямая уже не будет разделять наши классы, так как понятие «ниже прямой» или «выше прямой» теряет всякий смысл. Поэтому вместо прямых необходимо рассматривать гиперплоскости — пространства, размерность которых на единицу меньше, чем размерность исходного пространства. В , например, гиперплоскость — это обычная двумерная плоскость.
В нашем примере существует несколько прямых, разделяющих два класса (рис. 2):
С точки зрения точности классификации лучше всего выбрать прямую, расстояние от которой до каждого класса максимально. Другими словами, выберем ту прямую, которая разделяет классы наилучшим образом (красная прямая на рис.2). Такая прямая, а в общем случае — гиперплоскость, называется оптимальной разделяющей гиперплоскостью.
Вектора, лежащие ближе всех к разделяющей гиперплоскости, называются опорными векторами (support vectors). На рисунке 2 они помечены красным.
Немного математики
Пусть имеется обучающая выборка: .
Метод опорных векторов строит классифицирующую функцию F в виде ,
где — скалярное произведение, w — нормальный вектор к разделяющей гиперплоскости,b — вспомогательный параметр. Те объекты, для которых F(x) = 1 попадают в один класс, а объекты с F(x) = -1 — в другой. Выбор именно такой функции неслучаен: любая гиперплоскость может быть задана в виде для некоторых w и b.
Далее, мы хотим выбрать такие 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.
Читайте также: