Solved – Use Gaussian RBF kernel for mapping of 2D data to 3D

kernel trickMATLAB

I am working on SVMs and try to get all the concepts involved. For instance, the kernel mapping. I would like to construct some parts of the algorithm by myself, to understand what is happening.

My goal is to create a mapping as in this picture (taken from here)
Example mapping 2D --> 3D

I do not fully understand what the input and output values of the kernel are; to map the data points to the 3rd dimension, the output should be the Z-values, right? And the input are (vectors of) the X and Y-values?

My (matlab) code to get the z-values is:

z = exp(-( (abs(x-y).^2)./ (2*gamma^2) ));

But the z-values are just a bell-curve, us such:
enter image description here

I don't really know what I am doing wrong, but I think I confuse the concepts of kernel and (implicit/explicit) mapping.

How can I construct a (matlab) function that maps the 2D data to 3D space, using the Gaussian Radial Basis Function?

— Edit —
Thanks to user27840 I made it work, with the following matlab code:

gamma = 2;
D = squareform( pdist(data, 'euclidean') );
D = exp(-(D .^ 2) ./ ( 2*gamma^2));
z = sum(D);

This results in the following 3D plot, from original 2D data:
enter image description here

— Edit2: —
For those who are interested in one-class support vector machines; I wrote a blog post about it, using the answer from this thread: Introduction to one-class Support Vector Machine

Best Answer

I believe RBF projects the data into 3D space by centering a three dimensional bump (an un-normalized Gaussian) on top of each data point. The width of the bumps is given by the $gamma$ parameter.

These bumps overlap, so to figure out the z value at particular place you need to sum over all of the data points. If instead of $x, y$ we use $x_1, x_2$, and index all of the data points as $\mathbf{x}_i$ then the formula for to calculate the projection is:

$ z(\mathbf{x}) = \sum_{i=1}^{n} \exp\{ - \frac{ \| \mathbf{x} - \mathbf{x_i} \|^2}{2 \gamma^2 } \} $

Where $\mathbf{x}$ and $\mathbf{x}_i$ are two dimensional vectors and $\| \mathbf{x} - \mathbf{x}_i \|$ is the Euclidean distance between them.

That is, to find the z value at each point, you need to sum across all the data points.

Related Solutions

Solved – Plotting the decision boundary of a kernel SVM (RBF)

I figured out what is needed to be done. Actually, it's something simple, but its seems I had a matlaboid bug... Here is the code and the resulting figure for the "XOR" binary classification problem.

gamma     = getGamma();
b         = getB();
points_x1 = linspace(xLimits(1), xLimits(2), 100);
points_x2 = linspace(yLimits(1), yLimits(2), 100);
[X1, X2]  = meshgrid(points_x1, points_x2);

% Initialize f
f = ones(length(points_x1), length(points_x2))*rho;

% Iter. all SVs
for i=1:N_sv
    alpha_i = getAlpha(i);
    sv_i    = getSV(i);
    for j=1:length(points_x1)
        for k=1:length(points_x2)
            x = [points_x1(j);points_x2(k)];
            f(j,k) = f(j,k) + alpha_i*y_i*kernel_func(gamma, x, sv_i);
        end
    end    
end

surf(X1,X2,f);
shading interp;
lighting phong;
alpha(.6)

contourf(X1, X2, f, 1);

where the function

function k = kernel_func(gamma, x, x_i)
    k = exp(-gamma*norm(x - x_i)^2);
end

just produces the kernel function (RBF kernel), $k(\mathbf{x},\mathbf{x}')=\operatorname{exp}\left(-\gamma\lVert\mathbf{x}-\mathbf{x}'\rVert^2\right)$.

Here is the result for the XOR problem. Here $\gamma=4$.

enter image description here

Solved – How to apply a Gaussian radial basis function kernel PCA to nonlinear data

The first problem seems to be that the sign of gamma is wrong (it should be negative: $-15$, as in the definition of the kernel, not as in your code). Alternatively, use exp(-gamma * mat_sq_dists).

The second problem is that you clobber the eigenvectors with your invocation of zip's when you sort the list. The $i$-th eigenvector is eigvecs[:,i], not eigvecs[i,:], according to scipy.linalg.eigh (also: you should prefer eigh to eig because you have a symmetric real matrix).

Replace

< gamma = 15
> gamma = -15

and (to get ordered, real eigenvalues)

< eigvals, eigvecs = np.linalg.eig(K)
> eigvals, eigvecs = scipy.linalg.eigh(K)

and

< eigvals, eigvecs = zip(*sorted(zip(eigvals, eigvecs), reverse=True))
< X_pc1 = eigvecs[0]
> X_pc1 = eigvecs[:,99]

Finally, you can examine scikit-learn's own implementation here.

Best Answer

Related Solutions

Solved – Plotting the decision boundary of a kernel SVM (RBF)

Solved – How to apply a Gaussian radial basis function kernel PCA to nonlinear data

Related Question