«Машинное обучение на практике»: популярное понимание машин опорных векторов

машинное обучение
«Машинное обучение на практике»: популярное понимание машин опорных векторов

Я помещаю в него код, набор данных и статьюGitHub.com/AAA ZC/SVM_no…Выше статья находится в выпусках, рекомендуется прочитать этот сайт

«Машинное обучение на практике»: популярное понимание машин опорных векторов

Об этой статье

В конце концов, «Машинное обучение на практике» — это только практическая книга, она больше предназначена для того, чтобы читатели поняли, как использовать алгоритмы, при этом уменьшив долю теоретических частей. Как и в Главе 6: Машины опорных векторов, самое важное в нейКлассификаторы решают задачи оптимизацииЧуть меньше двух страниц. Знания о машинах опорных векторов уже неясны и трудны для понимания, но эта книга по-прежнему является хорошим вводным учебником.Я считаю, что многие студенты используют этот превосходный учебник, поэтому я использую этот учебник как основу для анализа.

Много статей об SVM в Интернете хорошо написано. Среди них, я думаю, лучшая из них — «Популярное введение в машины опорных векторов (понимание трехслойной области SVM)», написанное Июлем. Вывод формулы очень всеобъемлющий. , оправдано. Но я плохо изучаю математику, поэтому я думаю, что эта статья слишком «хардкорна» для меня, и я думаю, что, поскольку первое, что нужно изучить алгоритм, — это понять, популярный момент — преобразовать теоретические вещи в свои собственные. слова. Поэтому я хочу написать статью, которая будет легко понятна студентам моего уровня математики.Конечно, я не пропущу вывод математических формул, потому что это ядро, но я буду интерпретировать это в более популярной форме.

На самом деле, это учебная заметка, которая является чисто личным пониманием.Если у вас есть какие-либо вопросы, пожалуйста, не стесняйтесь исправлять меня, спасибо!

Какой части учебника соответствует эта статья?

Эта часть учебника действительно трудна для понимания. (Студенты, которые не видели, могут посмотреть содержание ниже)

Что такое СВМ

Видел очень яркий пример в статье:

Давным-давно возлюбленная героя попала в плен к дьяволу, герой хотел ее спасти, но дьявол затеял с ним игру, название было такое: Горсть риса и горсть камней на стол, я сейчас Вот палка, я хочу, чтобы вы взяли это и палку, чтобы разделить две вещи.

Итак, герой делит это так:

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

Итак, герои снова поставили палку

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

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

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

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

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

Линейная классификация

Как появились ярлыки 1 и -1?

Прежде чем перейти к обсуждению SVM, нам нужно обратиться к происхождению книги, установив метки двух категорий на 1 и -1.

​ Это должно исходить из происхождения линейной классификацииЛогистическая регрессияГоворя о:

Логистическая регрессия — это широко используемый метод бинарной регрессии. Он подробно описан в главе 5 «Машинное обучение на практике». На самом деле, грубо говоря, мы надеемся получить функцию, которая может получить рассчитанное нами значение, и затем разделите его на категорию 0 или 1. Наиболее распространенной такой функцией является сигмовидная функция, а ее формула расчета и изображение следующие:

о(z)=11+e−z\sigma(z) = \frac{1}{1+e^{-z}}

Наблюдая за изображением, мы можем получить, что когда z=0,о(z)=0.5\sigma(z) = 0.5, чем больше z, темо(z)\sigma(z)Оно бесконечно близко к 1, и чем меньше z,о(z)\sigma(z)бесконечно близко к 0. Вы можете себе представить, очень ли близко это изображение к ступенчатой ​​функции, когда масштаб z большой, тогда мы можем использовать эту функцию в качестве классификатора, когдао(z)\sigma(z)>0,5, я думаю, что это класс 1, в противном случае это класс 0.

​ На данный момент мы решили проблему классификатора, поэтому нам нужно сосредоточиться только на линейной аппроксимации, котораяz=w0+w1x1+...+wnxnz=w_0 + w_1x_1 + ...+w_nx_n, поэтому приведенную выше формулу можно преобразовать в:

о(∑i=0nwixi=11+e∑i=0nwixi)\sigma({\sum_{i=0}^n w_ix_i} = \frac{1}{1 + e^{\sum_{i=0}^n w_ix_i}})

Это то, что мы называем логистической регрессией. Далее мы свяжем это с SVM:

​ Формула гиперплоскости в книгеwTx+bw^Tx + b, на самом деле проще всего это понять на двумерной плоскости, w — параметр перед x и y, а b — точка пересечения. Как и линия на рисунке ниже, ее уравнение−x+2=y-x + 2 = y, сдвиньте его, чтобы получить:x+y−2=0x + y - 2 = 0, b равно 2, w равно [1, 1], x равно [x, y], вот что это значит, зачем использовать awTw^TЧтобы указать, что на самом деле в задаче линейной подгонки много параметров, и она написана так для красоты.

Теперь мы вносим изменения в сигмиод-функцию, меняем метку y=0 на y=-1 и меняем z наwTx+bw^Tx + b, а затем подставив его в функцию, вы получите отношение отображения между -1 и 1:

