C.2. Matlab Project 2: SVMs for Pattern Classification

C.2.1. Objectives

Use linear and nonlinear support vector machines (SVMs) to classify two-dimensional data.

C.2.2. Procedures

Linear SVMs
1.
Go to http://www.cis.tugraz.at/igi/aschwaig/software.html to download the software "svm_251" and save the m-files to your working directory. Some functions (e.g., plotboundary, plotdata, and plotsv) are included in the end of the m-file demsvm1.m. Extract these functions to form new m-files (e.g. plotboundary.m, plotdata.m and plotsv.m).

2.
Open Matlab, go to "File" → "Set Path" and add the directory where "svm_251" was saved. Alternatively, add the statement "addpath svmdir"—where svmdir is the directory storing "svm_251"—to your .m file.

3.
If your system does not have Matlab Optimization Toolbox installed, you may need to compile the files pr_loqo.c and loqo.c in Matlab's command prompt, as follows:

mex pr_loqo.c loqo.c

This will create a file named pr_loqo.dll; then, find the line

workalpha = loqo(H, f, A, eqconstr, VLB, VUB, startVal, 1);

in svmtrain.m and change loqo to pr_loqo.

4.
Input the following training data. X is a set of input data, 20 × 2 in size. Y contains the corresponding class labels, 20 × 1 in size.

X(2, 7)(3, 6)(2, 5)(3, 5)(3, 3)(2, 2)(5, 1)(6, 2)(8, 1)(6, 4)(4, 8)
Y+1+1+1+1+1+1+1+1+1+1-1

X(5, 8)(9, 5)(9, 9)(9, 4)(8, 9)(8, 8)(6, 9)(7,4)(4, 4)
Y-1-1-1-1-1-1-1-1-1

Plot a graph to show the data set using the commands plotdata:


x1ran = [0, 10]; x2ran = [0, 10]; %data range
f1 = figure; plotdata(X, Y, x1ran, x2ran);
title('Data from class + 1 (squares) and class — 1 (crosses)'),

5.
Create a support vector machine classifier by using the function svm.

net = svm(nin, kernel, kernelpar, C, use2norm, qpsolver, qpsize)

Set nin to 2 because X contains two-dimensional data. Set kernel to 'linear' to use linear SVM. Set kernelpar to [ ] because a linear kernel does not require any parameters, set C to 100, and set use2norm to 0 so that 1-norm is used (standard SVM). Set qpsolver to 'loqo' so that the C functions in pr_loqo.dll will be used for performing quadratic optimization. You may leave the last parameter qpsize blank (i.e., the default value is to be used).

After creating an SVM, train it by using the function svmtrain

net = svmtrain(net, X, Y, alpha0, dodisplay)

Set alpha0 to [ ], and set dodisplay to 2 to show the training data.

After carrying out the preceding steps, record the number of SVs. Also, record the norm of the separating hyperplane and calculate the length of the margin from net.normalw.

Plot the SVM using the commands plotboundary, plotdata, and plotsv as follows:

figure; plotboundary(net, x1ran, x2ran);
plotdata(X, Y, x1ran, x2ran); plotsv(net, X, Y);
normW = norm(net.normalw);
tstring = sprintf('Linear SVM, C = %.1f, #SV = %d, normW = %.2f',...
               C, length(net.svind), norm);
title(tstring,' FontSize', 11);

6.
Vary the value of C in the function svm and repeat Step 5 (e.g., C = 0.1, C = 10, and C = 1000). For different values of C, plot the corresponding SVM, record the number of the support vectors, the norm of the separating hyperplanes, and the margin width. Discuss the change in the number of SVs and the margin width as a result of varying C.

Nonlinear SVMs
1.
Repeat the procedures described in the preceding linear SVM, but this time replace the linear kernel with a polynomial kernel:


net = svm(2, 'poly', 2, C, 0, 'loqo'), % second-order polynomial kernel
net = svmtrain(net, X, Y, [ ], 2);

2.
Vary the value of C in the function svm and repeat Step 1 (e.g. C = 0.1, C = 10, and C = 1000). For different values of C, plot the corresponding SVM and record the number of the support vectors. Discuss the change in the number of SVs and the margin width as a result of varying C. Note that you cannot obtain the margin width from net.normalw because the margin width is different in different regions of the input space.

3.
Repeat Steps 1 and 2, but use a polynomial kernel of degree 3:


net = svm(2, 'poly', 3, C, 0, 'loqo'), % 2nd-order polynomial kernel
net = svmtrain(net, X, Y, [ ], 2);

Explain your observation.

4.
Repeat Steps 1 and 2, but use an RBF kernel:


