Граница решения
КОГДА ЗАСТРЕМИЛИСЬ, ПЕРЕКЛЮЧИТЕ К ДРУГОЙ ПЕРСПЕКТИВЕ
Машина опорных векторов
В начале 90-х Владимир Вапник представил идею SVM (машина опорных векторов).
- Если мы хотим различать сэмплы «+» и «-», как мы должны их разделить?
- Если вы проведете линию и разделите ее, какой это должна быть линия?
Самый простой и интуитивно понятный ответ - это, вероятно, следующая линия (пунктирная линия) с некоторыми линиями, которые используют наибольшее расстояние между образцами «+» и «-».
Самый интуитивно понятный способ - это указать самую широкую улицу, которая отделяет положительные образцы от отрицательных. Поэтому для разделения наиболее подходящего способа нужно найти самую широкую улицу (улица максимально широкая).
SVM - это процесс решения вышеуказанного вопроса. Я расскажу, как создавать и решать проблемы с этой точки зрения.
1. Правило принятия решения
Давайте подумаем над «каким должно быть правило принятия решения, чтобы определить границу принятия решения?»
- w⃗ перпендикулярно средней линии улицы.
- u⃗ - образец неизвестного происхождения, который находится на левой или правой стороне улицы.
Нас интересует, принадлежит ли неизвестный образец u⃗ правой или левой стороне улицы.
Один из способов сделать это - убедиться, что значение больше константы c после того, как мы использовали внутреннее произведение w⃗ и u⃗. . В диапазоне, не выходящем за рамки общности, это можно выразить следующим образом:
Логика очень простая. Легко понять, что внутренний продукт должен проецировать u⃗ на w⃗ на приведенном выше графике, и легко подумать, что длина велика и идет до вправо, если он выходит за границу, и влево, если он короче.
Таким образом, приведенное выше уравнение (1) становится нашим правилом принятия решения. Это также первый инструмент, который нам нужен для понимания SVM, но он все еще имеет множество недостатков. Тем не менее, мы понятия не имеем, что w⃗ должно быть установлено в этой формуле или какое b должно быть установлено. Но мы можем знать только то, что w⃗ ортогонален средней линии улицы, которую мы хотим.
К сожалению, такую w⃗ можно было нарисовать самыми разными способами, поэтому в моем суждении пока нет ограничений. Итак, что мы собираемся сделать, так это добавить несколько ограничений в формулу, чтобы мы могли вычислить w⃗ и b.
2. Обобщение
Разработайте и добавьте дополнительные ограничения
Допустим, x₊ - положительный (+) образец, а x₋ - отрицательный (-) образец.
Работа с двумя выражениями раздражает. Итак, мы создадим здесь переменную и обобщим ее до одного выражения.
Теперь давайте умножим это yᵢ на формулу выше.
Обобщение
Другими словами, результат формулы для двух образцов, «+» и «-», которые будут на границе (серые линии; желоба).
3. Ширина
Что мы хотим сделать, так это установить линию и максимально увеличить расстояние между результирующими образцами «+» и «-». Затем нам нужно подумать о том, как создать «улицу».
Какая ширина улицы?
Если бы у меня был единичный вектор в этом направлении, то я мог бы просто расставить точки вместе, это была бы ширина.
Уравнение (4) выше - это третий инструмент, который нам нужен для понимания SVM.
Методы оптимизации
Цель увеличения ШИРИНЫ можно описать следующим образом:
- Квадратичное программирование
- Метод множителя Лагранжа (1802 г.)
Мы можем максимизировать или минимизировать, больше не думая об ограничениях. В приведенном ниже уравнении α - множитель Лагранжа.
Перспектива дифференциации для w⃗:
Установить на ноль:
Он говорит нам, что w⃗ - это линейная сумма выборок (всех или некоторых). w⃗ будет линейным для некоторых из этих векторов (в наборе примеров, потому что для некоторых α будет 0)
Перспектива дифференциации на b:
Установить на ноль:
Теперь, используя полученные здесь уравнения, мы подставим уравнение (5) для α и упростим задачу.
поскольку ∑ᵢαᵢyᵢ равен нулю:
свяжите выражение:
Итак, теперь с проблемой максимизации для α все покончено. Решив эту проблему и получив α, w⃗ можно получить, используя уравнение (6), а затем b также можно получить с помощью уравнения (3). Уравнение (3) означает, что значение α не равно нулю, что означает, что соответствующий x⃗ является образцом, определяющим границу. линия. В SVM эти образцы называются «опорным вектором».
Я хочу найти, от чего зависит это максимальное значение в отношении этих векторов выборки. Я обнаружил, что оптимизация зависит только от скалярного произведения пар выборок. Итак, теперь мое правило принятия решения с этим выражением для w⃗ будет w⃗ подключено.
Правило принятия решения зависит только от скалярного произведения этих выборок.
Наконец, уравнение L имеет очень хорошие свойства при расширении. Для α первый член является линейным, а второй - квадратичным, поэтому для решения α можно использовать любой стандартный алгоритм с использованием техники квадратичного программирования.
Другими словами, в отличие от нейронных сетей, этой SVM вообще не нужно беспокоиться о попадании в локальные минимумы. Таким образом, решение, полученное с помощью SVM, «теоретически гарантированно является лучшим решением».
Следовательно, границы решения, определяемые опорными векторами, являются наиболее оптимальными границами, и когда новая выборка поступает только с данными, которые у нас есть, мы нашли правило принятия решения, которое может лучше всего обобщить.
