[SOLVED] EE5904-Project 2

Description

Task 1

Write a MATLAB (M-file) program to compute the discriminant function, if one exists, for the following SVMs, using the training set provided.

• Hard margin SVM with the linear kernel:

𝐾𝐾 (𝑥𝑥₁, 𝑥𝑥₂) = 𝑥𝑥₁^𝑇𝑇𝑥𝑥₂

• Hard margin SVM with a polynomial kernel:

𝐾𝐾 (𝑥𝑥₁, 𝑥𝑥₂) = (𝑥𝑥₁^𝑇𝑇𝑥𝑥₂ + 1)^𝑝𝑝

• Soft margin with a polynomial kernel as given in Equation (2).

The step of computing the discriminate function can be summarized as follows:

1. Data preparation and pre-preprocess.

Here our training and testing dataset have 2,000 and 1,536 samples respectively. Each sample has 57 features. To ensure the data in internally consistent and enhance our training confidence, I firstly use standardization method to pre-process the data.

1. Gram matrix

With the given kernel, we need to calculate the gram matrix.

c. Mercer condition

Compute the eigenvalues of (b) gram matrix. We need to make sure the minimal eigenvalue is still non-negative. If not, the kernel candidate is not admissible. In Matlab, the computed eigenvalues are pretty much small. Here I set -1e-6 as the threshold. Only when the min eigenvalue is greater than the threshold, the training can move on.

d. Quadratic programing

Since the Mercer condition is already met, we have a global optimal value for this optimization problem. Following the Quadratic programming documentation in Matlab, we can calculate the optimal values.

e. Support vector determination

Set the threshold as 1e-6 to determine supper vectors in Matlab.

1. Weights calculation For linear case:

∑𝒊𝒊=𝟏𝟏

𝑵𝑵                                                𝟏𝟏     𝑻𝑻𝒙𝒙𝒊𝒊 ; 𝒃𝒃𝟎𝟎 = 𝒎𝒎 𝒃𝒃𝟎𝟎,𝒊𝒊  

𝒘𝒘𝟎𝟎 = 𝜶𝜶𝟎𝟎,𝒊𝒊𝒅𝒅𝒊𝒊𝒙𝒙𝒊𝒊; 𝒃𝒃𝟎𝟎,𝒊𝒊 = − 𝒘𝒘𝟎𝟎

𝒅𝒅_𝒊𝒊                                                𝒎𝒎

𝒊𝒊=𝟏𝟏

For non-linear case:

𝑵𝑵                                                                        ∑𝒎𝒎 𝒃𝒃𝟎𝟎,𝒊𝒊

𝒊𝒊=𝟏𝟏

𝒈𝒈(𝒙𝒙) = 𝜶𝜶_{𝟎𝟎,𝒊𝒊}𝒅𝒅_𝒊𝒊𝑲𝑲(𝒙𝒙, 𝒙𝒙_𝒊𝒊) + 𝒃𝒃_𝟎𝟎; 𝒃𝒃_𝟎𝟎 =

𝒎𝒎

𝒊𝒊=𝟏𝟏

Task 2

Write a MATLAB (M-file) program to implement the SVMs with the discriminant functions obtained in Task 1.

Discussion

1. In terms of the hard margin with polynomial kernel, when p =4,5, the results are non-convex. The Mercer condition cannot be met in this situation.
2. In terms of the soft margin with polynomial kernel, when p = 4,5, the results are non-convex. The Mercer condition is not met no matter what c value is.
3. In terms of soft margin with polynomial kernel when p =2, we can find that with a larger tolerance of mis-classified samples (c value increases), the testing accuracy drops though the training accuracy is still consistent.
4. By comparing the hard margin with different kernel, although the training accuracy of linear kernel is lower than that of polynomial kernel, the testing accuracy of linear is higher.
5. Even though the training accuracy can reach almost 100% like p =2&3 with soft margin, the testing accuracy is still around 90%. It might be caused by overfitting.

Task 3

Design a SVM of your own.

In order to determine a better SVM classifier, we can start from two aspects based on previous experiment.

1. Kernel selection.

Here I tested two popular kernel besides linear and polynomial. They are Gaussian kernel and sigmoid kernel. After experiment, Gaussian kernel as a general-purpose kernel is used in this case. It works well when there is no prior knowledge about the data.

1. Soft margin parameters and Gaussian kernel parameters.

Here we found when sigma = 10 and c = 20, both training and testing accuracy achieve highest values in our experiment. Thus, we chose these two as our own SVM classifier.