Предположим, у нас есть линейно-разделимый обучающий набор данных с помеченными точками данных, принадлежащими одному из двух классов: Красный и Синий. Простой классификатор можно построить, найдя гиперплоскость, которая разделяет набор данных на две стороны со всеми экземплярами класса Красный на одной стороне и всеми экземплярами класса Синий на другой. На этой идее основан линейный SVM-классификатор с жесткими границами с одним важным дополнением: поле вокруг плоскости должно быть как можно больше. Это то, что мы будем называть исходной проблемой (OP),которая преследует три цели:
- Найдите гиперплоскость
- который разбивает набор обучающих данных так, чтобы точки данных, принадлежащие разным классам, находились по разные стороны гиперплоскости.
- «Запас» вокруг гиперплоскости должен быть как можно больше.
После быстрого поиска в Интернете вы обнаружите, что задача нахождения такой плоскости эквивалентна решению математической формулировки (МФ):
- Найдите w и b, минимизирующие w• w,
- При соблюдении следующих условий: y • w +b ≥ 1, если y принадлежит к классу «Красный»; y • w +b ≤ -1, если y принадлежит к классу «Синий»,
где «•» обозначает внутренний продукт.
Почему для решения исходной задачи достаточно найти решение МФ? Вы найдете много объяснений (или фрагментов объяснений). В этой статье я поделюсь своим ходом мыслей для ответа на этот вопрос.Цель состоит в том, чтобы показать, что каждая из трех целей в OP может быть достигнута путем поиска решения MF.
Задача №1 — найти гиперплан…
Гиперплоскость определяется как бесконечный набор векторов x, удовлетворяющих уравнению:
w • x + b = 0.
Следовательно, находя значения w и b, которые решают МФ, мы неявно находим плоскость и достигаем цели №1 в ОП.
Задача № 2 — Это разбивает набор обучающих данных…
Приводит ли решение MF к плоскости, которая разделяет набор данных, так что точки данных, принадлежащие разным классам, находятся на разных сторонах? Что вообще означает, что два вектора находятся по разные стороны плоскости?
Рассмотрим плоскость из предыдущего раздела (w • x + b = 0, где w и b — решения МФ). Предположим, у нас есть вектор x на плоскости и два вектора y и z, которые не лежат на плоскости. самолет. y и z находятся на противоположных сторонах тогда и только тогда, когда скалярные проекции y — x и z — xна w, вектор нормали плоскости, имеют противоположные знаки.
Если вы взглянете на определение скалярной проекции, вы сможете убедиться, что знак проекции вектора v на w равен знаку знак v• w.
Другими словами, простой способ проверить, находятся ли y и z на противоположных сторонах гиперплоскости (w• x + b = 0) — это сравнение знаков (y — x) • w и (y — x) • w(противоположные знаки означают противоположные стороны).
Теперь, когда мы знаем, что означает, что два вектора находятся на противоположных сторонах плоскости, легко понять, почему значения w и b, которые решают МФ, приводят к плоскости, которая разбивает набор данных на желаемый способ. В частности, если y и z принадлежат к разным классам, скажем, y помечен как «Красный», а z помечен «Синий, и если w и b являются решениями МФ, то выполняются следующие ограничения:
- y • w + b ≥ 1
- z • w + b ≤ -1
Кроме того, если мы допустим, что x является некоторым вектором на плоскости, мы можем вычесть x • w+b (что равно 0) из предыдущие уравнения без ущерба для их достоверности:
- y • w + b — (x • w + b) = y • w + b ≥ 1
- z • w + b — (x • w + b) = z • w + b ≤ -1
После небольшого упрощения видим, что:
- (y — x) • w ≥ 1
- (z — x) • w ≤ -1
Другими словами, если w и b являются решениями МФ и если y и z принадлежат разным классам, то y strong> и z должны находиться на противоположных сторонах гиперплоскости. Таким образом, решения MF достаточно для обеспечения достижения цели № 2 OP, поскольку x • w+b = 0 разбивает набор данных желаемым образом.
Задача № 3 — «Маржа» должна быть большой…
Конечная цель в OP состояла в том, чтобы убедиться, что поле вокруг гиперплоскости было как можно больше. Гарантируется ли это в решении МФ? Прежде чем мы сможем ответить на этот вопрос, нам нужно уточнить: что такое поле вокруг гиперплоскости?
Существует несколько способов определить запас, но для обучения SVM достаточно определить его как расстояние от плоскости до ближайшей точки данных (независимо от класса точки данных). Найдя плоскость, которая максимизирует это расстояние, мы пытаемся оптимизировать ошибку обобщения нашего классификатора.
Максимизирует ли решение MF расстояние от плоскости до ближайшей точки данных? Давайте посмотрим. Предположим, что w и b — решения МФ, x — точка на плоскости, а y — одна из наших обучающих точек данных. Тогда расстояние от точки y до плоскости, определяемой x • w+ b = 0, есть не что иное, как абсолютное значение скаляра проекция y — x на w:
Следовательно, расстояние y от плоскости равно:
|(y — x) • w| / ||w||.
Добавляя и вычитая b из левой части предыдущего уравнения, мы видим, что расстояние от y до плоскости равно:
|(y — x) • w + b — b| / ||w|| = |y • w + b — (x • w + b)| / ||w||.
Используя тот факт, что x является точкой на плоскости, так что x • w +b = 0, получаем:
расстояние от y до плоскости = |y • w +b| / ||в||.
Благодаря ограничениям МФ мы знаем, что |y • w +b| ≥ 1, что означает, что расстояние от y до плоскости не менее 1 / ||w||, независимо от y (или метка его класса). Минимизируя ||w|| мы увеличиваем эту нижнюю границу. Аналогично, минимизация ||w|| максимизирует поле вокруг плоскости.
В заключение, любое решение MF обеспечит выполнение Цели № 3 в OP.
Q.E.D.
В заключение, решение математической формулировки гарантирует, что мы найдем значения w и b, которые соответствуют всем целям в исходной формулировке задачи.
Если вы нашли эту статью полезной, подпишитесь на меня, чтобы быть в курсе моего контента!
