Машина опорных векторов

Глубокое погружение в модель SVM

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

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

Ниже у нас есть набор данных с двумя классами. Здесь мы показываем две границы решения, представленные линиями 1 и 2. Легко видеть, что есть много других линий, которые могут разделить входное пространство таким образом, чтобы все наблюдения были правильно классифицированы - фактически, существует бесконечное количество строк. .

Так как же SVM выбирает свою линию? Есть две основные идеи. Обратите внимание на то, как точка A очень далеко от линии 1. Кажется интуитивным сделать вывод, что на основе границы принятия решения, определенной линией 1, мы более уверены в том, что предсказываем, что точка A принадлежит классу круга, чем сказать то же самое о точке B SVM стремится к максимальной достоверности своих прогнозов в обучающем наборе. Также обратите внимание, что есть много точек очень близко к строке 2: это означает, что любое изменение параметров границы решения может привести к неправильному предсказанию классов некоторых из этих точек. Эти две идеи в сочетании образуют интуицию, лежащую в основе SVM.

Примечание. В этом посте вы увидите слово «гиперплоскость». Гиперплоскость - это просто причудливое название для подмножества с одним измерением меньше, чем его окружающее пространство, что является случаем для границы решения SVM. Это означает, что если входное пространство находится в ℝᵖ, граница решения имеет (p - 1) размерности. Например, на изображении ниже пространство ввода составляет ², поэтому граница решения SVM является одномерной: линия.

Маржа

SVM - это модель линейной классификации. Для выхода y ∈ {-1, 1} мы можем записать функцию гипотезы как линейную комбинацию входов:

И мы прогнозируем:

Кажется интуитивно понятным, что чем дальше значение гипотезы от нуля, тем больше мы уверены в своих прогнозах. Если h (x) = 10, мы более уверенно предсказываем y = 1, чем когда h (x) = 0,1.

Это может привести к мысли, что мы хотим найти параметры (w, b), которые будут максимизировать значения h, когда y⁽ⁱ⁾ = 1, и минимизировать значения h, когда y⁽ⁱ ⁾ = -1. Другими словами, мы можем захотеть максимизировать функциональную маржу γ̂:

Но с этим есть проблема: обратите внимание, что предсказанный класс зависит только от знака h. Это означает, что мы можем масштабировать параметры, например (w, b) → (10 w, 10b), не меняя предсказанные классы. Это увеличило бы значения h в 10 раз и дало бы ложное представление о том, что наша модель в 10 раз более уверена в своих прогнозах.

Здесь на помощь приходит понятие геометрического поля. Геометрическое поле γ̂ определяется как расстояние от i-го наблюдения до границы принятия решения. В отличие от функционального запаса, эта мера инвариантна к масштабированию параметров. В конце концов, гиперплоскость, определяемая как w ᵀ x + b = 0, точно такая же, как и гиперплоскость, определяемая как 10 w ᵀ х + 10b = 0.

SVM ищет гиперплоскость, которая находится как можно дальше от ближайшего члена каждого класса. Глядя на рисунок ниже, мы видим, что P₁ и P₂ - самые близкие наблюдения для каждого класса. Граница решения SVM равноудалена P₁ и P₂, то есть d₁ = d₂. Наконец, что более важно, из всех границ принятия решений, которые правильно классифицируют каждое наблюдение в обучающем наборе, SVM - это тот, у которого наибольшее минимальное расстояние min (d₁, d₂).

Другими словами, если мы определим γ = min γ⁽ⁱ⁾, SVM будет искать гиперплоскость с наибольшим значением γ.

SVM стремится максимизировать минимальный геометрический запас.

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

Например, на изображении ниже мы видим, что перед масштабированием функций SVM ищет границу принятия решения, чтобы вектор расстояния d₁ имел максимально возможную вертикальную составляющую. Вот почему мы всегда должны применять масштабирование функций перед установкой SVM.

Всегда масштабируйте элементы перед установкой SVM

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

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

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

