Метод опорных векторов python

Библиотека Scikit-learn — самый распространенный выбор для решения задач классического машинного обучения. Она предоставляет широкий выбор алгоритмов обучения с учителем и без учителя. Обучение с учителем предполагает наличие размеченного датасета, в котором известно значение целевого признака. В то время как обучение без учителя не предполагает наличия разметки в датасете — требуется научиться извлекать полезную информацию из произвольных данных. Одно из основных преимуществ библиотеки состоит в том, что она работает на основе нескольких распространенных математических библиотек, и легко интегрирует их друг с другом. Еще одним преимуществом является широкое сообщество и подробная документация. Scikit-learn широко используется для промышленных систем, в которых применяются алгоритмы классического машинного обучения, для исследований, а так же для новичков, которые только делает первые шаги в области машинного обучения.

Для своей работы, scikit-learn использует следующие популярные библиотеки:

NumPy: математические операциии и операции над тензорами
SciPy: научно-технические вычисления
Matplotlib: визуализация данных
IPython: интерактивная консоль для Python
SymPy: символьная математика
Pandas: обработка, манипуляции и анализ данных

Что содержит Scikit-learn

В задачи библиотеки не входит загрузка, обработка, манипуляция данными и их визуализация. С этими задачами отлично справляются библиотеки Pandas и NumPy. Scikit-learn специализируется на алгоритмах машинного обучения для решения задач обучения с учителем: классификации (предсказание признака, множество допустимых значений которого ограничено) и регрессии (предсказание признака с вещественными значениями), а также для задач обучения без учителя: кластеризации (разбиение данных по классам, которые модель определит сама), понижения размерности (представление данных в пространстве меньшей размерности с минимальными потерями полезной информации) и детектирования аномалий.

Библиотека реализует следующие основные методы:

Линейные: модели, задача которых построить разделяющую (для классификации) или аппроксимирующую (для регрессии) гиперплоскость.
Метрические: модели, которые вычисляют расстояние по одной из метрик между объектами выборки, и принимают решения в зависимости от этого расстояния (K ближайших соседей).
Деревья решений: обучение моделей, базирующихся на множестве условий, оптимально выбранных для решения задачи.
Ансамблевые методы: методы, основанные на деревьях решений, которые комбинируют мощь множества деревьев, и таким образом повышают их качество работы, а также позволяют производить отбор признаков (бустинг, бэггинг, случайный лес, мажоритарное голосование).
Нейронные сети: комплексный нелинейный метод для задач регрессии и классификации.
SVM: нелинейный метод, который обучается определять границы принятия решений.
Наивный Байес: прямое вероятностное моделирование для задач классификации.
PCA: линейный метод понижения размерности и отбора признаков
t-SNE: нелинейный метод понижения размерности.
K-средних: самый распространенный метод для кластеризации, требущий на вход число кластеров, по которым должны быть распределены данные.
Кросс-валидация:метод, при котором для обучения используется весь датасет (в отличие от разбиения на выборки train/test), однако обучение происходит многократно, и в качестве валидационной выборки на каждом шаге выступают разные части датасета. Итоговый результат является усреднением полученных результатов.
Grid Search: метод для нахождения оптимальных гиперпараметров модели путем построения сетки из значений гиперпараметров и последовательного обучения моделей со всеми возможными комбинациями гиперпараметров из сетки.

Это — лишь базовый список. Помимо этого, Scikit-learn содержит функции для расчета значений метрик, выбора моделей, препроцессинга данных и другие.

Пример применения

Чтобы дать вам представление о том, как легко обучать и тестировать модель ML с помощью Scikit-Learn, вот пример того, как это сделать для классификатора дерева решений!

Деревья решений для классификации и регрессии очень просты в использовании в Scikit-Learn. Сначала мы загрузим наш датасет, который фактически встроен в библиотеку. Затем мы инициализируем наше дерево решений для классификации. Обучение модели — это просто одна строчка .fit(X, Y), где X — обучающая выборка в формате массива NumPy, а Y — массив целевых значений, также в формате массива NumPy.