g(x)={1,z>=0−1,z<0g(x) = \begin{cases} 1, z>=0\\ -1, z<0 \end{cases}

На самом деле мы обнаружили, что эта связь на самом деле просто меняет метку 0 на -1, а другие вещи не изменились. Что касается того, почему бы не использовать напрямую 0 и 1, я объясню далее.

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

Почему вы хотите установить метки на 1 и -1

Возьмем простой пример. Как показано на рисунке ниже, на двумерной плоскости есть две группы чисел. Одна группа представлена ​​синим, а другая красным цветом. Пусть синий будет классом 1, а красный быть класса -1. Нетрудно видеть, что они линейно разделимы: сначала случайным образом находим гиперплоскость, затем точки выше гиперплоскости относятся к классу 1, а следующие — к классу -1.

Помните, какую проблему пытался решить SVM?Он заключается в том, чтобы найти тот, который дальше всего от гиперплоскости в опорном векторе., для интуитивного анализа мы могли бы также перевести прямую.Первая точка, в которой встречаются две параллельные прямые, является опорным вектором гиперплоскости.Чтобы найти расстояние между ними, первое, что приходит на ум, должна быть точка линия. Формула расстояния:

∣Ax+By+C∣A2+B2\frac{|Ax+By+C|}{\sqrt{A^2+B^2}}

(Честно говоря, то, что мы используем, это эта формула.Когда я начал учиться, я прочитал эту часть очень быстро, но я не мог понять это позже, потому что вывод SVM содержит много допущений, поэтому это место является фокусом)

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

​ Определить интервал функции (с помощью таблицыy^\hat{y}показано) как:

y^=yi(wTx+b)=yif(x)\hat{y} = y_i(w^Tx + b) = y_if(x)

из них формулаyiy_iпредставляет категорию, и этоf(x)f(x)Это уравнение гиперплоскости. Функциональный интервал интуитивно понимается как категория, умноженная на значение функции, которое представляет собой красный участок на рисунке ниже: то есть наша гиперплоскость - это черная сплошная линия. Если она находится на точка линии, в уравнениеf(x)f(x)Должен быть равен 0, если его нет на линии,f(x)f(x)Оно должно быть равно ненулевому числу, и теперь я умножаю перед ним его категорию, что эквивалентно добавлению к нему абсолютного значения. Таким образом, нам не нужно заботиться о том, что это такое, когда мы его вычисляем, потому что мы хотим найти опорный вектор, просто смотрим на расстояние и не заботимся о том, что он означает. Таким образом, это преимущество использования -1 и 1, это определение не только устраняет влияние знака, но и не затрагивает значение функции (из-за умножения на 1).

Но если он используется для представления расстояния, недостаточно использовать эту функцию расстояния.Можно подумать о проблеме.Когда w и b уравнения гиперплоскости расширяются в два раза, а именно2wTx+2b=02w^Tx + 2b = 0, не влияет на гиперплоскость, но влияет на функцию расстояния, которая теперь в четыре раза больше, что явно неверно.

Так в это время было введено понятие геометрического интервала:

Предположим, что есть точка x, которая проецируется на гиперплоскость какx0x_0, w — вектор нормали гиперплоскости, y — расстояние от x до гиперплоскости:

Согласно геометрическим знаниям, мы можем получитьx=x0+yw∣∣w∣∣x = x_0 + y\frac{w}{||w||}

​∣∣w∣∣||w||- нормальная форма второго порядка w, которая на самом деле является длиной по модулю,w∣∣w∣∣\frac{w}{||w||}— единичный вектор нормали к гиперплоскости, а вектор, деленный на ее модуль, — единичный вектор. так какx0x_0является точкой на гиперплоскости, поэтому мы говорим, чтоx0x_0принестиwT+b=0w^T + b = 0(здесь я записываю его как тип 1), в это время мы находимся вx=x0+yw∣∣w∣∣x = x_0 + y\frac{w}{||w||}Умножить и влево, и вправо наwTw^TИ объедините уравнение 1, чтобы получить: (Здесь процесс вывода использует свойство, котороеwTw=w2w^Tw = w^2, остальным просто нужно занести переложенные предметы, вывести не сложно)

y=wTx+b∣∣w∣∣y = \frac{w^Tx + b}{||w||}

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

y~=yi(wTx+b)∣∣w∣∣=y^∣∣w∣∣\tilde{y} = \frac{y_i(w^Tx + b)}{||w||} = \frac{\hat{y}}{||w||}

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

Определение классификатора максимальной маржи

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

Давайте рассмотрим, что делает SVM? SVMОн заключается в том, чтобы найти тот, который дальше всего от гиперплоскости в опорном векторе.. К чему бы мы ни пришли, в конце концов мы должны вернуться к этому вопросу! В предыдущем разделе мы говорили о нахождении интервалов с помощью геометрических интервалов, но давайте подробнее рассмотрим формулу:

y~=yi(wTx+b)∣∣w∣∣=y^∣∣w∣∣\tilde{y} = \frac{y_i(w^Tx + b)}{||w||} = \frac{\hat{y}}{||w||}

Мы обнаружили, что очень проблематично спрашивать расстояние, потому что мы не знаем w и b, и мы не знаем числителя и знаменателя соавторства, поэтому это очень сложно решить, поэтому мы можно было бы поставить знаменатель константой, тут много книг.Все ставят знаменатель = 1, ни для чего другого, потому что 1 легко считать. В это время геометрический интервал становитсяy~=1∣∣w∣∣\tilde{y} = \frac{1}{||w||}, становится намного проще решать интервал, я хочу сделать геометрический интервал больше, тогда∣∣w∣∣||w||Чтобы быть меньше, мы делаем вышеприведенное предположение, и оно становится таким:

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

Предположим, что исходная гиперплоскость становится двумя пунктирными линиями рядом с ней, расстояние от них до гиперплоскости равно1∣∣w∣∣\frac{1}{||w||}, поэтому длина всего интервала1∣∣w∣∣\frac{1}{||w||}, и таким образом мы не только упрощаем задачу, но и выделяем часть ненужных данных, как показано на рисунке выше.wx+b=1wx + b = 1,wx+b=−1wx + b = -1Точки, входящие в интервал выше, являются опорными векторами, остальные точки не имеют к нам никакого отношения, нам это не нужно, поэтому мы устанавливаем ограничение.yi(wTx+b)>=1y_i(w^Tx + b) >= 1, то есть точки на этой линии, включая точки над линией, не то, что нам нужно (почему нам не нужны точки на линии? Потому что эта линия может не найти опорный вектор в начале , в пределах диапазона могут быть точки). Таким образом, проблема, которую мы решаем, становится такой, где st представляет смысл ограничений:

y~=1∣∣w∣∣s.t.yi(wTx+b)>=1\tilde{y} = \frac{1}{||w||}\\ s.t.\quad y_i(w^Tx + b) >= 1

Но этого недостаточно с формулой, которая заключается в следующем.1∣∣w∣∣\frac{1}{||w||}Это не радует глаз.Вы можете себе представить, что дано уравнение и давайте решим его максимальное значение, первое, о чем мы думаем, это взять производную от этого числа.Это разделение времени выглядит очень неудобно, поэтому давайте преобразуем его , так как требование1∣∣w∣∣\frac{1}{||w||}Максимальное значение , в свою очередь, является решением12∣∣w∣∣2\frac{1}{2}||w||^2Минимальное значение (здесь вы можете взглянуть на производную и найти, что производная равна w), квадрат вводится, чтобы превратить ее в бинарную функцию, тогда производная сама w.

Что такое множители Лагранжа и законы двойственности

Если решать интуитивно12∣∣w∣∣2\frac{1}{2}||w||^2Максимальное значение, если честно, это было очень легко сделать, я могу напрямую дифференцировать уравнение и сделать это 0, но теперь это невозможно сделать это, потому что наше выше уравнение ограничено, он это может только быть сделано, если условия выполнены. Затем, чтобы решить эту проблему нахождения максимального значения с ограничениями, мы представили метод множителя Lagrange, и я непосредственно процитировал результаты других (потому что это было хорошо написано):

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

minf=2x12+3x22+7x32s.t.2x1+x2=12x2+3x3=2min\quad f=2x_1^2+3x_2^2+7x_3^2\\ s.t.\quad 2x_1+x_2=1\\ 2x_2+3x_3=2

Это задача оптимизации с ограничениями-равенствами, с объективными значениями и ограничениями. Итак, подумайте, как решить проблему предположения об отсутствии ограничений?Можно ли напрямую вывести производную каждого x, равного 0, и решить x. Но x равно 0 и не соответствует ограничениям, тогда возникает проблема. Дело в том, почему говорят, что производная равна 0. Теоретически большинство проблем возможны, но некоторые проблемы нет. Если вывод равен 0, это должно быть возможно, тогда f должна быть задачей выпуклой оптимизации.Что такое выпуклость?Как на следующем рисунке (выпуклость — это просто короткое имя, а направление может быть вверх или вниз):

Для этой выпуклой оптимизации правильнее сказать:

Доволенf(x1)+f(x2)2>f(x1+x22)orf(x1)+f(x2)2<f(x1+x22)\frac{f(x_1)+f(x_2)}{2} >f(\frac{x_1+x_2}{2})\\or\\\frac{f(x_1)+f(x_2)}{2}<f(\frac{x_1+x_2}{2}), которая является выпуклой функцией.

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

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

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

minf=2x12+3x22+7x32+α1(2x1+x2−1)+α2(2x2+3x3−2)min\quad f=2x_1^2+3x_2^2+7x_3^2+\alpha_1(2x_1+x_2-1)+\alpha_2(2x_2+3x_3-2)

Здесь вы можете увидетьα1\alpha_1,α2\alpha_2Все части умножения равны 0, поэтомуα1\alpha_1,α2\alpha_2Значением являются все действительные числа, и теперь эта целевая функция оптимизации не имеет ограничений, поэтому следующее решение состоит в том, чтобы использовать только производную, равную 0:

δfδx1=4x1+2α1=0⟹x1=−0.5α1δfδx2=6x2+α1+2α2=0⟹x2=−α1+2α26δfδx3=14x3+3α2=0⟹x3=−3α214\frac{\delta f}{\delta x_1}=4x_1+2\alpha_1=0 \Longrightarrow x_1 = -0.5\alpha_1\\ \frac{\delta f}{\delta x_2}=6x_2+\alpha_1+2\alpha_2=0\Longrightarrow x_2=-\frac{\alpha_1+2\alpha_2}{6}\\ \frac{\delta f}{\delta x_3}=14x_3+3\alpha_2=0 \Longrightarrow x_3 = -\frac{3\alpha_2}{14}

Затем помогите полученным выше результатам привести к ограничениям, и результаты могут быть полученыα1\alpha_1=-0,39,α2\alpha_2=-1,63, то ставимα\alphaПоднесите его к исходной формуле, чтобы получить х. Разрешать ограничения равенства — преступление, так что же нам делать с ограничениями неравенства? Необходимо использовать условие ККТ.

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

ККТ условия

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

minf=x12−2x1+1+x22+4x2+4s.t.x1+10x2>1010x1−10x2<10min\quad f=x_1^2-2x_1+1+x_2^2+4x_2+4\\ s.t.\quad x_1+10x_2>10\\ 10x_1-10x_2<10

Согласно приведенному выше утверждению, мы превращаем проблему «больше знака» в задачу «меньше знака» (почему изменение символа связано с тем, что для унификации операции, конечно, проще решить проблему в одном и том же направление, чем решать проблему в другом направлении), а затем следуйте за тягой. Практика метода множителя Грейнджа плюс альфа, мы получаем:

L(x,α)=f(x)+α1g(x)+α2g(x)=x12−2x1+1+x22+4x2+4+α1(10−x1−10x2)+α2(10x1−10x2−10)L(x, \alpha)=f(x)+\alpha_1 g(x)+\alpha_2 g(x)\\ =x_1^2-2x_1+1+x_2^2+4x_2+4+\alpha_1 (10-x_1-10x_2)+\alpha_2 (10x_1-10x_2-10)

Итак, каково определение состояния ККТ? Это относительное выражение, которое становится:

L(x,α,β)=f(x)+∑αigi(xi)+∑βihi(xi)L(x,\alpha,\beta)=f(x)+\sum \alpha_i g_i(x_i)+\sum \beta_i h_i(x_i)

​ Где g — ограничение неравенства, а h — ограничение равенства, тогда KKT относится к оптимальному решению функции, которое удовлетворяет следующим условиям:

(1)Lдля каждогоxВывод равен0(2)h(x)=0(3)∑αigi(xi)=0,α>=0(1) Производная L для каждого x равна 0\\ (2)h(x)=0\\ (3)\sum\alpha_i g_i(x_i)=0,\alpha>=0

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

Уравнение SVM:

y~=1∣∣w∣∣s.t.yi(wTx+b)>=1\tilde{y}=\frac{1}{||w||}\\ s.t.\quad y_i(w^Tx+b)>=1

KKT позже получает:

L(w,b,α)=1∣∣w∣∣−∑i=0nαiyi(wTxi+b−1)Для удобства следующий абзац записывается как1РежимL(w, b,\alpha)=\frac{1}{||w||}-\sum_{i=0}^{n}\alpha_i y_i(w^Tx_i+b-1)\quad для удобства Опишите следующий абзац как 1

Теперь о третьем условии, мы можем понять его так:

в условиях ограниченийyi(wTx+b)>=1y_i(w^Tx+b)>=1Для тех точек внутри он удовлетворяет ограничениям, поэтому мы можем напрямую вывести вывод.Другими словами, точки, взятые в синей области, изначально находятся в ограничениях, значит ли это, что ограничения недействительны?, тогда альфа равна равным 0, и мы можем напрямую найти оптимальное решение. И наоборот, точка вне ограничения — это то, что нам нужно, тогда альфа не равна 0, то есть нам нужно найти точку, не удовлетворяющую условию ограничения, то есть максимальное значение альфа.

Следовательно, согласно приведенному выше утверждению, уравнение 1 может быть записано как:

minθ(w)=minx,bmaxαi>=0L(w,b,α)=p*min\quad \theta(w)=min_{x,b}max_{\alpha_i>=0}L(w,b,\alpha)=p^*

Давайте посмотрим на формулу, которую мы получили выше:

minθ(x)=minw,bmaxαi>=0L(w,b,α)=p*min\quad \theta(x)=min_{w,b}max_{\alpha_i>=0}L(w,b,\alpha)=p^*

​ Давайте посмотрим слева направо. Найти задачу несложно. Чтобы решить уравнение, мы должны сначала решить внутренний слой. То есть мы должны вычислить решение ограничения неравенства в начале, а затем вычислить w и b, но это точно Трудно найти, так что лучше передумать, сначала рассчитать ситуацию без ограничений, добавить ограничения и снова сделать расчет, что и есть закон двойственности. То есть наше уравнение выше эквивалентно:

minθ(w)=maxαi>=0minw,bL(w,b,α)=d*min\quad \theta(w)=max_{\alpha_i>=0}min_{w,b}L(w,b,\alpha)=d^*

Подробный момент написанный

maxαi>=0minx,b(12∣∣w∣∣2−∑i=0nα1(yi(xTxi+b)))max_{\alpha_i>=0}min_{x,b}(\frac{1}{2}||w||^2-\sum_{i=0}^n\alpha_1(y_i(x^Tx_i+b)))

На этот раз гораздо удобнее, и это преобразование тоже приносит определенные преимущества.Находим w,b и затем находим альфу, то есть в конце есть только одно решение альфа, что сводит наше решение только к одному Теперь альфа может представлять все. Я не знаю, помните ли вы еще точку альфа = 0, о которой мы упоминали выше в рамках ограничений, тогда с этим легко справиться. Опорный вектор — это ненулевая альфа. Решение также альфа, как об этом, разве это не очень умно?

Трехшаговый вывод для решения двойственных задач

Происхождение алгоритма SMO

​ Мы очень близки к ответу.Мы продолжаем делать выводы согласно идее в начале.Теперь все уравнение разрешилось в состояние, которое позволяет нам напрямую вывести = 0, чтобы получить наиболее ценное состояние, тогда давайте попробуем:

Сначала зафиксируйте альфа и найдите частные производные по w и b:

δLδw=0⟹w=∑i=1nαiyixiδLδb=0⟹0=∑i=1nαiyi\frac{\delta L}{\delta w}=0\Longrightarrow w=\sum_{i=1}^n\alpha_i y_ix_i\\ \frac{\delta L}{\delta b}=0\Longrightarrow 0=\sum_{i=1}^n\alpha_iy_i

Собственно, в этом и смысл кода в статье:

fXi = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b

Затем приведенный выше результат привести к исходной формуле (набирать формулу слишком хлопотно, я напрямую использую процесс вывода июля):

Наконец получить:

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

L(w,b,α)=∑i=1nαi−12∑i,j=1nαiαjyiyjxiTxjL(w,b,\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i \alpha_j y_iy_j x_i^Tx_j

Вещи, выведенные выше, имеют еще один i и j в исходной формуле, Фактически это означает, что мы случайным образом извлекаем два из вектора и используем их, и используем эти два вектора, чтобы найти максимальный интервал.

что такое слабая переменная

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

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

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

Переменные Slack, как следует из названия, должны ослабить требования этого интервала:

​ Сравнив верхнее и нижнее изображения, я добавил к изображению две красные пунктирные линии, которые являются переменными slack,

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

0<α<Cand∑i=1nαiyi=0g(x)={C(α>=C)0(0<α<C)1(α<=0)0<\alpha<C\quad and\quad \sum_{i=1}^n\alpha_iy_i=0\\ g(x)=\begin{cases} C\quad (\alpha>=C)\\ 0\quad (0<\alpha<C)\\ 1\quad (\alpha<=0) \end{cases}

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

Затем давайте посмотрим на это в сочетании с SMO, Алгоритм SMO случайным образом берет два вектора и смотрит, можно ли их оптимизировать. Что такое оптимизация, то есть два полученных вектора связаны с проблемой, которую мы хотим решить, и я думаю, что их можно исследовать дальше. Это означает, что наши два вектора должны быть в пределах (0, C).Что, если вектор, который мы берем, не находится в этом диапазоне?Пусть он будет равен границе, например, на рисунке выше Да, если точка находится вне черным пунктиром, то я заставлю его быть равным 1 (альфа=0 объяснено выше) Аналогично, если он находится за пределами красного пунктира, то пусть он будет равен C. Это гарантировано, I каждый раз вектор нарисован, он не повлияет на предполагаемый интервал, если он не нужен.

Теперь, когда я объяснил самую основную часть, я продолжу работу с функциями ядра.

использованная литература

Машинное обучение в действии Питера Харрингтона

«Математические основы искусственного интеллекта» Тан Юди

Популярное введение в машины опорных векторов (понимание трехуровневой области SVM)

blog.CSDN.net/V_July_V/AR…

Углубленный анализ версии исходного кода SVM для Python (3) — категория прогноза выборки расчета

blog.CSDN.net/BBB EO Y/Ariti…

Расшифровка SVM Series (1): Окола лагранжианского мультипликатора и условий KKT

blog.CSDN.net/on2 Брасс/Аретти…

Основная идея SVM и вводное обучение (перепечатка + объяснение, почему minL(w) становится minmaxL(a,w))

blog.CSDN.net/яблочный плавник/…

Задача выпуклой оптимизации, задача выпуклого квадратичного программирования QP, выпуклая функция

blog.CSDN.net/обещание плюс/…

Трансформация SVM из примитивной проблемы в двойственную и причины

blog.CSDN.net/QQ_44987376…

Почему SVM преобразует исходную проблему в двойную?

blog.CSDN.net/QQ_40598006…

Математический вывод машины опорных векторов, часть 1

blog.CSDN.net/QQ_23869697…

Расшифровка серии SVM (1): о методе множителей Лагранжа и условиях ККТ

blog.CSDN.net/on2 Брасс/Аретти…

Понимание переменных Slack машины опорных векторов

blog.CSDN.net/UST не предназначен для /art…

Свободные переменные SVM

blog.CSDN.net/Пять цветных облаков/…

Примечания к изучению гиперплоскости максимального интервала SVM и размышления об установке интервала функции на 1

blog.CSDN.net/WeChat_4402…Выше статья находится в выпусках, рекомендуется посетить этот сайт**

«Машинное обучение на практике»: популярное понимание машин опорных векторов

Об этой статье

В конце концов, «Машинное обучение на практике» — это только практическая книга, она больше предназначена для того, чтобы читатели поняли, как использовать алгоритмы, при этом уменьшив долю теоретических частей. Как и в Главе 6: Машины опорных векторов, самое важное в нейКлассификаторы решают задачи оптимизацииЧуть меньше двух страниц. Знания о машинах опорных векторов уже неясны и трудны для понимания, но эта книга по-прежнему является хорошим вводным учебником.Я считаю, что многие студенты используют этот превосходный учебник, поэтому я использую этот учебник как основу для анализа.

Много статей об SVM в Интернете хорошо написано. Среди них, я думаю, лучшая из них — «Популярное введение в машины опорных векторов (понимание трехслойной области SVM)», написанное Июлем. Вывод формулы очень всеобъемлющий. , оправдано. Но я плохо изучаю математику, поэтому я думаю, что эта статья слишком «хардкорна» для меня, и я думаю, что, поскольку первое, что нужно изучить алгоритм, — это понять, популярный момент — преобразовать теоретические вещи в свои собственные. слова. Поэтому я хочу написать статью, которая будет легко понятна студентам моего уровня математики.Конечно, я не пропущу вывод математических формул, потому что это ядро, но я буду интерпретировать это в более популярной форме.

На самом деле, это учебная заметка, которая является чисто личным пониманием.Если у вас есть какие-либо вопросы, пожалуйста, не стесняйтесь исправлять меня, спасибо!

Какой части учебника соответствует эта статья?

Эта часть учебника действительно трудна для понимания. (Студенты, которые не видели, могут посмотреть содержание ниже)

Что такое СВМ

Видел очень яркий пример в статье:

Давным-давно возлюбленная героя попала в плен к дьяволу, герой хотел ее спасти, но дьявол затеял с ним игру, название было такое: Горсть риса и горсть камней на стол, я сейчас Вот палка, я хочу, чтобы вы взяли это и палку, чтобы разделить две вещи.

Итак, герой делит это так:

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

Итак, герои снова поставили палку

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

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

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

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

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

Линейная классификация

Как появились ярлыки 1 и -1?

Прежде чем перейти к обсуждению SVM, нам нужно обратиться к происхождению книги, установив метки двух категорий на 1 и -1.

​ Это должно исходить из происхождения линейной классификацииЛогистическая регрессияГоворя о:

Логистическая регрессия — это широко используемый метод бинарной регрессии. Он подробно описан в главе 5 «Машинное обучение на практике». На самом деле, грубо говоря, мы надеемся получить функцию, которая может получить рассчитанное нами значение, и затем разделите его на категорию 0 или 1. Наиболее распространенной такой функцией является сигмовидная функция, а ее формула расчета и изображение следующие:

о(z)=11+e−z\sigma(z) = \frac{1}{1+e^{-z}}

Наблюдая за изображением, мы можем получить, что когда z=0,о(z)=0.5\sigma(z) = 0.5, чем больше z, темо(z)\sigma(z)Оно бесконечно близко к 1, и чем меньше z,о(z)\sigma(z)бесконечно близко к 0. Вы можете себе представить, очень ли близко это изображение к ступенчатой ​​функции, когда масштаб z большой, тогда мы можем использовать эту функцию в качестве классификатора, когдао(z)\sigma(z)>0,5, я думаю, что это класс 1, в противном случае это класс 0.

​ На данный момент мы решили проблему классификатора, поэтому нам нужно сосредоточиться только на линейной аппроксимации, котораяz=w0+w1x1+...+wnxnz=w_0 + w_1x_1 + ...+w_nx_n, поэтому приведенную выше формулу можно преобразовать в:

о(∑i=0nwixi=11+e∑i=0nwixi)\sigma({\sum_{i=0}^n w_ix_i} = \frac{1}{1 + e^{\sum_{i=0}^n w_ix_i}})

Это то, что мы называем логистической регрессией. Затем мы связываем его с SVM:

​ Формула гиперплоскости в книгеwTx+bw^Tx + b, на самом деле проще всего это понять на двумерной плоскости, w — параметр перед x и y, а b — точка пересечения. Как и линия на рисунке ниже, ее уравнение−x+2=y-x + 2 = y, сдвиньте его, чтобы получить:x+y−2=0x + y - 2 = 0, b равно 2, w равно [1, 1], x равно [x, y], вот что это значит, зачем использовать awTw^TЧтобы указать, что на самом деле в задаче линейной подгонки много параметров, и она написана так для красоты.

Теперь мы вносим изменения в сигмиод-функцию, меняем метку y=0 на y=-1 и меняем z наwTx+bw^Tx + b, а затем подставив его в функцию, вы получите отношение отображения между -1 и 1:

g(x)={1,z>=0−1,z<0g(x) = \begin{cases} 1, z>=0\\ -1, z<0 \end{cases}

На самом деле мы обнаружили, что эта связь на самом деле просто меняет метку 0 на -1, а другие вещи не изменились. Что касается того, почему бы не использовать напрямую 0 и 1, я объясню далее.

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

Почему вы хотите установить метки на 1 и -1

Возьмем простой пример. Как показано на рисунке ниже, на двумерной плоскости есть две группы чисел. Одна группа представлена ​​синим, а другая красным цветом. Пусть синий будет классом 1, а красный быть класса -1. Нетрудно видеть, что они линейно разделимы: сначала случайным образом находим гиперплоскость, затем точки выше гиперплоскости относятся к классу 1, а следующие — к классу -1.

Помните, какую проблему пытался решить SVM?Он заключается в том, чтобы найти тот, который дальше всего от гиперплоскости в опорном векторе., для интуитивного анализа мы могли бы также перевести прямую.Первая точка, в которой встречаются две параллельные прямые, является опорным вектором гиперплоскости.Чтобы найти расстояние между ними, первое, что приходит на ум, должна быть точка линия. Формула расстояния:

∣Ax+By+C∣A2+B2\frac{|Ax+By+C|}{\sqrt{A^2+B^2}}

(Честно говоря, то, что мы используем, это эта формула.Когда я начал учиться, я прочитал эту часть очень быстро, но я не мог понять это позже, потому что вывод SVM содержит много допущений, поэтому это место является фокусом)

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

​ Определить интервал функции (с помощью таблицыy^\hat{y}показано) как:

y^=yi(wTx+b)=yif(x)\hat{y} = y_i(w^Tx + b) = y_if(x)

из них формулаyiy_iпредставляет категорию, и этоf(x)f(x)Это уравнение гиперплоскости. Функциональный интервал интуитивно понимается как категория, умноженная на значение функции, которое представляет собой красную секцию на рисунке ниже: то есть наша гиперплоскость - это черная сплошная линия. Если она находится на точка линии, в уравнениеf(x)f(x)Должен быть равен 0, если его нет на линии,f(x)f(x)Оно должно быть равно ненулевому числу, и теперь я умножаю перед ним его категорию, что эквивалентно добавлению к нему абсолютного значения. Таким образом, нам не нужно заботиться о том, что это такое, когда мы его вычисляем, потому что мы хотим найти опорный вектор, просто смотрим на расстояние и не заботимся о том, что он означает. Таким образом, это преимущество использования -1 и 1, это определение не только устраняет влияние знака, но и не затрагивает значение функции (из-за умножения на 1).

Но если он используется для представления расстояния, недостаточно использовать эту функцию расстояния.Можно подумать о проблеме.Когда w и b уравнения гиперплоскости расширяются в два раза, а именно2wTx+2b=02w^Tx + 2b = 0, не влияет на гиперплоскость, но влияет на функцию расстояния, которая теперь в четыре раза больше, что явно неверно.

Так в это время было введено понятие геометрического интервала:

Предположим, что есть точка x, которая проецируется на гиперплоскость какx0x_0, w — вектор нормали гиперплоскости, y — расстояние от x до гиперплоскости:

Согласно геометрическим знаниям, мы можем получитьx=x0+yw∣∣w∣∣x = x_0 + y\frac{w}{||w||}

​∣∣w∣∣||w||- нормальная форма второго порядка w, которая на самом деле является длиной по модулю,w∣∣w∣∣\frac{w}{||w||}— единичный вектор нормали к гиперплоскости, а вектор, деленный на ее модуль, — единичный вектор. так какx0x_0является точкой на гиперплоскости, поэтому мы говорим, чтоx0x_0принестиwT+b=0w^T + b = 0(здесь я записываю его как тип 1), в это время мы находимся вx=x0+yw∣∣w∣∣x = x_0 + y\frac{w}{||w||}Умножить и влево, и вправо наwTw^TИ объедините уравнение 1, чтобы получить: (Здесь процесс вывода использует свойство, котороеwTw=w2w^Tw = w^2, остальным просто нужно занести переложенные предметы, вывести не сложно)

y=wTx+b∣∣w∣∣y = \frac{w^Tx + b}{||w||}

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

y~=yi(wTx+b)∣∣w∣∣=y^∣∣w∣∣\tilde{y} = \frac{y_i(w^Tx + b)}{||w||} = \frac{\hat{y}}{||w||}

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

Определение классификатора максимальной маржи

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

Давайте рассмотрим, что делает SVM? SVMОн заключается в том, чтобы найти тот, который дальше всего от гиперплоскости в опорном векторе.. К чему бы мы ни пришли, в конце концов мы должны вернуться к этому вопросу! В предыдущем разделе мы говорили о нахождении интервалов с помощью геометрических интервалов, но давайте подробнее рассмотрим формулу:

y~=yi(wTx+b)∣∣w∣∣=y^∣∣w∣∣\tilde{y} = \frac{y_i(w^Tx + b)}{||w||} = \frac{\hat{y}}{||w||}

Мы обнаружили, что очень проблематично спрашивать расстояние, потому что мы не знаем w и b, и мы не знаем числитель и знаменатель соавторства, поэтому это очень сложно решить, поэтому мы можно было бы поставить знаменатель константой, тут много книг.Все ставят знаменатель = 1, ни для чего другого, потому что 1 легко считать. В это время геометрический интервал становитсяy~=1∣∣w∣∣\tilde{y} = \frac{1}{||w||}, становится намного проще решать интервал, я хочу сделать геометрический интервал больше, тогда∣∣w∣∣||w||Чтобы быть меньше, мы делаем вышеприведенное предположение, и оно становится таким:

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

Предположим, что исходная гиперплоскость становится двумя пунктирными линиями рядом с ней, расстояние от них до гиперплоскости равно1∣∣w∣∣\frac{1}{||w||}, поэтому длина всего интервала1∣∣w∣∣\frac{1}{||w||}, и таким образом мы не только упрощаем задачу, но и выделяем часть ненужных данных, как показано на рисунке выше.wx+b=1wx + b = 1,wx+b=−1wx + b = -1Точки, входящие в интервал выше, являются опорными векторами, остальные точки не имеют к нам никакого отношения, нам это не нужно, поэтому мы устанавливаем ограничение.yi(wTx+b)>=1y_i(w^Tx + b) >= 1, то есть точки на этой линии, включая точки над линией, не то, что нам нужно (почему нам не нужны точки на линии? Потому что эта линия может не найти опорный вектор в начале , в пределах диапазона могут быть точки). Таким образом, проблема, которую мы решаем, становится такой, где st представляет смысл ограничений:

y~=1∣∣w∣∣s.t.yi(wTx+b)>=1\tilde{y} = \frac{1}{||w||}\\ s.t.\quad y_i(w^Tx + b) >= 1

Но этого недостаточно с формулой, которая заключается в следующем.1∣∣w∣∣\frac{1}{||w||}Это не радует глаз.Вы можете себе представить, что дано уравнение и давайте решим его максимальное значение, первое, о чем мы думаем, это взять производную от этого числа.Это разделение времени выглядит очень неудобно, поэтому давайте преобразуем его , так как требование1∣∣w∣∣\frac{1}{||w||}Максимальное значение , в свою очередь, является решением12∣∣w∣∣2\frac{1}{2}||w||^2Минимальное значение (здесь вы можете взглянуть на производную и найти, что производная равна w), квадрат вводится, чтобы превратить ее в бинарную функцию, тогда производная сама w.

Что такое множители Лагранжа и законы двойственности

Если решать интуитивно12∣∣w∣∣2\frac{1}{2}||w||^2Максимальное значение , честно говоря, было очень легко сделать, я могу напрямую продифференцировать уравнение и сделать его равным 0, но сейчас это невозможно сделать, потому что наше приведенное выше уравнение ограничено, он может только быть выполнено, если условия соблюдены. Затем, чтобы решить эту проблему поиска максимального значения с ограничениями, мы ввели метод множителей Лагранжа, и я прямо процитировал результаты других (потому что это было хорошо написано):

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

minf=2x12+3x22+7x32s.t.2x1+x2=12x2+3x3=2min\quad f=2x_1^2+3x_2^2+7x_3^2\\ s.t.\quad 2x_1+x_2=1\\ 2x_2+3x_3=2

Это задача оптимизации с ограничениями-равенствами, с объективными значениями и ограничениями. Итак, подумайте, как решить проблему предположения об отсутствии ограничений?Можно ли напрямую вывести производную каждого x, равного 0, и решить x. Но x равно 0 и не соответствует ограничениям, тогда возникает проблема. Дело в том, почему говорят, что производная равна 0. Теоретически большинство проблем возможны, но некоторые проблемы нет. Если вывод равен 0, это должно быть возможно, тогда f должна быть задачей выпуклой оптимизации.Что такое выпуклость?Как на следующем рисунке (выпуклость — это просто короткое имя, а направление может быть вверх или вниз):

Для этой выпуклой оптимизации правильнее сказать:

Доволенf(x1)+f(x2)2>f(x1+x22)orf(x1)+f(x2)2<f(x1+x22)\frac{f(x_1)+f(x_2)}{2} >f(\frac{x_1+x_2}{2})\\or\\\frac{f(x_1)+f(x_2)}{2}<f(\frac{x_1+x_2}{2}), которая является выпуклой функцией.

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

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

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

minf=2x12+3x22+7x32+α1(2x1+x2−1)+α2(2x2+3x3−2)min\quad f=2x_1^2+3x_2^2+7x_3^2+\alpha_1(2x_1+x_2-1)+\alpha_2(2x_2+3x_3-2)

Здесь вы можете увидетьα1\alpha_1,α2\alpha_2Все части умножения равны 0, поэтомуα1\alpha_1,α2\alpha_2Значением являются все действительные числа, и теперь эта целевая функция оптимизации не имеет ограничений, поэтому следующее решение состоит в том, чтобы использовать только производную, равную 0:

δfδx1=4x1+2α1=0⟹x1=−0.5α1δfδx2=6x2+α1+2α2=0⟹x2=−α1+2α26δfδx3=14x3+3α2=0⟹x3=−3α214\frac{\delta f}{\delta x_1}=4x_1+2\alpha_1=0 \Longrightarrow x_1 = -0.5\alpha_1\\ \frac{\delta f}{\delta x_2}=6x_2+\alpha_1+2\alpha_2=0\Longrightarrow x_2=-\frac{\alpha_1+2\alpha_2}{6}\\ \frac{\delta f}{\delta x_3}=14x_3+3\alpha_2=0 \Longrightarrow x_3 = -\frac{3\alpha_2}{14}

Затем помогите полученным выше результатам привести к ограничениям, и результаты могут быть полученыα1\alpha_1=-0,39,α2\alpha_2=-1,63, то ставимα\alphaПоднесите его к исходной формуле, чтобы получить х. Разрешать ограничения равенства — преступление, так что же нам делать с ограничениями неравенства? Необходимо использовать условие ККТ.

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

ККТ условия

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

minf=x12−2x1+1+x22+4x2+4s.t.x1+10x2>1010x1−10x2<10min\quad f=x_1^2-2x_1+1+x_2^2+4x_2+4\\ s.t.\quad x_1+10x_2>10\\ 10x_1-10x_2<10

Согласно приведенному выше утверждению, мы превращаем проблему «больше знака» в задачу «меньше знака» (почему изменение символа связано с тем, что для унификации операции, конечно, проще решить проблему в одном и том же направление, чем решать проблему в другом направлении), а затем следуйте за тягой. Практика метода множителя Грейнджа плюс альфа, мы получаем:

L(x,α)=f(x)+α1g(x)+α2g(x)=x12−2x1+1+x22+4x2+4+α1(10−x1−10x2)+α2(10x1−10x2−10)L(x, \alpha)=f(x)+\alpha_1 g(x)+\alpha_2 g(x)\\ =x_1^2-2x_1+1+x_2^2+4x_2+4+\alpha_1 (10-x_1-10x_2)+\alpha_2 (10x_1-10x_2-10)

Итак, каково определение состояния ККТ? Это относительное выражение, которое становится:

L(x,α,β)=f(x)+∑αigi(xi)+∑βihi(xi)L(x,\alpha,\beta)=f(x)+\sum \alpha_i g_i(x_i)+\sum \beta_i h_i(x_i)

​ Где g — ограничение неравенства, а h — ограничение равенства, тогда KKT относится к оптимальному решению функции, которое удовлетворяет следующим условиям:

(1)Lдля каждогоxВывод равен0(2)h(x)=0(3)∑αigi(xi)=0,α>=0(1) Производная L для каждого x равна 0\\ (2)h(x)=0\\ (3)\sum\alpha_i g_i(x_i)=0,\alpha>=0

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

Уравнение SVM:

y~=1∣∣w∣∣s.t.yi(wTx+b)>=1\tilde{y}=\frac{1}{||w||}\\ s.t.\quad y_i(w^Tx+b)>=1

KKT позже получает:

L(w,b,α)=1∣∣w∣∣−∑i=0nαiyi(wTxi+b−1)Для удобства следующий абзац записывается как1РежимL(w, b,\alpha)=\frac{1}{||w||}-\sum_{i=0}^{n}\alpha_i y_i(w^Tx_i+b-1)\quad для удобства Опишите следующий абзац как 1

Теперь о третьем условии, мы можем понять его так:

в условиях ограниченийyi(wTx+b)>=1y_i(w^Tx+b)>=1Для тех точек внутри он удовлетворяет ограничениям, поэтому мы можем напрямую вывести вывод.Другими словами, точки, взятые в синей области, изначально находятся в ограничениях, значит ли это, что ограничения недействительны?, тогда альфа равна равным 0, и мы можем напрямую найти оптимальное решение. И наоборот, точка вне ограничения — это то, что нам нужно, тогда альфа не равна 0, то есть нам нужно найти точку, не удовлетворяющую условию ограничения, то есть максимальное значение альфа.

Следовательно, согласно приведенному выше утверждению, уравнение 1 может быть записано как:

minθ(w)=minx,bmaxαi>=0L(w,b,α)=p*min\quad \theta(w)=min_{x,b}max_{\alpha_i>=0}L(w,b,\alpha)=p^*

Давайте посмотрим на формулу, которую мы получили выше:

minθ(x)=minw,bmaxαi>=0L(w,b,α)=p*min\quad \theta(x)=min_{w,b}max_{\alpha_i>=0}L(w,b,\alpha)=p^*

​ Давайте посмотрим слева направо. Найти задачу несложно. Чтобы решить уравнение, мы должны сначала решить внутренний слой. То есть мы должны вычислить решение ограничения неравенства в начале, а затем вычислить w и b, но это точно Трудно найти, так что лучше передумать, сначала рассчитать ситуацию без ограничений, добавить ограничения и снова сделать расчет, что и есть закон двойственности. То есть наше уравнение выше эквивалентно:

minθ(w)=maxαi>=0minw,bL(w,b,α)=d*min\quad \theta(w)=max_{\alpha_i>=0}min_{w,b}L(w,b,\alpha)=d^*

Подробности написаны

maxαi>=0minx,b(12∣∣w∣∣2−∑i=0nα1(yi(xTxi+b)))max_{\alpha_i>=0}min_{x,b}(\frac{1}{2}||w||^2-\sum_{i=0}^n\alpha_1(y_i(x^Tx_i+b)))

На этот раз гораздо удобнее, и это преобразование также приносит определенные преимущества.Находим w, b и затем находим альфу, то есть в конце есть только одно решение, альфа, что сводит наше решение только к одному Теперь альфа может представлять все. Я не знаю, помните ли вы еще точку альфа = 0, о которой мы упоминали выше в рамках ограничений, тогда с этим легко справиться. Опорный вектор - это ненулевая альфа. Решение также альфа, как об этом, разве это не очень умно?

Трехшаговый вывод для решения двойственных задач

Происхождение алгоритма SMO

​ Мы очень близки к ответу.Мы продолжаем делать выводы согласно идее в начале.Теперь все уравнение разрешилось в состояние, которое позволяет нам напрямую вывести = 0, чтобы получить наиболее ценное состояние, тогда давайте попробуем:

Сначала зафиксируйте альфа и найдите частные производные по w и b:

δLδw=0⟹w=∑i=1nαiyixiδLδb=0⟹0=∑i=1nαiyi\frac{\delta L}{\delta w}=0\Longrightarrow w=\sum_{i=1}^n\alpha_i y_ix_i\\ \frac{\delta L}{\delta b}=0\Longrightarrow 0=\sum_{i=1}^n\alpha_iy_i

Собственно, в этом и смысл кода в статье:

fXi = float(np.multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b

Затем приведенный выше результат привести к исходной формуле (набирать формулу слишком хлопотно, я напрямую использую процесс вывода июля):

Наконец получить:

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

L(w,b,α)=∑i=1nαi−12∑i,j=1nαiαjyiyjxiTxjL(w,b,\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i \alpha_j y_iy_j x_i^Tx_j

Вещи, выведенные выше, имеют еще один i и j в исходной формуле, Фактически это означает, что мы случайным образом извлекаем два из вектора и используем их, и используем эти два вектора, чтобы найти максимальный интервал.

что такое слабая переменная

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

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

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

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

​ Сравнив верхнее и нижнее изображения, я добавил к изображению две красные пунктирные линии, которые являются переменными slack,

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

0<α<Cand∑i=1nαiyi=0g(x)={C(α>=C)0(0<α<C)1(α<=0)0<\alpha<C\quad and\quad \sum_{i=1}^n\alpha_iy_i=0\\ g(x)=\begin{cases} C\quad (\alpha>=C)\\ 0\quad (0<\alpha<C)\\ 1\quad (\alpha<=0) \end{cases}

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

Затем давайте посмотрим на это в сочетании с SMO, Алгоритм SMO случайным образом берет два вектора и смотрит, можно ли их оптимизировать. Что такое оптимизация, то есть два полученных вектора связаны с проблемой, которую мы хотим решить, и я думаю, что их можно исследовать дальше. Это означает, что наши два вектора должны быть в пределах (0, C).Что, если вектор, который мы берем, не находится в этом диапазоне?Пусть он будет равен границе, например, на рисунке выше Да, если точка находится вне черным пунктиром, то я заставлю его быть равным 1 (альфа=0 объяснено выше) Аналогично, если он находится за пределами красного пунктира, то пусть он будет равен C. Это гарантировано, I каждый раз вектор нарисован, он не повлияет на предполагаемый интервал, если он не нужен.

Теперь, когда я объяснил самую основную часть, я продолжу работу с функциями ядра.

использованная литература

Машинное обучение в действии Питера Харрингтона

«Математические основы искусственного интеллекта» Тан Юди

Популярное введение в машины опорных векторов (понимание трехуровневой области SVM)

blog.CSDN.net/V_July_V/AR…

Углубленный анализ версии исходного кода SVM для python (3) — категория прогноза расчетной выборки

blog.CSDN.net/BBB EO Y/Ariti…

Расшифровка серии SVM (1): о методе множителей Лагранжа и условиях ККТ

blog.CSDN.net/on2 Брасс/Аретти…

Основная идея SVM и вводное обучение (перепечатка + объяснение, почему minL(w) становится minmaxL(a,w))

blog.CSDN.net/яблочный плавник/…

Задача выпуклой оптимизации, задача выпуклого квадратичного программирования QP, выпуклая функция

blog.CSDN.net/обещание плюс/…

Трансформация SVM из примитивной проблемы в двойственную и причины

blog.CSDN.net/QQ_44987376…

Почему SVM преобразует исходную проблему в двойную?

blog.CSDN.net/QQ_40598006…

Математический вывод машины опорных векторов, часть 1

blog.CSDN.net/QQ_23869697…

Расшифровка серии SVM (1): о методе множителей Лагранжа и условиях ККТ

blog.CSDN.net/on2 Брасс/Аретти…

Понимание переменных Slack машины опорных векторов

blog.CSDN.net/UST не предназначен для /art…

Свободные переменные SVM

blog.CSDN.net/Пять цветных облаков/…

Примечания к изучению гиперплоскости максимального интервала SVM и размышления об установке интервала функции на 1

blog.CSDN.net/WeChat_4402…

Категории