Спасение перед интервью — функция ядра и нелинейный SVM

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

Этот раздел представляет собой относительно продвинутый уровень теории опорных векторов. Друзья, кто новичок в контакте, можете глянуть кстати«Элементарные машины опорных векторов»,или«Расширенные машины опорных векторов». Есть подробные теоретические выводы. Машины опорных векторов — одна из немногих моделей машинного обучения с полными математическими доказательствами.

Вознесение для решения проблем

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

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

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

Поясним роль размерности на примере.

Операционный процесс восходящей размерности

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

Мы устанавливаем абсциссу как x_1 , ордината x_2 , то мы можем получить функцию этой разделительной линии как:

f(x_1,x_2)=a_1x_1+a_2x_2+a_3x_1^2+a_4x_2^2+a_5x_1x_2+a_6

здесьявляется коэффициентом. Тогда мы можем сделать это сейчас, мы делаем Z=[x_1,x_2,x_1^2,x_2^2,x_1x_2] , и поПостроим координатную ось новой системы координат, тогда получим пятимерное картографическое пространство, в то время как исходное признаковое пространство имеет только два измерения (x_1,x_2) . В этом новом пятимерном пространстве мы видим, что функция делителя эллипса:

f(z_1,z_2,z_3,z_4,z_5)=a_1z_1+a_2z_2+a_3z_3+a_4z_4+a_5z_5+a_6

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

Эффект показан на рисунке:

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

вообще-то нет.

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

имеют, идея функции ядра.

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

Конкретно, как работать, мы также рассмотрим на этом примере.

Функция ядра

Вернемся к двойственной задаче о машинах с опорными векторами, упомянутой в предыдущем разделе. Мы знаем, что двойная задача о машинах с опорными векторами с мягкими краями записывается так:

\min_\alpha \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)-\sum_{i=1}^N \alpha_i

s.t. \qquad\sum_{i=1}^N \alpha_i y_i=0 \qquad \quad

\qquad \qquad \qquad \qquad 0 \leq \alpha_i \leq C \quad i=1,2,...,N

мы нашли здесь $\alpha$ предмет, который нужно запросить,Просто положительная и отрицательная метка класса, просто возьмите {-1, +1}, Таким образом, основным шагом наших обучающих данных является использование этого $x_i \cdot x_j$ .

Роль функции ядра

Мы используем приведенный выше пример в качестве предзнаменования для общего случая квадратичного полинома. У нас есть набор данных с функциями, распределенными пообъемное пространство, X=[x_1,x_2,...,x_d] является его характерным размером. Затем мы можем обновить его до этого пространства:

\Phi(x)=[1,x_1,x_2,...,x_d,x_1^2,x_1x_2,...,x_1x_d,x_2x_1,x_2^2,...,x_2x_d,...,x_d^2]

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

