Plotting the decision boundary of a kernel SVM (RBF)

Question

Suppose we are given a training set of 2D points that are linearly non-separable. I train a binary SVM with an RBF kernel in order to classify them. What I want to do is to draw the desicion boundary.

The kernel SVM I train leads to a decision function of the form: $$ f(\mathbf{x})=\sum_{i=1}^{N_s}\alpha_i y_i k(\mathbf{x}, \mathbf{x}_i)+b, $$ where $N_s$ is the number of support vectors, $\mathbf{x}_i$, $\alpha_i$, and $y_i$ are the $i$-th support vector, the corresponding positive Lagrangian multiplier, and the associated truth label, respectively. I use the LIBSVM package to train the SVM, thus all the above are known from the created model file.

If we extend the above decision function, we see that it's a sum of Gaussians centred at the support vectors, i.e., $$ f(\mathbf{x})=\sum_{i=1}^{N_s}\alpha_i y_i \operatorname{exp}\left(-\gamma\lVert\mathbf{x}-\mathbf{x}_i\rVert^2\right)+b, $$ where $\gamma=\frac{1}{2\sigma^2}>0$ is a user-defined parameter.

How could I plot in the same space of my input data (the Euclidean 2D space), the contour of the decision function? Could you please provide some equations or ideas? I've tried some things, but I had no luck!

Answer 1

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$.

Answer 2

Use a grid approach, divide your 2D space into a k by k grid, evaluate that point as a sample in your SVM (i.e., predict the label), and plot the predictions at all points.