The Problem a Support Vector Machine Solves
Picture two groups of points on a sheet of paper, red and blue, and suppose a straight line can separate them. Usually there are infinitely many lines that do the job. Some pass very close to a red point, others brush against a blue one. All of them classify the training data perfectly, but they will not all behave the same way on new points.
A support vector machine (SVM) answers the question of which line to pick with a specific rule: choose the one that leaves the widest possible gap between the two classes. That gap is called the margin, and the idea is that a boundary with lots of room on both sides is less likely to be fooled by a new point that lands slightly off from where the training points were. In more than two dimensions the line becomes a plane, and in general a hyperplane, but the principle does not change.
Support Vectors and the Maximum Margin
The points that sit exactly on the edge of the margin are the support vectors. They are the only training points that determine where the boundary goes. Move any other point around (without crossing the margin) and the solution stays exactly the same. Remove a support vector and the boundary shifts.
This is an unusual property. Most models are influenced a little by every training example. An SVM is defined by a small subset of them, often a small fraction of the dataset, which makes the final model compact and gives a concrete answer to the question «which examples were hard?»
Mathematically, maximizing the margin is equivalent to minimizing the norm of the weight vector subject to every point being on the correct side with some minimum distance. That is a convex quadratic optimization problem. Convex means there is a single global optimum and no local minima to get stuck in, which was a big selling point in the 1990s, when training neural networks was notoriously finicky.
Soft Margins for Messy Data
Real data is rarely perfectly separable. A few mislabeled points, or classes that genuinely overlap, make the strict version of the problem impossible to solve. Corinna Cortes and Vladimir Vapnik addressed this in their 1995 paper «Support-Vector Networks» by introducing the soft margin. Each point gets a slack variable that allows it to fall inside the margin or even on the wrong side, and the objective pays a penalty for every unit of slack.
The penalty is controlled by a parameter usually called C. A large C punishes violations heavily, so the model bends to classify almost every training point correctly and risks overfitting. A small C tolerates more violations in exchange for a wider, simpler margin. Tuning C is one of the two main decisions when training an SVM. The other is the kernel.
The Kernel Trick
A straight line cannot separate two concentric circles of points, one inside the other. But if each point (x, y) is mapped to three dimensions by adding a new coordinate x² + y², the inner circle ends up low and the outer circle ends up high, and a flat plane separates them easily. Many problems that are not linearly separable in their original space become separable after mapping to a higher-dimensional one.
The catch is cost. Explicitly mapping data into a space with thousands or millions of dimensions is expensive, and some useful mappings go to infinite dimensions. The kernel trick avoids the mapping entirely. The SVM’s optimization and its prediction rule only ever need dot products between pairs of points. A kernel function computes the dot product in the high-dimensional space directly from the original coordinates, without ever building the high-dimensional vectors.
Boser, Guyon and Vapnik combined this trick with the maximum margin classifier in 1992. The common kernels are the polynomial kernel, which corresponds to all feature products up to a certain degree, and the radial basis function (RBF) or Gaussian kernel, whose feature space is infinite-dimensional. The RBF kernel has its own parameter, gamma, which controls how far the influence of a single training point reaches. A large gamma makes each point’s influence very local and the boundary very wiggly. A small gamma makes it smooth.
Which functions count as valid kernels is governed by Mercer’s theorem: the kernel must produce a positive semi-definite matrix for any set of points. This opened the door to kernels built for specific data types, such as string kernels for text and DNA sequences, or graph kernels for molecules, where there is no natural vector representation to start from.
Training at Scale
The quadratic program behind an SVM involves a matrix with one entry per pair of training points. For 100,000 examples, that is ten billion entries. General-purpose solvers could not handle this, so specialized algorithms were developed. John Platt’s Sequential Minimal Optimization (SMO), published in 1998, broke the problem into the smallest possible subproblems (two variables at a time) that can be solved analytically. It became the basis for LIBSVM, the library by Chih-Chung Chang and Chih-Jen Lin that is still inside scikit-learn’s SVM classes today.
Even with SMO, kernel SVMs scale roughly between quadratically and cubically with the number of samples. For linear SVMs there are much faster solvers, like LIBLINEAR, that handle millions of examples. For kernel SVMs on large datasets, approximations such as random Fourier features (Rahimi and Recht, 2007) map the data into a finite space where a linear SVM can approximate the kernel version.
Where SVMs Were the Best Tool Available
For about fifteen years, SVMs were often the most accurate general-purpose classifier around. Thorsten Joachims showed in 1998 that linear SVMs worked very well for text categorization, where documents are represented as sparse vectors with tens of thousands of word dimensions and the classes tend to be linearly separable. Spam filters and news classifiers used them widely.
On the MNIST handwritten digit benchmark, DeCoste and Schölkopf reported a 0.56% test error in 2002 using a polynomial kernel SVM trained with «virtual» support vectors (shifted copies of the support vectors that teach the model small translations do not matter). That was competitive with the convolutional networks of the time. In bioinformatics, SVMs were used for protein classification, gene expression analysis for cancer subtypes, and splice site detection. In computer vision, the Dalal and Triggs pedestrian detector from 2005 combined histogram of oriented gradients (HOG) features with a linear SVM and became a standard method for years.
What Changed After Deep Learning
The same property that made SVMs attractive, a fixed kernel chosen before training, also limits them. The kernel decides what «similar» means, and if it is the wrong notion of similarity for the problem, no amount of training will fix it. Deep networks learn the representation and the classifier together. Once there was enough data and GPU compute, learned features beat hand-designed features plus an SVM on images, audio and eventually text.
SVMs have not disappeared. They remain a good option on small to medium datasets with a clear feature representation, particularly when the number of features is large compared to the number of samples, as in some genomics and spectroscopy problems. They are also still used as the final classifier on top of features extracted from a pre-trained neural network. Their one-class variant is used for novelty detection, and support vector regression uses the same margin idea to fit a tube around the data instead of separating it.
Reflection
The SVM made an idea very explicit: of all the boundaries that fit the data, prefer the one that sits farthest from the examples. That preference comes from statistical learning theory, and it held up in practice. It is also why a model trained on thousands of points ends up defined by a handful of them. Even where deep networks now do better, the central questions are the same ones the SVM asked directly: how much room there is between the classes, and what it means for two data points to be similar.
By: Max Johnson B.
Deja una respuesta