Дань Истинному Богу - SVM

Резюме

Для машины опорных векторов (SVM) вы остаетесь на уровне вызова связанных пакетов алгоритмов? Вас обескураживают скучные формулы каждый раз, когда вы хотите углубить свое понимание SVM? В этой статье в качестве организационной структуры статьи будет использоваться временная шкала истории разработки SVM, чтобы вы могли понять основные принципы SVM, неотъемлемые требования разработки и значение ее формулы.

0 Предисловие

SVM используется с 1964 года.VapnikПоскольку он был предложен и др., Он стал одним из важных классификаторов базовой линии. Первоначально SVM был предложен как линейный классификатор, и его характеристики алгоритма максимальной маржи (Max Margin) $^{[1]}$ Это делает SVM очень хорошей способностью к обобщению, но, поскольку данные в реальном мире не имеют таких строгих правил (есть много шумов), исследователи предложили Мягкую маржу для решения нестрогой линейности. общий). Несмотря на то, что мягкий интервал может в определенной степени смягчить нелинейную проблему, он по-прежнему является линейно разделимым в окончательном анализе.Применение функции ядра позволяет распространить мощную классификационную способность SVM на область нелинейных данных. На данный момент SVM с навыками ядра действительно стала общей технологией машинного обучения.

Чтобы читатели имели полное представление об основных принципах SVM, в этой статье в качестве организационной структуры статьи используются важные узлы исторического процесса разработки SVM.В первом разделе будет представлена линейная SVM и способы поиска ее оптимального решения; во втором разделе будет решаться проблема мягкого интервала Нестрого линейные задачи Раздел 3 описывает, как метод ядра SVM адаптируется к нелинейно разделимым данным Раздел 4 суммирует полный текст. В следующем процессе разработки основных принципов SVM вывод математических формул должен сопровождаться (потому что за SVM лежит очень красивая математическая теория), но постарайтесь сделать его простым для понимания и гарантировать, что математические части вывода независимы для удобство для читателей, чтобы обращаться к ним в будущем.

Кроме того, шедевр машинного обучения г-на Чжоу Чжихуа $^{[3]}$ (Далее: Арбузная книга) Объяснение СВМ очень хорошее. К сожалению, арбузная книга ограничена в пространстве и не может объяснить детали. Мое эссе пытается максимально восполнить этот недостаток. Поэтому все формулы в этой статье сравниваются с арбузной книгой. Автор не знает таланта и знаний, и я хотел бы попросить читателей быть элегантными, если в тексте есть неуместные вещи.

1 Линейный классификатор SVM

1.1 Основные принципы

Классификация — важная задача машинного обучения, и SVM изначально был предложен для решения задач линейной классификации. Рассмотрим простейшую задачу классификации, показанную на рис. 1.1, только с двумя репрезентативными точками данных. (0, 0) (1, 1) Соответствующие отрицательным и положительным классам соответственно $^{[注1]}$ . Что должен сделать классификатор, так это найти плоскость решения (называемую гиперплоскостью в SVM: гиперплоскость), а затем эффективно различать два типа.Разные классификаторы будут получать разные плоскости решения, и ошибка обобщения заключается в том, чтобы решить, какая плоскость решения лучше. количественный показатель. Очевидно, что цель SVM состоит в том, чтобы максимизировать ошибку обобщения, а идея Вапника состоит в том, чтобы найти плоскость принятия решений, которая может обеспечить наибольшее пространство отказоустойчивости, а это самое большое пространство отказоустойчивости состоит в том, чтобы максимизировать интервал $^{[1]}$ . SVM должен решить следующие две проблемы:

Как определить расстояние от точки выборки до гиперплоскости?
Как правильно классифицировать образцы по расстоянию?

Рисунок 1.1: Случай простой бинарной классификации

Вопрос 1: Как определить расстояние от точки выборки до гиперплоскости?

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

r_i = \frac{|w^Tx_i+b|}{||w||} , \qquad \qquad i=1,2, \cdots, m \quad (1.1)

в w^Tx+b является гиперплоскостью, которая, конечно же, является линией в двумерном пространстве признаков, и- нормальная векторная матрица гиперплоскости,- расстояние гиперплоскости от начала координат. очевидно все x_i до гиперплоскости можно найти по формуле (1.1).

