Basic SVM implemented in MATLAB

Question

Linearly Non-Separable Binary Classification Problem 

First of all, this program does not work correctly for RBF (gaussianKernel ()), and I want to fix it.

This is a non-linear SVM demonstration to illustrate class 2 classification using a hard field.

• The problem is two-dimensional radial random distributed data.

• I used the quadratic software solver to calculate the Lagrange multipliers (alpha)

 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 problem with nonlinear classification, I wrote some kernel functions, such as Gaussian (RBF), homogeneous and heterogeneous polynomial kernel functions.

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

Using the extension of the Tylor series, it gives:

And I split the Gaussian core as follows:

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

Implementation of this thought:

 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 believe that my RBF implementation is incorrect, but I do not know how to fix it. Please help me here.

Here is what I got as output:

where <

1) First image: Sample classes
2) Second image: class support vectors
3) Third image: adding random test data
4) Fourth Image: Classification

In addition, I implemented a homogeneous polynomial core "K (x, x ') = () ^ 2", code:

 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 an amazingly good result:

To summarize, the program works correctly using a homogeneous polynomial kernel, but when I use RBF, it does not work correctly, something is wrong with the RBF implementation.

If you know about RBF (Gaussian Kernel), please let me know how I can fix this.

Edit: if you have the same problem, use RBF directly as defined above and do not split it into phi.

Answer 1

Why do you want to calculate phi for a Gaussian kernel? Phi will be an infinite dimensional vector, and you limit the terms in your taylor series to 10, when we don’t even know if 10 is enough to approximate the kernel values ​​or not! Typically, the kernel is computed directly instead of obtaining phi (and calculating k). For example [1].

Does this mean that we should never calculate phi for gaussian? Not really, no, but we should be a little smarter about that. There were recent papers [2,3] that showed how to calculate phi for a Gaussian so that you can calculate approximate matrix matrices with only finite dimensional phi. Here [4] I give a very simple code to generate an approximate kernel using the trick from the article. However, in my experiments, I needed to generate anywhere from 100 to 10,000 dimensional phi in order to be able to get a good approximation to the core (depending on the number of features that the original input had, as well as the speed at which the original matrix narrows).

For now, just use code similar to [1] to generate a Gaussian kernel and then observe the SVM result. Also, play with the gamma parameter, a bad gamma parameter can lead to a 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

Answer 2

Since the Gaussian core is often referred to as a mapping into dimensions of infinity, I always believe in its ability. The problem here is probably due to a bad parameter, given that a grid search is always necessary for training SVM. Therefore, I suggest you familiarize yourself with here , where you can find some tricks for setting parameters. An exponentially increasing sequence is commonly used as candidates.