Понимание регрессии машины вектора поддержки

Математическая формулировка регрессии SVM

Обзор

Анализ машины вектора поддержки (SVM) является популярным инструментом машинного обучения для классификации и регрессии, сначала идентифицированной Владимиром Вапником и его коллегами в 1 992 [5]. Регрессия SVM рассматривается непараметрическим методом, потому что она полагается на функции ядра.

Statistics and Machine Learning Toolbox™ реализует линейный нечувствительный к эпсилону SVM (ε-SVM) регрессия, которая также известна как L 1 потеря. В ε-SVM регрессия, набор данных тренировки включает переменные прогноза и наблюдаемые значения ответа. Цель состоит в том, чтобы найти функциональный f (x), который отклоняется от _yn значением, не больше, чем ε для каждой учебной точки x, и в то же время является максимально плоским.

Линейная регрессия SVM: основная формула

Предположим, что у нас есть набор данных тренировки, где _xn является многомерным набором наблюдений N с наблюдаемыми значениями ответа _yn.

Найти линейную функцию

$f (x) = x' β + b,$

и гарантируйте, что это максимально плоско, найдите f (x) с минимальным значением нормы (β ′β). Это формулируется как выпуклая задача оптимизации, чтобы минимизировать

$J (β) = \frac{}{12} β' β$

подвергните всем невязкам, имеющим значение меньше, чем ε; или, в форме уравнения:

$\forall n : | y_{n} - (x_{n}' β + b) | \leq ε .$

Возможно, что никакой такой функциональный f (x) не существует, чтобы удовлетворить эти ограничения для всех точек. Чтобы иметь дело с в противном случае неосуществимыми ограничениями, введите слабые переменные _ξn и ξ ^*_n для каждой точки. Этот подход подобен “мягкой граничной” концепции в классификации SVM, потому что слабые переменные позволяют ошибкам регрессии существовать до значения _ξn и ξ ^*_n, и все же удовлетворить необходимые условия.

Включая слабые переменные приводит к целевой функции, также известной как основную формулу [5]:

$J (β) = \frac{}{12} β' β + C \sum_{n = 1}^{N} (ξ_{n} + ξ_{n}^{*}),$

подвергающийся:

$\begin{array}{l} \forall n : y_{n} - (x_{n}' β + b) \leq ε + ξ_{n} \\ \forall n : (x_{n}' β + b) - y_{n} \leq ε + ξ_{n}^{*} \\ \forall n : ξ_{n}^{*} \geq 0 \\ \forall n : ξ_{n} \geq 0 . \end{array}$

Постоянный C является ограничением поля, положительное числовое значение, которое управляет штрафом, наложенным на наблюдения, которые лежат вне поля эпсилона (ε) и помогают предотвратить сверхподходящий (регуляризация). Это значение определяет компромисс между плоскостью f (x) и суммой, до которой допускаются отклонения, больше, чем ε.

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

$L_{ε} = {\begin{array}{l} 0 & если | y - f (x) | \leq ε \\ | y - f (x) | - ε & в противном случае \end{array}$

Линейная регрессия SVM: двойная формула

Задача оптимизации, ранее описанная, в вычислительном отношении более проста решить в ее Лагранжевой двойной формулировке. Решение двойной проблемы предоставляет нижнюю границу решению основного (минимизация) проблема. Оптимальные значения основных и двойных проблем не должны быть равными, и различие называется “разрывом дуальности”. Но когда проблема выпукла и удовлетворяет ограничительное условие проверки, значение оптимального решения основной проблемы дано решением двойной проблемы.

Чтобы получить двойную формулу, создайте лагранжевую функцию из основной функции путем представления неотрицательных множителей _αn и α ^*_n для каждого наблюдения _xn. Это приводит к двойной формуле, где мы минимизируем

$L (α) = \frac{}{12} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (α_{i} - α_{i}^{*}) (α_{j} - α_{j}^{*}) x_{i}' x_{j} + ε \sum_{i = 1}^{N} (α_{i} + α_{i}^{*}) + \sum_{i = 1}^{N} y_{i} (α_{i}^{*} - α_{i})$

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

$\begin{array}{l} \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) = 0 \\ \forall n : 0 \leq α_{n} \leq C \\ \forall n : 0 \leq α_{n}^{*} \leq C . \end{array}$

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

$β = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) x_{n} .$

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

