Спасение перед интервью -- вывод машины опорных векторов

предисловие

SVM — один из немногих существующих алгоритмов машинного обучения с полным выводом математических доказательств. Его основная идея проста и практична, поэтому он широко используется. Я думаю, что если вы хотите глубже понять алгоритм, вы должны сначала понять его название. Потому что в процессе нам нужно понять, для решения какой проблемы был создан этот алгоритм, и как шаг за шагом улучшить его до того, что он есть. В этой статье я проверил множество материалов, прослушал множество онлайн-курсов в стране и за рубежом и объяснил вам эту проблему в изначальной идее SVM.

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

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

Линейно разделимые машины опорных векторов

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

бинарный классификатор

Машина опорных векторов была впервые введена из бинарного классификатора, и ее принцип показан на следующем рисунке:

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

В конечном итоге мы должны решить это алгоритмическиwиb, о чем будет сказано позже. Тогда у нас есть эта функция принятия решения о классификации:

Стоит отметить, что в многомерном пространстве данных наша линия называется гиперплоскостью, а нашаwиbстановятся многомерными векторами.

Интервалы и опорные векторы

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

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

Как показано на рисунке, мы видим, что A находится ближе к гиперплоскости и имеет большую вероятность неправильного суждения, чем C. Это позволяет нам количественно оценить уверенность в том, что классификация верна или нет, путем деления гиперплоскости (сплошная зеленая пунктирная линия) на расстояние данных. Мы хотим убедиться, что все данные правильно классифицированы как можно выше, а это значит, что ближайшая к гиперплоскости точка должна быть как можно дальше от гиперплоскости, то есть чем дальше точка А от зеленой линии, лучшее. Из рисунка видно, что пунктирная линия работает лучше, чем сплошная.

Геометрические и функциональные интервалы

Расстояние от точки до линии получается из геометрического интервала. Мы добавляем маркер класса на основе расстояния между точками и линиями.

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

\gamma _{i} = y_{i}( \frac{w}{||w||} \cdot x_{i}+\frac{b}{||w||} )

в ||w|| задвойная норма вектора, значение которого равноИзвлеките квадратный корень из каждого элемента в

Стоит отметить, что наша $y_{i}$ Это не координата оси Y, а маркер категории, значение {-1;+1}, когда точка делится на правую сторону гиперплоскости, это положительный пример, где положительный пример является $y_{i}$ для +1.

Сравниваем результат с этим $y_{i}$ Цель умножения состоит в том, чтобы результат всегда был положительным, подобно функции абсолютного значения расстояния от начала координат до прямой. учитывая $w \cdot x +b$ Отрицательные случаи будут браться с левой стороны строки.

Таким образом, мы можем уверенноГиперплоскостное и геометрическое разделение данныхОпределяется как минимальное геометрическое расстояние от всех образцов до гиперплоскости:

Учитывая, что для расщепленной гиперплоскости ||w|| то же самое, отбрасываем эту часть и получаемФункциональный интервал между гиперплоскостью и точками выборки:

\hat{\gamma_{i}}=y_{i}(w_{i} \cdot x_{i}+b)

ИФункциональный интервал между гиперплоскостью и данными:

\hat{\gamma} = \min_{i=1,...,N} \hat{\gamma_{i}}

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

Тогда мы можем узнать, что название этой машины опорных векторов происходит от этого, потому что опорный вектор — самая важная вещь во всем алгоритме, наша цель оптимизации будет расширена опорным вектором, как расширять, мы посмотрим вниз:

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

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

Тогда мы легко можем получить следующую формулу:

\begin{array}{l} \text{$ \max_{w,b}$} &\frac{\hat\gamma}{||w||}\\ \end{array}

\begin{array}{l} \text{$s.t.$} &y_{i}\left(w \cdot x_{i}+b\right)\geq \hat\gamma &&& i=1,2,...N\\ \end{array}

Мы должны получить при ограничениях $\frac{\hat\gamma}{||w||}$ самый большой w,b значение, процесс оптимизации является оптимизацией w,b , так что это $\hat\gamma$ Неважно, каково конкретное значение, это константа. Кроме того, нам нужно разместить два типа данных на одинаковом расстоянии от гиперплоскости, чтобы выразить ощущение, что гиперплоскость точно делит два типа данных пополам. Таким образом, мы можем легко вычислитьнастраивать $\hat\gamma$ 1, а положительное и отрицательное расстояния данных равны 1.

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

\begin{array}{l} \text{$ \min_{w,b}$} &\frac{1}{2}||w||^2\\ \end{array}

