Метод опорных векторов (SVM) — это алгоритм непараметрической классификации, основанный на геометрическом представлении двоичных, линейно разделимых данных. Хотя существует несколько расширений SVM, которые обрабатывают данные с мультиклассами, перекрывающимися данными и случаем нелинейной разделимости данных, в этой статье рассматривается только базовая постановка задачи, в которой есть две группы данных, которые могут быть классифицированы на. Более того, эти два класса не должны перекрываться геометрически, и между классами должно быть четкое расстояние (маржа), которое не включает точки данных ни от одного из них (поэтому базовая форма SVM называется SVM с жесткими маржами), тогда гиперплоскость (обобщение линии, линия в 2D, плоскость в 3D и гиперплоскость из 4D и далее) может быть проведена в середине этого поля, чтобы сформировать «границу классификации» между двумя классами данных. Алгоритм SVM определяет систематический подход к аппроксимации параметров, определяющих эту гиперплоскость.
Цели
Эта статья призвана предоставить пошаговую математическую формулировку SVM с жестким запасом с нуля, оставив расширения SVM для обсуждения в следующих статьях.
Определение данных
Во-первых, данные, которые будут использоваться в этой демонстрации, имеют только 2 функции; это формирование позволяет нам сделать визуализацию в 2D, что значительно упрощает передачу геометрических понятий, на которые опирается SVM, после чего все понятия в 2D хорошо обобщаются в более высоких измерениях. Данные могут выглядеть следующим образом:
Каждая строка в приведенной выше таблице состоит из двух компонентов, первый компонент — это точка 𝑋𝑖 в пространстве 𝑅² (данные из столбцов 𝑥1, 𝑥2) такая, что 𝑋𝑖=(𝑥_𝑖1, 𝑥_𝑖2), ∀i=1, 2 , …, n, а второй компонент — это группа 𝑦𝑖, которой принадлежит 𝑋𝑖. В нашем базовом случае 𝑦𝑖 включает только две группы, численно группы могут быть представлены любыми двумя целыми числами, но пусть для удобства они будут 𝑦𝑖 ∈ {−1, 1}.
Данные при построении в 2D должны быть геометрически линейно разделены, поэтому они будут выглядеть примерно так, как показано на следующем графике.
Общая форма линейного уравнения
Как упоминалось выше, цель SVM — определить линию, которая разделяет две группы данных наилучшим образом. Мы подробнее остановимся на том, как этот лучший способ работает в SVM, в следующих разделах.
Теперь важно отметить, что линейное уравнение, используемое для описания разделительной линии, которое мы ищем, не является обычно используемым пересечение наклона (𝑦=𝑚𝑥+𝑐). Причина в том, что форма пересечение наклона не описывает вертикальную линию, которая может быть кандидатом на роль границы решения в SVM.
Таким образом, вместо этого мы используем общую форму линейного уравнения, 𝐴𝑥+𝑏𝑦+C=0, которое может описать линию 𝑥=𝑎, установив 𝐴=1, 𝐵=0 и 𝐶=-𝑎. Общая форма имеет еще одну полезную характеристику: она сообщает, находится ли точка выше или ниже линии. например если 𝐿 — прямая, имеющая следующий общий вид 𝑎1𝑥+𝑏1𝑦+𝑐1=0 и 𝑝=(𝑥1,𝑦1) — точка, то подставив 𝑝 в 𝐿, мы получим значение 𝑣=𝑎1𝑥1+𝑏1𝑦1+𝑐1, если 𝑣 ›0, значит, точка 𝑝 выше линии 𝐿, 𝑣‹0 означает, что 𝑝 ниже 𝐿, наконец, если 𝑣=0, значит, 𝑝 на 𝐿.
Теперь перерисуем предыдущую фигуру, по наитию , добавьте линию между двумя группами данных, пометьте точки в группе данных выше линии как (+), а точки в группе данных ниже линии как (- ). Линия (w_1 x_1+ w_2 x_2 + b = 0) может быть выражена в векторной записи как 𝑤𝑥+𝑏=0.
SVM-подход
Во введении мы упомянули, что SVM с жесткими границами находит четкую границу, не содержащую точек данных, и помещает разделительную линию в ее середину. Вопрос в том, как определить эту маржу? ; потому что может быть сформировано несколько полей и, следовательно, много кандидатов на границу классификации.
Подход SVM включает в себя поиск двух параллельных линий, каждая из которых проходит через хотя бы одну краевую точку каждой группы данных, и лучшей парой линий является та, которая имеет наибольшее расстояние между ними, это расстояние называется «поле», то разделительная линия находится посередине между этими двумя параллельными линиями и параллельна им. Этот подход называется подходом самой широкой улицы, а граничные точки каждой группы данных, через которые проходят параллельные линии, называются «векторами поддержки».
Как мы уже упоминали, SVM с жесткими полями не позволяет размещать точки внутри полей. Это означает, что для каждой точки данных 𝑋𝑖 не только 𝑤𝑥+𝑏›0, если 𝑦𝑖=1, или 𝑤𝑥+b‹0, если 𝑦𝑖=−1, но должен существовать порог «𝑎», такой, что 𝑤𝑥+𝑏≥a, если 𝑦𝑖=1, и 𝑤𝑥+𝑏≤-𝑎, если 𝑦𝑖=−1.
Естественно, 𝑎 выбирается равным 1, потому что для каждой точки данных (xi, yi) либо wx_i+b≥1, если yi=1, либо wx_i+b≤1, если yi=-1 > поэтому верхняя строка 𝑤𝑥+𝑏=1, а нижняя строка 𝑤𝑥+𝑏=−1.
Формулировка ширины поля
Если у нас есть формула, описывающая ширину полей, включая w, b,, мы можем максимизировать ее и вывести w, b, определяющие две параллельные линии, wx+ b=1, wx+b=-1, что каждый из них проходит через одну или несколько краевых точек соответствующего ему класса данных и имеет максимальную ширину между ними. Чтобы добраться до этого момента, мы должны рассмотреть следующее.
1- w перпендикулярно границе классификации wx+b=0. Это можно доказать, взяв две точки x0, x1 на wx+b=0,
⇒ wx0+b = 0, wx1+b = 0 ⇒ вычитанием: w(x0-x1) = 0 ⇒ w ⊥ (x0-x1)
потому что x0 , x1 — произвольные точки на wx+b=0 ⇒ w ⊥ wx+ б=0
Мы можем использовать тот факт, что w перпендикулярно wx+b=0, чтобы вычислить расстояние от линии 𝑤𝑥+𝑏=0 до линии 𝑤𝑥+𝑏=1 или линия 𝑤𝑥+𝑏=−1 как кратная единичному вектору 𝑤 (w/||w||), начиная с точки 𝑥∗ на линии 𝑤𝑥+𝑏=0. Расстояние от wx+b=0 до wx+b=1 или wx+b=-1 равно, потому что wx+b=0 находится посередине между ними. Давайте решим рассчитать расстояние от 𝑤𝑥+𝑏=0 до 𝑤𝑥+𝑏=1 и обозначим это расстояние как 𝑘. Следовательно, соответствующая точка 𝑥+ на линии 𝑤𝑥+𝑏=1, которая находится на другом конце перпендикулярной линии от wx*+b=0, может быть рассчитана как:
Мы рассчитали расстояние от wx+b=0 до wx+b=1, которое составляет половину расстояния поля.
На данный момент мы сформулировали меру маржи, и мы должны максимизировать ее, как указывает подход SVM.
Два приведенных выше ограничения можно объединить в одно следующим образом:
Мы решили минимизировать ½||𝑤||² для математического удобства.
Множители Лагранжа
Метод множителей Лагранжа используется для включения задачи минимизации вместе с ее ограничениями в одну функцию, называемую (функция стоимости).
Общая форма метода множителей Лагранжа такова:
minimize(f(w)) s.t g(w) ≤ 0, h (w) = 0, тогда:
В настройке SVM с жестким запасом нет ограничения равенства, поэтому:
Теперь существует одна функция стоимости J(w, b, α) для минимизации w.r.t (w, b, α). Но естьлемма из метода множителей Лагранжа, которую нам нужно пройти, она подразумевает следующее:
⇒ Следовательно, основная задача метода множителей Лагранжа может быть выражена следующим образом:
Двойственная проблема
Операции минимизации/максимизации могут выполняться в обратном порядке ( минимизировать J(w, b, α) по отношению к (w, b), затем максимизировать его по отношению к /em> (α))и получить одно и то же решение задачи, эта процедура поддерживается двумя теоремами: слабая двойственность и сильная двойственность теоремы. После перестановки операций (сначала минимизация, затем максимизация) проблема называется двойственной.
- теоремы слабой двойственности предполагают, что d* ≤ p*
- Теорема сильной двойственности подразумевает, что iff существует седловая точка 𝐽(𝑤,𝑏,𝛼) ⇔ d*= p* и эта седловая точка удовлетворяет условию Каруша Куна-Таккера KKT, состоящему из следующих членов.
Давайте разделим J w.r.t w и b
Теперь разверните функцию 𝐽 и подставьте члены, которые мы получили из производных выше.
Подставив w в J, мы получим
Матричное обозначение
⊙ – это элементарный продукт.
⇒
Теперь двойственная задача решается только для α
Решение этой задачи максимизации можно найти с помощью метода градиентного восхождения или превратить ее в задачу минимизации и решить ее с помощью квадратичного программирования.
Восстановление w
Найдя 𝛼, мы можем восстановить w с помощьюиспользования
Как правило, существует несколько ненулевых 𝛼, связанных с векторами поддержки (помните, что векторы поддержки — это точки на линиях wx+b=1 и wx +b=-1); это из условия ККТ где
⇒
Только точки на линиях wx-b=1 и wx+b=-1 дадут y_i(wx_i+b)=1, а из KKT выше, это единственный случай, когда𝛼_i может быть ненулевым. Следовательно, w будет восстановлено исключительно из опорных векторов и связанных с ними 𝛼.
В этой статье мы математически сформулировали базовый случай SVM (Hard Margin SVM). Формулировка сводилась к компактной функции стоимости, записанной в матричной записи, которую можно было использовать для вычисления значений 𝛼 и w программным путем.
Использованная литература:
1- Лекция MIT OCW по SVM, [Видео].
2- Онлайн-курс NPTEL, SVM: The Dual Formulation, [видео]
2- Вероятностное машинное обучение, введение. Кевин П. Мерфи [Книга].