f (x) = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) (x_{n}' x) + b .

(1)

Условия взаимозависимости Karush-Kuhn-Tucker (KKT) являются ограничениями оптимизации, требуемыми получить оптимальные решения. Для линейной регрессии SVM эти условия

$\begin{array}{l} \forall n : α_{n} (ε + ξ_{n} - y_{n} + x_{n}' β + b) = 0 \\ \forall n : α_{n}^{*} (ε + ξ_{n}^{*} + y_{n} - x_{n}' β - b) = 0 \\ \forall n : ξ_{n} (C - α_{n}) = 0 \\ \forall n : ξ_{n}^{*} (C - α_{n}^{*}) = 0 . \end{array}$

Эти условия указывают, что все наблюдения строго в трубе эпсилона имеют множители Лагранжа _αn = 0 и _αn* = 0. Если или _αn или _αn* не являются нулем, то соответствующее наблюдение называется вектором поддержки.

Свойство Alpha обученной модели SVM хранит различие между двумя множителями Лагранжа векторов поддержки, _αn – _αn^*. Свойства SupportVectors и Bias хранят _xn и b, соответственно.

Нелинейная регрессия SVM: основная формула

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

Получите нелинейную модель регрессии SVM, заменив скалярное произведение x _1′x2 с нелинейной функцией ядра G (x ₁, x ₂) = <φ (x ₁), φ (x ₂)>, где φ (x) является преобразованием, которое сопоставляет x с высоким мерным пространством. Statistics and Machine Learning Toolbox обеспечивает следующие встроенные полуопределенные функции ядра.

Имя ядра	Функция ядра
Линейный (скалярное произведение)	$G (x_{j}, x_{k}) = x_{j}' x_{k}$
Гауссов	$G (x_{j}, x_{k}) = \exp (- {‖ x_{j} - x_{k} ‖}^{2})$
Полином	$G (x_{j}, x_{k}) = {(1 + x_{j}' x_{k})}^{q}$ , где q находится в наборе {2,3...}.

Матрицей Грамма является n-by-n матрица, которая содержит элементы _gi,j = G (_xi, _xj). Каждый элемент _gi,j равен скалярному произведению предикторов, как преобразовано φ. Однако мы не должны знать φ, потому что мы можем использовать функцию ядра, чтобы сгенерировать матрицу Грамма непосредственно. Используя этот метод, нелинейный SVM находит оптимальный функциональный f (x) на преобразованном пробеле предиктора.

Нелинейная регрессия SVM: двойная формула

Двойная формула для нелинейной регрессии SVM заменяет скалярное произведение предикторов (_xi ′_xj) с соответствующим элементом матрицы Грамма (_gi,j).

Нелинейная регрессия SVM находит коэффициенты, которые минимизируют

$L (α) = \frac{}{12} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (α_{i} - α_{i}^{*}) (α_{j} - α_{j}^{*}) G (x_{i}, x_{j}) + ε \sum_{i = 1}^{N} (α_{i} + α_{i}^{*}) - \sum_{i = 1}^{N} y_{i} (α_{i} - α_{i}^{*})$

подвергающийся

$\begin{array}{l} \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) = 0 \\ \forall n : 0 \leq α_{n} \leq C \\ \forall n : 0 \leq α_{n}^{*} \leq C . \end{array}$

Функция, используемая, чтобы предсказать новые значения, равна

f (x) = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) G (x_{n}, x) + b .

(2)

Условия взаимозависимости KKT

$\begin{array}{l} \forall n : α_{n} (ε + ξ_{n} - y_{n} + f (x_{n})) = 0 \\ \forall n : α_{n}^{*} (ε + ξ_{n}^{*} + y_{n} - f (x_{n})) = 0 \\ \forall n : ξ_{n} (C - α_{n}) = 0 \\ \forall n : ξ_{n}^{*} (C - α_{n}^{*}) = 0 . \end{array}$

Решение задачи оптимизации регрессии SVM

Алгоритмы решателя

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

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

Последовательная минимальная оптимизация (SMO) является самым популярным подходом для решения проблем SVM [4]. SMO выполняет ряд оптимизации 2D точки. В каждой итерации рабочий набор двух точек выбран на основе правила выбора, которое использует информацию второго порядка. Затем множители Лагранжа для этого рабочего набора решены аналитически с помощью подхода, описанного в [2] и [1].

В регрессии SVM, векторе градиента $\nabla L$ поскольку активный набор обновляется после каждой итерации. Анализируемое уравнение для вектора градиента

${(\nabla L)}_{n} = {\begin{matrix} \sum_{i = 1}^{N} (α_{i} - α_{i}^{*}) G (x_{i}, x_{n}) + ε - y_{n}, n \leq N \\ - \sum_{i = 1}^{N} (α_{i} - α_{i}^{*}) G (x_{i}, x_{n}) + ε + y_{n}, n > N \end{matrix} .$

Итеративный один алгоритм данных (ISDA) обновляет один множитель Лагранжа с каждой итерацией [3]. ISDA часто проводится без термина смещения b путем добавления маленького положительного постоянного a в функцию ядра. Отбрасывание b пропускает ограничение суммы

$\sum_{n = 1}^{N} (α_{i} - α^{*}) = 0$

в двойном уравнении. Это позволяет нам обновлять один множитель Лагранжа в каждой итерации, которая облегчает, чем SMO удалять выбросы. ISDA выбирает худшего нарушителя KKT среди всего _n α и α _n^* значения как рабочий набор, который будет обновлен.

Критерии сходимости

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

Разрыв выполнимости — разрыв выполнимости выражается как
$Δ = \frac{J (β) + L (α)}{J (β) + 1},$
где J (β) является основной целью, и L (α) является двойной целью. После каждой итерации программное обеспечение оценивает разрыв выполнимости. Если разрыв выполнимости является меньше, чем значение, заданное GapTolerance, то алгоритм соответствовал критерию сходимости, и программное обеспечение возвращает решение.
Различие в градиенте — После каждой итерации, программное обеспечение оценивает вектор градиента, $\nabla L$ . Если различием в значениях вектора градиента для текущей итерации и предыдущей итерации являются меньше, чем значение, заданное DeltaGradientTolerance, то алгоритм соответствовал критерию сходимости, и программное обеспечение возвращает решение.
Самое большое нарушение KKT — После каждой итерации, программное обеспечение оценивает нарушение KKT для всего _n α и α _n^* значения. Если самое большое нарушение является меньше, чем значение, заданное KKTTolerance, то алгоритм соответствовал критерию сходимости, и программное обеспечение возвращает решение.

Ссылки

[1] Вентилятор, R.E., П.Х. Чен и К.Дж. Лин. Исследование методов разложения SMO-типа для машин вектора поддержки. Транзакции IEEE на нейронных сетях, 17:893–908, 2006.

[2] Вентилятор, R.E., П.Х. Чен и К.Дж. Лин. Выбор Рабочего набора Используя информацию о Втором порядке для Учебных Машин Вектора Поддержки. Журнал Исследования машинного обучения, 6:1871–1918, 2005.

[3] Хуан, T.M., В. Кекмен и я. Kopriva. Основанные на ядре алгоритмы для горной промышленности огромных наборов данных: контролируемое, полуконтролируемое, и безнадзорное изучение. Спрингер, Нью-Йорк, 2006.

[4] Платт, J. Последовательная минимальная оптимизация: алгоритм FAST для учебных машин вектора поддержки. Технический отчет MSR TR-98-14, 1999.

[5] Vapnik, V. Природа статистической теории обучения. Спрингер, Нью-Йорк, 1995.

Документация