Practical 5: Support Vector Machines

C matters, and the table says by how much. At C = 0.01 the penalty for a mistake is so small that the model gives up and gets 0.571 on the training rows, which is barely better than guessing. From C = 1 upward it reaches 0.905 training and 0.667 test, and the weights stop changing much.

The five nearest points are the support vectors, and look at the first two: Amit, with 44 per cent attendance and 9 hours of practice, who passed, and Gauri, with 98 per cent attendance and 9 hours, who failed. Those are the two students the dataset was built around, the exceptions to its own rule, and they carry margins of -1.570 and -0.335, both negative, meaning both are on the wrong side of the line. The SVM has decided to accept those two mistakes in exchange for a wider corridor everywhere else. That is the soft margin doing its job, and it is the sentence to write in the journal.

Step 2: the picture

Figure 8.1 All thirty students. The solid line is the boundary scikit-learn's linear SVC found on the twenty-one training rows with C = 1; the dashed lines are one unit of margin either side of it.

Reading it is the analysis MU asks for. The corridor runs from the lower left to the upper right, the Pass students sit mostly to the upper right of it, and the handful of filled circles on the wrong side and hollow squares on the right side are the errors the soft margin bought the corridor with.

Step 3: the same model from scikit-learn, and the kernels

A straight line is not always enough. The kernel trick lets an SVM draw a curved boundary without ever computing the curve: it measures similarity between points with a different function, and a straight line in that space of similarities is a curve in the original one. Three kernels are worth knowing, and MU's theory paper names them.

• linear: the straight line above.
• rbf, the radial basis function: similarity falls off with distance, so the boundary can be any smooth shape. The default in scikit-learn.
• poly: a polynomial of the given degree, 3 by default.

"""The same job from scikit-learn: SVC, the kernels, and tuning C."""
import csv
from sklearn.svm import SVC
from sklearn.preprocessing import MinMaxScaler
from sklearn.model_selection import train_test_split

with open("students.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
X = [[float(r["attendance"]), float(r["practice"])] for r in rows]
y = [r["result"] for r in rows]
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)
scaler = MinMaxScaler().fit(Xtr)
Str, Ste = scaler.transform(Xtr), scaler.transform(Xte)

print("%-10s %8s %10s %10s %16s" % ("kernel", "C", "train acc", "test acc", "support vectors"))
for kernel in ("linear", "rbf", "poly"):
    for C in (0.1, 1.0, 10.0):
        m = SVC(kernel=kernel, C=C, gamma="scale", degree=3, random_state=0).fit(Str, ytr)
        print("%-10s %8s %10.3f %10.3f %16d"
              % (kernel, C, m.score(Str, ytr), m.score(Ste, yte), len(m.support_)))

print()
m = SVC(kernel="linear", C=1.0).fit(Str, ytr)
print("linear, C=1: w = [%.4f, %.4f]  b = %.4f"
      % (m.coef_[0][0], m.coef_[0][1], m.intercept_[0]))
print("support vectors:", len(m.support_), "of", len(Str), "training rows")

print()
print("unscaled, to show it matters:")
for kernel in ("linear", "rbf"):
    m = SVC(kernel=kernel, C=1.0, gamma="scale").fit(Xtr, ytr)
    print("  %-8s train %.3f  test %.3f" % (kernel, m.score(Xtr, ytr), m.score(Xte, yte)))

kernel            C  train acc   test acc  support vectors
linear          0.1      0.524      0.556               20
linear          1.0      0.810      0.889               18
linear         10.0      0.810      0.889               13
rbf             0.1      0.524      0.556               21
rbf             1.0      0.857      0.889               15
rbf            10.0      0.905      0.889               14
poly            0.1      0.762      0.889               12
poly            1.0      0.857      1.000               12
poly           10.0      0.810      1.000               11

linear, C=1: w = [2.1774, 1.2564]  b = -2.0961
support vectors: 18 of 21 training rows

unscaled, to show it matters:
  linear   train 0.810  test 0.889
  rbf      train 0.810  test 1.000

Four things in that table, and all four belong in the journal.

Our own SVM is right. scikit-learn's linear SVC with C = 1 gave w = [2.1774, 1.2564] and b = -2.0961. Our own program, written from the hinge loss with plain sub-gradient steps, gave w = [2.2230, 1.1924] and b = -2.0817. Two independent programs agreeing to two decimal places on all three numbers is the strongest evidence available that the implementation is correct.

C = 0.1 is too small for every kernel. 0.524 training accuracy, which is worse than answering the commoner class. Under-penalised, the model gives up.

The number of support vectors falls as C rises. Linear: 20 at C = 0.1, 18 at C = 1, 13 at C = 10. A large C forces the model to take the training points seriously, so fewer of them end up inside the corridor.

The poly kernel scored 1.000 on the test set, and that is not a result. Nine test rows. One row is 0.111 of the accuracy, so 1.000 and 0.889 are one student apart. On a test set this small, rbf at 0.889 and poly at 1.000 have not been distinguished, and a write-up that declares poly the winner has read noise as a finding. Say the size of the test set beside every score.

Scaling. The unscaled runs came out at 0.810 and 0.889, which is no worse than the scaled ones, so on this dataset scaling did not decide anything. Scale anyway, and here is the honest reason: C and the RBF's gamma are defined in terms of distances, so their meaning changes when the units change. A C of 1 on features running to 98 is not the C of 1 in the table above, and a model tuned on one scale cannot be reused on another.

Procedure

1. Write the dataset, scale both features to the range 0 to 1, and split 70 to 30 with a seeded shuffle.
2. Implement the sub-gradient training loop: for each row compute y * (w.x + b); if it is below 1, apply both terms of the update; if not, apply only the shrink. Reduce the step size as the epoch number rises.
3. Train for several values of C and record w, b and both accuracies for each.
4. List the training points with the smallest margins: those are the support vectors.
5. Plot the points, the boundary and the two margin lines.
6. Run SVC with the linear, rbf and poly kernels at three values of C, and record the number of support vectors each keeps.
7. Compare scikit-learn's w and b with your own.
8. Run once without scaling and say what changed.

Observations

Result

A linear soft-margin Support Vector Machine was implemented from the hinge loss and trained by sub-gradient descent on the thirty-student dataset, scaled and split 21 to 9. C was tuned over five values: below 1 the model failed, reaching 0.571 training accuracy, and from 1 upward it reached 0.905 training and 0.667 test. Its weights, [2.2230, 1.1924] with bias -2.0817, agree to two decimal places with scikit-learn's linear SVC. The five smallest margins identified the support vectors, of which the two smallest were the dataset's two deliberate exceptions, both accepted as errors by the soft margin. Across three kernels and three values of C, test accuracy on nine rows ranged from 0.556 to 1.000, a spread of four students, and the number of support vectors fell as C rose.

Where marks are lost

Not scaling, and not saying why. C and gamma are distances. Scale, or justify not scaling.

Reporting one value of C. MU says "optimize its parameters". A single run has optimised nothing; show the table.

Calling 1.000 on nine rows a result. Quote the size of the test set beside the score.

Labelling the classes 0 and 1. The margin y * (w.x + b) needs y to be +1 and -1. With 0 and 1 every margin for the zero class is zero and the model never learns.

Never naming the support vectors. They are the point of the model. List them.

A constant learning rate. The steps must shrink or the weights oscillate around the answer.

Saying an SVM "finds the best line" with no definition of best. Best means the widest corridor, subject to the price C on violations.

For the journal

Aim; the line, the labels +1 and -1, the margin and the hinge loss written out; the training program; the table of C against weights and accuracy; the support vectors listed with their margins; the plot with the boundary and both margin lines; the scikit-learn table across kernels and C; the comparison of your weights with scikit-learn's; both observation tables; the result; one paragraph analysing which setting you would ship and why.

Quick revision

• An SVM finds the boundary with the widest empty corridor between the classes.
• Labels are +1 and -1. The margin of a point is y * (w.x + b).
• Support vectors are the points closest to the boundary. Only they decide it.
• The soft margin allows violations and charges C for each.
• Small C: wide corridor, many mistakes. Large C: narrow corridor, few mistakes, and a risk of overfitting.
• The objective is (1/2)|w|^2 + C * sum of hinge losses.
• Hinge loss is max(0, 1 - y*(w.x + b)): zero outside the corridor.
• Kernels: linear, rbf (curved, the default), poly.
• The kernel trick draws a curve without computing one, by changing how similarity is measured.
• Scale the features: C and gamma are measured in the units of the data.
• Fewer support vectors at a larger C.

Questions you must be able to answer

1. What does an SVM maximise? The margin: the width of the empty corridor between the two classes, measured to the nearest points on each side.

2. What is a support vector? A training point on or inside the margin. It is one of the few points that decide where the boundary goes; moving a point far from the boundary changes nothing.

3. What does C do? It sets the price of letting a training point violate the margin. Small C prefers a wide corridor and tolerates errors; large C insists on classifying the training points and narrows the corridor.

4. What happened at C = 0.01 in your run? The model reached 0.571 on the training rows and 0.444 on the test rows: the penalty was too small to make it separate anything.

5. What is the hinge loss? max(0, 1 - y*(w.x + b)). It is zero for a point at least one unit outside the boundary on the right side, and rises linearly as the point moves inside the corridor and beyond it.

6. Why must the labels be +1 and -1? Because the margin is the label times the signed distance, and that expression only tells the two sides apart when the labels have opposite signs.

7. What is the kernel trick, in one sentence? Replacing the ordinary dot product with another similarity function, so that a straight boundary in the new space of similarities becomes a curved boundary in the original one, without ever constructing that space.

8. Two of your support vectors had negative margins. Is the model broken? No. A negative margin means the point is on the wrong side, and the soft margin is what allows that. Both were the dataset's deliberate exceptions, and accepting them bought a wider corridor for everyone else.

9. Your poly kernel scored 1.000 on the test set. Is it the best model? Not on this evidence. The test set has nine rows, so 1.000 is one student away from 0.889, and several settings are within that. Report the figure with the size of the test set and say the difference is not measurable here.

10. Does the SVM need scaled features? It works without them here, but C and the RBF gamma are defined in terms of distances, so their meaning changes with the units. Scale, so that a tuned value means the same thing on the next dataset.