Вспомогательный векторный машинный анализ (SVM) - популярный инструмент машинного обучения для классификации и регрессии, впервые выявленный Владимиром Вапником и его коллегами в 1992 [5]. Регрессия SVM считается непараметрическим методом, поскольку опирается на функции ядра.
Statistics and Machine Learning Toolbox™ реализует линейную эпсилонно-нечувствительную SVM-регрессию, которая также известна как потеря L1. При регрессии (В-СВМ) набор обучающих данных включает в себя переменные предиктора и наблюдаемые значения ответа. Цель состоит в том, чтобы найти функцию f (x), которая отклоняется от yn на величину, не превышающую λ для каждой обучающей точки x, и в то же время является максимально плоской.
Предположим, что у нас есть набор обучающих данных, где xn - многомерный набор N наблюдений с наблюдаемыми значениями ответа yn.
Поиск линейной функции
=x′β+b,
и убедитесь, что он максимально плоский, найдите f (x) с минимальным значением нормы (β′β). Это сформулировано как выпуклая задача оптимизации для минимизации
=12β′β
при условии, что все остатки имеют значение, меньшее или, в форме уравнения:
.
Возможно, что такой функции f (x) не существует для удовлетворения этих ограничений для всех точек. Чтобы справиться с непостижимыми в противном случае ограничениями, введите для каждой точки переменные «провисание» («slack variables») («провисание»). Этот подход сходен с концепцией «мягкого запаса» в классификации SVM, поскольку переменные слабости позволяют существовать ошибкам регрессии вплоть до значения, равного
Включение переменных слабости приводит к целевой функции, известной также как основная формула [5]:
(
при условии:
−yn≤ε+ξn*∀n:ξn*≥0∀n:ξn≥0.
Константа C является ограничением поля, положительным числовым значением, которое управляет штрафом, наложенным на наблюдения, которые лежат за пределами эпсилонового запаса ("" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " Это значение определяет компромисс между плоскостностью f (x) и величиной, до которой допускаются отклонения, превышающие
Линейная функция нечувствительности к потерям не учитывает ошибки, которые находятся на расстоянии, находящемся в пределах, от наблюдаемого значения, рассматривая их как равные нулю. Потери измеряются на основе расстояния между наблюдаемым значением y и границей, на которой находится λ. Это формально описано
αotherwise
Описанная выше задача оптимизации является более простой в вычислительном отношении для решения в ее двойной формулировке Лагранжа. Решение двойной задачи обеспечивает нижнюю границу решения основной (минимизационной) задачи. Оптимальные значения первичной и двойной задач не обязательно должны быть равными, и разница называется «разрывом двойственности». Но когда задача является выпуклой и удовлетворяет условию квалификации ограничения, значение оптимального решения основной задачи задается решением двойной задачи.
Чтобы получить двойственную формулу, постройте функцию Лагранжа из основной функции, введя неотрицательные множители αn и α * n для каждого наблюдения xn. Это приводит к двойной формуле, где мы минимизируем
+∑i=1Nyi (αi * − αi)
с учетом ограничений
=0∀n:0≤αn≤C∀n:0≤αn*≤C.
Параметр β может быть полностью описан как линейная комбинация тренировочных наблюдений с помощью уравнения
xn.
Функция, используемая для прогнозирования новых значений, зависит только от векторов поддержки:
| xn′x) + b. | (1) |
Условия комплементарности Karush-Kuhn-Tucker (KKT) являются ограничениями оптимизации, необходимыми для получения оптимальных решений. Для линейной регрессии SVM эти условия
(C − αn *) = 0.
Эти условия указывают на то, что все наблюдения строго внутри эпсилонной трубки имеют множители Лагранжа αn = 0 и αn * = 0. Если αn или αn * не равно нулю, то соответствующее наблюдение называется вектором поддержки .
Свойство Alpha обученной модели SVM хранит разницу между двумя умножителями Лагранжа векторов поддержки, αn - αn *. Свойства SupportVectors и Bidance хранят xn и b соответственно.
Некоторые проблемы регрессии не могут быть адекватно описаны с помощью линейной модели. В таком случае двойственная формулировка Лагранжа позволяет распространить описанную выше методику на нелинейные функции.
Получить модель нелинейной регрессии SVM путём замены скалярного произведения x1′x2 на нелинейную функцию ядра G (x1, x2) = < start( x1), start( x2) >, где start( x) - преобразование, отображающее x в высокомерное пространство. Statistics and Machine Learning Toolbox предоставляет следующие встроенные положительные полуопределённые функции ядра.
| Имя ядра | Функция ядра |
|---|---|
| Линейный (скалярное произведение) | =xj′xk |
| Гауссовский | −‖xj−xk‖2) |
| Полиномиал | 1+xj′xk) q, где q находится в множестве {2,3,...}. |
Матрица Грама представляет собой матрицу n-на-n, которая содержит элементы gi, j = G (xi, xj). Каждый элемент gi, j равен внутреннему произведению предикторов, преобразованному с помощью Тем не менее, нам не нужно знать start, потому что мы можем использовать функцию ядра для генерации матрицы Gram напрямую. Используя этот метод, нелинейный SVM находит оптимальную функцию f (x) в преобразованном предикторном пространстве.
Двойственная формула для нелинейной регрессии SVM заменяет внутреннее произведение предикторов (xi′xj) соответствующим элементом матрицы Грама (gi, j).
Нелинейная регрессия SVM находит коэффициенты, которые минимизируют
*) −∑i=1Nyi (αi − αi *)
подлежит
=0∀n:0≤αn≤C∀n:0≤αn*≤C.
Функция, используемая для прогнозирования новых значений, равна
| xn, x) + b. | (2) |
Условия комплементарности KKT:
C−αn*) =0.
Задача минимизации может быть выражена в стандартной квадратичной форме программирования и решена с использованием общих методов квадратичного программирования. Однако использование алгоритмов квадратичного программирования может быть дорогостоящим в вычислительном отношении, тем более что матрица Грама может быть слишком большой для сохранения в памяти. Использование метода разложения может ускорить вычисления и избежать нехватки памяти.
Методы декомпозиции (также называемые методами порции и рабочего набора) разделяют все наблюдения на два непересекающихся набора: рабочий набор и оставшийся набор. Метод разложения изменяет только элементы в рабочем наборе в каждой итерации. Поэтому в каждой итерации необходимы только некоторые столбцы матрицы Gram, что уменьшает объем хранения, необходимый для каждой итерации.
Последовательная минимальная оптимизация (SMO) является наиболее популярным подходом для решения задач SVM [4]. SMO выполняет ряд двухточечных оптимизаций. В каждой итерации выбирается рабочий набор из двух точек на основе правила выбора, использующего информацию второго порядка. Тогда множители Лагранжа для этого рабочего набора решаются аналитически с использованием подхода, описанного в [2] и [1].
При регрессии SVM вектор градиента, для активного набора, обновляется после каждой итерации. Разложенное уравнение для вектора градиента
yn, n> N.
Итеративный алгоритм одиночных данных (ISDA) обновляет один множитель Лагранжа с каждой итерацией [3]. ISDA часто проводится без члена смещения b путем добавления небольшой положительной константы a к функции ядра. Удаление b уменьшает ограничение суммы
*) = 0
в двойственном уравнении. Это позволяет обновлять один множитель Лагранжа в каждой итерации, что упрощает удаление отклонений по сравнению с SMO. ISDA выбирает худшего нарушителя KKT среди всех значений αn и αn * в качестве обновляемого рабочего набора.
Каждый из этих алгоритмов решателя итеративно вычисляется до тех пор, пока не будет соблюден заданный критерий сходимости. Существует несколько вариантов критериев сходимости:
Пробел технико-экономического обоснования - пробел технико-экономического обоснования выражается как
(β) + 1,
где J (β) - основная цель, а L (α) - двойственная цель. После каждой итерации программа оценивает пробел выполнимости. Если промежуток выполнимости меньше значения, указанного вGapToleranceзатем алгоритм удовлетворяет критерию сходимости и программное обеспечение возвращает решение.
Разность градиентов - после каждой итерации программа вычисляет вектор градиента, . Если разность значений вектора градиента для текущей итерации и предыдущей итерации меньше значения, указанного в DeltaGradientToleranceзатем алгоритм удовлетворяет критерию сходимости и программное обеспечение возвращает решение.
Наибольшее нарушение KKT - после каждой итерации программное обеспечение оценивает нарушение KKT для всех значений αn и αn *. Если наибольшее нарушение меньше значения, указанного KKTToleranceзатем алгоритм удовлетворяет критерию сходимости и программное обеспечение возвращает решение.
[1] Fan, R.E., P.H. Chen и C.J. Лин. «Исследование методов разложения SMO-типа для поддерживающих векторных машин». Сделки IEEE по нейронным сетям, том 17: 893-908, 2006.
[2] Фан, Р.Е., П.Х. Чен и К.Ж. Лин. «Выбор рабочего набора с использованием информации второго порядка для обучающих вспомогательных векторных машин». Журнал исследований машинного обучения, т. 6:1871 - 1918, 2005.
[3] Хуан, Т. М., В. Кекман и И. Коприва. Алгоритмы на основе ядра для интеллектуального анализа огромных наборов данных: контролируемое, полупроверяемое и неконтролируемое обучение. Спрингер, Нью-Йорк, 2006.
[4] Platt, J. Последовательная минимальная оптимизация: быстрый алгоритм для обучения векторных машин поддержки. Технический отчет MSR-TR-98-14, 1999 год.
[5] Вапник, В. Природа теории статистического обучения. Спрингер, Нью-Йорк, 1995 год.
fitrsvm | predict | RegressionSVM | resubPredict