Вопрос 2: Как правильно классифицировать выборки по расстоянию?

Распространенным методом является объединение классов в соответствии с определенным порогом, т. е.

f(x)=\left\{ \begin{aligned} & w^Tx_i+b \geq +1, & y_i=+1\\ & w^Tx_i+b \leq -1, & y_i=-1 \end{aligned} \right. \qquad (1.2)

для точки выборки x_i , если его расстояние до этой гиперплоскости больше или равно 1, он классифицируется как положительный класс, а обратное верно для отрицательного класса. Что касается того, почему в формуле (1.2) установлен порог равный 1, то одна из моих незрелых идей состоит в том, что блок номер 1 может обеспечить хорошее удобство работы, а конкретное изменение интервала можно определить поконтролировать.

Но кусочные функции и неравенства очень хлопотно вычислять.Для кусочных функций очень интуитивно понятно переписать формулу (1.2) в следующем виде:

y_i(w^Tx_i+b) \geq 1, \qquad \qquad i=1 \cdots m \quad (1.3)

Для решения неравенства Вапник предложил очень хитрый способ, то есть ориентироваться только на расстояние от критических точек выборки (значений) в каждом классе до гиперплоскости, а остальные точки выборки до этой плоскости должны быть больше критических точек выборки , то есть опорные векторы. А расстояние этих опорных векторов до гиперплоскости и есть искомый интервал. Описать этот отрывок на математическом языке можно так:

y_i(w^Tx_i+b) \geq 1 \to y_s(w^Tx_s+b) = 1, \qquad i \in D, s \in support \quad vectors

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

\gamma = \frac{2*|w^Tx_s+b|}{||w||} = \frac{2}{||w||}, \qquad \qquad \qquad (1.4)

Таким образом, получается ядро SVM: максимальный интервал $\max \limits_{w, b} \gamma=\frac{2}{||w||}$ , ограничения $y_i(w^Tx_i+b) \geq 1$ . максимизировать $||w||^{-1}$ может быть эквивалентно минимизации $||w||^{2}$ , так что разобрались:

\begin{aligned} & \min_{w, b} \frac{1}{2}||w||^2 \qquad \qquad \qquad (1.5)\\ & s.t. \quad y_i(w^Tx_i+b) \geq 1,\qquad i = 1,2,\cdots,m \end{aligned}

Формула (1.5) является основным типом SVM $^{[3]}$ . До сих пор была объяснена основная концепция и математическое описание SVM.Еще одна магическая особенность SVM заключается в том, что она превращает всю проблему оптимизации в задачу выпуклой оптимизации (квадратичного программирования), которая сообщает нам вывод квадратного уравнения. ||w||^2 Либо решения нет, либо есть одно и только одно оптимальное решение.

На рис. 1.2 показаны три гиперплоскости решений (границы), которые $x_1=\frac{1}{2}, x_2=\frac{1}{2}, x_1+x_2-1=0$ , все три плоскости могут правильно различать положительные и отрицательные образцы.Согласно упомянутой выше идее SVM, будет выбрана решающая гиперплоскость с наибольшим интервалом, как показано на рисунке 1.3, очевидно x_1+x_2-1=0 Эта гиперплоскость делает две точки выборки (опорные векторы) максимальными для гиперплоскости, и мы можем интуитивно увидеть результат выбора SVM на графике.

В разделе 1.2 мы выведем формулу для примера на рисунке 1.1 и получим результаты, показанные на рисунке 1.3.Пример, использованный в этой статье, требует небольшого объема вычислений.Я считаю, что после его расчета один раз он углубит вашу работу SVM понимание принципов. Конечно, вы также можете пропустить ссылку на вывод формулы, что не повлияет на чтение следующего содержания.

Рисунок 1.2: Гиперплоскость принятия решения

Рисунок 1.3: Интервальное сравнение

Примечание 1: На самом деле пример распределения данных, используемый во многих книгах, объясняющих принцип SVM, аналогичен рисунку 1, но объем данных немного больше, но большой объем данных не подходит для ручных операций. Поэтому в этом примере для арифметического вывода используются только две точки.

1.2 Решение базового типа SVM

Вспоминая формулу (1.5), мы знаем, что решение SVM на самом деле является задачей выпуклой оптимизации (условной оптимизации), поэтому можно использовать метод множителя (оператора) Лагранжа $^{[4]}$ Решите уравнение (1.5), добавив операторы для каждого ограничения в уравнении (1.5). $\alpha \geq 0$ ,имеют:

L(w, b, \alpha) = \frac{1}{2}||w||^2 + \sum_{i=1}^{m} \alpha_{i}(1 - y_i(w^Tx_i+b)) \qquad \qquad \qquad (1.6)

Частная производная параметра в формуле (1.6) равна нулю:

\begin{aligned} \frac{\partial L}{\partial w} & = w-\sum_{i=1}^{m}\alpha_iy_ix_i=0 \rightarrow w=\sum_{i=1}^{m}\alpha_iy_ix_i & (1.7) \\ \frac{\partial L}{\partial b} & = \sum_{i=1}^{m}\alpha_iy_i=0 & (1.8) \\ \frac{\partial L}{\partial \alpha} &=\sum_{i=1}^{m} 1 - y_i(w^Tx_i+b)=0 &(1.9) \\ \end{aligned}

Подставим уравнение (1.7) в уравнение (1.6) и исключим w,b Получил: (Примечание: ||w||^2=w^Tw )

\begin{aligned} L(w, b, \alpha) & = \frac{1}{2}||w||^2 + \sum_{i=1}^{m} \alpha_{i}(1 - y_i(w^Tx_i+b)) \\ & = \frac{1}{2}\sum_{i=1}^{m}(\alpha_iy_ix_i)^T\sum_{j=1}^{m}\alpha_jy_jx_j + \sum_{i=1}^{m} \alpha_{i}- \sum_{i=1}^{m} \alpha_{i}y_i(\sum_{j=1}^{m}(\alpha_jy_jx_j)^Tx_i+b) \\ & = \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x_i^T x_j + \sum_{i=1}^{m} \alpha_i - \sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x_j^T x_i \\ & = \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x_i^T x_j \qquad \qquad \qquad(1.10) \end{aligned}

Уравнение (1.5) является исходной задачей, и его двойственная задача может быть получена из уравнения (1.1)0, а именно:

\begin{aligned} \max_{\alpha} & \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x_i^T x_j \qquad \qquad (1.11) \\ & s.t \quad \sum_{i=1}^{m}\alpha_iy_i=0 , \\ & a_i \geq 0, \qquad i=1,2,\cdots,m \end{aligned}

Я не буду объяснять, в чем здесь двойная проблема, пока мы знаем, что вывод двойной проблемы таков:Если исходная задача является выпуклой функцией, а ограничения представляют собой лишь конечное число линейных уравнений (неравенств) с одной переменной, то решением двойственной задачи является решение исходной задачи.Очевидно, что исходная формула задачи (1.5) является выпуклой функцией, поэтому нам нужно решить только формулу (1.1)1. Существует множество эффективных пакетов алгоритмов для решения уравнения (1.1) 1, таких как SMO (подробно описанный в книге про арбузы) и т. д. Решение $\alpha$ Тогда получается прототип алгоритма:

\begin{aligned} f(x) &= w^Tx+b \\ & = \sum_{i=1}^{m}(\alpha_iy_ix_i)^Tx+b \qquad \qquad \qquad (1.12) \\ \end{aligned}

Согласно формуле (1.9), b может быть решена, а точка отсчета, которая может обеспечить справедливость формулы (1.9), является опорным вектором (x_s, y_s) :

b= \frac{1}{y_s}-\sum_{i \in S } \alpha_i y_i x_i^T x_s \qquad \qquad \qquad (1.13)

Мы используем точки выборки из раздела 1.1. $x = \{ (0, 0), (1, 1)\}, y = \{-1, +1\}$ Подставляем в формулу (1.1)1:

\begin{aligned} \theta(\alpha) &= \sum_{i=1}^{2} \alpha_i - \frac{1}{2}\sum_{i=1}^{2}\sum_{j=1}^{2}\alpha_i \alpha_j y_i y_j x_i^T \cdot x_j \\ & s.t \quad \sum_{i=1}^{2}\alpha_iy_i=0 \end{aligned}

в:

\begin{aligned} & \sum_{i=1}^{2}\sum_{j=1}^{2}y_i y_j x_i^T \cdot x_j = \begin{bmatrix} y_1 y_1 x_1 \cdot x_1 & y_1y_2x_1 \cdot x_2 \\ y_2y_1x_2 \cdot x_1 & y_2y_2x_2 \cdot x_2 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} \\ & \sum_{i=1}^{2}\alpha_iy_i= \alpha_2 -\alpha_1 = 0 \to \alpha_1 = \alpha_2 \end{aligned}

