UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 7.6 Free with a free account
Classifying Data with Support Vector Machines
Introduction to Artificial Intelligence · Chapter 7: Machine Learning, NLP, and PerceptionSection 7.6 · lesson 54 of 6912 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Reasoning Under Uncertainty: Probabilistic Foundations →← Making Choices with Decision NetworksNext lesson: Reasoning Under Uncertainty: Probabilistic Foundations →
In this lesson
How support vector machines find the widest margin and use kernels.
- Explain the margin and why only support vectors decide the boundary
- Classify new points using an SVM's score and margin
- Describe how the C setting trades margin width against training errors
- Apply the kernel trick and choose among linear, polynomial and RBF kernels
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,731 words). Read along, or search it.
Opening Question
A Road Between Two Towns
Two towns sit on a map, and a road must run between them. Many routes would keep the towns apart. One hugs the first town, and another grazes the second. The sensible plan is a road that stays as far as possible from both. A support vector machine, or SVM, applies the same thinking to labeled data. Which line should it draw, and why that one?
Linear Score
Weights, Bias and the Hyperplane
An SVM is a supervised model, so it follows the workflow from Section 7.1: split the data, train, tune settings on validation data, and test. To keep it simple, each example has numeric features, and one of two labels, written plus one and minus one. A straight boundary can be written as a score: f of x equals w dot x, plus b. The model learns the numbers w and b. A positive score predicts plus one, and a negative score predicts minus one. The boundary is where the score is exactly zero. With two features it's a line. With more, it's a flat surface called a hyperplane.
Margin
Widest Strip and the Support Vectors
The margin is the width of the empty strip around the boundary, measured out to the nearest training point on each side. A wide margin helps, because new points that resemble the training data are less likely to land on the wrong side. The SVM picks the boundary with the largest margin. The training points sitting exactly on the edge of the strip are the support vectors. They alone decide where the boundary goes. Any other point could move a little, or vanish, and the boundary wouldn't change. The scores are scaled so that support vectors score exactly plus one or minus one. Then the margin is two, divided by the length of w. So the widest margin is the same as the shortest w.
Worked Example
Six Points and One Boundary
Six points. The minus-one group is at one, one; two, one; and one, two. The plus-one group is at three, three; four, three; and three, four. Training a hard-margin linear SVM gives this score: two thirds of x1, plus two thirds of x2, minus three. The boundary is where that's zero: the line x1 plus x2 equals four and a half. The two thin edge lines sit where the score is minus one, and plus one. Three points lie exactly on those edges: two, one and one, two below, and three, three above. Those are the support vectors.
Checking Scores
A Margin 2.12 Wide
Check with the scores. One, one scores minus 1.67, beyond the edge. Two, one and one, two score exactly minus one: on the edge. Three, three scores plus one. And four, three and three, four score plus 1.67. The length of w is about 0.943, so the margin is two over 0.943: 2.12 wide. Delete four, three and retrain, and the same boundary comes back. It was never a support vector.
Prediction
Classifying New Points by Score
To classify a new point, compute its score. Three, two scores plus 0.33, so the model predicts plus one. Two, two scores minus 0.33, so it predicts minus one. Both scores lie between minus one and plus one, so both points fall inside the strip, and the model isn't confident about either. The size of a score is a rough measure of confidence, because a point's distance from the boundary is its score, divided by the length of w.
Quick Check
Which New Point Moves the Boundary
Quick check. Two new points join the plus-one group: five, five, and two, three. The model is retrained. Which new point changes the boundary? Pause, and decide. Only two, three. Its score is two thirds of five, minus three: plus 0.33. That's inside the strip, which a hard margin forbids, so the boundary must move. Five, five scores plus 3.67, far beyond the edge. Like four, three, it would never be a support vector. Both is the tempting answer, but only points on or inside the margin can shape it.
Soft Margin
Allowing Violations at a Price
A hard margin demands perfection: every training point on the correct side, and outside the strip. That works only when a straight line can separate the groups, and it's fragile. One stray point can tilt the boundary, squeeze the margin, or make the demand impossible. A soft margin relaxes it. Points may sit inside the strip, or even on the wrong side, but each violation is charged a penalty. A setting called C sets how heavy that penalty is.
Tuning C
Narrow Fit Versus Wide Margin
A large C punishes violations hard. The model works to fit every training point, and accepts a narrow margin. A small C tolerates violations. It keeps a wide margin, and ignores a few awkward points. In one example, a single plus-one point strays deep into the minus-one group. With C at 1,000, the boundary bends to fit it: no training mistakes, but a margin only 0.37 wide, held up by 3 support vectors. With C at 0.05, it leaves the stray on the wrong side: one mistake, but a margin 2.33 wide, with 25 support vectors. The narrow one is probably overfitting a single odd point, the same trade-off as with decision trees in Section 5.3. There's no universal best C: it's chosen on validation data.
Curved Boundaries
Adding X Squared as a Feature
Many problems need a curved boundary. Take one feature, x. The plus-one points sit at both ends, at minus three, minus two, two and three. The minus-one points sit in the middle: minus one, zero, and one. No single cut-off value separates them. Now add a second feature: x squared. The plus-one points get four and nine. The minus-one points get zero and one. And a flat line at x squared equals 2.5 separates them perfectly. That's the general strategy: map the data into a space with more features, where a straight boundary works. Seen back in the original space, it's a curve.
Kernel Trick
Dot Products Without New Features
The catch is cost. Building many new features for every example is slow, and some mappings would need infinitely many. The kernel trick avoids building them. Training an SVM, and predicting with it, use the data only through dot products between pairs of points: numbers measuring how alike two points are. A kernel function, K of x and z, returns the dot product the two points would have in the new space, computed straight from the original values. For the mapping from x to x and x squared, the kernel is x times z, plus x squared times z squared. Two original numbers, and no new features. The most popular kernel reaches a space with infinitely many features, and its formula still fits on one line.
Common Kernels
Linear, Polynomial and RBF
Three kernels cover most needs. The linear kernel is the plain dot product: a straight boundary. It suits many features, or nearly separable data, and it's a good first try. The polynomial kernel raises x dot z plus one to a degree d, giving smooth curves when features interact. The RBF, or Gaussian, kernel measures similarity by distance: nearby points are alike, far ones aren't. It can draw flexible, closed shapes, and it's a strong default when the shape is unknown. Its setting, gamma, controls how far one training point's influence reaches. A small gamma gives a wide reach and a smooth boundary. A large gamma gives a tiny reach, so the boundary can wrap around single points, and memorize the training data.
Worked Example
A Ring Around a Cluster
In one example, the training data is a ring of minus-one points around a cluster of plus-one points, 160 points in all. A linear kernel reaches only 56 percent on new data, close to guessing, because no straight line separates a ring from its center. An RBF kernel reaches 100 percent, with a boundary that closes around the inner group. One caution for every kernel: they depend on distances, so scale the features to similar ranges first, or one large-valued feature dominates.
Quick Check
Fixing an Overfit RBF Model
Quick check. An RBF model scores 100 percent on its training data, but only 70 percent on validation data. Which change would you try first? Pause, and decide. Lower gamma. A perfect training score with a big drop on new data is overfitting: the boundary is wrapping around single points. A smaller gamma widens each point's reach, and smooths the boundary. Lowering C would help too. Raising gamma, or raising C, pushes the model to fit the training data even more closely, which makes the gap worse.
Strengths and Limits
When SVMs Work Well
Strengths. SVMs work well with many features, even more features than examples. Only the support vectors matter, so the model can be compact. The wide-margin goal tends to resist overfitting. And kernels give curved boundaries, without building features by hand. Limits. Training can be slow on very large data sets. Features must be scaled, and the kernel and its settings chosen with care. A nonlinear kernel makes the model hard to interpret. And an SVM outputs scores, not probabilities: extra steps are needed to estimate those.
More Than Two Labels
One-Versus-Rest and One-Versus-One
An SVM separates exactly two groups. With k labels, several SVMs are trained, and their results combined. One-versus-rest trains one SVM per label, that label against all the others. The label whose SVM scores highest wins. One-versus-one trains an SVM for every pair of labels, k times k minus one, over two, and the label that wins the most pairwise votes is chosen. With 3 labels, both need 3 machines. With 5 labels, 5 against 10. With 10 labels, 10 against 45. One-versus-one trains more machines, but each sees only two labels' data, so each is smaller and faster to train.
Application
The Widest Road Between Towns
Back to the two towns. The SVM's road is the one that keeps the widest gap from both, and only the houses closest to the road decide where it runs. If a straight road can't do it, a kernel lets the road curve around a town, without ever drawing the new map. Compared with a decision tree from Section 5.3, an SVM is often more accurate on medium-sized problems with many features, but harder to explain.
Key Takeaways
Margins, Kernels and Multiclass SVMs
To sum up. An SVM picks the boundary with the widest margin, and the support vectors on its edge alone decide it. A hard margin demands perfect separation. A soft margin allows violations, and C sets their price. The kernel trick computes dot products in a richer space, without building it. Linear, polynomial and RBF kernels suit different shapes, tuned on validation data. And more than two labels are handled with one-versus-rest, or one-versus-one.
Think About It
Six Labels and a Million Examples
Here's something to think about. A data set has 6 labels and a million examples. Would you choose one-versus-rest or one-versus-one? And would an SVM be your first choice at all?
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Classifying Data with Support Vector Machines
What is a support vector machine?
What does the C parameter do in an SVM?
What is the kernel trick in SVMs?
How do you fix an RBF SVM that overfits?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →