Support Vector Machines: Maximum-Margin Separation and the Kernel Trick

Suppose red and blue are two classes in a training set. We want a line that puts every red point on one side and every blue point on the other. This data is linearly separable, so at least one such line exists. In fact, one separating line is easy to draw. Every red point lies above it, and every blue point lies below it. But this line runs rather close to the blue class. Another line also separates the data, but now it passes close to the red class. A tilted line works too. Correct classification alone does not tell us which of these choices is preferable. Imagine placing an empty corridor around a separator. Its walls remain parallel to the line, and we widen them until one wall would hit red or the other would hit blue. The corridor's width measures how much room the classifier has before a training point changes sides. Now slide the centre line inside that gap. If it moves down, the lower clearance shrinks. If it moves up, the upper clearance shrinks. The best position balances the nearest points on the two sides and maximizes the smaller clearance. The points that stop the two walls are special. Three red points touch the upper wall, and two blue points touch the lower wall. These are the support vectors, because they physically support the widest corridor. Points farther away do not determine the final position. We could move one of those distant points slightly without changing either wall. Move a support vector, however, and the maximum-margin separator generally has to move with it. So an SVM does not merely search for zero training errors. Among all separating hyperplanes, it chooses the one with the largest geometric margin. Next we will turn this corridor into an optimization problem.

A line in two dimensions, or a hyperplane in any dimension, can be written as w dot x plus b equals zero. The vector w is perpendicular to the separator, while b shifts it without changing its orientation. The expression w dot x plus b is a signed score. Positive scores lie on one side, negative scores lie on the other, and its sign becomes the predicted class. Let each training label y sub i be plus one for red and minus one for blue. Correct classification then has one compact condition: y sub i times the score must be positive. There is a scaling ambiguity. Multiplying both w and b by any positive number leaves the zero set unchanged, so it leaves the separating hyperplane unchanged. We use that freedom to make the closest signed scores equal to one. After this normalization, every red point must have score at least plus one, and every blue point must have score at most minus one. The support vectors are precisely the points where the combined inequality becomes an equality. The perpendicular distance from a point x to the central hyperplane is the absolute score divided by the length of w. Each wall has score one in magnitude, so each wall is one over the length of w from the centre. The full corridor therefore has width two over the length of w. To make that width large, we must make the length of w small. Squaring it changes neither the minimizing choice nor the geometry. We have reached the hard-margin optimization problem. Minimize one half w dot w, which is one half the squared length of the normal vector. The minimization is subject to one constraint per training example: y sub i times w dot x sub i plus b must be at least one. These inequalities say that every point lies outside the empty corridor on its proper side. Only a few of those constraints are tight at the solution. Those active constraints belong to the support vectors. The remaining points satisfy their inequalities with room to spare and do not pin the optimum. This completes the geometric derivation. A wide corridor became a small normal vector, correct classification became a family of inequalities, and the points touching equality became the support vectors.

Real classes often overlap. A red example may sit deep among blue examples, while a blue example may sit among red ones. No line can put every point on its requested side in this training set. If we insist on the hard-margin constraints, the optimization problem has no feasible answer. The red point below and the blue point above cannot both satisfy the same perfect separation. A soft-margin SVM relaxes each constraint with a nonnegative slack variable xi sub i. Instead of demanding a signed score of at least one, it permits the score to fall short by xi sub i. Draw the central separator and its two margin walls. A point outside its correct wall needs zero slack. A point inside the corridor needs some slack, because it has not reached the wall required by its label. This red point is not merely inside the margin. It lies on the blue side of the separator, so its slack exceeds one. The same is true in reverse for this blue point. Slack records the degree of each violation rather than pretending the data is perfectly separable. The new objective contains two costs. One half w dot w still rewards a wide margin. The sum of the slacks penalizes points that enter the margin or cross the separator, and the constant C controls how heavily that penalty is counted. This is not permission to ignore errors for free. Every violation raises the objective. The optimizer accepts a violation only when avoiding it would require a sufficiently narrower or more contorted decision boundary. With a smaller C, slack is relatively inexpensive. The optimizer is more willing to tolerate unusual training points in exchange for a broad, stable corridor. With a larger C, violations are expensive. The separator bends its linear choice as far as it can toward fitting difficult examples, often leaving a narrower margin. The drawing is schematic, but the trade is exact: margin width against total slack. Small C can underreact to genuine structure. Very large C can overreact to noise or mislabeled examples. In practice C is a regularization hyperparameter, chosen by validation rather than by demanding zero training error. Support vectors still matter in the soft-margin model. They now include points touching a margin wall and points lying inside or beyond it. These are the examples that exert force on the final decision boundary.