Итак, есть:

\begin{aligned} \theta(\alpha) & = 2a_1 - a_1^2 \\ let \quad \frac{\partial \theta}{\partial \alpha} &= 2 - 2a_1 = 0 \end{aligned}

Так что это решено a_1 = a_2 = 1 ,но w , b Они есть:

\begin{aligned} w & = \sum_{i \in S}\alpha_iy_ix_i = 1 \times (-1) \times [0, 0] + 1 \times 1 \times [1, 1] = [1, 1] \\ b & = (-1) - ( 1\times (-1) \times [0, 0]^T \times [0, 0] + 1 \times 1 \times [0, 0]^T \times [1, 1] ) = -1 \end{aligned}

Решения должны w = [1, 1], b = -1 (здесьнужно использовать только один из опорных векторов), поэтому гиперплоскость x_1 + x_2 - 1 = 0 . Тогда гиперплоскость, которую SVM выберет в предыдущем разделе, естественно, x_1 + x_2 - 1 =0 , также легко найти интервал $\gamma = \frac{1}{||w||} = \frac{1}{\sqrt{2}} = \frac{\sqrt{2}}{2}$ .

Кроме того, при решении уравнения (1.5) также необходимо выполнениеKKT(Karush-Kuhn-Tucker):

\left\{ \begin{aligned} & a_i \geq 0; \\ & y_i(w^Tx_i+b)-1 \geq 0; \qquad \qquad (1.14)\\ & a_i(y_i(w^Tx_i+b)-1) = 0; \end{aligned} \right.

Из уравнения (1.14) условия ККТ мы можем знать, что $\alpha$ тот факт, что когда $\alpha_i=0$ когда, в это время (x_i,y_i) не будет работать по формуле (1.11), поэтому точки выборки в этот момент должны быть не опорными векторами, а когда $\alpha_i > 0$ , должно быть только y_i(w^Tx_i+b)=1 , так что на этот раз (x_i,y_i) является опорным вектором.

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

2 Данные о шуме и мягкий интервал

В предыдущем разделе мы узнали обо всех возможностях SVM на линейно разделимых наборах данных, но реальные данные не являются полностью чистыми, то есть присутствует определенная степень шума, и эти шумы, вероятно, приводят к тому, что данные не быть вполне линейно сепарабельным. Конечно, задача предварительной обработки данных состоит в том, чтобы максимально уменьшить шум, но это может уменьшить только известный шум. Для правильной работы с неполностью линейно разделимыми наборами данных SVM вводит концепцию Soft Margin, которая позволяет некоторым выборкам не удовлетворять ограничениям в уравнении (1.5). $y_i(w^Tx_i+b) \geq 1$ , как показано на рисунке 2.1, представляет собой набор данных, который не является полностью линейно разделимым Две точки в красном кружке вообще не удовлетворяют требованиям формулы (1.5), поэтому формулу (1.5) также называют жесткой маржой (Hard Margin). ).

Рисунок 2.1: Неполностью линейный набор данных

Применение уравнения (1.5) к данным на рисунке 2.1 может привести к риску переобучения данных.По этой причине SVM вводит концепцию резервных переменных для решения проблемы неполной линейной разделимости. Процесс проектирования мягкой маржи очень подробно объясняется на странице 130 книги про арбузы, поэтому здесь мы прямо приводим результат, то есть базовый тип SVM мягкой маржи (soft-margin svm):

\begin{aligned} \min_{w,b} \quad & \sum_{i=1}^{m} \frac{1}{2}||w||^2 + C\sum_{i=1}^{m} \xi_i \qquad \qquad \qquad (2.1) \\ & s.t. \quad y_i(w^Tx_i + b) \ge 1-\xi_i \\ & \qquad \quad \xi_i \ge 0, \qquad \qquad i=1,2, \cdots, m. \end{aligned}

в— гиперпараметр, контролирующий степень влияния переменной резерва на гиперплоскость, а $\xi$ – степень, в которой выборка не удовлетворяет ограничениям в уравнении (1.5). Процесс решения уравнения (2.1) также будет самостоятельным в разделе 2.1, и здесь нам нужно только понять основной принцип мягкого интервала.

Жесткий интервал SVM формулы (1.5), очевидно, не может решить ситуацию с распределением данных на рисунке 2.1, но формула (2.1) позволяет двум выборкам в красном кружке находиться за пределами этого диапазона, так как же она дополняет эту концепцию? Мы наблюдаем две нелинейно разделяемые точки на рис. 2.2 ( $(0.2, 0.13) \to 1,(0.9, 0.8) \to -1$ ) в гиперплоскость соответственно 0.47 и 0.49 , такие расстояния не встречаются $y_i(w^Tx_i+b) \geq 1$ Это требование, но если в это время добавляется резервная переменная $\xi$ сделать $y_i(w^Tx_i+b) \geq 1-\xi_i$ Ситуация улучшится.