Но давайте посмотрим, что произойдет, когда мы добавим к этому набору данных одну дополнительную функцию: а именно расстояние каждого наблюдения до точки (0). Это означает, что точка, обозначенная (-3) в исходном пространстве ввода, теперь представлена ​​парой (-3, 3); аналогично точка, представленная (5), становится (5, 5). Мы переназначаем пространство ввода с одного измерения на два. И, как вы можете видеть на изображении справа, этот мощный и простой прием делает данные линейно разделяемыми в ℝ² и, как следствие, более подходящими для SVM.

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

Один из распространенных способов реализации этой идеи - добавление полиномов более высокой степени к обучающей выборке. На изображении ниже показан набор данных с двумя характеристиками (x₁, x₂), которые явно нельзя разделить линейно в ℝ².

Нам нужно преобразовать входные данные таким образом, чтобы данные стали линейно разделяемыми (не забудьте потом масштабировать их!). Мы добавим полиномиальные функции до третьей степени, переназначив пространство ввода с ℝ² на ℝ¹⁰, так что (x₁, x₂) становится (1, x₁, x₂, x₁x₂, x₁², x₂², x₁²x₂, x₂²x₁, x₁³, x₂³). К сожалению, мы не можем увидеть крутой 10-мерный график, поэтому остановились на 2D-представлении с исходными характеристиками. Обратите внимание, что для прогнозирования новых точек данных нам необходимо применить то же полиномиальное преобразование, прежде чем передавать его в SVM.

Другой способ обойти линейные ограничения SVM - использовать меры сходства, которые представляют собой просто функции, которые количественно определяют сходство между двумя точками данных. Одной из наиболее распространенных функций подобия является радиальная базисная функция Гаусса (RBF), которая определяется как:

Мы можем выбрать несколько ориентиров и переназначить входные данные на вектор, содержащий расстояние до каждого ориентира. Итак, если у нас есть три точки ориентиров (l ₁, l ₂, l ₃), и мы используем функцию подобия RBF ϕ, наблюдение первоначально представленный x становится (ϕ (x, l ₁), ϕ (x, l ₂), ϕ (x, l ₃)).

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

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

Математика, лежащая в основе модели

Как мы уже говорили ранее, SVM - это модель линейной классификации, и мы можем записать ее функцию гипотезы как линейную комбинацию входных данных:

И мы прогнозируем:

Пришло время воплотить цель SVM по нахождению наибольшего геометрического поля в математической задаче. Если задана точка x ⁽ⁱ⁾, каково ее расстояние до границы принятия решения, определенной как w ᵀ x + b = 0? Итак, мы знаем, что w - это нормальный вектор этой гиперплоскости, что означает, что он перпендикулярен плоскости. И если w - вектор нормали, то w / || w || - единичный вектор, перпендикулярный плоскости.

Пусть теперь γ будет расстоянием от x до гиперплоскости - тогда мы можем сказать, что x - γ * (w / || w ||) приземляется на гиперплоскость (обозначенную p на изображении выше). И последнее, поскольку p является вектором на гиперплоскости, это означает, что он должен удовлетворять уравнению гиперплоскости w ᵀ p + b = 0. Это дает используйте систему уравнений ниже:

И если мы решим его относительно γ, мы обнаружим, что расстояние от точки x ⁽ⁱ⁾ до границы решения SVM определяется выражением γ⁽ⁱ⁾ = (w ᵀ x ⁽ⁱ⁾ + b) / || w ||. Обратите внимание, что это уравнение действительно только для точек в том же направлении, что и вектор нормали w, поскольку мы вычли его из x; в противном случае нам пришлось бы добавить γ w / w ||. После небольшой настройки мы можем записать обобщенную геометрическую границу γ как:

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

Жесткая маржа SVM

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

