Машины опорных векторов (SVM) для машинного обучения

SVM

SVM означает машину опорных векторов и часто используется в моделях бинарной классификации. Его основная идея заключается в следующем:

Это линейный классификатор с самым большим запасом в пространстве признаков.
В случае линейной неразделимости алгоритм нелинейного отображения используется для отображения линейно неразделимых выборок в низкоразмерном пространстве в многомерное пространство признаков, а многомерное пространство признаков может быть линейно проанализировано.

структурный риск

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

Если мы можем получить все данные, то мы хотим, чтобы потери всего набора данных были как можно меньше, а значит, лучше модель. Но во многих случаях получить все данные в принципе невозможно, в это время ожидаемый риск можно рассчитать по совместному распределению P(X,Y) выборки:

$R_{exp}(f) = E[L[Y,f(X)]] = \int L(Y,f(X))P(x,y)dxdy$

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

Структурный риск = эмпирический риск + риск достоверности. Риск достоверности может быть термином регуляризации, который называется регуляризацией, Срок регуляризации связан со сложностью модели, Чем выше сложность, тем больше значение регуляризации. Обычно используемым термином регуляризации является норма параметров модели.

$R = R_{exp} + \lambda J(f)$

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

интервальная максимизация

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

для заданного набора образцов $T=\{(x_1,y_1),(x_2,y_2)...,(x_n,y_n)\}$ ,в $y_i \in Y=\{+1,-1\}$ , представляющий тег класса, обозначаемый +1 и -1 соответственно. Запишем уравнение, соответствующее гиперплоскости, в виде

w^Tx + b =0

Где w - вектор нормали, b - член смещения, а гиперплоскость определяется совместно вектором нормали (определяющим направление) и членом смещения (определяющим расстояние между гиперплоскостью и началом координат). Тогда расстояние от точки, соответствующей образцу, до гиперплоскости равно

$l = \frac{|w^T+b|}{||w||}$

В случае, если все выборки можно корректно разделить гиперплоскостью, то в выборке T для y_i=+1 тогда есть w^Tx + b >0 , и наоборот для y_i=-1 тогда есть w^Tx + b <0 .

Есть несколько точек выборки, ближайших к гиперплоскости по обеим сторонам гиперплоскости (эти точки называются опорными векторами).Средняя гиперплоскость на рисунке перенесена в обе стороны, чтобы получить две гиперплоскости, и соответствующие дисперсии равны

w^Tx + b =1

w^Tx + b =-1

Расстояние между этими двумя гиперплоскостями называется интервалом, а сумма расстояний от точек выборки этих двух гиперплоскостей до средней гиперплоскости равна

$l = \frac{2}{||w||}$

Теперь наша задача — найти наибольший интервал при ограничениях, т. е. найти такие w и b, что l — наибольшее,

$\underset{w,b}{max} \quad l$

$s.t.\ y_i(w^Tx_i+b) \ge 1 ,\ i=1,2,...,n$

На самом деле максимизация $\frac{1}{||w||}$ , что эквивалентно минимизации $\frac{1}{2}||w||^2$ , поэтому приведенная выше проблема оптимизации становится

$\underset{w,b}{min} \quad \frac{1}{2}||w||^2$

$s.t.\ y_i(w^Tx_i+b) \ge 1 ,\ i=1,2,...,n$

Решение этой задачи оптимизации дает гиперплоскость максимального разделения.

двойная проблема

Вышеупомянутая задача оптимизации представляет собой задачу выпуклого квадратичного программирования, которая в общем случае может быть решена методом Лагранжа. Во-первых, вводится функция Лагранжа, требующая $a_i \ge 0$ ,

$L(w,b,a)=\frac{1}{2}||w||^2 +\sum^n_{i=1}a_i(1-y_i(w^Tx_i+b))$

в a= (a_1,a_2,...a_n)^T — вектор множителей Лагранжа.

Для того чтобы найти решение двойственной задачи, необходимо сначала найти минимальное значение функции Лагранжа для w и b, а затем найти максимальное значение функции Лагранжа для a, т. е. $\underset{a}{max} \ \underset{w,b}{min} L(w,b,a)$ .

Чтобы найти минимум, возьмите частную производную w и b и установите их равными 0, мы имеем

$\triangledown_w L(w,b,a) = w - \sum^n_{i=1}a_iy_ix_i =0$

$\triangledown_b L(w,b,a) = \sum^n_{i=1}a_iy_i =0$

Объединение приведенных выше формул с заменой w обратно на исходную формулу может исключить w и b, поэтому максимальное значение функции Лагранжа для a становится равным

$\underset{a}{max} \ \sum^n_{i=1}a_i -\frac{1}{2}\sum^n_{i=1}\sum^n_{j=1}a_ia_jy_iy_jx_i^Tx_j$

$s.t. \ \sum^n_{i=1}a_iy_i =0$

$a_i \ge0, i=1,2,...,n$

Приведенные выше уравнения могут быть решены с помощью алгоритма квадратичного программирования, численного метода или алгоритма SMO. Решив a, вы можете решить w и b.

Кроме того, существует очень важное ограничение, a_i(y_i(wx_i+b)-1)=0 , видно, что для любой выборки (x_i,y_i) , всегда устраивает a_i=0 или y_i(wx_i+b)=1 . Когда соответствующий коэффициент Лагранжа отличен от нуля, выборка является опорным вектором. Когда соответствующий коэффициент Лагранжа равен 0, выборка не является опорным вектором. Также можно видеть, что большинство коэффициентов Лагранжа равны 0, поскольку большинство выборок не являются опорными. векторы.

Функция ядра

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

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

Предположение $\Phi(x)$ представляет собой сопоставленный вектор признаков, тогда модель, обсуждаемая в пространстве признаков, становится,

$f(x) = w^T\Phi(x) + b$

Также решить двойную задачу

$\underset{a}{max} \ \sum^n_{i=1}a_i -\frac{1}{2}\sum^n_{i=1}\sum^n_{j=1}a_ia_jy_iy_j\Phi(x_i)^T\Phi(x_j)$

$s.t. \ \sum^n_{i=1}a_iy_i =0$

$a_i \ge0, i=1,2,...,n$

продолжать выполнять функции

$k(x_i,x_j) = \Phi(x_i)^T\Phi(x_j)$

Так что это может быть решено,

$f(x) = \sum^n_{i=1}a_iy_i k(x,x_i)+b$

Здесь функция k является функцией ядра.

Обычно используемые функции ядра включают линейное ядро, полиномиальное ядро, ядро Гаусса, сигмовидное ядро и так далее.

------------- Рекомендуем прочитать ------------

Резюме моей статьи за 2017 год — машинное обучение

Краткое изложение моих статей за 2017 год — Java и промежуточное ПО

Резюме моих статей 2017 года — глубокое обучение

Краткое изложение моих статей за 2017 год — исходный код JDK

Резюме моей статьи за 2017 год — обработка естественного языка

------------------рекламное время----------------

Меню официальной учетной записи было разделено на «распределенное», «машинное обучение», «глубокое обучение», «НЛП», «глубина Java», «ядро параллелизма Java», «исходный код JDK», «ядро Tomcat», и т.д. Там может быть один стиль, чтобы удовлетворить ваш аппетит.

Моя новая книга «Анализ проектирования ядра Tomcat» продана на Jingdong, и нуждающиеся друзья могут ее купить. Спасибо друзья.

Зачем писать «Анализ проектирования ядра Tomcat»

Добро пожаловать, чтобы следовать: