読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

ガウシアンカーネルを用いたSVMについて

備忘録

教師付き2クラスの分類問題

  • ラベル付き訓練データ: \{(\mathbf{x}_i,y_i)\}_{i=1}^n
  • 入力: \mathbf{x}\in \mathbb{R}^d
  • 出力: y\in \{+1,-1\}

超平面分類器

  •  f_{\mathbf{w},b}(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b\ (\mathbf{w,x}\in \mathbb{R}^d)
  •  \text{find } \mathbf{w},b\ s.t. \\ y_i f_{\mathbf{w},b}(\mathbf{x}_i)\geq 1 \text{ for }i=1,\dots,n

ソフトマージン

  •  min_{\mathbf{w,\xi},b}\|\mathbf{w}^2\| + C\sum_{i=1}^n\xi_i \\ \text{subject to }y_i f_{\mathbf{w},b}(\mathbf{x}_i)\geq 1-\xi_i \\ \xi_i \geq 0 \text{ for } i=1,\dots,n

カーネルトリック

微分法による実装

SVM.m
function t = SVM(x,y,C,h,alpha=0.5,beta=0.8)
  [r c] = size(x); ep=alpha; hh=h^2;
  t = zeros([r 1]); x2 = diag(x*x');
  K = exp(-(repmat(x2,1,r)+repmat(x2',r,1)-2*x*x')/2*hh);
  for k = 1:100
    sum = zeros([200 1]);
    for i = 1:r
      if 1 > y(i) * K(i,:) * t
        sum += y(i)*K(i,:)';
      end
    end
    t = t - ep*(C*sum+2*K*t);
    ep *= beta;
  end
end
script.m
clear all; rand('state',0); randn('state',0);
n=200; a=linspace(0,4*pi,n/2);
%u=[a.*cos(a) (a+pi).*cos(a)]'+1*rand(n,1);
%v=[a.*sin(a) (a+pi).*sin(a)]'+1*rand(n,1);
u=[6*cos(a) 12*cos(a)]'+2*rand(n,1);
v=[6*sin(a) 12*sin(a)]'+3*rand(n,1);
x=[u v]; y=[ones(1,n/2) -ones(1,n/2)]';
C=1; h=1; hh=2*h^2;
t=SVM(x,y,C,h); % x:data y:label C:const h:sigma
m=500; X=linspace(-15,15,m)'; X2=X.^2;
U=exp(-(repmat(u.^2,1,m)+repmat(X2',n,1)-2*u*X')/hh);
V=exp(-(repmat(v.^2,1,m)+repmat(X2',n,1)-2*v*X')/hh);
% U_ij=||x_i-x_j||^2 : i = 1..n, j = 1..m
% V_ij=||y_i-y_j||^2 : i = 1..n, j = 1..m
figure(1); clf; hold on; axis([-15 15 -15 15]);
contourf(X,X,sign(V'*(U.*repmat(t,1,m))));
f1=plot(x(y==1,1),x(y==1,2),'bo'); f2=plot(x(y==-1,1),x(y==-1,2),'rx');
set(f1,'linewidth',2.0);set(f2,'linewidth',2.0); axis equal;
xlabel('X(1)'); ylabel('X(2)');
colormap([0.7 1 1; 1 0.7 1]);
%print SVM.png ;