Scikit-Learn также позволяет нам визуализировать наше дерево. Для этого есть несколько настриваемых опций, которые помогут визуализировать узлы принятия решений и разбить изученную модель, что очень полезно для понимания того, как она работает. Ниже мы раскрасим узлы на основе имен признаков и отобразим информацию о классе и объектах каждого узла.

Каждый из параметров алгоритма интуитивно назван и доступно объяснен. Кроме того, разработчики также предлагают туториалы с примером кода о том, как обучать и применять модель, ее плюсы и минусы и практические советы по применению.

Метод опорных векторов (англ. support vector machine, SVM) — один из наиболее популярных методов обучения, который применяется для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки оптимальным способом. Алгоритм работает в предположении, что чем больше расстояние (зазор) между разделяющей гиперплоскостью и объектами разделяемых классов, тем меньше будет средняя ошибка классификатора.

Содержание

Метод опорных векторов в задаче классификации [ править ]

Рассмотрим задачу бинарной классификации, в которой объектам из $X=mathbb^n$ соответствует один из двух классов $Y = <-1, +1>$.

Пусть задана обучающая выборка пар "объект-ответ": $T^ell = (vec_i, y_i)_^ell$. Необходимо построить алгоритм классификации $a(vec) : X o Y$.

Разделяющая гиперплоскость [ править ]

В пространстве $mathbb^n$ уравнение $langle vec, vec
angle – b = 0$ при заданных $vec$ и $b$ определяет гиперплоскость — множество векторов $vec = (x_1, ldots, x_n)$, принадлежащих пространству меньшей размерности $mathbb^$. Например, для $mathbb^1$ гиперплоскостью является точка, для $mathbb^2$ — прямая, для $mathbb^3$ — плоскость и т.д. Параметр $vec$ определяет вектор нормали к гиперплоскости, а через $frac <lVert vec
Vert>$ выражается расстояние от гиперплоскости до начала координат.

Гиперплоскость делит $mathbb^n$ на два полупространства: $langle vec, vec
angle – b > 0$ и $langle vec, vec
angle – b 0, && forall x in C_1 \ langle vec, vec
angle – b 0, && forall x in C_2end$

Линейно разделимая выборка [ править ]

Пусть выборка линейно разделима, то есть существует некоторая гиперплоскость, разделяющая классы $-1$ и $+1$. Тогда в качестве алгоритма классификации можно использовать линейный пороговый классификатор:

$a(vec) = sign(langle vec, vec
angle – b) = signleft(sumlimits_^ell w_i x_i – b
ight)$

где $vec = (x_1, ldots, x_n)$ — вектор значений признаков объекта, а $vec = (w_1, ldots, w_n) in mathbb^n$ и $b in mathbb$ — параметры гиперплоскости.

Но для двух линейно разделимых классов возможны различные варианты построения разделяющих гиперплоскостей. Метод опорных векторов выбирает ту гиперплоскость, которая максимизирует отступ между классами:

Определение:

Отступ (англ. margin) — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M_i$, тем ближе объект $vec_i$ подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M_i$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $vec_i$.

Для линейного классификатора отступ определяется уравнением: $M_i(vec, b) = y_i(langle vec, vec_i
angle – b)$

Если выборка линейно разделима, то существует такая гиперплоскость, отступ от которой до каждого объекта положителен:

$exists vec, b : ; M_i(vec, b) = y_i(langle vec, vec_i
angle – b) > 0, ; i = 1ldotsell$

Мы хотим построить такую разделяющую гиперплоскость, чтобы объекты обучающей выборки находились на наибольшем расстоянии от неё.