Рисунок 2.2: Расстояние между неразделимыми точками

\begin{aligned} \xi_1 & \ge 1 - (-1 \times ([1, 1]^T \cdot [0.2, 0.13] -1) ) \approx 0.33 \\ \xi_2 & \ge 1 - (1 \times ([1, 1]^T \cdot [0.9, 0.8] -1) ) \approx 0.30 \end{aligned}

Из приведенной выше формулы видно, что две нелинейно разделяемые точки выборки все еще могут быть правильно классифицированы в это время. В разделе 2.1 мы подробно обсудим с математической точки зрения $\xi$ Математические свойства и значение .

2.1 Решение прототипа SVM с мягкой маржой

Метод решения прототипа по-прежнему заключается в использовании метода оператора Лагранжа для вывода двойственной задачи по формуле (2.1) и в нахождении решения исходной задачи через двойственную задачу. который:

\begin{aligned} L(w, b, \alpha, \xi, \mu) & = \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}\xi_i + \sum_{i=1}^{m}\alpha_i(1 - \xi_i-y_i(w^Tx_i+b)) - \sum_{i=1}^{m}\mu_i \xi_i \quad (2.2) \end{aligned}

в $\alpha_i \ge 0 ,\mu_i \ge 0$ добавленный оператор Лагранжа. Те же шаги, что и в разделе 1.1, делаютЧастная производная каждого параметра равна 0, а затем подставьте ее обратно в формулу (2.2), чтобы вывести двойственную задачу. следующее:

\begin{aligned} \frac{\partial L}{\partial w} & = w - \sum_{i=1}^{m}\alpha_i y_i x_i = 0 \to w = \sum_{i=1}^{m}\alpha_i y_i x_i \qquad \qquad & (2.3) \\ \frac{\partial L}{\partial b} & = \sum_{i=0}^{m}\alpha_i y_i = 0& (2.4) \\ \frac{\partial L}{\partial \alpha} & = \sum_{i=1}^{m} (1 - \xi_i-y_i(w^Tx_i+b)) = 0 & (2.5) \\ \frac{\partial L}{\partial \xi} & = mC -\sum_{i=1}^{m} \alpha_i - \mu_i \to C = \alpha_i + \mu_i = 0 &(2.6) \\ \frac{\partial L}{\partial \mu} & = \sum_{i=1}^{m}\xi_i = 0 &(2.7) \end{aligned}

Очевидно, что только уравнения [2.3, 2.4, 2.6] могут упростить уравнение (2.2), и подставив их в:

\begin{aligned} L(w, b, \alpha, \xi, \mu) & = \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}\xi_i + \sum_{i=1}^{m}\alpha_i(1 - \xi_i-y_i(w^Tx_i+b)) - \sum_{i=1}^{m}\mu_i \xi_i \\ & = \frac{1}{2}\sum_{i=1}^{m}(\alpha_iy_ix_i)^T\sum_{j=1}^{m}\alpha_jy_jx_j + \sum_{i=1}^{m}(\bcancel{\alpha_i} + \bcancel{\mu_i})\xi_i \\ & +\sum_{i=1}^{m}\alpha_i(1 - \bcancel{\xi_i} -y_i(w^Tx_i+b)) - \bcancel{ \sum_{i=1}^{m} \mu_i \xi_i} \end{aligned}