Now consider a different training set. The red examples form a compact inner cluster, while the blue examples make a ring around them. This is a simple nonlinear pattern with no noise and no overlap. Try a slanted line. It can place some blue points opposite the red cluster, but blue points remain on both sides. Rotating the line merely changes which part of the ring is misclassified. Move the line above the centre instead. The red points may all fall below it, but so do the blue points around the lower half of the ring. No translation fixes the problem either. There is a geometric reason, not just a failure of imagination. Join the outer blue points to form their convex hull. The entire red cluster lies inside that hull. A straight line divides the plane into two half-planes. If every blue vertex lies in one half-plane, then every convex combination of those vertices lies there too. The red points inside their hull therefore cannot all occupy the opposite half-plane. The useful feature here is not left versus right or up versus down. It is distance from the centre. Square that distance and call it q of x: x one squared plus x two squared. Every red point has a small value of q. Every blue point has a much larger value. A threshold at two separates them perfectly: red below two, blue above two. Back in the original plane, the threshold q equals two is a circle, not a line. So the data is nonlinear in its original coordinates. The next move is to change coordinates rather than abandon maximum-margin separation.

A feature map replaces each original input by a new vector. For this problem, map x one and x two to three quadratic features: x one squared, square root two times x one x two, and x two squared. At first I have placed the points in a flat copy of their familiar arrangement. Now apply the feature map. Each point moves to the three coordinates computed from its original two. The inner red points remain near the origin of feature space. The outer blue points rise onto a distant sheet because x one squared plus x two squared is large for every point on the ring. In this three-dimensional space, one flat plane separates the classes. Its equation is feature one plus feature three equals two. Red points lie below it, and blue points lie above it. This is ordinary linear separation again. We can place parallel margin planes around this separator, maximize their distance, and obtain support vectors exactly as before. The only change is that the vectors now live in feature space. Now compare the two spaces. On the left is the original input plane. On the right is the lifted feature space with its flat separating plane. The plane above is feature one plus feature three equals two. Substitute the definitions of those features and the same condition becomes x one squared plus x two squared equals two below. That equation draws this circle in the input plane. A linear decision surface in feature space has become a nonlinear decision boundary in the original coordinates. The construction works, but it seems expensive. A richer feature map may contain hundreds, millions, or even infinitely many coordinates. Writing and storing every lifted vector would defeat the purpose. The escape comes from noticing what the SVM calculation actually asks of those lifted vectors. It does not need to inspect their coordinates one at a time. It needs inner products between them.

Return to the quadratic feature map. To compare two lifted examples phi of x and phi of z, the SVM needs their inner product. Let us calculate that inner product once and see what remains. Multiply matching lifted coordinates. The first contribution is x one squared z one squared. The middle contribution contains the factor two, and the last is x two squared z two squared. Those three terms form a familiar square. They equal x one z one plus x two z two, all squared. But x one z one plus x two z two is simply the ordinary dot product x dot z. Therefore the lifted inner product is the square of one dot product in the original two-dimensional space. Define K of x z to be that squared dot product. Evaluating K gives exactly the number we would have obtained by constructing both three-dimensional feature vectors and taking their inner product. That replacement is the kernel trick. We behave as if the data had been lifted, while every computation stays in the original input space. The feature coordinates disappear, but their geometry remains in the kernel values. Why are inner products enough? At the optimum, the normal vector in feature space can be written as a weighted sum of lifted training examples. Each weight is alpha sub i times the label y sub i. To classify a new input, begin with w dot phi of x plus b. Substitute the weighted expansion of w, and the calculation becomes a sum of inner products between training features and the new feature vector. Now replace every lifted inner product by K of x sub i and x. Prediction can be performed without forming w and without explicitly forming phi of any example. Most coefficients alpha sub i are zero. Only support vectors have nonzero coefficients and contribute to the final sum. The same small set of geometrically decisive points now makes prediction sparse. Training can also be written entirely in terms of pairwise kernels. The dual objective contains K of x sub i and x sub j for pairs of training examples, together with nonnegative coefficients whose label-weighted sum is zero. The optimization therefore needs a matrix of pairwise kernel values, often called the Gram matrix. Once those values are available, the algorithm can operate as though it knew every lifted coordinate. A kernel supplies exactly the required feature-space inner product. Different kernels encode different notions of similarity. The linear kernel is the ordinary dot product, so it gives the original linear SVM. A polynomial kernel raises a shifted dot product to a degree d. Our quadratic example used degree two with no shift. Higher degrees represent richer interactions among the original coordinates. The radial basis kernel decreases exponentially with squared distance between two inputs. It corresponds to a very rich feature space and produces flexible local boundaries, with gamma controlling how quickly similarity falls away. A kernel is not magic permission to use any similarity formula. It must behave like a genuine inner product in some feature space. When it does, the maximum-margin optimization remains mathematically well formed. Let us connect the whole argument. First, maximum margin chooses the separator with the widest empty corridor. The nearest points become support vectors because their constraints pin that corridor in place. When classes overlap, slack variables measure margin violations, and C trades a wider corridor against the cost of those violations. When no straight boundary works, a feature map can lift the examples into a space where a hyperplane does work. The decision surface is linear there even though it is curved in the original coordinates. Finally, the kernel trick computes only the inner products required by training and prediction. It preserves the lifted geometry without paying the cost of explicitly writing the lifted vectors. That is the support vector machine in one connected picture: maximize geometric separation, let a small set of points determine the answer, tolerate overlap when necessary, and use kernels when the useful separation lives in a nonlinear feature space.