The Soft Margin and the Kernel

Problem two: exclusive-or, and the mapping

# The soft margin and the kernel. Exclusive-or cannot be separated by any line;
# mapped to three dimensions it can. And the kernel trick computed BOTH ways.
import itertools, math

XOR = [((0, 0), -1), ((1, 1), -1), ((0, 1), +1), ((1, 0), +1)]
print("EXCLUSIVE-OR: (0,0) and (1,1) are one class, (0,1) and (1,0) the other.")
print("can ANY straight line w1*x + w2*y + b = 0 separate them? search a grid:")
found = 0
for w1 in [i / 2.0 for i in range(-8, 9)]:
    for w2 in [i / 2.0 for i in range(-8, 9)]:
        for b in [i / 2.0 for i in range(-8, 9)]:
            if all(lab * (w1 * x + w2 * y + b) > 0 for (x, y), lab in XOR):
                found += 1
print("   lines tried: %d      lines that separate: %d"
      % (17 ** 3, found))
print("   none. exclusive-or is NOT linearly separable, which is what defeated")
print("   the perceptron of the previous chapter.")
print()
print("MAP IT UP. send (x, y) to (x, y, x*y), a third dimension:")
for (x, y), lab in XOR:
    print("   (%d, %d) class %+d  ->  (%d, %d, %d)" % (x, y, lab, x, y, x * y))
print("   now the PLANE  x + y - 2*(x*y) = 0.5  separates them:")
for (x, y), lab in XOR:
    v = x + y - 2 * (x * y) - 0.5
    print("      (%d, %d, %d)  value %+.1f  side %+d   correct: %s"
          % (x, y, x * y, v, 1 if v > 0 else -1, lab == (1 if v > 0 else -1)))
print()
print("THE KERNEL TRICK. a polynomial kernel of degree 2 computes the inner")
print("product in the mapped space WITHOUT building it. take two points:")
A, B = (2.0, 3.0), (4.0, 1.0)

def phi(p):
    """The explicit degree-2 map, six numbers for two."""
    x, y = p
    return (x * x, y * y, math.sqrt(2) * x * y,
            math.sqrt(2) * x, math.sqrt(2) * y, 1.0)

explicit = sum(a * b for a, b in zip(phi(A), phi(B)))
kernel = (A[0] * B[0] + A[1] * B[1] + 1.0) ** 2
print("   A = %s   B = %s" % (A, B))
print("   phi(A) = (%s)" % ", ".join("%.4f" % v for v in phi(A)))
print("   phi(B) = (%s)" % ", ".join("%.4f" % v for v in phi(B)))
print("   explicit inner product of the two 6-vectors : %.6f" % explicit)
print("   the kernel (A.B + 1)**2, on the ORIGINAL 2  : %.6f" % kernel)
print("   the same number, and the second never built the six numbers.")
print()
print("THE SOFT MARGIN. one +1 point is placed INSIDE the -1 group, so no line")
print("separates the seven at all. C decides how much a violation costs.")
POS = [(3, 3), (4, 4), (4, 2), (0, 1)]        # (0,1) is the intruder
NEG = [(1, 1), (0, 2), (1, 0)]
PTS = [(p, +1) for p in POS] + [(p, -1) for p in NEG]

def hinge_objective(w, b, C):
    """0.5*|w|^2 + C * sum of hinge losses. The SVM's own objective."""
    reg = 0.5 * (w[0] ** 2 + w[1] ** 2)
    loss = sum(max(0.0, 1 - lab * (w[0] * x + w[1] * y + b)) for (x, y), lab in PTS)
    return reg + C * loss, reg, loss

print("   the intruder is (0, 1), labelled +1, surrounded by the -1 points.")
print("   C      | best objective | 0.5|w|^2 | total hinge loss | errors")
for C in (0.01, 0.05, 0.2, 1.0, 5.0):
    best = None
    for w1 in [i / 10.0 for i in range(-30, 31)]:
        for w2 in [i / 10.0 for i in range(-30, 31)]:
            for b in [i / 10.0 for i in range(-50, 51)]:
                obj, reg, loss = hinge_objective((w1, w2), b, C)
                if best is None or obj < best[0]:
                    err = sum(1 for (x, y), lab in PTS
                              if lab * (w1 * x + w2 * y + b) <= 0)
                    best = (obj, reg, loss, err, (w1, w2), b)
    print("   %6g | %14.4f | %8.4f | %16.4f | %d of 7"
          % (C, best[0], best[1], best[2], best[3]))
print()
print("   read the two middle columns against each other. as C rises, half the")
print("   squared norm rises 0.0000, 0.0250, 0.1700, 0.2500, which means the")
print("   MARGIN SHRINKS; and the hinge loss falls 6.0, 4.7, 2.7, 2.5, which")
print("   means the violations are being paid down. that is the whole trade.")
print()
print("   the error count is NOT monotonic, and it is not supposed to be: the")
print("   objective minimises the hinge loss, which charges for being close to")
print("   the boundary as well as for being on the wrong side of it.")
print()
print("   C is the regularization dial of chapter 50 with 1/C in place of lambda:")
print("   large C means little regularization, a narrow margin, few violations.")

Read the three blocks.

Exclusive-or. Four thousand nine hundred and thirteen candidate lines were tried and none separates the four points. This is not a failure of search; it is a theorem, and it is the problem that stopped the perceptron of The Artificial Neuron and the Perceptron.

The mapping. Send (x, y) to (x, y, xy). The four points become four points in three dimensions, and the plane x + y - 2xy = 0.5 separates them. A linear boundary in the new space is a non-linear boundary in the old one: back in two dimensions, that plane is the curve x + y - 2xy = 0.5.

The trick. phi sends a two-dimensional point to six numbers. The inner product of phi(A) and phi(B) is 144.000000. The kernel (A . B + 1)2, computed on the original two numbers, is 144.000000. The same number, and the second never built the six.** That is the kernel trick entire: since Support Vector Machines: The Margin showed the dual uses the data only through inner products, replacing every inner product with K runs the whole algorithm in the six-dimensional space at the cost of arithmetic on two numbers.

The soft margin. As C rises from 0.01 to 5, 0.5 ||w||2 rises 0.0000, 0.0250, 0.1700, 0.2500, so the margin shrinks; and the hinge loss falls 6.0, 4.7, 2.7, 2.5, so the violations are paid down**. The error count is not monotonic, which is honest: the objective minimises the hinge loss, and the hinge charges for being near the boundary as well as for being past it.

The standard kernels

A paper asks for these three by name.

The RBF kernel's feature space has infinitely many dimensions, and a boundary is still found in it in finite time, because the algorithm never enters that space. That is the sharpest statement of what the trick buys and a paper likes it.

gamma controls the reach of each training point. Large gamma makes each point influence only its immediate neighbourhood, giving a wiggly boundary and overfitting; small gamma makes the boundary smooth and can underfit. So an RBF SVM has two hyperparameters, C and gamma, and they are tuned together on a grid by cross-validation. That is the usual answer to "how is an SVM tuned".

What makes a function a kernel

Not every two-argument function is one, and the condition has a name.

Mercer's condition. K is a valid kernel if it is symmetric and the matrix K(x_i, x_j) formed from any finite set of points is positive semi-definite. If that holds, some mapping phi exists for which K is the inner product, and it need not be written down.

Two useful consequences. Kernels can be combined: the sum of two kernels is a kernel, and so is a positive multiple, and so is a product. And a kernel can be defined on objects that are not vectors at all, such as strings, trees or graphs, which is how SVMs are applied to text and to molecules.

Choosing between them

A paper asking which kernel to use expects a rule rather than a preference.

Linear when the number of features is large, especially larger than the number of instances, as in text. The data is usually already separable in such a space and a non-linear kernel only overfits.

RBF as the general-purpose default when the number of features is moderate and the boundary is unknown. It is the usual first choice.

Polynomial when interactions of a known degree are expected, for example when the effect of two features together matters.

And the practical warning from k-NN for Regression, and What Limits the Method: scale the features first. The RBF kernel measures a distance, and the polynomial an inner product, so a feature with a large numeric range dominates both, exactly as it dominates a nearest-neighbour search.

Distinctions

What it does not mean

The kernel does not map the data. It computes what the inner product would be if the data had been mapped. Nothing is ever mapped.

A kernel is not a distance. It is an inner product in some space; the RBF kernel is built from a distance but is not one.

The soft margin is not a way of handling curved boundaries. It handles violations of a linear boundary.

C is not the margin. It is the price of violating it, and 1/C behaves as the regularization strength lambda.

Not every function of two arguments is a kernel. Mercer's condition must hold.

A non-linear kernel is not always better. With more features than instances, a linear kernel usually wins, because the data is already separable and a richer kernel only fits noise.

Quick revision

• Soft margin: allow y_i (w . x_i + b) >= 1 - s_i with slack s_i >= 0, and minimise 0.5 ||w||2 + C * sum of s_i. Equivalently the hinge loss**, which charges for being inside the corridor as well as past the boundary.
• C is the exchange rate. Measured: as C rises, 0.5||w||2 rises 0.0000 to 0.2500, so the margin shrinks, while the hinge loss falls 6.0 to 2.5. 1/C plays the part of lambda** in Regularization.
• Exclusive-or: 4,913 candidate lines tried, 0 separate it. Mapped to (x, y, xy), the plane x + y - 2xy = 0.5 does.
• The kernel trick, both ways: the inner product of two explicit 6-vectors is 144.000000, and (A . B + 1)2 on the original two numbers is 144.000000**. The dual uses the data only through inner products, so replacing them with K runs the algorithm in the mapped space without entering it.
• Kernels: linear, polynomial (x.z + c)d, RBF exp(-gamma ||x - z||2) whose feature space is infinite dimensional, and sigmoid.
• RBF has two hyperparameters, C and gamma, tuned together by cross-validation. Large gamma overfits, small gamma underfits.
• Mercer's condition: symmetric and positive semi-definite. Kernels can be summed and multiplied, and defined on strings, trees and graphs.
• Scale the features first. And the soft margin fixes noise, the kernel fixes curvature; swapping them is the standard mistake.

Test yourself

1. What does the soft margin change, and what does C control? It replaces the requirement that every point satisfy the margin with the weaker requirement y_i (w . x_i + b) at least 1 - s_i for a non-negative slack, and adds C times the sum of the slacks to the objective. C is the price of a violation: it sets the exchange rate between a wide margin and few violations.

2. Write the SVM objective as an unconstrained loss and say what the hinge charges for. Half the squared norm of w, plus C times the sum over instances of the maximum of zero and 1 - y_i (w . x_i + b). The hinge charges both for being on the wrong side of the boundary and for being on the correct side but inside the margin corridor.

3. In this chapter's measurement, what happened as C rose? Half the squared norm rose from 0.0000 to 0.2500, meaning the margin shrank, while the total hinge loss fell from 6.0 to 2.5, meaning violations were paid down. The error count was not monotonic, because the objective minimises the hinge loss rather than the count.

4. Show that exclusive-or is not linearly separable, and give a mapping that fixes it. Searching 4,913 candidate lines over a grid of weights and offsets finds none that separates the four points. Mapping (x, y) to (x, y, xy) places the points in three dimensions, where the plane x + y - 2xy = 0.5 separates them; back in two dimensions that plane is a curve.

5. State the kernel trick and give the numerical demonstration from this chapter. The dual formulation uses the training data only through inner products, so replacing each inner product with a kernel function computes the inner product in some mapped space without performing the mapping. Here the explicit degree-two map sends two numbers to six, and the inner product of the two six-vectors is 144.000000, which is exactly what the kernel (A . B + 1) squared gives from the original two numbers.

6. Name three kernels and say what is remarkable about one of them. Linear, x . z. Polynomial, (x . z + c) to the power d. And the radial basis function, the exponential of minus gamma times the squared distance. The last is remarkable because its feature space has infinitely many dimensions, and a boundary is still found in it in finite time, because the algorithm never enters that space.

7. When would you use a linear kernel rather than an RBF one? When the number of features is large, especially larger than the number of instances, as in text classification. The data is then usually already separable in the original space, and a richer kernel would fit noise rather than structure.