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

Математическая формулировка регрессии 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{1}{2} β' β$

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

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

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

Включая слабые переменные приводит к целевой функции, также известной как основную формулу [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) и суммой, до которой допускаются отклонения, больше, чем ε.

Линейная ε-insensitive функция потерь игнорирует ошибки, которые являются на расстоянии ε наблюдаемой величины путем обработки их как равных нулю. Потеря измеряется на основе расстояния между наблюдаемой величиной 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)

Условиями взаимозависимости 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{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

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

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

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

Последовательная минимальная оптимизация (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.

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