Ядро SVM: я хочу, чтобы интуитивное понимание отображения на пространство пространственных объектов было более многомерным, и как это делает возможным линейное разделение

15

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

Что я знаю о ядре, так это то, что оно фактически представляет «сходство» между двумя точками данных. Но как это связано с проекцией?

Karnivaurus
источник
3
Если вы перейдете в достаточно большое пространство измерений, все точки тренировочных данных могут быть идеально разделены плоскостью. Это не значит, что у него будет какая-то предсказательная сила. Я думаю, что переход в очень высокое пространство измерений - это моральный эквивалент (форма) переоснащения.
Марк Л. Стоун
@Mark L. Stone: это правильно (+1), но все же может быть хорошим вопросом спросить, как ядро ​​может отображаться в бесконечномерном пространстве? Как это работает? Я пытался, см. Мой ответ
Я был бы осторожен, называя отображение объектов «проекцией». Отображение объекта обычно является нелинейным преобразованием.
Пол
Очень полезная статья о трюке ядра визуализирует внутреннее пространство продуктов ядра и описывает, как для достижения этого используются векторы пространственных объектов, надеюсь, это кратко ответит на вопрос: eric-kim.net/eric-kim-net/ posts / 1 / kernel_trick.html
JStrahl

Ответы:

6

Пусть h(x) проекция высокой размерности пространства F . В основном функция ядра K(x1,x2)=h(x1),h(x2) , который является внутренним продуктом. Таким образом, он не используется для проецирования точек данных, а скорее является результатом проекции. Это можно считать мерой сходства, но в SVM это нечто большее.

Оптимизация для нахождения наилучшей разделяющей гиперплоскости в F включает h(x) только через форму внутреннего произведения. То есть, если вы знаете K(,) , вам не нужно знать точную форму h(x) , что облегчает оптимизацию.

Каждому ядру K(,) также соответствует h(x) . Так что, если вы используете SVM с этим ядром, то вы неявно находите линию линейного решения в пространстве, в которое отображается h(x) .

Глава 12 « Элементы статистического обучения» дает краткое введение в SVM. Это дает более подробную информацию о связи между ядром и отображением функций: http://statweb.stanford.edu/~tibs/ElemStatLearn/