net = svm(2, 'rbf', 8, C, 0,' loqo'), % RBF kernel with 2σ2 = 8
net = svmtrain(net, X, Y, [ ], 2);

Explain your observations.

The Role of Kernel Parameters

  1. Edit the file svmkernel.m to implement the kernel function


    Set p = 2 and rerun the 20-point problem in Section C.2.2 for different values of σ. How does σ affect the shape of the decision boundary for a fixed C and p? Discuss your observations.

  2. Vary the integer p but fix σ. How does p affect the shape of the decision boundary for a fixed C and σ? Discuss your observations.

  3. Vary the kernel parameter σ of the RBF kernel and repeat the 20-point problem. How does σ affect the shape of the decision boundary for a fixed C? Discuss your observations.

Invariance Properties of SVMs

  1. Input the following Matlab code to your .m file to create a noisy XOR problem:

    shift = 0;
scale = 1;
xmean = [−1, −1; −1, 1; 1, −1; 1, 1];
xstd = 0.5;
randn('state', 0);
x = [xstd * randn(N, 1) + xmean(l, 1,) xstd * randn(N, 1) + xmean(1, 2);...
     xstd * randn(N, 1) + xmean(2, 1) xstd * randn(N, 1) + xmean(2, 2);...
     xstd * randn(N, 1) + xmean(3, 1) xstd * randn(N, 1) + xmean(3, 2);...
     xstd * randn(N, 1) + xmean(4, 1) xstd * randn(N, 1) + xmean(4, 2)];
x = x * scale + shift;
    y = [−1 * ones(N, 1); ones(N, 1); ones(N, 1); −1 * ones(N, 1)];
    x1range = [−2, 2] * scale + shift;
    x2range = [−2, 2] * scale + shift;

  2. Use linear SVMs, polynomial SVMs, and RBF SVMs to solve the noisy XOR problem. For each case, record the decision boundaries and the number of SVs. Note that you may need to edit the file "plotdata.m" to remove the labels of the data points on the plots. Can the linear SVM solve the XOR problem? Explain your observations.

  3. Scale Invariance. Set scale = 5 to scale the training data (xi ← 5xi) and repeat Step 2 for using polynomial SVMs and RBF SVMs. Note that you need to change the polynomial kernel function to (1 + xTxi/β2)2, where β = 5 in this case. This can be done by editing the svmkernel.m file. You also need to properly scale the kernel parameter of the RBF kernel, as follows:

    net = svm(2, `rbf', (sigma^ 0.5*scale)" 2,C,0, 'loqo'),

    where sigma is the kernel parameter σ in


    for the unsealed data. You may set sigma = 1 to obtain reasonably good results. Are all of the SVMs scale invariant? Explain your observations.

  4. Change the kernel function in svmkernel.m to (β2 + xTxi)2 and repeat Step 3. Does this kernel function lead to scale invariant SVMs? If not, why?

  5. Translation Invariance. Set shift = 12 to shift the training data—xi ← xi + [12 12]T—and repeat Step 2. Which type of SVMs is not translation invariant? Explain your observations.

  6. Set scale = 5 and shift = 12 to investigate both the scale and translation invariance properties of different SVMs.

Verifying the Analytical Solutions
1.
Create a 4-point XOR problem by entering the following Matlab code to your .m file:

   C = 100;
   shift = 0;
   scale = 1;
   x = [0, 0; 0, 1; 1, 0; 1, 1] * scale + shift;
   y =[−1; 1; 1; −1];
   x1range = [−1, 2] * scale + shift;
   x2range = [−1, 2] * scale + shift;

2.
Create a polynomial SVM to solve this XOR problem and show that the Lagrange multipliers and the bias are α1 = 10/3, α2 = 8/3,α3 = 8/3, α4 = 2, and b = 1. Determine the maximum value of the Lagrangian L(α). You can use the following code fragment to display the multipliers and the slack variables ξi:

[svDec, svOut] = svmfwd(net, net.sv);
svSlack = 1 - y(net.svind). * svOut;
svAlpha = net. alpha(net.svind);
fprintf ('svind    ai      xiin'),
fori = 1 : length(net.svind)
   fprintf ('%d       %.4f      %fn', net.svind(i), svAlpha(i), svSlack(i));
end

3.
Set shift = − 0.5 and repeat Step 2. Compare the decision boundary between the SVM obtained in Step 2 and the one obtained in this step. What are the implications of your result? Suggest a possible method to address the translation invariance issue.

4.
Repeat Steps 2 and 3, but this time use an RBF SVM to solve the four-point XOR problem. Based on your results, comment on the applicability of polynomial SVMs and RBF SVMs in real-world problems.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.221.165.115