Теперь вспомните, как мы сказали, что предсказанные классы зависят только от знака h и что геометрические поля инвариантны к масштабированию параметров? Это означает, что мы можем добавлять произвольные ограничения к параметрам, не влияя на модель. Для любой подходящей SVM мы можем наложить ограничение вроде || w || = 1, то все, что нам нужно сделать, это изменить масштаб его параметров, и модель останется неизменной.

Мы можем использовать этот результат вместе с тем фактом, что геометрические и функциональные поля равны, когда || w || = 1, чтобы записать цель оптимизации SVM с жестким запасом:

Первое ограничение заставляет правильно классифицировать каждое наблюдение. Второе ограничение заставляет γ быть не только нижней границей функционального запаса, но также и геометрического запаса. Это как раз и является целью оптимизации hard margin SVM:

для максимального увеличения минимального геометрического поля без каких-либо ошибок в классификации

Если бы у нас были инструменты для решения этой проблемы ограниченной оптимизации, мы могли бы остановиться на этом. Но, к сожалению, || w || = 1 - невыпуклое ограничение, поэтому нам нужно будет внести некоторые изменения, чтобы преобразовать эту проблему в более удобный формат.

Мы можем избавиться от неприятного ограничения, разделив цель на норму - если γ - нижняя граница функционального запаса, то γ / || w || - нижняя граница геометрического поля. Итак, нашу новую задачу можно записать так:

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

Наша новая цель оптимизации состоит в том, чтобы максимизировать 1 / || w ||, что эквивалентно минимизации || w ||. Последний, с тех пор как || w || не дифференцируема в 0, вместо этого мы минимизируем (1/2) * || w || ², производная которого равна просто w. Алгоритмы оптимизации намного лучше работают с дифференцируемыми функциями.

Наконец, мы определяем цель оптимизации hard margin SVM как:

Теперь, когда у нас есть цель оптимизации SVM, определенная таким образом, чтобы мы могли ее эффективно оценить (квадратичная цель и линейные ограничения), мы можем написать код для ее решения. Прочтите приведенный ниже код (или в этом репозитории) или попробуйте реализовать его самостоятельно, используя функцию свернуть SciPy. Если вы прочитаете документацию, то увидите, что минимизируемая целевая функция принимает в качестве аргумента список, поэтому мы поместим w и b в один и тот же вектор. Он также принимает аргумент _constraints_, который может представлять равенство (функция ограничения должна возвращать 0) или неравенство (функция ограничения должна возвращать неотрицательные значения). Мы перепишем наше обобщенное ограничение как y⁽ⁱ⁾ (w ᵀ x ⁽ⁱ⁾ + b) - 1 ≥ 0, чтобы соответствовать _SciPy _ спец.

Теперь мы можем увидеть, как наша модель работает при параллельном сравнении с реализацией _SKLearn_. Не так уж плохо!

Мягкая маржа SVM

У SVM жесткого поля есть два очень важных ограничения:

- работает только с линейно разделяемыми данными;

- очень чувствительно к выбросам.

Если мы хотим большей гибкости, нам нужно ввести в модель способ, позволяющий допускать неправильные классификации, и мы делаем это, используя концепцию переменных резервирования. У каждого наблюдения есть своя собственная мера резервирования, которая показывает, насколько эта конкретная точка данных может нарушить маржу. Наше новое ограничение можно переписать так: y⁽ⁱ⁾ (w ᵀ x ⁽ⁱ⁾ + b) ≥ 1 - ϵ⁽ⁱ⁾. Обратите внимание, что теперь нам нужно оценить одну дополнительную переменную для каждого наблюдения.

Осталась одна проблема. Если мы все еще пытаемся минимизировать || w ||, мы можем просто позволить ϵ → ∞ и быть уверенным, что новые ограничения будут соблюдаться. Нам нужна новая целевая функция для представления конфликтующих целей SVM с мягким запасом: мы по-прежнему хотим, чтобы поля были как можно шире, и мы хотим, чтобы переменные резервов были как можно меньше, чтобы предотвратить нарушения полей. Это дает нам цель классификатора soft margin SVM:

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

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