Заметим, что при умножении $vec$ и $b$ на константу $c
eq 0$ уравнение $langle cvec, vec
angle – cb = 0$ определяет ту же самую гиперплоскость, что и $langle vec, vec
angle – b = 0$. Для удобства проведём нормировку: выберем константу $c$ таким образом, чтобы $min M_i(vec, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один "граничный" объект обучающей выборки, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с большим отступом, тем самым увеличив минимальное расстояние от гиперплоскости до объектов обучающей выборки.

Обозначим любой "граничный" объект из класса $+1$ как $vec_+$, из класса $-1$ как $vec_-$. Их отступ равен единице, то есть

$egin M_+(vec, b) = (+1)(langle vec, vec_+
angle – b) = 1 \ M_-(vec, b) = (-1)(langle vec, vec_-
angle – b) = 1 end$

Нормировка позволяет ограничить разделяющую полосу между классами: $

На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, и необходимо ослабить ограничения, позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $xi_i$, но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи, называемой также SVM с мягким отступом (англ. soft-margin SVM):

Мы не знаем, какой из функционалов $frac<1> <2>lVert vec
Vert^2$ и $sumlimits_^ell xi_i$ важнее, поэтому вводим коэффициент $C$, который будем оптимизировать с помощью кросс-валидации. В итоге мы получили задачу, у которой всегда есть единственное решение.

Заметим, что мы можем упростить постановку задачи:

$egin xi_i geq 0 \ xi_i geq 1 – M_i(vec, b) \ sumlimits_^ell xi_i o min end ,Rightarrow, egin xi_i geq max(0, 1 – M_i(vec, b)) \ sumlimits_^ell xi_i o min end ,Rightarrow, xi_i = (1- M_i(vec, b))_+$

Получим эквивалентную задачу безусловной минимизации:

$frac<1> <2>lVert vec
Vert^2 + C sumlimits_^ell left(1 – M_i(vec, b)
ight)_+ o minlimits_$

Теперь научимся её решать.

Теорема (Условия Каруша—Куна—Таккера):

$$ egin f(x) o minlimits_ \ g_i(x) leq 0,;i=1ldots m \ h_j(x) = 0,;j=1ldots k end $$

Если $x$ — точка локального минимума при наложенных ограничениях, то существуют такие множители $mu_i, i = 1ldots m$, $;lambda_j, j = 1ldots k$, что для функции Лагранжа $L(x; mu, lambda)$ выполняются условия:

$$eginfrac<partial L> <partial x>= 0, quad L(x; mu, lambda) = f(x) + sumlimits_^m mu_i g_i(x) + sumlimits_^k lambda_j h_j(x) \ g_i(x) leq 0,;h_j(x) = 0 quad ext <(исходные ограничения)>\ mu_i geq 0 quad ext <(двойственные ограничения)>\ mu_i g_i(x) = 0 quad ext <(условие дополняющей нежёсткости)>end$$

При этом искомая точка является седловой точкой функции Лагранжа: минимумом по $x$ и максимумом по двойственным переменным $mu$.

По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче поиска седловой точки функции Лагранжа:

$mathscr(vec,b,xi; lambda, eta) = frac<1> <2>lVert w
Vert^2 – sumlimits_^ell lambda_i left(M_i(vec, b) – 1
ight) – sumlimits_^ell xi_i left(lambda_i + eta_i – C
ight)$

$lambda_i$ — переменные, двойственные к ограничениям $M_i geq 1 – xi_i$

$eta_i$ — переменные, двойственные к ограничениям $xi_i geq 0$

Запишем необходимые условия седловой точки функции Лагранжа:

Продифференцируем функцию Лагранжа и приравняем к нулю производные. Получим следующие ограничения:

$egin frac<partial mathscr> <partial w>= vec – sumlimits_^ell lambda_i y_i vec_i = 0 & Rightarrow & vec = sumlimits_^ell lambda_i y_i vec_i \ frac<partial mathscr> <partial b>= -sumlimits_^ell lambda_i y_i = 0 & Rightarrow & sumlimits_^ell lambda_i y_i = 0 \ frac<partial mathscr> <partial xi_i>= -lambda_i – eta_i + C = 0 & Rightarrow & eta_i + lambda_i = C, quad i = 1, ldots, ell end$

Заметим, что $eta_i geq 0$, $lambda_i geq 0$, $C > 0$, поэтому из последнего ограничения получаем $0 leq eta_i leq C$, $0 leq lambda_i leq C$.

Диапазон значений $lambda_i$ (которые, как указано выше, соответствуют ограничениям на величину отступа) позволяет нам разделить объекты обучающей выборки на три типа:

$lambda_i = 0 ; Rightarrow ; eta_i = C; ; xi_i = 0; ; M_i geq 1 ;$ — периферийные (неинформативные) объекты
Эти объекты лежат в своём классе, классифицируются верно и не влияют на выбор разделяющей гиперплоскости (см. уравнение для $vec$)
$0 0; ; M_i 0, M_i = 1 end$

На практике для повышения вычислительной устойчивости рекомендуется при расчёте $b$ брать медиану по опорным граничным объектам:

$b = med< langle vec, vec_i
angle – y_i : lambda_i > 0, M_i = 1, i = 1, ldots, ell>$

Теперь можем переписать наш линейный классификатор, выразив $vec$ через $vec<lambda>$:

$a(x) = sign left(sumlimits_^ell lambda_i y_i langle vec_i, vec
angle – b
ight)$

Нелинейное обобщение, kernel trick [ править ]

Существует ещё один подход к решению проблемы линейной разделимости, известный как трюк с ядром (kernel trick). Если выборка объектов с признаковым описанием из $X = mathbb^n$ не является линейно разделимой, мы можем предположить, что существует некоторое пространство $H$, вероятно, большей размерности, при переходе в которое выборка станет линейно разделимой. Пространство $H$ здесь называют спрямляющим, а функцию перехода $psi : X o H$ — спрямляющим отображением. Построение SVM в таком случае происходит так же, как и раньше, но в качестве векторов признаковых описаний используются векторы $psi(vec)$, а не $vec$. Соответственно, скалярное произведение $langle vec_1, vec_2
angle$ в пространстве $X$ везде заменяется скалярным произведением $langle psi(vec_1), psi(vec_2)
angle$ в пространстве $H$. Отсюда следует, что пространство $H$ должно быть гильбертовым, так как в нём должно быть определено скалярное произведение.

Обратим внимание на то, что постановка задачи и алгоритм классификации не используют в явном виде признаковое описание и оперируют только скалярными произведениями признаков объектов. Это даёт возможность заменить скалярное произведение в пространстве $X$ на ядро — функцию, являющуюся скалярным произведением в некотором $H$. При этом можно вообще не строить спрямляющее пространство в явном виде, и вместо подбора $psi$ подбирать непосредственно ядро.

Постановка задачи с применением ядер приобретает вид:

$egin -mathscr(lambda) = -sumlimits_^ell lambda_i + frac<1> <2>sumlimits_^ell sumlimits_^ell lambda_i lambda_j y_i y_j color_i, vec_j)> o minlimits_lambda \ 0 leq lambda_i leq C, quad i = 1, ldots, ell \ sumlimits_^ell lambda_i y_i = 0 end$

$a(x) = sign left(sumlimits_^ell lambda_i y_i color_i, vec)> – b
ight)$

Преимущества и недостатки SVM [ править ]

Преимущества SVM перед методом стохастического градиента и нейронными сетями:

Задача выпуклого квадратичного программирования хорошо изучена и имеет единственное решение.
Метод опорных векторов эквивалентен двухслойной нейронной сети, где число нейронов на скрытом слое определяется автоматически как число опорных векторов.
Принцип оптимальной разделяющей гиперплоскости приводит к максимизации ширины разделяющей полосы, а следовательно, к более уверенной классификации.

Недостатки классического SVM:

Неустойчивость к шуму: выбросы в исходных данных становятся опорными объектами-нарушителями и напрямую влияют на построение разделяющей гиперплоскости.
Не описаны общие методы построения ядер и спрямляющих пространств, наиболее подходящих для конкретной задачи.
Нет отбора признаков.
Необходимо подбирать константу $C$ при помощи кросс-валидации.

Модификации [ править ]

Существуют различные дополнения и модификации метода опорных векторов, направленные на устранение описанных недостатков: