Support vector machines and kernels

Warm-up

One question before the lesson. Choose an answer and check it.

Try it yourself

Set C and watch the street widen or narrow, with each student’s hinge loss worked out, on the students marked by the pattern or by their real results. Then switch to an RBF kernel and raise γ, and watch training and validation accuracy pull apart.

Practice problems

Work each problem out on paper, then type your answer and press Check. Every problem has hints and a full solution.

Programming exercise

Write the pieces of an SVM in plain Python: distances and the margin, the hinge loss and the objective, training by subgradient descent, and the RBF kernel. Save svm.py and test_svm.py in the same folder, fill in each function in svm.py, and run the tests:

python test_svm.py

"""Support vector machines: programming exercise. Write the pieces of a support vector machine in plain Python: a line's valueand distance, the street's width, the hinge loss and the objective, trainingby subgradient descent, and the RBF kernel. Run the tests from this folder:     python test_svm.py A point x is a list of two numbers, such as [hours studied, hours slept]. Theweights w are a list of two numbers too, and b is a number. A result y is +1for passed and -1 for failed.""" import math  # noqa: F401  (you will need math.hypot and math.exp)  def decision(w, b, x):    """Return the line's value for x: w[0] * x[0] + w[1] * x[1] + b."""    raise NotImplementedError  def distance(w, b, x):    """Return how far x is from the line w . x + b = 0: the size of decision(w, b, x), divided by the length of w."""    raise NotImplementedError  def margin_width(w):    """Return the width of the street, 2 divided by the length of w, for w scaled so the support vectors give +1 and -1."""    raise NotImplementedError  def hinge(w, b, x, y):    """Return the hinge loss of point x with result y: max(0, 1 - y * decision(w, b, x))."""    raise NotImplementedError  def objective(w, b, C, xs, ys):    """Return the soft margin's objective: half the squared length of w, plus C times the total hinge loss of the points."""    raise NotImplementedError  def train(xs, ys, C, steps, rate):    """Train a soft-margin SVM by subgradient descent, and return (w, b).     Start from w = [0, 0] and b = 0. Each step, find the points whose    y * decision(w, b, x) is less than 1. The objective's slope for w is w    minus C times the sum of y * x over those points, and for b it is minus C    times the sum of their y. Move w and b against their slopes, by rate times    each slope, all at once.    """    raise NotImplementedError  def rbf(x, z, gamma):    """Return the RBF kernel: e to the power of -gamma times the squared distance between x and z."""    raise NotImplementedError  def kernel_decision(xs, ys, alphas, b, x, gamma):    """Return a kernel SVM's value for x: the sum of alphas[i] * ys[i] * rbf(xs[i], x, gamma) over every point, plus b."""    raise NotImplementedError 

Stuck? Write decision first: the other functions use it. train moves w and b against the objective’s slope: w’s slope is w minus C times the sum of yᵢxᵢ over the students whose hinge loss is above 0, and b’s is minus C times the sum of their yᵢ. The Solution tab has one way to write each function.

In practice: SVMs in real projects

Scale the inputs. An SVM measures distances, so an input measured in large units drowns out the others, as with k-nearest neighbours in Lesson 6. Standardise each input first, for example with scikit-learn’s StandardScaler in a pipeline, fitted on the training data only.

Choosing C and γ. Try values spaced by factors of 10 (0.01, 0.1, 1, 10 and so on) for both, scored on a validation set or by cross-validation; scikit-learn’s GridSearchCV does this. scikit-learn’s SVC starts at C = 1 and γ = "scale", which is 1 divided by the number of inputs times the variance of all the inputs.

Size and speed. A kernel SVM compares training examples in pairs, so training time grows at least with the square of their number, and past tens of thousands of examples it gets slow. For large or sparse data, such as text, a linear SVM (LinearSVC, or SGDClassifier with hinge loss) scales far better. SVC gives probabilities only if asked (probability=True), by fitting an extra model on top.

Test your knowledge

1. 01What is the margin of a linear classifier, and why maximise it?Show answer

   The distance from the boundary to the nearest training examples. Many lines may separate the training data; the one with the widest margin leaves the most room for new examples that land a little away from the training ones.

2. 02What are support vectors?Show answer

   The training examples on the edges of the margin, or inside it. The boundary depends only on them: moving any other example, without it crossing into the margin, leaves the boundary where it is.

3. 03What does C control in a soft-margin SVM?Show answer

   How much each unit of hinge loss costs against the width of the margin. A small C allows a wide margin with more examples inside it; a large C narrows the margin to make fewer training mistakes, and can overfit.

4. 04What is the kernel trick?Show answer

   An SVM uses its inputs only through dot products between examples. A kernel computes the dot product of a larger set of features straight from the original inputs, so the SVM can draw curved boundaries without ever building those features.

5. 05What does γ do in an RBF kernel?Show answer

   It sets how quickly similarity falls with distance. A large γ lets each example affect only its close neighbours, so the boundary can wrap around single examples and overfit; a small γ gives smooth boundaries. γ is chosen with C on a validation set.

Exit ticket

One last question on the main idea of the lesson.