\begin{array}{l} \text{$s.t.$} &y_{i}\left(w \cdot x_{i}+b\right)-1\geq 0 &&& i=1,2,...N\\ \end{array}

здесь ||w||^2 еще один перед $\frac{1}{2}$ , но и для удобства последующих расчетов. С или без. в квадрате, потому что ||w|| В выражении есть знак корня, вычислить который непросто.

Тогда основной алгоритм машины опорных векторов очень ясен:Алгоритм машинного обучения линейных разделимых опорных векторов — метод максимального интервала:

входить: линейно разделимый обучающий набор данных T={( $x_{1},y_{1}$ ),( $x_{2},y_{21}$ ),...,( $x_{N},y_{N}$ )},в $x_{i}\in\chi=R^n$ , $y_{i}\in{-1,+1}$ ,

вывод: максимальный запас, разделяющий гиперплоскость и функцию принятия решения о классификации

Постройте и решите эту задачу оптимизации с ограничениями:

$\begin{array}{l} \text{$ \min_{w,b}$} &\frac{1}{2}||w||^2\\ \end{array}$

$\begin{array}{l} \text{$s.t.$} &y_{i}\left(w \cdot x_{i}+b\right)-1\geq 0 &&& i=1,2,...N\\ \end{array}$

Получите разделяющую гиперплоскость:

$w^* \cdot x+b^* = 0$

и функция принятия решения о классификации:

$f(x)=sign(w^* \cdot x+b^*)$

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

решение проблем

В этой части довольно много галантереи, поэтому я написал отдельную статью в качестве дополнения. Вы можете видеть это«Двойственность Лагранжа».в качестве грунтовки. Есть также некоторые условия ККТ, эквивалентность двойственности и исходной проблемы, пожалуйста, нажмите на эту статью.«Множители Лагранжа»., который содержит вывод происхождения условия ККТ и другие подробные выводы.

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

Сначала напишем функцию Лагранжа и введем множитель Лагранжа $\alpha_i \geq 0,i = 1,2,...,N$ , то есть:

L(w,b, \alpha) = \frac{1}{2} ||w^2|| - \sum_{i=1}^N \alpha_i y_i (w \cdot x_i+b)+ \sum_{i=1} ^N \alpha_i

Двойственная проблема исходной задачи:

первый шаг $\min_{w,b}L(w,b,\alpha)$

Мы устанавливаем дифференциал функции Лагранжа равным 0, и вы можете просто вычислить следующие два вывода:

w= \sum_{i=1}^N \alpha_iy_ix_i \qquad \qquad (I)

\sum_{i=1}^N \alpha_iy_i=0 \qquad \qquad (II)

Подставьте (I) и (II) в исходную функцию Лагранжа, чтобы получить:

L(w,b,\alpha)=\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i \cdot x_j)

\qquad \qquad \qquad \qquad -\sum_{i=1}^N\alpha_i y_i \left[ \left( \sum_{j=1}^N \alpha_jy_jx_j \right)\cdot x_j+b \right]+\sum_{i=1}^N \alpha_i

После упрощения получаем:

\min_{w,b}L(w,b,\alpha)=-\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^N\alpha_i

Затем мы максимизируем эту минимальную задачу, которая является двойственной проблемой

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

\min_\alpha \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^N\alpha_i

s.t. \sum_{i=1}^N \alpha_iy_i=0 \qquad \alpha_i \geq 0, \quad i=1,2,...,N

Рассматривая исходную задачу и двойственную задачу, мы можем судить из теоремы двойственности Лагранжа, что эта задача имеет то же решение, что и исходная задача и двойственная задача, и решение есть $w^*,\alpha^*,\beta^*$ .

Предположим, что для линейно разделимого обучающего набора данных задача двойной оптимизации имеет $\alpha$ Решение $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_l^*)$ , то его можно задать $\alpha^*$ Найдите исходную пару задач оптимизации (w,b) решение w^*,b^* :

b^*=y_j- \sum_{i=1}^N\alpha_i^*y_i(x_i \cdot x_j)

Первоначальная форма разделяющей гиперплоскости:

После подстановки разделяющая гиперплоскость будет:

\sum_{i=1}^N \alpha_i^*y_i (x \cdot x_i)+b^* = 0

Функция принятия решения о классификации может быть записана как:

f(x)=sign \left( \sum_{i=1}^N \alpha_i ^ *y_i(x \cdot x_i)+b^* \right)

Суммировать

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

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