Понимание Машины опорных векторов регрессия

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

Обзор

Машина опорных векторов (SVM) - популярный инструмент машинного обучения для классификации и регрессии, впервые выявленный Владимиром Вапником и его коллегами по 1992 [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{1}{2} β' β$

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

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

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

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

$J (β) = \frac{1}{2} β' β + 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) и величиной, до которой допускаются отклонения, большие ε.

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

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

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

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

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

$L (α) = \frac{1}{2} \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)

Условия комплементарности Каруша-Куна-Такера (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 ₋ x 2 на нелинейную функцию ядра G ₍x 1, x 2₎ = < _φ (x 1), φ (x 2) >, где φ (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 _{элемента} равен скалярному произведению предикторов, преобразованному φ. Однако нам не нужно знать φ, потому что мы можем использовать функцию ядра, чтобы сгенерировать матрицу Gram непосредственно. Используя этот метод, нелинейный SVM находит оптимальную функцию f (x) в преобразованном пространстве предикторов.

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

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

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

$L (α) = \frac{1}{2} \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

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

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

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

Последовательная минимальная оптимизация (SMO) является наиболее популярным подходом к решению задач SVM [4]. SMO выполняет ряд двухточечных оптимизаций. В каждой итерации рабочий набор из двух точек выбирается на основе правила выбора, которое использует информацию второго порядка. Затем множители Лагранжа для этого рабочего набора решаются аналитически с помощью подхода, описанного в [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., P.H. Chen и C.J. Лин. «Исследование методов разложения типа SMO для машин опорных векторов». Транзакции IEEE по нейронным сетям, том 17: 893-908, 2006.

[2] Вентилятор, R.E., P.H. Chen и C.J. Lin. «Работа набора с использованием информации второго порядка для обучающих машин опорных векторов». Журнал исследований машинного обучения, том 6:1871 - 1918, 2005.

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

[4] Platt, J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Технический доклад MSR-TR-98-14, 1999.

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

См. также

fitrsvm | predict | RegressionSVM | resubPredict

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