После удаления редуцированной части в приведенной выше формуле приведенная выше формула в точности совпадает с формулой (1.1)0, то есть получается двойственная задача:

\begin{aligned} \max_{\alpha} & \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x_i^T x_j \qquad \qquad (2.8) \\ & s.t \quad \sum_{i=1}^{m}\alpha_iy_i=0 , \\ & \qquad 0 \leq a_i \leq C, \qquad i=1,2,\cdots,m \end{aligned}

Уравнение (2.8) является двойственной задачей уравнения (2.1), а отличие от уравнения (1.1)1 состоит в том, что имеется еще одно ограничение $\alpha_i \leq C$ , полученное из уравнения (2.6) $C=\alpha_i + \mu_i(\alpha_i \geq 0, \mu_i \geq 0)$ Для выполнения этой формулы необходимо $\alpha_i \leq C$ . Аналогично можно получить и условие ККТ уравнения (2.1):

\left\{ \begin{aligned} & a_i \geq 0, \quad \mu_i \geq 0, \quad \xi_i \geq 0;\\ & y_i(w^Tx_i+b)-1 + \xi_i \geq 0; \qquad \qquad (2.9) \\ & a_i(y_i(w^Tx_i+b)-1 +\xi_i ) = 0; \\ & \mu_i \xi_i =0; \end{aligned} \right.

Из формулы (2.9) условия ККТ можно узнать, что для всех образцов должно быть $\alpha_i=0$ или $y_i(w^Tx_i+b)-1+\xi_i=0$ , вывод в разделе 1.2 уместен $\alpha_i = 0$ Это означает, что выборка является не опорным вектором, и когда $\alpha_i > 0$ должно быть $y_i(w^Tx_i+b) = 1 - \xi_i$ , который является опорным вектором. Из уравнения (2.6) можно сделать вывод, что некоторые $\xi$ Математические свойства : когда $\alpha_i < C$ должно быть $\mu_i > 0$ , так что есть $\xi_i=0$ , что указывает на то, что точка выборки попадает на край наибольшего интервала, который является опорным вектором, то есть на две пунктирные линии на рисунке 2.1; когда $\alpha_i = C$ иногда $\mu_i = 0$ , то если $\xi_i \leq 1$ Это означает, что точка выборки попадает в максимальный интервал, то есть, как две точки выборки в красном кружке на рис. 2.1, их $\xi$ соответственно 0.33, 0.30 ,как $\xi_i > 1$ Объясните, что выборочная классификация неверна.

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

3 Отображение многомерного пространства признаков и методы ядра

Рассмотрим явление в реальности: для вещей в реальном мире атрибуты, которые мы можем наблюдать в области познания, ограничены. Например, когда мы описываем человека, мы можем описать его только со стороны. другие атрибуты этого человека (характер, мышление и т. д.), мы можем глубже понять этого человека и сделать более точные суждения. То же самое верно и в области машинного обучения.Наше познание объекта, подлежащего измерению, то есть собранных атрибутов, ограничено, поэтому нам часто нужно делать более сложные гипотезы (Hypothesis), чтобы понять объект, как показано на левая часть рисунка 3.1. Во входном пространстве атрибуты, которые мы можем собрать, могут формировать только двумерное пространство, поэтому нам нужно сделать сложную функцию предположения, чтобы различать эти выборки, но если мы можем спроецировать исходное входное пространство на определенные отношения отображения. В подходящем пространстве признаков мы можем различать эти выборки, делая относительно простые предположения, как показано в правой части рис. 3.1, посредством $\phi$ Это отношение отображения проецируется в трехмерное пространство признаков, и для его различения требуется только простая плоскость, и плоскость может быть выражена как:

f(x) = w^T\phi(x)+b, \qquad \qquad \qquad (3.1)

Рисунок 3.1: Пространственное картирование

Было показано, что при отображении точек выборки исходного пространства в достаточно высокое пространство признаков (которое мы считаем бесконечномерным) вероятность того, что эти выборки будут линейно разделимыми, увеличивается. Хотя эта теория красива, из уравнения (1.7) видно, что при расчете w^Tw когда рассчитывать $x_i^T \cdot x_j$ этого элемента, и через отношения отображения $\phi$ После обработки становится $\phi(x_i)^T \cdot \phi(x_j)$ , а если мы не знаем $\phi$ Явное выражение , похоже, что решение всего прототипа SVM станет невозможным для запуска.Для решения этой задачи SVM вводит функцию ядра, то есть предполагается, что существует такая функция, которая удовлетворяет:

\kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle = \phi(x_i)^T \cdot \phi(x_j) \qquad \qquad \qquad (3.2)

это можно решить $\phi(x_i)^T \cdot \phi(x_j)$ , преобразованный в решение $\kappa(x_i, x_j)$ ,в $\kappa(\cdot, \cdot)$ Называется «функция ядра» и представляет собой сильную теоретическую поддержку метода ядра SVM. Теоретическая основа навыков ядра на самом деле раньше, чем SVM. SVM использует только этот метод. Теория навыков ядра хорошо представлена в книге арбуз. Читатели, которые хотят углубиться, могут прочитать ее. Здесь мы используем только некоторые методы ядра. Заключение показывает, как SVM выполняет задачу распознавания нелинейных наборов данных. После добавления SVM с техникой ядра «выбор функции ядра» стал самой большой проблемой SVM. Неправильный выбор «функции ядра» приведет к тому, что пространство признаков все еще не может полностью выразить объект наблюдения, поэтому функция ядра, обычно используемая в отрасли, является основным критерием выбора (подробности см. На стр. 128 «Арбузной книги»). Итак, теперь мы перепишем вывод из уравнения (3.2) в двойственную задачу исходной задачи SVM уравнения (2.8):

\begin{aligned} \max_{\alpha} & \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j \kappa(x_i, x_j) \qquad \qquad (3.3) \\ & s.t \quad \sum_{i=1}^{m}\alpha_iy_i=0 , \\ & \qquad 0 \leq a_i \leq C, \qquad i=1,2,\cdots,m. \end{aligned}

Как и в предыдущем процессе, после решения двойственной задачи уравнения (3.3) исходная задача принимает вид:

\begin{aligned} f(x) &= w^T \phi(x)+b \\ & = \sum_{i=1}^{m}\alpha_i y_i \phi(x_i)^T \phi(x) +b \\ & = \sum_{i=1}^{m}\alpha_i y_i \kappa(x_i, x) + b \qquad \qquad \qquad (3.4) \end{aligned}

Примечание. Процесс вывода добавления прототипа SVM функции ядра аналогичен описанному выше процессу, только вычисление внутреннего произведения точек выборки заменено вычислением функции ядра. Поэтому дальнейшее описание не приводится.

До сих пор все формы SVM были объяснены.Хотя я много раз читал связанные теории SVM, я все еще чувствую себя удивительным и восхитительным в процессе написания этой статьи, поэтому эта статья также является данью уважения Вапнику (Истинному Богу). ). Еще раз повторюсь, автор невежественен, и хотелось бы, чтобы читатели указали на неуместность статьи. Кроме того, экспериментальный код этой статьи можно скачать в приложении.

4 Резюме

Взяв в качестве введения важные узлы развития формы SVM, описываются сущность SVM, изменения и неизменность ее математической теории.Хотя базовая теория SVM была относительно совершенной, предстоит еще много работы. улучшены в своем приложении, например, расширены до задач мультиклассификации, или как задача регрессии и т. д. Информацию, соответствующую области применения, читатели могут найти сами, но на самом деле суть SVM неизменна: освоив существенное содержание SVM, вы сможете адаптироваться к изменениям, как и процесс его разработки!

использованная литература

[1] Boser, Bernhard E., Isabelle M. Guyon, and Vladimir N. Vapnik. "A training algorithm for optimal margin classifiers." Proceedings of the fifth annual workshop on Computational learning theory. 1992.
[2] Burges, Christopher JC. "A tutorial on support vector machines for pattern recognition." Data mining and knowledge discovery 2.2 (1998): 121-167.
[3] Чжоу Чжихуа, Машинное обучение [M], Цин хуа да сюэ чу бань шэ, 2016.
[4] Klein, Dan. "Lagrange multipliers without permanent scarring." University of California at Berkeley, Computer Science Division (2004): 1-11.

приложение

Код этой статьи