基本SVM在MATLAB中实现

Question

  Linearly Non-Separable Binary Classification Problem

首先,这个程序对RBF(gaussianKernel())没有正常工作,我想修复它.

它是一个非线性SVM演示,用于说明使用硬边距应用对2类进行分类.

• 问题是关于二维径向随机分布数据.

• 我使用二次规划求解器来计算拉格朗日乘数(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);

• 为了解决这个非线性分类问题,我编写了一些核函数,如高斯(RBF),同质和非齐次多项式核函数.

对于RBF,我在下图中实现了该功能:

使用Tylor Series Expansion,它可以产生:

而且,我像这样分离了高斯内核:

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

这个想法的实现是:

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

***我认为我的RBF实现是错误的,但我不知道如何解决它.请帮帮我.

这是我得到的输出:

哪里,

1)第一个图像:类的样本
2)第二个图像:标记类的支持向量
3)第三个图像:添加随机测试数据
4)第四个图像:分类

另外,我实现了Homogenous Polinomial Kernel"K(x,x')=()^ 2",代码是:

function phi = quadraticKernel(x)

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

end

我得到了令人惊讶的好输出:

总之,程序正在使用同源多项式内核,但是当我使用RBF时,它不能正常工作,RBF实现有问题.

如果您了解RBF(高斯内核),请告诉我如何才能做到正确..

编辑:如果您有相同的问题,请直接使用上面定义的RBF并且不要通过phi分类.

Answer 1

为什么要计算高斯核的 phi？Phi 将是无限维向量，当我们甚至不知道 10 是否足以近似核值时，您将泰勒级数中的项限制为 10！通常，直接计算内核而不是获取 phi（和计算 k）。例如[1]。

这是否意味着我们永远不应该计算高斯的 phi？不完全是，不，但我们必须对此更加聪明一些。最近的工作 [2,3] 展示了如何计算高斯的 phi，以便您可以在只有有限维 phi 的情况下计算近似核矩阵。在这里 [4] 我给出了非常简单的代码，使用论文中的技巧生成近似内核。然而，在我的实验中，我需要生成 100 到 10000 维 phi 的任意位置，以便能够获得内核的良好近似值（取决于原始输入的特征数量以及特征值的速率）原始矩阵逐渐减小）。

目前，只需使用类似于[1]的代码来生成高斯核，然后观察SVM的结果。另外，尝试一下伽玛参数，不好的伽玛参数可能会导致非常糟糕的分类。

[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