\min_\alpha \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j[(\Phi(x_i)\cdot \Phi(x_j)]-\sum_{i=1}^N \alpha_i

Если мы решим ее в соответствии с нормальным способом мышления, мы должны сначала найти $\Phi(x_i) \cdot \Phi(x_j)$ :

\Phi(x_i) \cdot \Phi(x_j)=1+\sum_{i=1}^d \sum_{j=1}^dx_ix_j+\sum_{i=1}^d\sum_{i=1}^d x_i x_j x_i^\prime x_j^\prime

Объем вычислений здесь o(d^2) . существуетВ крупных случаях стоимость по-прежнему значительна. Затем мы демонстрируем мощь функции ядра:

Мы должны отметить, что здесь x_ix_j и до $x_i \cdot x_j$ Не то же самое у нас

x_i \cdot x_j = \sum_{i=1}^d \sum_{j=1}^dx_ix_j

Может быть, кто-то из моих друзей влюблен в это $x^\prime$ Я не понимаю, это на самом деле очень просто. $\Phi(x)$ Если вы вычислите свой собственный внутренний продукт, вы это поймете.

Преобразуем его:

\Phi(x_i) \cdot \Phi(x_j)=1+ \sum_{i=1}^d \sum_{j=1}^dx_ix_j+\sum_{i=1}^d\sum_{i=1}^d x_i x_j \sum_{i=1}^d\sum_{i=1}^dx_i^\prime x_j^\prime

Тогда мы знаем, что:

\Phi(x_i) \cdot \Phi(x_j)=1+ x_i \cdot x_j + (x_i \cdot x_j)^2

Это позволяет нам узнать, что $\Phi(x_i) \cdot \Phi(x_j)$ можно рассчитать по $x_i \cdot x_j$ Рассчитать. и $x_i \cdot x_j$ Вычислительная сложность o(d) .Роль функции ядра заключается в значительном сокращении объема вычислений., принцип здесь. Далее вводится форма функции ядра.

Определение функции ядра и навыков ядра

мы будем $\kappa(x_i,x_j)=\Phi(x_i) \cdot \Phi(x_j)$ определяется какФункция ядраи определить $\Phi(x)$ является картографической функцией.

ядерные трюкиИдея такова: использовать только в обучении и прогнозировании $\kappa(x_i,x_j)$ , вместо использования или явного вычисления $\Phi(x)$ . Вот почему мы упаковываем $\Phi(x_i) \cdot\Phi(x_j)$ Причина быть функцией. потому что мы используем только это $\Phi(x_i) \cdot\Phi(x_j)$ Только тогда, когда вы сможете ощутить удобство ядерных умений.

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

b^*=y_j -\sum_{i=1}^Ny_i\alpha_i^*(\Phi(x_i) \cdot \Phi(x_j) )=y_j -\sum_{i=1}^Ny_i\alpha_i^*(\kappa(x_i,x_j))

Функция принятия решения о классификации:

f(x)=sign \left( \sum_{i=1}^{N_s} \alpha_i^*y_i \Phi(x_i) \cdot \Phi(x_j)+b^* \right )=sign \left( \sum_{i=1}^{N_s} \alpha_i^*y_i \kappa(x_i,x_j)+b^* \right )

Нелинейный алгоритм машинного обучения опорных векторов

Вход: обучающий набор данных,в, $x \in \chi=R^n,y_i \in \lbrace-1,+1 \rbrace \qquad i=1,2,...,N$

Выход: функция решения классификации.

Выберите подходящую функцию ядра $\kappa(x_i,x_j)$ и соответствующие параметры, построим и решим задачу оптимизации:

$\min_\alpha \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j\kappa(x_i,x_j)- \sum_{i=1}^N \alpha_i$

$s.t. \qquad\sum_{i=1}^N \alpha_i y_i=0 \qquad \quad$

$\qquad \qquad \qquad \qquad 0 \leq \alpha_i \leq C \quad i=1,2,...,N$

найти оптимальное решение $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$

выберите $\alpha^*$ компонент $\alpha_j^*$ подходящие условия $0<\alpha_j^*<C$ , рассчитать:

$b^*=y_j - \sum_{i=1}^Ny_i\alpha_i^*(\kappa(x_i,x_j))$

Построим решающую функцию разделения:

$f(x)=sign \left( \sum_{i=1}^{N_s} \alpha_i^*y_i \kappa(x_i,x_j)+b^* \right )$

положительно определенное ядро

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

Ответ на самом деле ваш собственный выбор. Мы решаем, в какое пространство отображать исходные данные, в соответствии с выбранной нами функцией ядра.

наш $\kappa(x_i,x_j)$ образован внутренним произведением отображающей функции: $\Phi(x) \cdot \Phi(x)$ , значит, это симметричная функция. Обратно, для функции $\kappa(x_i,x_j)$ , если это Gram Матрица положительно-полуопределенная, то необходимо найти соответствующее ей отображение $\Phi$ . Gram Матрица выглядит так:

Gram \quad K= \begin{bmatrix} \kappa(x_1,x_1) & ... & \kappa(x_1,x_j) & ... & \kappa(x_1,x_m) \\ \cdot & ... & \cdot & ... & \cdot \\ \kappa(x_i,x_1) & ... & \kappa(x_i,x_j) & ... & \kappa(x_i,x_m) \\ \cdot & ... & \cdot & ... & \cdot \\ \kappa(x_m,x_1) & ... & \kappa(x_m,x_j) & ... & \kappa(x_m,x_m) \\ \end{bmatrix}

У нас есть следующая теорема: *сделать $\chi$ входное пространство, $\kappa(\cdot , \cdot)$ быть определены в $\chi \times \chi$ Симметричная функция на , тогда: $\kappa$ может использоваться как функция ядра $\Longleftrightarrow$ положительно полуопределенный

Кажется, что процесс совершенен, но «построить» ядерную функцию самостоятельно нам довольно сложно, нужно продемонстрировать полуположительную определенность матрицы Грама, а процесс вычисления очень сложен. Таким образом, обычно у нас есть несколько зрелых функций ядра, которые можно вызывать. Нам достаточно для решения задачи разных сценариев.

Несколько часто используемых функций ядра

\begin{array}{c|lcr} 名称 & \text{表达式} & \text{参数} \\ \hline 线性核 & \kappa(x_i,x_j)=x_i^Tx_j & 无 \\ 多项式核 & \kappa(x_i,x_j)=(x_i^Tx_j)^d & d \geq1为多项式次数 \\ 高斯核 & \kappa(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2\sigma^2}) & \sigma >0为高斯核带宽 \\ 拉普拉斯核 & \kappa(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{\sigma}) & \sigma>0 \\ Sigmoid 核 & \kappa(x_i,x_j)=tanh(\beta x_i^Tx_j+\theta) \qquad &tanh为双曲正切函数，\beta >0,\theta<0 \\ \end{array}

Мы также можем комбинировать эти функции ядра.

как $\kappa_1$ и $\kappa_2$ является функцией ядра, то для любого положительного числа $\gamma_1,\gamma_2$ , линейная комбинация $\gamma_1\kappa_1+\gamma_2\kappa_2$ также является функцией ядра.
как $\kappa_1$ и $\kappa_2$ является функцией ядра, то прямое произведение функции $\kappa_1 \bigotimes \kappa_2=\kappa_1\kappa_2$ Также функция ядра:
как $\kappa_1$ является функцией ядра, то для любой функции, $\kappa(x_1,x_2)=g(x)\kappa_1(x_1,x_2)g(x_2)$ также является функцией ядра

Конечно, после того, как мы определили функцию ядра, у нас есть функция решения классификации:

f(x)=sign \left( \sum_{i=1}^{N_s} \alpha_i^*y_i \kappa(x_i,x_j)+b^* \right )

На вопрос о том, как выбрать функцию ядра, профессор Ву Энда сказал:

Если количество функций велико, аналогично количеству образцов, выберите LR или SVM Linear Kernel в это время.

Если количество функций относительно невелико, а размер выборки средний, не слишком большой и не слишком маленький, используйте SVM+Gaussian Kernel.

Если количество функций относительно невелико, а количество выборок велико, вам необходимо вручную добавить некоторые функции, чтобы они стали первым случаем.

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

[1]Функция ядра | Подробное объяснение десяти лучших алгоритмов интеллектуального анализа данных

[2]Курс Coursera Национального Тайваньского Университета