Octaveで非線形SVMを解く

前回の線形SVMに引き続き、今回はカーネルトリックを使って非線形SVMを解いてみます。
カーネルを使うために主問題を双対問題に変換します。下のプログラムを見ると分かるように、主問題よりも双対問題の方がQPソルバーに乗せるのは簡単です。

#--------------------------------------------------------------------
# procedure:
#   solve a dual svm
# input: 
#   x feature vectors of training data
#   y labels of training data
#   C upper bound for alpha
#   kernel kernel function to be used
# output:
#   ret [w; b] where w x + b = 0 is the obtained hyperplane
# -------------------------------------------------------------------
function ret = dsvm(x, y, C, kernel)
    l = rows(x);           # number of training data

    x0 = zeros(l, 1);
    H = zeros(l);
    for i = 1:l
        for j = 1:l
            H(i, j) = y(i) * y(j) * kernel(x(i,:), x(j,:));
        endfor
    endfor
    q = -ones(l, 1);
    A = transpose(y);
    b = [0];
    lb = zeros(l, 1);
    ub = C * ones(l, 1);
    Al = [-inf];
    Ai = ones(1, l);
    Au = [inf];
    
    [sol, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub, Al, Ai, Au);
    ret = sol;
    
endfunction;

線形分離不可能な学習データを学習させてみました。
まずは、円を使うと分けられるパターン。カーネル関数にはK(u, v) = (uv + 1)^2を使いました。

次に円でも分離できないパターン。手裏剣のような形を使うとうまく分離できそうです。
ガウシアンカーネルK(u, v) = exp(- |u-v| / 20)を使って学習してみました。

うお、そう分けるか。。すごい。