Basic SVM Implemented in MATLAB

Question

  Linearly Non-Separable Binary Classification Problem

First of all, this program isn' t working correctly for RBF ( gaussianKernel() ) and I want to fix it.

It is a non-linear SVM Demo to illustrate classifying 2 class with hard margin application.

• Problem is about 2 dimensional radial random distrubuted data.

• I used Quadratic Programming Solver to compute Lagrange multipliers (alphas)

xn    = input .* (output*[1 1]);    % xiyi
phi   = gaussianKernel(xn, sigma2); % Radial Basis Function

k     = phi * phi';                 % Symmetric Kernel Matrix For QP Solver
gamma = 1;                          % Adjusting the upper bound of alphas
f     = -ones(2 * len, 1);          % Coefficient of sum of alphas
Aeq   = output';                    % yi
beq   = 0;                          % Sum(ai*yi) = 0
A     = zeros(1, 2* len);           % A * alpha <= b; There isn't like this term
b     = 0;                          % There isn't like this term
lb    = zeros(2 * len, 1);          % Lower bound of alphas
ub    = gamma * ones(2 * len, 1);   % Upper bound of alphas

alphas = quadprog(k, f, A, b, Aeq, beq, lb, ub);

• To solve this non linear classification problem, I wrote some kernel functions such as gaussian (RBF), homogenous and non-homogenous polynomial kernel functions.

For RBF, I implemented the function in the image below:

Using Tylor Series Expansion, it yields:

And, I seperated the Gaussian Kernel like this:

K(x, x') = phi(x)' * phi(x')

The implementation of this thought is:

function phi = gaussianKernel(x, Sigma2)

gamma   = 1 / (2 * Sigma2);
featDim = 10; % Length of Tylor Series; Gaussian Kernel Converge 0 so It doesn't have to Be Inf Dimension
phi     = []; % Kernel Output, The Dimension will be (#Sample) x (featDim*2)

    for k = 0 : (featDim - 1) 

        % Gaussian Kernel Trick Using Tylor Series Expansion
        phi = [phi, exp( -gamma .* (x(:, 1)).^2) * sqrt(gamma^2 * 2^k / factorial(k)) .* x(:, 1).^k, ...
            exp( -gamma .* (x(:, 2)).^2) * sqrt(gamma^2 * 2^k / factorial(k)) .* x(:, 2).^k];
    end

end

*** I think my RBF implementation is wrong, but I don' t know how to fix it. Please help me here.

Here is what I got as output:

where,

1) The first image : Samples of Classes
2) The second image : Marking The Support Vectors of Classes
3) The third image : Adding Random Test Data
4) The fourth image : Classification

Also, I implemented Homogenous Polinomial Kernel " K(x, x') = ( )^2 ", code is:

function phi = quadraticKernel(x)

    % 2-Order Homogenous Polynomial Kernel
    phi = [x(:, 1).^2, sqrt(2).*(x(:, 1).*x(:, 2)), x(:, 2).^2];

end

And I got surprisingly nice output:

To sum up, the program is working correctly with using homogenous polynomial kernel but when I use RBF, it isn' t working correctly, there is something wrong with RBF implementation.

If you know about RBF (Gaussian Kernel) please let me know how I can make it right..

Edit: If you have same issue, use RBF directly that defined above and dont separe it by phi.

Answer 1

Why do you want to compute phi for Gaussian Kernel? Phi will be infinite dimensional vector and you are bounding the terms in your taylor series to 10 when we don't even know whether 10 is enough to approximate the kernel values or not! Usually, the kernel is computed directly instead of getting phi (and the computing k). For example [1].

Does this mean we should never compute phi for Gaussian? Not really, no, but we have to be slightly smarter about it. There have been recent works [2,3] which show how to compute phi for Gaussian so that you can compute approximate kernel matrices while having just finite dimensional phi's. Here [4] I give the very simple code to generate the approximate kernel using the trick from the paper. However, in my experiments I needed to generate anywhere from 100 to 10000 dimensional phi's to be able to get a good approximation of the kernel (depending upon on the number of features the original input had as well as the rate at which the eigenvalues of the original matrix tapers off).

For the moment, just use code similar to [1] to generate the Gaussian kernel and then observe the result of SVM. Also, play around with the gamma parameter, a bad gamma parameter can result in really bad classification.

[1] https://github.com/ssamot/causality/blob/master/matlab-code/Code/mfunc/indep/HSIC/rbf_dot.m

[2] http://www.eecs.berkeley.edu/~brecht/papers/07.rah.rec.nips.pdf

[3] http://www.eecs.berkeley.edu/~brecht/papers/08.rah.rec.nips.pdf

[4] https://github.com/aruniyer/misc/blob/master/rks.m