Квадратичное программирование

Квадратичное программирование (QP) - это система для решения определенного типа задач оптимизации, в которых целевая функция является квадратичной, а ограничения линейны - это именно тот тип проблем, с которыми мы имели дело!

То, как различные алгоритмы решают оптимизацию QP, выходит за рамки этого поста. Вместо этого мы сосредоточимся на выводе проблемы оптимизации SVM, которая решается такими библиотеками, как libsvm.

Учитывая, что проблема QP определяется как:

Все, что нам нужно сделать, это выяснить, какие значения P, q, G, h представляют проблему SVM, и мы можем использовать решатель (мы будем использовать cvxopt позже), чтобы получить оценки параметров.

Обратите внимание, что нам нужно будет переписать ограничения SVM, чтобы они соответствовали форме ограничений QP. Они будут:

Итак, для soft margin SVM, пусть X будет обучающим набором, представленным матрицей m × (n + 1) (m наблюдений и n функций), дополненной слева вектор-столбцом для перехвата. . Тогда проблема SVM QP определяется с помощью:

Как же так? Поскольку нам нужно оценить b, w и ϵ, вектор u задачи QP принимает вид [b, w₁,…, wₙ, ε₁,…, εₘ]. А потом:

- матрица P использует тождество для возврата w и нулей для отмены b и ϵ;

- вектор q умножает b и w на 0, а ϵ умножает на C, так что у нас есть вторая часть цели оптимизации C. ∑ᵢ₌₁ᵐ ε⁽ⁱ⁾;

- матрица K дает нам -y⁽ⁱ⁾ (w ᵀ x ⁽ⁱ⁾ + b), а -Iₘ справа от нее вычитает εᵢ. Нижняя строка матрицы G представляет -ϵ⁽ⁱ⁾ ≤ 0;

- наконец, вектор h имеет -1 и 0, как и ограничения (≤ -1 и ≤ 0).

Теперь все, что нам нужно сделать, это передать эти значения программе QP, и у нас есть параметры soft margin SVM. Вы можете проверить код для реализации этой идеи ниже (или в этом репо). Мы уже добились большого прогресса, но еще не закончили.

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

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

Двойственность Лагранжа

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

- Уловка ядра: обучение и прогнозы SVM будут зависеть от точек данных только через их внутренний продукт. Этот мощный результат позволяет нам применять любые преобразования к обучающей выборке (даже переназначая ее в бесконечномерное пространство!), Пока мы можем вычислить этот внутренний продукт;

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

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

Для простоты мы проанализируем проблему только с ограничениями-неравенствами (например, SVM), но результаты можно легко обобщить до равенств. Один из способов переписать эту проблему - использовать бесконечную ступенчатую функцию g (u):

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

Обратите внимание, что мы штрафуем J (x) положительным членом бесконечности, если какое-либо из исходных ограничений не выполняется. И когда все ограничения выполнены, то g (fᵢ (x)) = 0 ∀ i и J (x) = f₀ (x). Таким образом, минимизация J (x) эквивалентна исходной задаче, но мы пока не можем решить эту новую оптимизацию - ступенчатая функция не является ни непрерывной, ни дифференцируемой.

Что, если бы вместо функции бесконечного шага мы использовали линейную функцию вроде g (u) = α u? Если мы применяем α ≥ 0, то штраф, по крайней мере, в правильном направлении, когда ограничение не выполняется (α u ›0). Кроме того, теперь g можно непрерывно дифференцировать: он гораздо лучше подходит для задач оптимизации.

Итак, если мы подставим наш новый линейный штраф в уравнение J (x) выше, мы получим функцию от x и α, которая известна как лагранжиан:

Обратите внимание, что если мы максимизируем лагранжиан относительно α, мы получим J (x) обратно: αᵢ = 0, если fᵢ (x) ‹0 (поскольку αᵢ ≤ 0), и αᵢ → ∞, если fᵢ (x)› 0. Таким образом, Исходная задача теперь может быть записана как функция лагранжиана:

Наконец, поскольку min max f ≥ max min f для любой функции f, мы имеем следующее:

Minₓ L (x, α) называется двойственной функцией, а ее максимум - это нижняя граница для исходной (прямой) задачи оптимизации. Более того, можно показать, что при определенных условиях:

так что мы можем решить двойную проблему в отличие от основной проблемы. К счастью, SVM удовлетворяет этим условиям (в частности, условию Слейтера): целевая функция и функция ограничения являются выпуклыми и непрерывно дифференцируемыми.

Поскольку SVM удовлетворяет условиям регулярности, при наличии решения прямой задачи оно обязательно будет среди стационарных точек (x * , α *) лагранжиана, которые удовлетворяют уравнению Каруша – Куна– Условия Такера (ККТ). Кроме того, в случае SVM (выпуклой дифференцируемой) условия KKT не только необходимы, но и достаточны для оптимальности.

Какие условия ККТ? Если основная задача имеет решение x * , а α * является решением двойственной задачи, такое, что L (x * , α *) = f₀ (x * ). Тогда должны быть выполнены условия ККТ:

Двойная форма SVM

Ниже у нас есть проблема оптимизации SVM с мягкой маржой:

Если мы перепишем оба ограничения как:

Лагранжиан можно записать как:

Помните, что поскольку задача оптимизации SVM удовлетворяет некоторым особым условиям (целевая функция и функция ограничений являются выпуклыми и непрерывно дифференцируемыми), любое решение лагранжиана является решением исходной оптимизации и должно удовлетворять условиям KKT. Из ККТ у нас есть:

Из условия двойной допустимости имеем:

Итак, на основе частной производной от b, градиента над w и двойного условия выполнимости мы выводим ограничения для двойственной задачи:

Мы почти на месте! Вернемся к лагранжиану и воспользуемся результатом, полученным с помощью градиента w (w = ∑ᵢ₌₁ᵐ α⁽ⁱ⁾ y⁽ⁱ⁾ x ⁽ⁱ⁾) и подставим его в последний член лагранжевой суммы:

Позволять

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

Наконец, поскольку ∑ α⁽ⁱ⁾ y⁽ⁱ⁾ = C - λ⁽ⁱ⁾ - α⁽ⁱ⁾ = 0, мы, наконец, имеем двойную форму SVM мягкого поля (после умножения на - 1 и превратив максимизацию в задачу минимизации):

Теперь нам просто нужно вернуть вектор весов w и член смещения b из множителей Лагранжа α. Для весов мы можем просто использовать тот факт, что w = ∑ α⁽ⁱ⁾ y⁽ⁱ⁾ x ⁽ⁱ⁾. Обратите внимание, что нас интересуют только те индексы, где α⁽ⁱ⁾ ›0.

Чтобы вернуться к b, давайте в последний раз взглянем на условия KKT - исходя из дополнительной расслабленности, мы имеем:

Из первого уравнения мы видим, что при αᵢ * ›0 i-е ограничение должно быть активным, то есть оно должно выполняться по равенству, что:

Исходя из λ⁽ⁱ⁾ ϵ⁽ⁱ⁾ = 0 и C - α⁽ⁱ⁾ - λ⁽ⁱ⁾ = 0, имеем 0 ‹α⁽ⁱ⁾‹ C = ›λ⁽ⁱ⁾› 0 = ›ϵ⁽ ⁱ⁾ = 0. Мы будем усреднять это подмножество обучающей выборки, чтобы вычислить b. Если 0 ‹α⁽ⁱ⁾‹ C, имеем:

где M - подмножество обучающей выборки, удовлетворяющее 0 ‹α⁽ⁱ⁾‹ C, а nₘ - ее размер. Наконец, чтобы сделать прогноз о новом наблюдении x, нам необходимо вычислить:

Это был долгий путь, но мы только что вывели точную задачу оптимизации, которую решает популярная библиотека libsvm! Позже мы будем использовать стандартный решатель QP, но если вам интересно, как они решают его более эффективно, вы можете проверить эту статью, где они представляют алгоритм последовательной минимальной оптимизации (SMO), который _libsvm_ библиотека основана на.

Двойные выводы

Следует выделить два очень важных результата:

1. Прогнозы SVM зависят только от наблюдений, где α⁽ⁱ⁾> 0. Эти точки представляют собой очень специальное подмножество обучающей выборки и называются опорными векторами.

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

2. Во время обучения и для прогнозирования мы зависим от точек данных только через их внутренний продукт (x⁽ⁱ⁾) ᵀ x⁽ʲ⁾. Этот красивый и важный результат позволяет трюк с ядром.

Ядра

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

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

Вместо того, чтобы настраивать SVM с использованием исходных функций (x₁, x₂), мы хотим использовать ϕ (x). Мы уже видели, что при использовании двойной формы SVM зависит от точек данных только через их внутренний продукт. Это означает, что нам нужно только рассчитать:

Здесь на помощь приходят ядра. В машинном обучении ядро ​​ - это функция, которая вычисляет внутренний продукт ϕ (x ⁽ⁱ⁾) ᵀ ϕ (x ⁽ʲ⁾) только на основе исходных векторов (x ⁽ⁱ⁾, x ⁽ʲ⁾). Не нужно вычислять преобразование ϕ (x) или даже знать о нем!

Давайте посмотрим на небольшой пример. Пусть ϕ (x) будет функцией отображения признаков, определенной ниже:

Тогда внутреннее произведение двух векторов a = [a₁, a₂] и b = [b₁, b₂] после применения преобразования ϕ равно:

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

Если бы мы подгоняли SVM к этим данным, мы могли бы просто взять квадрат скалярных произведений исходных векторов, и мы, по сути, подгоняли бы модель к преобразованным векторам.

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

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

Все это вызывает вопрос: может ли каждая функция использоваться как ядро? Можно показать, что если функция K (a, b) удовлетворяет нескольким условиям (условиям Мерсера), то существует функция ϕ, которая отображает a и b в другой пробел, так что: K (a, b) = ϕ (a ) ᵀ ϕ (б). Тогда мы можем использовать K как ядро, потому что знаем, что ϕ существует. Итак, пока функция удовлетворяет условиям Mercer, ее можно использовать в качестве ядра.

И последнее замечание: если мы используем ядро, мы обычно не можем получить вектор веса w из множителей Лагранжа. Это происходит потому, что после преобразования входных данных w = ∑ᵢ α⁽ⁱ⁾ y⁽ⁱ⁾ ϕ (x ⁽ⁱ⁾) и ϕ не обязательно известно. Но это не представляет проблемы, потому что везде нам нужно только вычислить ϕ (x ⁽ⁱ⁾) ϕ (x ⁽ʲ⁾) = K (x ⁽ⁱ⁾, x ⁽ʲ⁾).

Окончательный код

Теперь, когда мы знаем, как вывести и решить проблему оптимизации SVM, мы готовы разобраться в коде, стоящем за ней. Исходный код доступен в этом репо - единственное изменение заключалось в оценке b путем усреднения по экземплярам, ​​где 0 ‹α⁽ⁱ⁾‹ C (вместо 0 ‹α⁽ⁱ⁾).

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

Ссылки

- http://cs229.stanford.edu/notes/cs229-notes3.pdf

- https://www-cs.stanford.edu/people/davidknowles/lagrangian_duality.pdf

- https://gist.github.com/mblondel/586753

- Бишоп, Кристофер - Распознавание образов и машинное обучение (ссылка)

- Жерон, Орелиен - Практическое машинное обучение с помощью Scikit-Learn, Keras и TensorFlow, 2-е издание (ссылка)