Lii
источник
Вы имеете в виду, что для ядра K(x,y) существует уникальный базовый h(x) ?
2
@fcoppens Нет; для тривиального примера рассмотрим h и h . Однако существует уникальное гильбертово пространство воспроизводящего ядра, соответствующее этому ядру.
Дугал
@Dougal: Тогда я могу согласиться с вами, но в ответе выше было сказано «соответствующий h », поэтому я хотел быть уверен. Что касается RKHS, я вижу, но вы думаете, что можно «интуитивно объяснить», как выглядит это преобразование h для ядра K(x,y) ?
@fcoppens В общем, нет; найти явные представления этих карт сложно. Для некоторых ядер это либо не слишком сложно, либо сделано ранее.
Дугал
1
@fcoppens вы правы, h (x) не уникален. Вы можете легко вносить изменения в h (x), сохраняя внутренний продукт <h (x), h (x ')> одинаковым. Однако вы можете рассматривать их как базисные функции, и пространство, которое они охватывают (т. Е. RKHS), является уникальным.
Лий
4

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

Этот ответ объясняет следующее:

  1. Почему идеальное разделение положительных и отрицательных обучающих данных всегда возможно с гауссовым ядром с достаточно малой пропускной способностью (за счет переобучения)
  2. Как это разделение можно интерпретировать как линейное в пространстве признаков.
  3. Как ядро ​​используется для построения отображения из пространства данных в пространство признаков. Спойлер: пространство признаков - это очень математически абстрактный объект с необычным абстрактным внутренним продуктом, основанным на ядре.

1. Достижение идеального разделения

Идеальное разделение всегда возможно с ядром Гаусса из-за свойств локальности ядра, которые приводят к произвольно гибкой границе решения. Для достаточно малой пропускной способности ядра граница принятия решения будет выглядеть так, как будто вы просто рисуете маленькие кружочки вокруг точек всякий раз, когда они необходимы для разделения положительных и отрицательных примеров:

Something like this

(Фото: онлайн курс по машинному обучению Эндрю Нг ).

Итак, почему это происходит с математической точки зрения?

Рассмотрим стандартную настройку: у вас есть гауссово ядро и обучающие данные ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , , ( x ( n ) ,K(x,z)=exp(||xz||2/σ2) где значения y ( i ) равны ± 1 . Мы хотим узнать функцию классификатора(x(1),y(1)),(x(2),y(2)),,(x(n),y(n))y(i)±1

y^(x)=iwiy(i)K(x(i),x)

Теперь, как мы будем когда-либо назначать веса ? Нужны ли нам бесконечномерные пространства и алгоритм квадратичного программирования? Нет, потому что я просто хочу показать, что могу отлично разделять точки. Поэтому я делаю σ в миллиард раз меньше, чем наименьшее разделение | | x ( i ) - x ( j ) | | между любыми двумя примерами обучения, и я просто установил w i = 1 . Это означает , что все учебные пункты являются миллиард сигмы друг от друга, насколько это ядро касается, и каждая точка полностью контролирует знак уwiσ||x(i)x(j)||wi=1y^в его окрестностях. Формально у нас есть

y^(x(k))=i=1ny(k)K(x(i),x(k))=y(k)K(x(k),x(k))+iky(i)K(x(i),x(k))=y(k)+ϵ

where ϵ is some arbitrarily tiny value. We know ϵ is tiny because x(k) is a billion sigmas away from any other point, so for all ik we have

K(x(i),x(k))=exp(||x(i)x(k)||2/σ2)0.

Since ϵ is so small, y^(x(k)) definitely has the same sign as y(k), and the classifier achieves perfect accuracy on the training data. In practice this would be terribly overfitting but it shows the tremendous flexibility of the Gaussian kernel SVM, and how it can act very similar to a nearest neighbor classifier.

2. Kernel SVM learning as linear separation

The fact that this can be interpreted as "perfect linear separation in an infinite dimensional feature space" comes from the kernel trick, which allows you to interpret the kernel as an abstract inner product some new feature space:

K(x(i),x(j))=Φ(x(i)),Φ(x(j))

where Φ(x) is the mapping from the data space into the feature space. It follows immediately that the y^(x) function as a linear function in the feature space:

y^(x)=iwiy(i)Φ(x(i)),Φ(x)=L(Φ(x))

where the linear function L(v) is defined on feature space vectors v as

L(v)=iwiy(i)Φ(x(i)),v

This function is linear in v because it's just a linear combination of inner products with fixed vectors. In the feature space, the decision boundary y^(x)=0 is just L(v)=0, the level set of a linear function. This is the very definition of a hyperplane in the feature space.

3. How the kernel is used to construct the feature space

Kernel methods never actually "find" or "compute" the feature space or the mapping Φ explicitly. Kernel learning methods such as SVM do not need them to work; they only need the kernel function K. It is possible to write down a formula for Φ but the feature space it maps to is quite abstract and is only really used for proving theoretical results about SVM. If you're still interested, here's how it works.

Basically we define an abstract vector space V where each vector is a function from X to R. A vector f in V is a function formed from a finite linear combination of kernel slices:

f(x)=i=1nαiK(x(i),x)
(Here the x(i) are just an arbitrary set of points and need not be the same as the training set.) It is convenient to write f more compactly as
f=i=1nαiKx(i)
where Kx(y)=K(x,y) is a function giving a "slice" of the kernel at x.

The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:

i=1nαiKx(i),j=1nβjKx(j)=i,jαiβjK(x(i),x(j))

This definition is very deliberate: its construction ensures the identity we need for linear separation, Φ(x),Φ(y)=K(x,y).

With the feature space defined in this way, Φ is a mapping XV, taking each point x to the "kernel slice" at that point:

Φ(x)=Kx,whereKx(y)=K(x,y).

You can prove that V is an inner product space when K is a positive definite kernel. See this paper for details.

Paul
источник
Great explanation, but I think you have missed a minus for the definition of the gaussian kernel. K(x,z)=exp(-||x−z||2/σ2) . As it's written, it does not make sense with the ϵ found in the part (1)
hqxortn
1

For the background and the notations I refer to How to calculate decision boundary from support vectors?.

So the features in the 'original' space are the vectors xi, the binary outcome yi{1,+1} and the Lagrange multipliers are αi.

As said by @Lii (+1) the Kernel can be written as K(x,y)=h(x)h(y) ('' represents the inner product.

I will try to give some 'intuitive' explanation of what this h looks like, so this answer is no formal proof, it just wants to give some feeling of how I think that this works. Do not hesitate to correct me if I am wrong.

I have to 'transform' my feature space (so my xi) into some 'new' feature space in which the linear separation will be solved.

For each observation xi, I define functions ϕi(x)=K(xi,x), so I have a function ϕi for each element of my training sample. These functions ϕi span a vector space. The vector space spanned by the ϕi, note it V=span(ϕi,i=1,2,N).

I will try to argue that is the vector space in which linear separation will be possible. By definition of the span, each vector in the vector space V can be written as as a linear combination of the ϕi, i.e.: i=1Nγiϕi, where γi are real numbers.

N is the size of the training sample and therefore the dimension of the vector space V can go up to N, depending on whether the ϕi are linear independent. As ϕi(x)=K(xi,x) (see supra, we defined ϕ in this way), this means that the dimension of V depends on the kernel used and can go up to the size of the training sample.

The transformation, that maps my original feature space to V is defined as

Φ:xiϕ(x)=K(xi,x).

This map Φ maps my original feature space onto a vector space that can have a dimension that goed up to the size of my training sample.

Obviously, this transformation (a) depends on the kernel, (b) depends on the values xi in the training sample and (c) can, depending on my kernel, have a dimension that goes up to the size of my training sample and (d) the vectors of V look like i=1Nγiϕi, where γi, γi are real numbers.

Looking at the function f(x) in How to calculate decision boundary from support vectors? it can be seen that f(x)=iyiαiϕi(x)+b.

In other words, f(x) is a linear combination of the ϕi and this is a linear separator in the V-space : it is a particular choice of the γi namely γi=αiyi !

The yi are known from our observations, the αi are the Lagrange multipliers that the SVM has found. In other words SVM find, through the use of a kernel and by solving a quadratic programming problem, a linear separation in the V-spave.

This is my intuitive understanding of how the 'kernel trick' allows one to 'implicitly' transform the original feature space into a new feature space V, with a different dimension. This dimension depends on the kernel you use and for the RBF kernel this dimension can go up to the size of the training sample.

So kernels are a technique that allows SVM to transform your feature space , see also What makes the Gaussian kernel so magical for PCA, and also in general?

Community
источник
"for each element of my training sample" -- is element here referring to a row or column (i.e. feature )
user1761806
what is x and x_i? If my X is an input of 5 columns, and 100 rows, what would x and x_i be?
user1761806
@user1761806 an element is a row. The notation is explained in the link at the beginning of the answer
1

Transform predictors (input data) to a high-dimensional feature space. It is sufficient to just specify the kernel for this step and the data is never explicitly transformed to the feature space. This process is commonly known as the kernel trick.

Let me explain it. The kernel trick is the key here. Consider the case of a Radial Basis Function (RBF) Kernel here. It transforms the input to infinite dimensional space. The transformation of input x to ϕ(x) can be represented as shown below (taken from http://www.csie.ntu.edu.tw/~cjlin/talks/kuleuven_svm.pdf)

enter image description here

The input space is finite dimensional but the transformed space is infinite dimensional. Transforming the input to an infinite dimensional space is something that happens as a result of the kernel trick. Here x which is the input and ϕ is the transformed input. But ϕ is not computed as it is, instead the product ϕ(xi)Tϕ(x) is computed which is just the exponential of the norm between xi and x.

There is a related question Feature map for the Gaussian kernel to which there is a nice answer /stats//a/69767/86202.

The output or decision function is a function of the kernel matrix K(xi,x)=ϕ(xi)Tϕ(x) and not of the input x or transformed input ϕ directly. enter image description here

prashanth
источник
0

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

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

Принимая во внимание проблему переобучения, вы можете переопределить любой набор наблюдений, определив достаточно условий, чтобы выделить каждое наблюдение в свой собственный класс, что эквивалентно отображению ваших данных в (n-1) D, где n - количество ваших наблюдений. ,

Возьмем простейшую задачу, где ваши наблюдения - это [[1, -1], [0,0], [1,1]] [[feature, value]], переместившись в 2D-измерение и разделив ваши данные линией Вы просто поворачиваете условную классификацию feature < 1 && feature > -1 : 0на определение линии, которая проходит через (-1 + epsilon, 1 - epsilon). Если у вас было больше точек данных и требовалось больше условий, вам просто нужно было добавить еще одну степень свободы к вашему более высокому измерению каждым новым определенным вами условием.

You can replace the process of mapping to a higher dimension with any process that provides you with a 1 to 1 relationship between the conditions and the degrees of freedom of your new problem. Kernel tricks simply do that.

Hou
источник
1
As a different example, take the problem where the phenomenon results in observations of the form of [x, floor(sin(x))]. Mapping your problem into a 2D dimension is not helpful here at all; in fact, mapping to any plane will not be helpful here, which is because defining the problem as a set of x < a && x > b : z is not helpful in this case. The simplest mapping in this case is mapping into a polar coordinate, or into the imaginary plane.
Hou