programming assignment support vector machines

SVM Machine Learning Tutorial – What is the Support Vector Machine Algorithm, Explained with Code Examples

By Milecia McGregor

Most of the tasks machine learning handles right now include things like classifying images, translating languages, handling large amounts of data from sensors, and predicting future values based on current values. You can choose different strategies to fit the problem you're trying to solve.

The good news? There's an algorithm in machine learning that'll handle just about any data you can throw at it. But we'll get there in a minute.

Supervised vs Unsupervised learning

Two of the most commonly used strategies in machine learning include supervised learning and unsupervised learning.

What is supervised learning?

Supervised learning is when you train a machine learning model using labelled data. It means that you have data that already have the right classification associated with them. One common use of supervised learning is to help you predict values for new data.

With supervised learning, you'll need to rebuild your models as you get new data to make sure that the predictions returned are still accurate. An example of supervised learning would be labeling pictures of food. You could have a dataset dedicated to just images of pizza to teach your model what pizza is.

What is unsupervised learning?

Unsupervised learning is when you train a model with unlabeled data. This means that the model will have to find its own features and make predictions based on how it classifies the data.

An example of unsupervised learning would be giving your model pictures of multiple kinds of food with no labels. The dataset would have images of pizza, fries, and other foods and you could use different algorithms to get the model to identify just the images of pizza without any labels.

So what's an algorithm?

When you hear people talk about machine learning algorithms, remember that they are talking about different math equations.

An algorithm is just a customizable math function. That's why most algorithms have things like cost functions, weight values, and parameter functions that you can interchange based on the data you're working with. At its core, machine learning is just a bunch of math equations that need to be solved really fast.

That's why there are so many different algorithms to handle different kinds of data. One particular algorithm is the support vector machine (SVM) and that's what this article is going to cover in detail.

What is an SVM?

Support vector machines are a set of supervised learning methods used for classification, regression, and outliers detection. All of these are common tasks in machine learning.

You can use them to detect cancerous cells based on millions of images or you can use them to predict future driving routes with a well-fitted regression model.

There are specific types of SVMs you can use for particular machine learning problems, like support vector regression (SVR) which is an extension of support vector classification (SVC).

The main thing to keep in mind here is that these are just math equations tuned to give you the most accurate answer possible as quickly as possible.

SVMs are different from other classification algorithms because of the way they choose the decision boundary that maximizes the distance from the nearest data points of all the classes. The decision boundary created by SVMs is called the maximum margin classifier or the maximum margin hyper plane.

How an SVM works

A simple linear SVM classifier works by making a straight line between two classes. That means all of the data points on one side of the line will represent a category and the data points on the other side of the line will be put into a different category. This means there can be an infinite number of lines to choose from.

What makes the linear SVM algorithm better than some of the other algorithms, like k-nearest neighbors, is that it chooses the best line to classify your data points. It chooses the line that separates the data and is the furthest away from the closet data points as possible.

A 2-D example helps to make sense of all the machine learning jargon. Basically you have some data points on a grid. You're trying to separate these data points by the category they should fit in, but you don't want to have any data in the wrong category. That means you're trying to find the line between the two closest points that keeps the other data points separated.

So the two closest data points give you the support vectors you'll use to find that line. That line is called the decision boundary.

The decision boundary doesn't have to be a line. It's also referred to as a hyperplane because you can find the decision boundary with any number of features, not just two.

Types of SVMs

There are two different types of SVMs, each used for different things:

• Simple SVM: Typically used for linear regression and classification problems.
• Kernel SVM: Has more flexibility for non-linear data because you can add more features to fit a hyperplane instead of a two-dimensional space.

Why SVMs are used in machine learning

SVMs are used in applications like handwriting recognition, intrusion detection, face detection, email classification, gene classification, and in web pages. This is one of the reasons we use SVMs in machine learning. It can handle both classification and regression on linear and non-linear data.

Another reason we use SVMs is because they can find complex relationships between your data without you needing to do a lot of transformations on your own. It's a great option when you are working with smaller datasets that have tens to hundreds of thousands of features. They typically find more accurate results when compared to other algorithms because of their ability to handle small, complex datasets.

Here are some of the pros and cons for using SVMs.

• Effective on datasets with multiple features, like financial or medical data.
• Effective in cases where number of features is greater than the number of data points.
• Uses a subset of training points in the decision function called support vectors which makes it memory efficient.
• Different kernel functions can be specified for the decision function. You can use common kernels, but it's also possible to specify custom kernels.
• If the number of features is a lot bigger than the number of data points, avoiding over-fitting when choosing kernel functions and regularization term is crucial.
• SVMs don't directly provide probability estimates. Those are calculated using an expensive five-fold cross-validation.
• Works best on small sample sets because of its high training time.

Since SVMs can use any number of kernels, it's important that you know about a few of them.

Kernel functions

These are commonly recommended for text classification because most of these types of classification problems are linearly separable.

The linear kernel works really well when there are a lot of features, and text classification problems have a lot of features. Linear kernel functions are faster than most of the others and you have fewer parameters to optimize.

Here's the function that defines the linear kernel:

In this equation, w is the weight vector that you want to minimize, X is the data that you're trying to classify, and b is the linear coefficient estimated from the training data. This equation defines the decision boundary that the SVM returns.

The polynomial kernel isn't used in practice very often because it isn't as computationally efficient as other kernels and its predictions aren't as accurate.

Here's the function for a polynomial kernel:

This is one of the more simple polynomial kernel equations you can use. f(X1, X2) represents the polynomial decision boundary that will separate your data. X1 and X2 represent your data.

Gaussian Radial Basis Function (RBF)

One of the most powerful and commonly used kernels in SVMs. Usually the choice for non-linear data.

Here's the equation for an RBF kernel:

In this equation, gamma specifies how much a single training point has on the other data points around it. ||X1 - X2|| is the dot product between your features.

More useful in neural networks than in support vector machines, but there are occasional specific use cases.

Here's the function for a sigmoid kernel:

In this function, alpha is a weight vector and C is an offset value to account for some mis-classification of data that can happen.

There are plenty of other kernels you can use for your project. This might be a decision to make when you need to meet certain error constraints, you want to try and speed up the training time, or you want to super tune parameters.

Some other kernels include : ANOVA radial basis, hyperbolic tangent, and Laplace RBF.

Now that you know a bit about how the kernels work under the hood, let's go through a couple of examples.

Examples with datasets

To show you how SVMs work in practice, we'll go through the process of training a model with it using the Python Scikit-learn library . This is commonly used on all kinds of machine learning problems and works well with other Python libraries.

Here are the steps regularly found in machine learning projects:

• Import the dataset
• Explore the data to figure out what they look like
• Pre-process the data
• Split the data into attributes and labels
• Divide the data into training and testing sets
• Train the SVM algorithm
• Make some predictions
• Evaluate the results of the algorithm

Some of these steps can be combined depending on how you handle your data. We'll do an example with a linear SVM and a non-linear SVM. You can find the code for these examples here .

Linear SVM Example

We'll start by importing a few libraries that will make it easy to work with most machine learning projects.

For a simple linear example, we'll just make some dummy data and that will act in the place of importing a dataset.

The reason we're working with numpy arrays is to make the matrix operations faster because they use less memory than Python lists. You could also take advantage of typing the contents of the arrays. Now let's take a look at what the data look like in a plot:

Once you see what the data look like, you can take a better guess at which algorithm will work best for you. Keep in mind that this is a really simple dataset, so most of the time you'll need to do some work on your data to get it to a usable state.

We'll do a bit of pre-processing on the already structured code. This will put the raw data into a format that we can use to train the SVM model.

Now we can create the SVM model using a linear kernel.

That one line of code just created an entire machine learning model. Now we just have to train it with the data we pre-processed.

That's how you can build a model for any machine learning project. The dataset we have might be small, but if you encounter a real-world dataset that can be classified with a linear boundary this model still works.

With your model trained, you can make predictions on how a new data point will be classified and you can make a plot of the decision boundary. Let's plot the decision boundary.

Non-Linear SVM Example

For this example, we'll use a slightly more complicated dataset to show one of the areas SVMs shine in. Let's import some packages.

This set of imports is similar to those in the linear example, except it imports one more thing. Now we can use a dataset directly from the Scikit-learn library.

The next step is to take a look at what this raw data looks like with a plot.

Now that you can see how the data are separated, we can choose a non-linear SVM to start with. This dataset doesn't need any pre-processing before we use it to train the model, so we can skip that step. Here's how the SVM model will look for this:

In this case, we'll go with an RBF (Gaussian Radial Basis Function) kernel to classify this data. You could also try the polynomial kernel to see the difference between the results you get. Now it's time to train the model.

You can start labeling new data in the correct category based on this model. To see what the decision boundary looks like, we'll have to make a custom function to plot it.

You have everything you need to plot the decision boundary for this non-linear data. We can do that with a few lines of code that use the Matlibplot library, just like the other plots.

When you have your data and you know the problem you're trying to solve, it really can be this simple.

You can change your training model completely, you can choose different algorithms and features to work with, and you can fine tune your results based on multiple parameters. There are libraries and packages for all of this now so there's not a lot of math you have to deal with.

Tips for real world problems

Real world datasets have some common issues because of how large they can be, the varying data types they hold, and how much computing power they can need to train a model.

There are a few things you should watch out for with SVMs in particular:

• Make sure that your data are in numeric form instead of categorical form. SVMs expect numbers instead of other kinds of labels.
• Avoid copying data as much as possible. Some Python libraries will make duplicates of your data if they aren't in a specific format. Copying data will also slow down your training time and skew the way your model assigns the weights to a specific feature.
• Watch your kernel cache size because it uses your RAM. If you have a really large dataset, this could cause problems for your system.
• Scale your data because SVM algorithms aren't scale invariant. That means you can convert all of your data to be within the ranges of [0, 1] or [-1, 1].

Other thoughts

You might wonder why I didn't go into the deep details of the math here. It's mainly because I don't want to scare people away from learning more about machine learning.

It's fun to learn about those long, complicated math equations and their derivations, but it's rare you'll be writing your own algorithms and writing proofs on real projects.

It's like using most of the other stuff you do every day, like your phone or your computer. You can do everything you need to do without knowing the how the processors are built.

Machine learning is like any other software engineering application. There are a ton of packages that make it easier for you to get the results you need without a deep background in statistics.

Once you get some practice with the different packages and libraries available, you'll find out that the hardest part about machine learning is getting and labeling your data.

I'm working on a neuroscience, machine learning, web-based thing! You should follow me on Twitter to learn more about it and other cool tech stuff.

Learn to code. Build projects. Earn certifications—All for free.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

1.4. Support Vector Machines #

Support vector machines (SVMs) are a set of supervised learning methods used for classification , regression and outliers detection .

The advantages of support vector machines are:

Effective in high dimensional spaces.

Still effective in cases where number of dimensions is greater than the number of samples.

Uses a subset of training points in the decision function (called support vectors), so it is also memory efficient.

Versatile: different Kernel functions can be specified for the decision function. Common kernels are provided, but it is also possible to specify custom kernels.

The disadvantages of support vector machines include:

If the number of features is much greater than the number of samples, avoid over-fitting in choosing Kernel functions and regularization term is crucial.

SVMs do not directly provide probability estimates, these are calculated using an expensive five-fold cross-validation (see Scores and probabilities , below).

The support vector machines in scikit-learn support both dense ( numpy.ndarray and convertible to that by numpy.asarray ) and sparse (any scipy.sparse ) sample vectors as input. However, to use an SVM to make predictions for sparse data, it must have been fit on such data. For optimal performance, use C-ordered numpy.ndarray (dense) or scipy.sparse.csr_matrix (sparse) with dtype=float64 .

1.4.1. Classification #

SVC , NuSVC and LinearSVC are classes capable of performing binary and multi-class classification on a dataset.

SVC and NuSVC are similar methods, but accept slightly different sets of parameters and have different mathematical formulations (see section Mathematical formulation ). On the other hand, LinearSVC is another (faster) implementation of Support Vector Classification for the case of a linear kernel. It also lacks some of the attributes of SVC and NuSVC , like support_ . LinearSVC uses squared_hinge loss and due to its implementation in liblinear it also regularizes the intercept, if considered. This effect can however be reduced by carefully fine tuning its intercept_scaling parameter, which allows the intercept term to have a different regularization behavior compared to the other features. The classification results and score can therefore differ from the other two classifiers.

As other classifiers, SVC , NuSVC and LinearSVC take as input two arrays: an array X of shape (n_samples, n_features) holding the training samples, and an array y of class labels (strings or integers), of shape (n_samples) :

After being fitted, the model can then be used to predict new values:

SVMs decision function (detailed in the Mathematical formulation ) depends on some subset of the training data, called the support vectors. Some properties of these support vectors can be found in attributes support_vectors_ , support_ and n_support_ :

SVM: Maximum margin separating hyperplane

SVM-Anova: SVM with univariate feature selection

1.4.1.1. Multi-class classification #

SVC and NuSVC implement the “one-versus-one” approach for multi-class classification. In total, n_classes * (n_classes - 1) / 2 classifiers are constructed and each one trains data from two classes. To provide a consistent interface with other classifiers, the decision_function_shape option allows to monotonically transform the results of the “one-versus-one” classifiers to a “one-vs-rest” decision function of shape (n_samples, n_classes) .

On the other hand, LinearSVC implements “one-vs-the-rest” multi-class strategy, thus training n_classes models.

See Mathematical formulation for a complete description of the decision function.

Note that the LinearSVC also implements an alternative multi-class strategy, the so-called multi-class SVM formulated by Crammer and Singer [ 16 ] , by using the option multi_class='crammer_singer' . In practice, one-vs-rest classification is usually preferred, since the results are mostly similar, but the runtime is significantly less.

For “one-vs-rest” LinearSVC the attributes coef_ and intercept_ have the shape (n_classes, n_features) and (n_classes,) respectively. Each row of the coefficients corresponds to one of the n_classes “one-vs-rest” classifiers and similar for the intercepts, in the order of the “one” class.

In the case of “one-vs-one” SVC and NuSVC , the layout of the attributes is a little more involved. In the case of a linear kernel, the attributes coef_ and intercept_ have the shape (n_classes * (n_classes - 1) / 2, n_features) and (n_classes * (n_classes - 1) / 2) respectively. This is similar to the layout for LinearSVC described above, with each row now corresponding to a binary classifier. The order for classes 0 to n is “0 vs 1”, “0 vs 2” , … “0 vs n”, “1 vs 2”, “1 vs 3”, “1 vs n”, . . . “n-1 vs n”.

The shape of dual_coef_ is (n_classes-1, n_SV) with a somewhat hard to grasp layout. The columns correspond to the support vectors involved in any of the n_classes * (n_classes - 1) / 2 “one-vs-one” classifiers. Each support vector v has a dual coefficient in each of the n_classes - 1 classifiers comparing the class of v against another class. Note that some, but not all, of these dual coefficients, may be zero. The n_classes - 1 entries in each column are these dual coefficients, ordered by the opposing class.

This might be clearer with an example: consider a three class problem with class 0 having three support vectors \(v^{0}_0, v^{1}_0, v^{2}_0\) and class 1 and 2 having two support vectors \(v^{0}_1, v^{1}_1\) and \(v^{0}_2, v^{1}_2\) respectively. For each support vector \(v^{j}_i\) , there are two dual coefficients. Let’s call the coefficient of support vector \(v^{j}_i\) in the classifier between classes \(i\) and \(k\) \(\alpha^{j}_{i,k}\) . Then dual_coef_ looks like this:

Plot different SVM classifiers in the iris dataset

1.4.1.2. Scores and probabilities #

The decision_function method of SVC and NuSVC gives per-class scores for each sample (or a single score per sample in the binary case). When the constructor option probability is set to True , class membership probability estimates (from the methods predict_proba and predict_log_proba ) are enabled. In the binary case, the probabilities are calibrated using Platt scaling [ 9 ] : logistic regression on the SVM’s scores, fit by an additional cross-validation on the training data. In the multiclass case, this is extended as per [ 10 ] .

The same probability calibration procedure is available for all estimators via the CalibratedClassifierCV (see Probability calibration ). In the case of SVC and NuSVC , this procedure is builtin in libsvm which is used under the hood, so it does not rely on scikit-learn’s CalibratedClassifierCV .

The cross-validation involved in Platt scaling is an expensive operation for large datasets. In addition, the probability estimates may be inconsistent with the scores:

the “argmax” of the scores may not be the argmax of the probabilities

in binary classification, a sample may be labeled by predict as belonging to the positive class even if the output of predict_proba is less than 0.5; and similarly, it could be labeled as negative even if the output of predict_proba is more than 0.5.

Platt’s method is also known to have theoretical issues. If confidence scores are required, but these do not have to be probabilities, then it is advisable to set probability=False and use decision_function instead of predict_proba .

Please note that when decision_function_shape='ovr' and n_classes > 2 , unlike decision_function , the predict method does not try to break ties by default. You can set break_ties=True for the output of predict to be the same as np.argmax(clf.decision_function(...), axis=1) , otherwise the first class among the tied classes will always be returned; but have in mind that it comes with a computational cost. See SVM Tie Breaking Example for an example on tie breaking.

1.4.1.3. Unbalanced problems #

In problems where it is desired to give more importance to certain classes or certain individual samples, the parameters class_weight and sample_weight can be used.

SVC (but not NuSVC ) implements the parameter class_weight in the fit method. It’s a dictionary of the form {class_label : value} , where value is a floating point number > 0 that sets the parameter C of class class_label to C * value . The figure below illustrates the decision boundary of an unbalanced problem, with and without weight correction.

SVC , NuSVC , SVR , NuSVR , LinearSVC , LinearSVR and OneClassSVM implement also weights for individual samples in the fit method through the sample_weight parameter. Similar to class_weight , this sets the parameter C for the i-th example to C * sample_weight[i] , which will encourage the classifier to get these samples right. The figure below illustrates the effect of sample weighting on the decision boundary. The size of the circles is proportional to the sample weights:

SVM: Separating hyperplane for unbalanced classes

SVM: Weighted samples

1.4.2. Regression #

The method of Support Vector Classification can be extended to solve regression problems. This method is called Support Vector Regression.

The model produced by support vector classification (as described above) depends only on a subset of the training data, because the cost function for building the model does not care about training points that lie beyond the margin. Analogously, the model produced by Support Vector Regression depends only on a subset of the training data, because the cost function ignores samples whose prediction is close to their target.

There are three different implementations of Support Vector Regression: SVR , NuSVR and LinearSVR . LinearSVR provides a faster implementation than SVR but only considers the linear kernel, while NuSVR implements a slightly different formulation than SVR and LinearSVR . Due to its implementation in liblinear LinearSVR also regularizes the intercept, if considered. This effect can however be reduced by carefully fine tuning its intercept_scaling parameter, which allows the intercept term to have a different regularization behavior compared to the other features. The classification results and score can therefore differ from the other two classifiers. See Implementation details for further details.

As with classification classes, the fit method will take as argument vectors X, y, only that in this case y is expected to have floating point values instead of integer values:

Support Vector Regression (SVR) using linear and non-linear kernels

1.4.3. Density estimation, novelty detection #

The class OneClassSVM implements a One-Class SVM which is used in outlier detection.

See Novelty and Outlier Detection for the description and usage of OneClassSVM.

1.4.4. Complexity #

Support Vector Machines are powerful tools, but their compute and storage requirements increase rapidly with the number of training vectors. The core of an SVM is a quadratic programming problem (QP), separating support vectors from the rest of the training data. The QP solver used by the libsvm -based implementation scales between \(O(n_{features} \times n_{samples}^2)\) and \(O(n_{features} \times n_{samples}^3)\) depending on how efficiently the libsvm cache is used in practice (dataset dependent). If the data is very sparse \(n_{features}\) should be replaced by the average number of non-zero features in a sample vector.

For the linear case, the algorithm used in LinearSVC by the liblinear implementation is much more efficient than its libsvm -based SVC counterpart and can scale almost linearly to millions of samples and/or features.

1.4.5. Tips on Practical Use #

Avoiding data copy : For SVC , SVR , NuSVC and NuSVR , if the data passed to certain methods is not C-ordered contiguous and double precision, it will be copied before calling the underlying C implementation. You can check whether a given numpy array is C-contiguous by inspecting its flags attribute.

For LinearSVC (and LogisticRegression ) any input passed as a numpy array will be copied and converted to the liblinear internal sparse data representation (double precision floats and int32 indices of non-zero components). If you want to fit a large-scale linear classifier without copying a dense numpy C-contiguous double precision array as input, we suggest to use the SGDClassifier class instead. The objective function can be configured to be almost the same as the LinearSVC model.

Kernel cache size : For SVC , SVR , NuSVC and NuSVR , the size of the kernel cache has a strong impact on run times for larger problems. If you have enough RAM available, it is recommended to set cache_size to a higher value than the default of 200(MB), such as 500(MB) or 1000(MB).

Setting C : C is 1 by default and it’s a reasonable default choice. If you have a lot of noisy observations you should decrease it: decreasing C corresponds to more regularization.

LinearSVC and LinearSVR are less sensitive to C when it becomes large, and prediction results stop improving after a certain threshold. Meanwhile, larger C values will take more time to train, sometimes up to 10 times longer, as shown in [ 11 ] .

Support Vector Machine algorithms are not scale invariant, so it is highly recommended to scale your data . For example, scale each attribute on the input vector X to [0,1] or [-1,+1], or standardize it to have mean 0 and variance 1. Note that the same scaling must be applied to the test vector to obtain meaningful results. This can be done easily by using a Pipeline :

See section Preprocessing data for more details on scaling and normalization.

Regarding the shrinking parameter, quoting [ 12 ] : We found that if the number of iterations is large, then shrinking can shorten the training time. However, if we loosely solve the optimization problem (e.g., by using a large stopping tolerance), the code without using shrinking may be much faster

Parameter nu in NuSVC / OneClassSVM / NuSVR approximates the fraction of training errors and support vectors.

In SVC , if the data is unbalanced (e.g. many positive and few negative), set class_weight='balanced' and/or try different penalty parameters C .

Randomness of the underlying implementations : The underlying implementations of SVC and NuSVC use a random number generator only to shuffle the data for probability estimation (when probability is set to True ). This randomness can be controlled with the random_state parameter. If probability is set to False these estimators are not random and random_state has no effect on the results. The underlying OneClassSVM implementation is similar to the ones of SVC and NuSVC . As no probability estimation is provided for OneClassSVM , it is not random.

The underlying LinearSVC implementation uses a random number generator to select features when fitting the model with a dual coordinate descent (i.e. when dual is set to True ). It is thus not uncommon to have slightly different results for the same input data. If that happens, try with a smaller tol parameter. This randomness can also be controlled with the random_state parameter. When dual is set to False the underlying implementation of LinearSVC is not random and random_state has no effect on the results.

Using L1 penalization as provided by LinearSVC(penalty='l1', dual=False) yields a sparse solution, i.e. only a subset of feature weights is different from zero and contribute to the decision function. Increasing C yields a more complex model (more features are selected). The C value that yields a “null” model (all weights equal to zero) can be calculated using l1_min_c .

1.4.6. Kernel functions #

The kernel function can be any of the following:

linear: \(\langle x, x'\rangle\) .

polynomial: \((\gamma \langle x, x'\rangle + r)^d\) , where \(d\) is specified by parameter degree , \(r\) by coef0 .

rbf: \(\exp(-\gamma \|x-x'\|^2)\) , where \(\gamma\) is specified by parameter gamma , must be greater than 0.

sigmoid \(\tanh(\gamma \langle x,x'\rangle + r)\) , where \(r\) is specified by coef0 .

Different kernels are specified by the kernel parameter:

See also Kernel Approximation for a solution to use RBF kernels that is much faster and more scalable.

1.4.6.1. Parameters of the RBF Kernel #

When training an SVM with the Radial Basis Function (RBF) kernel, two parameters must be considered: C and gamma . The parameter C , common to all SVM kernels, trades off misclassification of training examples against simplicity of the decision surface. A low C makes the decision surface smooth, while a high C aims at classifying all training examples correctly. gamma defines how much influence a single training example has. The larger gamma is, the closer other examples must be to be affected.

Proper choice of C and gamma is critical to the SVM’s performance. One is advised to use GridSearchCV with C and gamma spaced exponentially far apart to choose good values.

RBF SVM parameters

Scaling the regularization parameter for SVCs

1.4.6.2. Custom Kernels #

You can define your own kernels by either giving the kernel as a python function or by precomputing the Gram matrix.

Classifiers with custom kernels behave the same way as any other classifiers, except that:

Field support_vectors_ is now empty, only indices of support vectors are stored in support_

A reference (and not a copy) of the first argument in the fit() method is stored for future reference. If that array changes between the use of fit() and predict() you will have unexpected results.

You can use your own defined kernels by passing a function to the kernel parameter.

Your kernel must take as arguments two matrices of shape (n_samples_1, n_features) , (n_samples_2, n_features) and return a kernel matrix of shape (n_samples_1, n_samples_2) .

The following code defines a linear kernel and creates a classifier instance that will use that kernel:

You can pass pre-computed kernels by using the kernel='precomputed' option. You should then pass Gram matrix instead of X to the fit and predict methods. The kernel values between all training vectors and the test vectors must be provided:

SVM with custom kernel

1.4.7. Mathematical formulation #

A support vector machine constructs a hyper-plane or set of hyper-planes in a high or infinite dimensional space, which can be used for classification, regression or other tasks. Intuitively, a good separation is achieved by the hyper-plane that has the largest distance to the nearest training data points of any class (so-called functional margin), since in general the larger the margin the lower the generalization error of the classifier. The figure below shows the decision function for a linearly separable problem, with three samples on the margin boundaries, called “support vectors”:

In general, when the problem isn’t linearly separable, the support vectors are the samples within the margin boundaries.

We recommend [ 13 ] and [ 14 ] as good references for the theory and practicalities of SVMs.

1.4.7.1. SVC #

Given training vectors \(x_i \in \mathbb{R}^p\) , i=1,…, n, in two classes, and a vector \(y \in \{1, -1\}^n\) , our goal is to find \(w \in \mathbb{R}^p\) and \(b \in \mathbb{R}\) such that the prediction given by \(\text{sign} (w^T\phi(x) + b)\) is correct for most samples.

SVC solves the following primal problem:

Intuitively, we’re trying to maximize the margin (by minimizing \(||w||^2 = w^Tw\) ), while incurring a penalty when a sample is misclassified or within the margin boundary. Ideally, the value \(y_i (w^T \phi (x_i) + b)\) would be \(\geq 1\) for all samples, which indicates a perfect prediction. But problems are usually not always perfectly separable with a hyperplane, so we allow some samples to be at a distance \(\zeta_i\) from their correct margin boundary. The penalty term C controls the strength of this penalty, and as a result, acts as an inverse regularization parameter (see note below).

The dual problem to the primal is

where \(e\) is the vector of all ones, and \(Q\) is an \(n\) by \(n\) positive semidefinite matrix, \(Q_{ij} \equiv y_i y_j K(x_i, x_j)\) , where \(K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) is the kernel. The terms \(\alpha_i\) are called the dual coefficients, and they are upper-bounded by \(C\) . This dual representation highlights the fact that training vectors are implicitly mapped into a higher (maybe infinite) dimensional space by the function \(\phi\) : see kernel trick .

Once the optimization problem is solved, the output of decision_function for a given sample \(x\) becomes:

and the predicted class correspond to its sign. We only need to sum over the support vectors (i.e. the samples that lie within the margin) because the dual coefficients \(\alpha_i\) are zero for the other samples.

These parameters can be accessed through the attributes dual_coef_ which holds the product \(y_i \alpha_i\) , support_vectors_ which holds the support vectors, and intercept_ which holds the independent term \(b\)

While SVM models derived from libsvm and liblinear use C as regularization parameter, most other estimators use alpha . The exact equivalence between the amount of regularization of two models depends on the exact objective function optimized by the model. For example, when the estimator used is Ridge regression, the relation between them is given as \(C = \frac{1}{alpha}\) .

The primal problem can be equivalently formulated as

where we make use of the hinge loss . This is the form that is directly optimized by LinearSVC , but unlike the dual form, this one does not involve inner products between samples, so the famous kernel trick cannot be applied. This is why only the linear kernel is supported by LinearSVC ( \(\phi\) is the identity function).

The \(\nu\) -SVC formulation [ 15 ] is a reparameterization of the \(C\) -SVC and therefore mathematically equivalent.

We introduce a new parameter \(\nu\) (instead of \(C\) ) which controls the number of support vectors and margin errors : \(\nu \in (0, 1]\) is an upper bound on the fraction of margin errors and a lower bound of the fraction of support vectors. A margin error corresponds to a sample that lies on the wrong side of its margin boundary: it is either misclassified, or it is correctly classified but does not lie beyond the margin.

1.4.7.2. SVR #

Given training vectors \(x_i \in \mathbb{R}^p\) , i=1,…, n, and a vector \(y \in \mathbb{R}^n\) \(\varepsilon\) -SVR solves the following primal problem:

Here, we are penalizing samples whose prediction is at least \(\varepsilon\) away from their true target. These samples penalize the objective by \(\zeta_i\) or \(\zeta_i^*\) , depending on whether their predictions lie above or below the \(\varepsilon\) tube.

The dual problem is

where \(e\) is the vector of all ones, \(Q\) is an \(n\) by \(n\) positive semidefinite matrix, \(Q_{ij} \equiv K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) is the kernel. Here training vectors are implicitly mapped into a higher (maybe infinite) dimensional space by the function \(\phi\) .

The prediction is:

These parameters can be accessed through the attributes dual_coef_ which holds the difference \(\alpha_i - \alpha_i^*\) , support_vectors_ which holds the support vectors, and intercept_ which holds the independent term \(b\)

where we make use of the epsilon-insensitive loss, i.e. errors of less than \(\varepsilon\) are ignored. This is the form that is directly optimized by LinearSVR .

1.4.8. Implementation details #

Internally, we use libsvm [ 12 ] and liblinear [ 11 ] to handle all computations. These libraries are wrapped using C and Cython. For a description of the implementation and details of the algorithms used, please refer to their respective papers.

The text is released under the CC-BY-NC-ND license , and code is released under the MIT license . If you find this content useful, please consider supporting the work by buying the book !

In-Depth: Support Vector Machines

< In Depth: Linear Regression | Contents | In-Depth: Decision Trees and Random Forests >

Support vector machines (SVMs) are a particularly powerful and flexible class of supervised algorithms for both classification and regression. In this section, we will develop the intuition behind support vector machines and their use in classification problems.

We begin with the standard imports:

Motivating Support Vector Machines ¶

As part of our disussion of Bayesian classification (see In Depth: Naive Bayes Classification ), we learned a simple model describing the distribution of each underlying class, and used these generative models to probabilistically determine labels for new points. That was an example of generative classification ; here we will consider instead discriminative classification : rather than modeling each class, we simply find a line or curve (in two dimensions) or manifold (in multiple dimensions) that divides the classes from each other.

As an example of this, consider the simple case of a classification task, in which the two classes of points are well separated:

A linear discriminative classifier would attempt to draw a straight line separating the two sets of data, and thereby create a model for classification. For two dimensional data like that shown here, this is a task we could do by hand. But immediately we see a problem: there is more than one possible dividing line that can perfectly discriminate between the two classes!

We can draw them as follows:

These are three very different separators which, nevertheless, perfectly discriminate between these samples. Depending on which you choose, a new data point (e.g., the one marked by the "X" in this plot) will be assigned a different label! Evidently our simple intuition of "drawing a line between classes" is not enough, and we need to think a bit deeper.

Support Vector Machines: Maximizing the Margin ¶

Support vector machines offer one way to improve on this. The intuition is this: rather than simply drawing a zero-width line between the classes, we can draw around each line a margin of some width, up to the nearest point. Here is an example of how this might look:

In support vector machines, the line that maximizes this margin is the one we will choose as the optimal model. Support vector machines are an example of such a maximum margin estimator.

Fitting a support vector machine ¶

Let's see the result of an actual fit to this data: we will use Scikit-Learn's support vector classifier to train an SVM model on this data. For the time being, we will use a linear kernel and set the C parameter to a very large number (we'll discuss the meaning of these in more depth momentarily).

To better visualize what's happening here, let's create a quick convenience function that will plot SVM decision boundaries for us:

This is the dividing line that maximizes the margin between the two sets of points. Notice that a few of the training points just touch the margin: they are indicated by the black circles in this figure. These points are the pivotal elements of this fit, and are known as the support vectors , and give the algorithm its name. In Scikit-Learn, the identity of these points are stored in the support_vectors_ attribute of the classifier:

A key to this classifier's success is that for the fit, only the position of the support vectors matter; any points further from the margin which are on the correct side do not modify the fit! Technically, this is because these points do not contribute to the loss function used to fit the model, so their position and number do not matter so long as they do not cross the margin.

We can see this, for example, if we plot the model learned from the first 60 points and first 120 points of this dataset:

In the left panel, we see the model and the support vectors for 60 training points. In the right panel, we have doubled the number of training points, but the model has not changed: the three support vectors from the left panel are still the support vectors from the right panel. This insensitivity to the exact behavior of distant points is one of the strengths of the SVM model.

If you are running this notebook live, you can use IPython's interactive widgets to view this feature of the SVM model interactively:

Beyond linear boundaries: Kernel SVM ¶

Where SVM becomes extremely powerful is when it is combined with kernels . We have seen a version of kernels before, in the basis function regressions of In Depth: Linear Regression . There we projected our data into higher-dimensional space defined by polynomials and Gaussian basis functions, and thereby were able to fit for nonlinear relationships with a linear classifier.

In SVM models, we can use a version of the same idea. To motivate the need for kernels, let's look at some data that is not linearly separable:

It is clear that no linear discrimination will ever be able to separate this data. But we can draw a lesson from the basis function regressions in In Depth: Linear Regression , and think about how we might project the data into a higher dimension such that a linear separator would be sufficient. For example, one simple projection we could use would be to compute a radial basis function centered on the middle clump:

We can visualize this extra data dimension using a three-dimensional plot—if you are running this notebook live, you will be able to use the sliders to rotate the plot:

We can see that with this additional dimension, the data becomes trivially linearly separable, by drawing a separating plane at, say, r =0.7.

Here we had to choose and carefully tune our projection: if we had not centered our radial basis function in the right location, we would not have seen such clean, linearly separable results. In general, the need to make such a choice is a problem: we would like to somehow automatically find the best basis functions to use.

One strategy to this end is to compute a basis function centered at every point in the dataset, and let the SVM algorithm sift through the results. This type of basis function transformation is known as a kernel transformation , as it is based on a similarity relationship (or kernel) between each pair of points.

A potential problem with this strategy—projecting $N$ points into $N$ dimensions—is that it might become very computationally intensive as $N$ grows large. However, because of a neat little procedure known as the kernel trick , a fit on kernel-transformed data can be done implicitly—that is, without ever building the full $N$-dimensional representation of the kernel projection! This kernel trick is built into the SVM, and is one of the reasons the method is so powerful.

In Scikit-Learn, we can apply kernelized SVM simply by changing our linear kernel to an RBF (radial basis function) kernel, using the kernel model hyperparameter:

Using this kernelized support vector machine, we learn a suitable nonlinear decision boundary. This kernel transformation strategy is used often in machine learning to turn fast linear methods into fast nonlinear methods, especially for models in which the kernel trick can be used.

Tuning the SVM: Softening Margins ¶

Our discussion thus far has centered around very clean datasets, in which a perfect decision boundary exists. But what if your data has some amount of overlap? For example, you may have data like this:

To handle this case, the SVM implementation has a bit of a fudge-factor which "softens" the margin: that is, it allows some of the points to creep into the margin if that allows a better fit. The hardness of the margin is controlled by a tuning parameter, most often known as $C$. For very large $C$, the margin is hard, and points cannot lie in it. For smaller $C$, the margin is softer, and can grow to encompass some points.

The plot shown below gives a visual picture of how a changing $C$ parameter affects the final fit, via the softening of the margin:

The optimal value of the $C$ parameter will depend on your dataset, and should be tuned using cross-validation or a similar procedure (refer back to Hyperparameters and Model Validation ).

Example: Face Recognition ¶

As an example of support vector machines in action, let's take a look at the facial recognition problem. We will use the Labeled Faces in the Wild dataset, which consists of several thousand collated photos of various public figures. A fetcher for the dataset is built into Scikit-Learn:

Let's plot a few of these faces to see what we're working with:

Each image contains [62×47] or nearly 3,000 pixels. We could proceed by simply using each pixel value as a feature, but often it is more effective to use some sort of preprocessor to extract more meaningful features; here we will use a principal component analysis (see In Depth: Principal Component Analysis ) to extract 150 fundamental components to feed into our support vector machine classifier. We can do this most straightforwardly by packaging the preprocessor and the classifier into a single pipeline:

For the sake of testing our classifier output, we will split the data into a training and testing set:

Finally, we can use a grid search cross-validation to explore combinations of parameters. Here we will adjust C (which controls the margin hardness) and gamma (which controls the size of the radial basis function kernel), and determine the best model:

The optimal values fall toward the middle of our grid; if they fell at the edges, we would want to expand the grid to make sure we have found the true optimum.

Now with this cross-validated model, we can predict the labels for the test data, which the model has not yet seen:

Let's take a look at a few of the test images along with their predicted values:

Out of this small sample, our optimal estimator mislabeled only a single face (Bush’s face in the bottom row was mislabeled as Blair). We can get a better sense of our estimator's performance using the classification report, which lists recovery statistics label by label:

We might also display the confusion matrix between these classes:

This helps us get a sense of which labels are likely to be confused by the estimator.

For a real-world facial recognition task, in which the photos do not come pre-cropped into nice grids, the only difference in the facial classification scheme is the feature selection: you would need to use a more sophisticated algorithm to find the faces, and extract features that are independent of the pixellation. For this kind of application, one good option is to make use of OpenCV , which, among other things, includes pre-trained implementations of state-of-the-art feature extraction tools for images in general and faces in particular.

Support Vector Machine Summary ¶

We have seen here a brief intuitive introduction to the principals behind support vector machines. These methods are a powerful classification method for a number of reasons:

• Their dependence on relatively few support vectors means that they are very compact models, and take up very little memory.
• Once the model is trained, the prediction phase is very fast.
• Because they are affected only by points near the margin, they work well with high-dimensional data—even data with more dimensions than samples, which is a challenging regime for other algorithms.
• Their integration with kernel methods makes them very versatile, able to adapt to many types of data.

However, SVMs have several disadvantages as well:

• The scaling with the number of samples $N$ is $\mathcal{O}[N^3]$ at worst, or $\mathcal{O}[N^2]$ for efficient implementations. For large numbers of training samples, this computational cost can be prohibitive.
• The results are strongly dependent on a suitable choice for the softening parameter $C$. This must be carefully chosen via cross-validation, which can be expensive as datasets grow in size.
• The results do not have a direct probabilistic interpretation. This can be estimated via an internal cross-validation (see the probability parameter of SVC ), but this extra estimation is costly.

With those traits in mind, I generally only turn to SVMs once other simpler, faster, and less tuning-intensive methods have been shown to be insufficient for my needs. Nevertheless, if you have the CPU cycles to commit to training and cross-validating an SVM on your data, the method can lead to excellent results.

Browse Course Material

Course info.

• Patrick Henry Winston

Departments

• Electrical Engineering and Computer Science

As Taught In

• Algorithms and Data Structures
• Artificial Intelligence
• Theory of Computation

Learning Resource Types

Mega-recitation 5: support vector machines.

Description: We start by discussing what a support vector is, using two-dimensional graphs as an example. We work Problem 1 of Quiz 4, Fall 2008: identifying support vectors, describing the classifier, and using a kernel function to project points into a new space.

Instructor: Mark Seifter

• Download video
• Download transcript

You are leaving MIT OpenCourseWare

• 🌐 All Sites
• _APDaga DumpBox
• _APDaga Tech
• _APDaga Invest
• _APDaga Videos
• 🗃️ Categories
• _Free Tutorials
• __Python (A to Z)
• __Internet of Things
• __Coursera (ML/DL)
• __HackerRank (SQL)
• __Interview Q&A
• _Artificial Intelligence
• __Machine Learning
• __Deep Learning
• _Internet of Things
• __Raspberry Pi
• __Coursera MCQs
• __Linkedin MCQs
• __Celonis MCQs
• _Handwriting Analysis
• __Graphology
• _Investment Ideas
• _Open Diary
• _Troubleshoots
• _Freescale/NXP
• 📣 Mega Menu
• _Logo Maker
• _Youtube Tumbnail Downloader
• 🕸️ Sitemap

Coursera: Machine Learning (Week 7) [Assignment Solution] - Andrew NG

Recommended Machine Learning Courses: Coursera: Machine Learning    Coursera: Deep Learning Specialization Coursera: Machine Learning with Python Coursera: Advanced Machine Learning Specialization Udemy: Machine Learning LinkedIn: Machine Learning Eduonix: Machine Learning edX: Machine Learning Fast.ai: Introduction to Machine Learning for Coders

• ex6.m - Octave/MATLAB script for the first half of the exercise
• ex6data1.mat - Example Dataset 1
• ex6data2.mat - Example Dataset 2
• ex6data3.mat - Example Dataset 3
• svmTrain.m - SVM training function
• svmPredict.m - SVM prediction function
• plotData.m - Plot 2D data
• visualizeBoundaryLinear.m - Plot linear boundary
• visualizeBoundary.m - Plot non-linear boundary
• linearKernel.m - Linear kernel for SVM
• [*] gaussianKernel.m - Gaussian kernel for SVM
• [*] dataset3Params.m - Parameters to use for Dataset 3
• ex6 spam.m - Octave/MATLAB script for the second half of the exercise
• spamTrain.mat - Spam training set
• spamTest.mat - Spam test set
• emailSample1.txt - Sample email 1
• emailSample2.txt - Sample email 2
• spamSample1.txt - Sample spam 1
• spamSample2.txt - Sample spam 2
• vocab.txt - Vocabulary list
• getVocabList.m - Load vocabulary list
• porterStemmer.m - Stemming function
• readFile.m - Reads a file into a character string
• submit.m - Submission script that sends your solutions to our servers
• [*] processEmail.m - Email preprocessing
• [*] emailFeatures.m - Feature extraction from emails
• Video - YouTube videos featuring Free IOT/ML tutorials

gaussianKernel.m :

Dataset3params.m :, processemail.m :, check-out our free tutorials on iot (internet of things):.

emailFeatures.m :

26 comments.

processEmail code is not running in matlab , it is showing the following error in the command prompt : !! Submission failed: unexpected error: Error using fprintf Function is not defined for 'cell' inputs. Error from file:/MATLAB Drive/machine-learning-ex/ex6/processEmail.m This is line 114 : fprintf('%s ', str); How to resolve it . And , error 2 is catch str = ''; continue; in the above line it is telling variable assigned to variable "str" might be unused . Function:processEmail On line:114 And third error is : word_indices = {word_indices; index}; In the above line it is telling variable "word_indices" tend to change size on every loop iteration . Consider preallocating for speed .

All the above errors mentioned are in the processemail part only .

Hi Alankar, First of all, These are not Errors, These are warnings. You might have made some silly mistakes in your code. I feel you haven't understood the code I have provided above. Please try to understand that and then write you logic. Don't just copy paste blindly.

In this line of code: coderesult = zeros(length(C_list)+length(sigma_list),3) you would get a 16x3 matrix since both arrays are 8 units long. However, wouldn't you need a 64x3 matrix since we need to try out each possibility in C_list and sigma_list, which would mean trying out 64 different permutations?

I have the same question, would be helpful if you could answer this

Well, after posting the comment, I tried to investigate further. It does not matter what size you give for result 1) you can initialize with size(64,3) 2) Even though the size is (16,3) , you can still add more rows like 17 onward. Hope it helps

Yes. In MATLAB, matrix has capability to update. i.e You can change the size of Matrix after initializing it. BUT, If you keep on updating/changing the size of matrix in each iteration, you will get the warning and you code will be slower (not optimized). So, It is always advised to initialize the matrix with it final size (if known) and then only update the values on the matrix not the size.

Thank you for your replying after figuring out the solution. It saved my time.

Your code for dataset3param gives c =0.1and sigma =0.1 which is not correct. Correct value for c and sigma is 0.3 and 0.1 respectively.

Thanks for the feedback. You might be correct. Coursera keep on updating their assignments time to time. All my answers belongs to the time I was doing it. and these were 100% correct answers by then.

Hey Akshay, I have a suggestion for a small optimization.. In the emailFeatures.m we can instead write for i = word_indices x(i) = 1; end Hope its better

This comment has been removed by the author.

In emailfeatures.m rather than using loop x(word_indices,1)=1;

Thanks. Did it work for you?

Yes, works perfect!

why is i showing training " out of time" error

what is the use of @.

What is the value for the features in Gaussian kernel,can you help me in understanding the criteria for selecting x1,x2 in svmTrain.m

Please could you explain to me what's the difference between svmtrain and svmpredict ? what are the results returned? I get a little confused. Thank you in advance

https://www.mathworks.com/matlabcentral/answers/320129-what-does-do This may help

Thanks for sharing the meaning of "@" symbol in MATLAB.

please could you explain to me in the dataset3Params.m why the result = zeros(length(C_list)+length(sigma_list),3); is not result = zeros(length(C_list)*length(sigma_list),3);?

Hi Akshay,a question: in emailFeatures.m length(word_indices) = 53 why are there 45 but not 53 non-zero entries???

Hi! Thank you for your code! It is useful to see different ways to solve the exercises. In my case I followed the tutorial indications and I didn't use any for loop in emailFeature.m, so I just wrote: x(word_indices) = 1; And that's all! It worked and submitted perfectly so it seems to be fine and it's just one line :D

Hi!! I use online matlab to execute code. For both parameters to be used for data set 3 and process email code it takes a long time for training or execution and matlab session gets timed out and the process starts all over again. Please can you help me out with proper parameter values or any another solution to solve this problem. Thank you!!

i am using octave and while submitting it shows "training...... done training..... done...." but My assignment is not submitting. i dont know why.............someone plz help me.............................

Our website uses cookies to improve your experience. Learn more

Contact form

• Learn Python
• Python Lists
• Python Dictionaries
• Python Strings
• Python Functions
• Learn Pandas & NumPy
• Pandas Tutorials
• Numpy Tutorials
• Learn Data Visualization
• Python Seaborn
• Python Matplotlib

Support Vector Machines (SVM) in Python with Sklearn

• February 25, 2022 April 22, 2023

In this tutorial, you’ll learn about Support Vector Machines (or SVM) and how they are implemented in Python using Sklearn . The support vector machine algorithm is a supervised machine learning algorithm that is often used for classification problems, though it can also be applied to regression problems.

This tutorial assumes no prior knowledge of the support vector machines algorithm . By the end of this tutorial, you’ll have learned:

• How the SVM algorithm was designed and how to understand it conceptually
• How the SVM algorithm is used to make predictions of classes
• How the algorithm handles multiple dimensions
• How the kernel trick makes the SVM algorithm a practical algorithm
• How to validate your algorithm’s effectiveness and accuracy
• How the algortihm can be tweaked using hyper-parameter tuning

Table of Contents

What are Support Vector Machines in Machine Learning?

Support vector machines (or SVM, for short) are algorithms commonly used for supervised machine learning models. A key benefit they offer over other classification algorithms ( such as the k-Nearest Neighbor algorithm ) is the high degree of accuracy they provide.

Conceptually, SVMs are simple to understand. This tutorial will guide you through SVMs in increasing complexity to help you fully grasp the concepts behind them.

In short, support vector machines separate data into different classes of data by using a hyperplane . This hyper-plane, as you’ll soon learn, is supported by the use of support vectors . These vectors are used to ensure that the margin of the hyper-plane is as large as possible.

Why is the SVM Algorithm Useful to Learn?

The Support Vector Machines algorithm is a great algorithm to learn. It offers many unique benefits, including high degrees of accuracy in classification problems. The algorithm can also be applied to many different use cases, including facial detection, classification of websites or emails, and handwriting recognition.

However, a key benefit of the algorithm is that it is intuitive . Being able to understand the mechanics behind an algorithm is important. This is true even when the math is a bit out of scope.

Additionally, the algorithm works especially well with high-dimensional datasets. This makes it particularly useful, especially compared to other algorithms that may struggle under significant dimensionality.

In this tutorial, we’ll focus on learning the mechanics and motivations behind the algorithm, rather than focusing on the math. This is because much of the math is abstracted by machine learning libraries such as Scikit-Learn.

How Does the Support Vector Machine Algorithm Work?

In this section, we’ll explore the mechanics and motivations behind the support vector machines algorithm. We’ll start with quite straightforward examples and work our way up to more complex uses of the algorithm.

As mentioned earlier in the tutorial, the SVM algorithm aims to find the optional hyper-plane that separates classes of data. But, what is a hyper-plane? A hyper-plane is a decision boundary (such as a point, a line, or a plane) that separates classes of data .

Let’s first look at data that are linearly separatable, which is one of the simplest applications of the support vector machines algorithm.

Support Vector Machines with Linearly Separatable Data

Data that are linearly separable means that we can separate the data into distinct classes using a linear model, such as a line.

To better illustrate this, as well as how the SVM algorithm works, let’s take a look at some data. We’ll plot two-dimensional data along the x and y axis.

In the scatter plot above we visualized our data along two dimensions. Visually, it’s quite clear that we have two distinct clusters of data. Thankfully, our data came pre-labeled and we can map in these target features into our visualization!

Let’s see what this looks like this classes mapped into it:

Awesome! We can see that we have two clusters: those belonging to 'No' and those belonging to 'Yes' . The support vector machines algorithm seeks to separate these two clusters of data by using a hyper-plane. In this case, our hyper-plane would be a line that splits the data into two.

Let’s see how we can draw a few lines that all separate the data perfectly:

All of the lines above separate the data perfectly. So, how do we choose a single line to use as our algorithm’s hyperplane? The idea behind choosing the line is the one that best separates the data. SVM algorithms do this process iteratively. They will try a line, then another, and another, until they find the best one. In this case, the best line is the one shown below:

Why is this the best hyperplane to use? In short, this line maximizes the margins between the line and the closest data points . The margins are the gaps between the line and the nearest data points of either class.

This gap is measured as the perpendicular distance between the hyperplane and the data point. In practice, the larger the margin better, and a smaller margin is worse.

Let’s visualize what these margins look like, based on the line that we’ve drawn above:

We can see that we have drawn two margins here. Intuitively, we can imagine that the margins of this line are larger than the margins of the other lines would have been.

If you look closely, you’ll notice that the two margins actually touch some of the data points of both classes. Let’s take a closer look at these:

These points have a special purpose in SVM algorithms. They are known as the support vectors of our model. They’re called support vectors because they’re the data points that define the boundary that divides our two classes of data.

In fact, they’re the only points that influence the data, as the data currently stands. Adding additional points on either side of the margin (as long as they’re classified properly) has no impact on the hyperplane of the supporting margins .

In a later section, you’ll learn how to build these SVM models in Scikit-Learn. In the next section, however, you’ll learn some additional mechanics behind the SVM algorithm.

Transforming Data to Produce Linearly Seperatable Data

In this section, we’ll dive into some more complex data. In particular, we’ll take a look at how we can transform data using some simple transformations to make the data linearly separatable.

To better understand this, let’s take a look at an example of one-dimensional data.

In the example above, we have three clusters, but only two labels. There’s no straight line that can effectively split the data appropriately. So, what can we do? One of the things things that SVM does particularly well is transform the data in order to allow a hyperplane to separate the data .

Let’s try raising each value of x to the power of 4. This adds a second dimension, where we can plot the values as (x i , x i 4 ) . Let’s see what this looks like:

We can see that the data are now able to be separated by a straight line. Let’s draw a hyperplane to separate the data to be used to classify:

Ok, so we’ve taken a look at two examples. For our final example, let’s look at a different, yet common scenario: data that form clustered circles.

Transforming Non-Linear With Inseperable Planes

In this final example, we’ll take a look at how we can best transform data which no amount of linear transformation can make separable. In this case, we’ll look at data that’s in the shape of clustered circles.

Take a look at the graph below. It’s clear that we certainly cannot fit a line to separate this data.

One thing we can do is apply the kernel trick to transform the data into a higher dimension.

The kernel trick is powerful because it allows us to operate in the original vector space without needing to compute the coordinates of data in a higher dimensional space . In short, it allows us to find the optimal function to apply, without needing to formally apply it.

Let’s take a look at how we could, for example, transfer for the data above to a different dimension in order to find an appropriate hyperplane.

One thing you might note is that the inner circle is centred around the origin. By transforming these values to a higher dimension, these values will remain lower.

Let’s find the negative sum of the squares of the coordinates for each of these values and have that equal the third dimension of the data. Doing this results in the following visualization:

We can now easily see that we can in fact separate the data. However, because we’re now working in three dimension, our hyperplane becomes a plane that separates the two classes.

Now that you understand the motivations and mechanics of support vector machines, let’s see how we can implement them using the Python Scikit-Learn library!

Support Vector Machines in Python’s Scikit-Learn

In this section, you’ll learn how to use Scikit-Learn in Python to build your own support vector machine model. In order to create support vector machine classifiers in sklearn, we can use the SVC class as part of the svm module.

Let’s begin by importing the required libraries for this tutorial:

Let’s break down the libraries that we’re using in this tutorial:

• The seaborn library is used to provide the dataset we’ll be using throughout this tutorial – the 'penguins' dataset. We’ll also use the pairplot() function to better understand our data.
• matplotlib.pyplot to show and modify our visualizations
• Pandas is used to manipulate our data via DataFrame methods
• The SVC class is used to create our classification model
• The train_test_split() function is used to split our data into training and testing data
• The accuracy_score() function allows us to evaluate the performance of our model

For this tutorial, we’ll focus on the Penguins dataset that comes bundled with Seaborn. The dataset covers information on different species of penguins, including the island the sample was taken from, as well as their bill length and depth.

The dataset focuses on predicting the species of a penguin based on its physical characteristics. There are three types of Penguins that the dataset has data on: the Adelie, Chinstrap, and Gentoo penguins, as shown below:

Let’s begin by first loading our dataset and exploring it a little bit:

In the data shown above, we can see that we have a mix of numerical and categorical columns. In the process of this tutorial, we’ll use all the features to predict the 'species' column.

To better understand what some of these measurements represent, take a look at the image below:

We can see that we also have a number of missing values. While we could impute this data, it’s a little outside of the scope of this tutorial. Since machine learning algorithms cannot work with missing data, let’s drop these records.

Now, let’s explore the numeric features of this data a little bit to see what how the data is spread out. For this, we can use the Seaborn pairplot() function to visualize the data by its pairs of features:

This returns the following image:

Multi-Class Classification with SVM with Sklearn

Before diving further into building our model, I want to take a moment to discuss how multi-class classification works in SVM. In all the theory covered above we focused on binary classifiers (either “Yes” or “No”, 0 or 1, etc.). As you can see in the data above, there are three classes.

When facing multiple classes, Sklearn applies a one-to-one approach where it models the hyperplane for each pair of potential options. For example, it would build the classifer for Adelie vs. Chinstrap, ignoring Gentoo. Then it would do that same for Adelie vs. Gentoo, ignoring Chinstrap.

In one-to-one multi-class SVM, the class with the most predicted values is the one that’s predicted.

We can determine the number of models that need to be built by using this formula:

We can see that we’ll need to build three models for our classifier to work. Fortunately, Sklearn handles and abstracts all of this!

Splitting our Data into Testing and Training Data

Let’s now split our data into training and testing data. This step is important because it allows us to validate the accuracy of our model against data that the model hasn’t yet seen. For this, we’ll use Sklearn’s train_test_split() function, which I cover in detail here .

To start off with, let’s only look at two numeric variables. We’ll discuss working with categorical data later in the tutorial, but for now let’s ignore those features.

We can follow Sklearn convention and create two different arrays of data:

• X will be our feature matrix. The letter is capitalized as it is a multi-dimensional array.
• y will be our target array. The letter is not capitalized as it is one-dimensional.

Let’s create these variables now and split them using the train_test_split() function:

By default, Sklearn will reserve 25% of the dataset for training.

Understanding Support Vector Classifiers (SVC) in Sklearn

In order to handle classifications, Sklearn provides a support vector machines classifier class called SVC . Let’s take a look at the different parameters of the class:

The class has a lot of different parameters. In this tutorial, we’ll focus on only a few of them, but set you up to be able to explore the others confidently. In particular, we’ll focus on:

• kernel= , which defines what type of function is used to transform the dataset
• C= , which defines the regularization of the error.
• gamma= defines how loosely the model will fit the training data, allowing you to prevent overfitting

Let’s try building our model first with only the default parameters, except using a linear kernel. Once our model has been set up, we can apply the .train() method to train the data using the X_train and y_train variables:

We can now use the model to make predictions of the data. We can do this by using the .predict() method and passing in our testing features.

Let’s see what this looks like:

You’ve now built your first SVM classifier and made some predictions based on the data!

One of the wonderful things about Scikit-Learn is how much it abstracts what’s going on with the algorithm. This, however, can also be one of the challenges that comes with learning how this actually works. Before diving further into the algorithm, let’s try and visualize what’s gone on here.

We can write some helper code to help us visualize the distribution of the data and plot the linear model that separates the data. Let’s see what this looks like. In order to make this simpler, let’s limit our algorithm to a binary classification.

We were able to get the coefficient and intercept for our data points and plotted them. One thing you’ll notice is that the data can’t be perfectly separated like our earlier examples. Let’s explore this a little further.

Soft Margin Classification in Support Vector Machines

In these cases you, as a data scientist, needs to decide whether to transform the data (and risk overfitting and computational overhead) or whether to soften the margin and allow misclassification of some data.

Softening the margin allows us to find a good balance between keeping a wide margin and limiting the number of margin violations that occur. We’ll explore this a little further when we discuss hyperparameters. For now, it’s important to recognize that by having a harder margin, our data may not generalize to new data as well. By having too soft a margin, our data may not classify well to begin with.

Testing the Accuracy of our SVM Algorithm

Now that we’ve worked through this aside, lets begin looking at how we can test the accuracy of our model. Since our model aims to classify something, it’s either right or wrong for each data point. Because we already split our data into training and testing data, we can actually run a simple accuracy statistics.

Sklearn comes with a function, accuracy_score() , that calculates the proportion of accurate predictions the model made out of the total number of predictions. Let’s use this function to see how accurate our model is.

We’ll expand the scope to the original intent of the algorithm, to classify all three penguin specifies:

We can see here that our model’s accuracy is 97%! Let’s take a look at how we can add in categorical variables to make use of the rest of the dimensions we have access to.

Working with Categorical Data in Support Vector Machines

By their nature, machine learning algorithms cannot work with non-numeric data. This means that when our dataset has features that aren’t numeric, we need to find a way to transform them into types that the algorithm can work with.

One of the most common processes for this is One-Hot Encoding . One-hot encoding takes a categorical feature and converts it into binary columns. Take a look at the image below that illustrates what happens:

Each unique value in the categorical column is given its own column. If that value matches the column, then it’s assigned a value of 1 . Otherwise, it’s assigned a value of 0 .

While it may seem more efficient to assign each category a value of, say, [0, 1, 2] , this isn’t always a great idea. Unless the ordering of our data has meaning, such as with, say, clothing sizes, this has the potential to misrepresent the distances between our data .

In the same data above, the island Dream isn’t any more different from Torgensen than Biscoe. Because of this one-hot encoding is a safer option for categorical, non-ordinal data.

In order to one-hot encode our data in sklearn, we can make use of the OneHotEncoder class and the make_column_transformer() function. Let’s see how we can one-hot encode our columns, island and sex:

Let’s break down what we did here, as we’ve changed some of the lines of code from above:

• We loaded the data and dropped missing records
• For X , we now load all columns except for the target column, 'species'
• We split the data into training and testing data in the same way as before
• We then make a new variable, column_transformer that applies the OneHotEncoder class to the sex and island columns.
• The remainder= parameter determines what to do with the remaining columns. We’re telling sklearn to simply pass through these.
• We fit and transform the X_train data with the .fit_transform() method
• Finally, we turn that array back into a Pandas DataFrame

Our data now looks like this:

We can see that the data now also has our one-hot encoded columns. We can now use these columns in our algorithm!

Standardizing Data for Support Vector Machines

Support vector machines are optimized by the effectiveness of the hyperplane. If our data has different ranges, this can leader to one dimension dominating the others. For example, in our data we now have some binary values (0 or 1) and other data that ranges into the hundreds.

Because the kernel values tend to depend on the dot product of feature vectors, larger ranges can create problems.

In order to circumvent the problem of some dimensions dominating others, we can standardize our data. When we scale our data, the data will have a mean of 0 and a standard deviation of 1 .

We can scale our data using the StandardScaler class in sklearn. Because we have already set up a column transformer, we can actually just add this step into it. We’ll apply the transformation to all the numeric columns.

Let’s see how this can work:

The main thing we have added here is importing the StandardScaler class and adding the additional transformation to our dataset.

In the next section, you’ll learn more about the different hyperparameters that we can apply to tweak our model.

Hyper-Parameters of the SVM Algorithm in Scikit-Learn

The support vector machine classifier model in sklearn comes with a number of hyper-parameters. In this tutorial, we’ll focus on three main ones:

Let’s take a look at each of these parameters in-depth, to really understand what they’re doing.

Understanding C for Regularization in Support Vector Machines

In an earlier section, you learned that because most data sets aren’t perfect and overlap occurs, it’s important to find a balance between the softness of your margin and the number of misclassifications that occur.

This is the “art” of data science – there is no set answer for what the best margin is, but it varies from dataset to dataset. More importantly, the context varies greatly, too. There are some domains in which error is more acceptable. In other domains, such as medicine, error can be negatively life-changing.

The C parameter of the SVC class is the parameter that regulates how soft a margin can be. By default, it is given a value of 1. Generally speaking, the values can be thought os as:

• The smaller the value of C , the wider the margins – which may lead to more misclassifications.
• Inversely, the larger the value of C , the more narrow the margins of the classifier become – this may lead to fewer misclassifications.

At this point, you may be thinking, “Well, Nik, I’ll just crank up the value of C !” In theory this sounds great. However, it will likely lead to overfitting your model. This means that your model does not generalize well to new data.

Understanding Kernels in Support Vector Machines

Let’s talk about the kernel now. You’ve already seen the power of transformations in being able to more clearly separate your data. This is where the kernel comes in. A kernel transformation looks at the similarly relationship (or kernel) between each pair of points and aims to find the best function transformation for that relationship.

For example, the kernel can take a number of different forms, depending on the relationship we want it to use. These can take different forms, including linear, nonlinear, polynomial, radial basis function, and sigmoid. Of these, the radial basis function is the most common. The rbf allows us to overcome space complexities since it only needs to store the support vectors during training (rather than the entire dataset).

Of course, calculating the actual values of each of these feature spaces would be computationally expensive. Because of this, data scientists and sklearn apply what’s referred to as the kernel trick , in which the data are not explicitly mapped. Instead, an implicit feature space is created without calculating the new coordinates.

The kernel trick, then, saves us much computing cost and simply calculates the inner products between the images of all pairs of data in the feature space .

Understanding Gamma for Regularization in Support Vector Machines

Finally, let’s take a look at the gamma hyperparameter. The gamma defines how far the influence of a single training example reaches. The lower the value, the further the reach of a training point. Inversely, the larger the value, the lower the reach of the training point.

Because of this inverse relationship, we can say that using a smaller gamma may mean that a model is more generalized. Inversely, the larger the value of gamma, the more likely the model may be overfitted to the training data.

In short: a small gamma will lower your bias but increase your variance, while a large gamma will increase your bias but lower your variance .

Hyper-Parameter Tuning and Cross-Validation for Support Vector Machines

In this section, you’ll learn how to apply your new knowledge of the different hyperparameters available in the support vector machines algorithm. Hyperparameters refer to the variables that are specified while building your model (that don’t come from the data itself).

Hyper-parameter tuning , then, refers to the process of tuning these values to ensure a higher accuracy score.  One way to do this is, simply, to plug in different values and see which hyper-parameters return the highest score.

This, however, is quite time-consuming. Scikit-Learn comes with a class  GridSearchCV  which makes the process simpler. You simply provide a dictionary of values to run through and sklearn returns the values that worked best.

By using this class, sklearn actually handles cross-validation as well. What this means is that it doesn’t simply split the data into one training and testing set, but rather into k sets and runs through each one to find the optimal hyperparameters.

Want to learn about a more efficient way to optimize hyperparameters? You can optimize and speed up your hyperparameter tuning using the Optuna library.

Let’s take a look at the three hyperparameters we explored in the previous section. We can create a dictionary for the various values that we want to loop through:

Let’s break down what we did here:

• We defined a dictionary of the different hyperparameters and their values to test
• We created a new GridSearchCV object. In this, we passed in that we wanted to use the SVC() estimator with our parameter grid.
• We fit the training data into this new GridSearchCV object, which runs through the different permutations of the search
• Finally, we access the .best_params_ attribute, which tells us what the best values are ( for the values we provided )

In this case, the best selection for hyperparameters to use are:

• kernel='rbf'

Support Vector Machines in Sklearn: Putting it All Together

In this final section, we’ll see what our code looks like now that it’s all come together. The code below cleans up everything we did above and learned about what hyperparameters to apply:

We can see that the accuracy is nearly 99%!

It’s important to note that accuracy is just a single criterion for evaluating the performance of a classification problem. If you want to learn more about this, check out my in-depth post on calculating and visualizing a confusion matrix in Python .

Now that we have our model, we can actually go one step further. Let’s imagine we have a pet penguin but don’t actually know what species it is. We find our penguin (let’s call her Penny) and take some measurements. We can now take our model to predict Penny’s species. Let’s see how we can do this:

We can be quite confident that Penny is an Adelie penguin!

In this tutorial, you learned all about the support vector machines algorithm. You learned the motivations and concepts behind how the algorithm works and why it’s a great algorithm for classification problems.

Then, you learned how to create the SVM algorithm in Scikit-Learn using the SVC class. You learned how to evaluate the model’s performance and tune its hyperparameters. You also learned how to work with categorical data as well as how to scale your data to prevent some dimensions from having too much unintended influence.

Additional Resources

To learn more about related topics, check out the tutorials below:

• K-Nearest Neighbor (KNN) Algorithm in Python
• Hyper-parameter Tuning with GridSearchCV in Sklearn
• Introduction to Scikit-Learn (sklearn) in Python
• Linear Regression in Scikit-Learn (sklearn): An Introduction
• Introduction to Machine Learning in Python
• Official Documentation: SVC in Sklearn

Nik Piepenbreier

Nik is the author of datagy.io and has over a decade of experience working with data analytics, data science, and Python. He specializes in teaching developers how to use Python for data science using hands-on tutorials. View Author posts

2 thoughts on “Support Vector Machines (SVM) in Python with Sklearn”

Pingback:  When to use SVM algorithm? - What Type Degree

Pingback:  When to use support vector machines? - What Type Degree

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

• AMPL Support Forum
• AMPL Download Portal
• AMPL Development Resources
• Hands-On Optimization in Python
• AMPL Model Colaboratory
• AMPL on Streamlit Cloud
• amplpy: Python API
• rAMPL: R API
• AMPL Plugins
• amplpyfinance
• Solver Callbacks
• MP: Solver Interface Framework
• AMPL & Solvers pricing
• Free AMPL For Teaching
• Free AMPL Community Edition
• Twitter / X

Support Vector Machines for Binary Classification

Support vector machines for binary classification #.

Support Vector Machines (SVM) are a type of supervised machine learning model. Similar to other machine learning techniques based on regression, training an SVM classifier uses examples with known outcomes, and involves optimization some measure of performance. The resulting classifier can then be applied to classify data with unknown outcomes.

In this notebook, we will demonstrate the process of training an SVM for binary classification using linear and quadratic programming. Our implementation will initially focus on linear support vector machines which separate the feature space by means of a hyperplane. We will explore both primal and dual formulations. Then, using kernels, the dual formulation is extended to binary classification in higher-order and nonlinear feature spaces. Several different formulations of the optimization problem are given in AMPL and applied to a banknote classification application.

Binary classification #

Binary classifiers are functions designed to answer questions such as “does this medical test indicate disease?”, “will this specific customer enjoy that specific movie?”, “does this photo include a car?”, or “is this banknote genuine or counterfeit?” These questions are answered based on the values of “features” that may include physical measurements or other types of data collected from a representative data set with known outcomes.

In this notebook we consider a binary classifier that might be installed in a vending machine to detect banknotes. The goal of the device is to accurately identify and accept genuine banknotes while rejecting counterfeit ones. The classifier’s performance can be assessed using definitions in following table, where “positive” refers to an instance of a genuine banknote.

A vending machine user would be frustrated if a genuine banknote is incorrectly rejected as a false negative. Sensitivity is defined as the number of true positives (TP) divided by the total number of actual positives (TP + FN). A user of the vending machine would prefer high sensitivity because that means genuine banknotes are likely to be accepted.

The vending machine owner/operator, on the other hand, wants to avoid accepting counterfeit banknotes and would therefore prefer a low number of false positives (FP). Precision is the number of true positives (TP) divided by the total number of predicted positives (TP + FP). The owner/operate would prefer high precision because that means almost all of the accepted notes are genuine.

Sensitivity : The number of true positives divided by the total number of actual positives. High sensitivity indicates a low false negative rate.

Precision : The number of true positives identified by the model divided by the total number of predicted positives, which includes both true and false positives. High precision indicates a low false positive rate.

To achieve high sensitivity, a classifier can follow the “innocent until proven guilty” standard, rejecting banknotes only when certain they are counterfeit. To achieve high precision, a classifier can adopt the “guilty unless proven innocent” standard, rejecting banknotes unless absolutely certain they are genuine.

The challenge in developing binary classifiers is to balance these conflicting objectives and to optimize performance from both perspectives at the same time.

The data set #

The following data set contains measurements from a collection of known genuine and known counterfeit banknote specimens. The data includes four continuous statistical measures obtained from the wavelet transform of banknote images named “variance”, “skewness”, “curtosis”, and “entropy”, and a binary variable named “class” which is 0 if genuine and 1 if counterfeit.

https://archive.ics.uci.edu/ml/datasets/banknote+authentication

Read data #

Select features and training sets #

We divide the data set into a training set for training the classifier, and a testing set for evaluating the performance of the trained classifier. In addition, we select a two dimensional subset of the features so that the results can be plotted for better exposition. Since our definition of a positive outcome corresponds to detecting a genuine banknote, the “class” feature is scaled to have values of 1 for genuine banknotes and -1 for counterfeit banknotes.

The following cell defines a function scatter that produces a 2D scatter plots of a labeled features. The function assigns default labels and colors, and otherwise passes along other keyword arguments.

Support vector machines (SVM) #

Linear svm classifier #.

A linear support vector machine (SVM) is a binary classification method that employs a linear equation to determine class assignment. The basic formula is expressed as:

where \(x\) is a point \(x\in\mathbb{R}^p\) in “feature” space. Here \(w\in \mathbb{R}^p\) represents a set of coefficients, \(w^\top x\) is the dot product, and \(b\) is a scalar coefficient. The hyperplane defined by \(w\) and \(b\) separates the feature space into two classes. Points on one side of the hyperplane are have a positive outcome (+1); while points on the other side have a negative outcome (-1).

The following cell presents a simple Python implementation of a linear SVM. An instance of LinearSVM is defined with a coefficient vector \(w\) and a scalar \(b\) . In this implementation, all data and parameters are provided as Pandas Series or DataFrame objects, and the Pandas .dot() function is used to compute the dot product.

A visual inspection of the banknote training set shows the two dimensional feature set can be approximately split along a vertical axis where “variance” is zero. Most of the positive outcomes are on the right of the axis, most of the negative outcomes on the left. Since \(w\) is a vector normal to this surface, we choose

The code cell below evaluates the accuracy of the linear SVM by calculating the accuracy score , which is the fraction of samples that were predicted accurately.

Performance metrics #

The accuracy score alone is not always a reliable metric for evaluating the performance of binary classifiers. For instance, when one outcome is significantly more frequent than the other, a classifier that always predicts the more common outcome without regard to the feature vector can achieve. Moreover, in many applications, the consequences of a false positive can differ from those of a false negative. For these reasons, we seek a more comprehensive set of metrics to compare binary classifiers. A detailed discussion on this topic recommends the Matthews correlation coefficient (MCC) as a reliable performance measure for binary classifiers.

The code below demonstrates an example of a function that evaluates the performance of a binary classifier and returns the Matthews correlation coefficient as its output.

Linear optimization model #

A training or validation set consists of \(n\) observations \((x_i, y_i)\) where \(y_i = \pm 1\) and \(x_i\in\mathbb{R}^p\) for \(i=1, \dots, n\) . The training task is to find coefficients \(w\in\mathbb{R}^p\) and \(b\in\mathbb{R}\) to achieve high sensitivity and high precision for the validation set. All points \((x_i, y_i)\) for \(i\in 1, \dots, n\) are successfully classified if

As written, this condition imposes no scale for \(w\) or \(b\) (that is, if the condition is satisfied for any pair \((w, b)\) , then it also satisfied for \((\gamma w, \gamma b)\) where \(\gamma > 0\) ). To remove the ambiguity, a modified condition for correctly classified points is given by

which defines a hard-margin classifier. The size of the margin is determined by the scale of \(w\) and \(b\) .

In practice, it is not always possible to find \(w\) and \(b\) that perfectly separate all data. The condition for a hard-margin classifier is therefore relaxed by introducing non-negative decision variables \(z_i \geq 0\) where

The variables \(z_i\) measure the distance of a misclassified point from the separating hyperplane. An equivalent notation is to rearrange this expression as

which is hinge-loss function. The training problem is formulated as minimizing the hinge-loss function over all the data samples:

Practice has shown that minimizing this term alone produces classifiers with large entries for \(w\) which performs poorly on new data samples. For that reason, regularization adds a term to penalize the magnitude of \(w\) . In most formulations a norm \(\|w\|\) is used for regularization, commonly a sum of squares such as \(\|w\|_2^2\) . Another choice is \(\|w\|_1\) which, similar to Lasso regression, may result in sparse weighting vector \(w\) indicating the elements of the feature vector that can be neglected for classification purposes. These considerations result in the objective function

The needed weights are a solution to following LP:

This is the primal optimization problem in decision variables \(w\in\mathbb{R}^p\) , \(b\in\mathbb{R}\) , and \(z\in\mathbb{R}^n\) , a total of \(n + p + 1\) unknowns with \(2n\) constraints. This can be recast as a linear program with the usual technique of setting \(w = w^+ - w^-\) where \(w^+\) and \(w^-\) are non-negative. Then

AMPL implementation #

The AMPL implementation is a factory function. The function accepts a set of training data, creates and solves an AMPL model for \(w\) and \(b\) , then returns a trained LinearSVM object that can be applied to a other feature data.

Quadratic programming model #

Primal form #.

The standard formulation of a linear support vector machine uses training sets with \(p\) -element feature vectors \(x_i\in\mathbb{R}^p\) along with classification labels for those vectors, \(y_i = \pm 1\) . A classifier is defined by two parameters: a weight vector \(w\in\mathbb{R}^p\) and a bias term \(b\in\mathbb{R}\)

If a separating hyperplane exists, then we choose \(w\) and \(b\) so that a hard-margin classifier exists for the training set \((x_i, y_i)\) where

This can always be done if a separating hyperplane exists. But if a separating hyperplane does not exist, we introduce non-negative slack variables \(z_i\) to relax the constraints and settle for a soft-margin classifier

The training objective is to minimize the total distance to misclassified data points. This leads to the optimization problem

where \(\frac{1}{2} \|\bar{w}\|_2^2\) is included to regularize the solution for \(w\) . Choosing larger values of \(c\) will reduce the number and size of misclassifications. The trade-off will be larger weights \(w\) and the accompanying risk of over over-fitting the training data.

Dual Formulation #

The dual formulation for the SVM provides insight into how a linear SVM works and essential for extending SVM to nonlinear classification. The dual formulation begins by creating a differentiable Lagrangian with dual variables \(\alpha_i \geq 0\) and \(\beta_i \geq 0\) for \(i = 1, \dots, n\) . The task is to find saddle points of

Taking derivatives with respect to the primal variables

This can be arranged in the form of a standard quadratic program in \(n\) variables \(\alpha_i\) for \(i = 1, \dots, n\) .

The symmetric \(n \times n\) Gram matrix is defined as

where each entry is dot product of two vectors \((y_i x_i), (y_j x_j) \in \mathbb{R}^{p+1}\) .

Compared to the primal, the dual formulation appears to have reduced the number of decision variables from \(n + p + 1\) to \(n\) . But this has come with the penalty of introducing a dense matrix with \(n^2\) coefficients and potential processing time of order \(n^3\) . For large training sets where \(n\sim 10^4-10^6\) or even larger, this becomes a prohibitively expensive calculation. In addition, the Gram matrix will be rank deficient for cases \(p< n\) .

We can eliminates the need to compute and store the full Gram matrix \(G\) by introducing the \(n \times p\) matrix \(F\)

Then \(G = FF^\top\) which brings the \(p\) primal variables \(w = F^\top\alpha\) back into the computational problem. The optimization problem becomes

The solution for the bias term \(b\) is obtained by considering the complementarity conditions on the dual variables. The slack variables \(z_i\) are zero if \(\beta_i > 0\) which is equivalent to \(\alpha_i < \frac{c}{n}\) . If \(\alpha_i > 0\) then \(1 - y_i (w^\top x_i + b)\) . Putting these facts together gives a formula for \(b\)

This model is implemented below.

Kernelized SVM #

Nonlinear feature spaces #.

A linear SVM assumes the existence of a linear hyperplane that separates labeled sets of data points. Frequently, however, this is not possible and some sort of nonlinear method is needed.

Consider a binary classification done given by a function

where \(\phi(x)\) is a function mapping \(x\) into a higher dimensional “feature space”. That is, \(\phi : \mathbb{R}^{p} \rightarrow \mathbb{R}^d\) where \(d \geq p \) . The additional dimensions may include features such as powers of the terms in \(x\) , or products of those terms, or other types of nonlinear transformations. As before, we wish to find a choice for \(w\in\mathbb{R}^d\) such that the soft-margin classifier

Using the machinery as before, we set up the Lagrangian

then take derivatives to find

This is similar to the case of a linear SVM, but now the vector of weights \(w\in\mathbb{R}^d\) which can be a high dimensional space with nonlinear features. Working through the algebra, we are once again left with a quadratic program in \(n\) variables \(\alpha_i\) for \(i = 1, \dots, n\) .

where the resulting classifier is given by

The kernel trick #

This is an interesting situation where the separating hyperplane is embedded in a high dimensional space of nonlinear features determined by the mapping \(\phi(x)\) , but all we need for computation are the inner products \(\phi(x_i)^\top\phi(x_j)\) to train the classifier, and the inner products \(\phi(x_i)^\top\phi(x)\) to use the classifier. If we had a function \(K(x, z)\) that returned the value \(\phi(x)^\top\phi(z)\) then we would never need to actually compute \(\phi(x)\) , \(\phi(z)\) or their inner product.

Mercer’s theorem turns the analysis on its head by specifying conditions for which a function \(K(x, z)\) to be expressed as an inner product for some \(\phi(x)\) . If \(K(x, z)\) is symmetric (i.e, \(K(x, z) = K(z, x)\) , and if the Gram matrix constructed for any collection of points \(x_1, x_2, \ldots, x_n\)

is positive semi-definite, then there is some \(\phi(x)\) for which \(K(x, z)\) is an inner product. We call such functions kernels. The practical consequence is that we can train and implement nonlinear classifiers using kernel and without ever needing to compute the higher dimensional features. This remarkable result is called the “kernel trick”.

Implementation #

To take advantage of the kernel trick, we assume an appropriate kernel \(K(x, z)\) has been identified, then replace all instances of \(\phi(x_i)^\top \phi(x)\) with the kernel. The “kernelized” SVM is given by a solution to

We define the \(n\times n\) positive symmetric semi-definite Gram matrix

We factor \(G = F F^\top\) where \(F\) has dimensions \(n \times q\) and where \(q\) is the rank of \(G\) . The factorization is not unique. As demonstrated in the Python code below, one suitable factorization is the spectral factorization \(G = U\Lambda U^T\) where \(\Lambda\) is a \(q\times q\) diagonal matrix of non-zero eigenvalues, and \(U\) is an \(n\times q\) normal matrix such that \(U^\top U = I_q\) . Then

Once this factorization is complete, the optimization problem for the kernalized SVM is the same as for the linear SVM in the dual formulation

The result is a quadratic program for the dual coefficients \(\alpha\) and auxiliary variables \(v\) .

Summarizing, the essential difference between training the linear and kernelized SVM is the need to compute and factor the Gram matrix. The result will be a set of non-zero coefficients \(\alpha_i > 0\) the define a set of support vectors \(\mathcal{SV}\) . The classifier is then given by

The implementation of the kernelized SVM is split into two parts. The first part is a class used to create instances of the classifier.

The second part of the implementation is a factory function containing the optimization model for training an SVM. Given training data and a kernal function, the factory returns an instance of a kernelized SVM. The default is a linear kernel.

Linear kernel #

For comparison with the previous cases, the first kernel we consider is a linear kernel

which should reproduce the results obtained earlier.

Polynomial kernels #

A polynomial kernel of order \(d\) has the form

The following cell demonstrates a quadratic kernel applied to the banknote data.

Welcome to our newly formatted notes. Update you bookmarks accordingly.

11   Support Vector Machines

Textbook reading: Chapter 9: Support Vector Machines (exclude Section 9.5).

Overview of the Algorithm

Support vector machines are a class of statistical models first developed in the mid-1960s by Vladimir Vapnik. In later years, the model has evolved considerably into one of the most flexible and effective machine learning tools available. It is a supervised learning algorithm which can be used to solve both classification and regression problem, even though the current focus is on classification only.

To put it in a nutshell, this algorithm looks for a linearly separable hyperplane , or a decision boundary separating members of one class from the other. If such a hyperplane exists, the work is done! If such a hyperplane does not exist, SVM uses a nonlinear mapping to transform the training data into a higher dimension. Then it searches for the linear optimal separating hyperplane. With an appropriate nonlinear mapping to a sufficiently high dimension, data from two classes can always be separated by a hyperplane. The SVM algorithm finds this hyperplane using support vectors and margins . As a training algorithm, SVM may not be very fast compared to some other classification methods, but owing to its ability to model complex nonlinear boundaries, SVM has high accuracy. SVM is comparatively less prone to overfitting. SVM has successfully been applied to handwritten digit recognition, text classification, speaker identification etc.

After completing the reading for this lesson, please finish the Quiz and R Lab on Canvas (check the course schedule for due dates).

Upon successful completion of this lesson, you should be able to:

• Understand how the maximal margin classifier works for datasets in which two classes are separable by a linear boundary.
• Understand the support vector classifier, which extends the maximal margin classifier to work with overlapping classes.
• Understand support vector machines, which extend support vector classifiers to accommodate non-linear class boundaries.

11.1 Support Vector Classifier

The maximal margin classifier is a very natural way to perform classification, is a separating hyperplane exists. However the existence of such a hyperplane may not be guaranteed, or even if it exists, the data is noisy so that maximal margin classifier provides a poor solution. In such cases, the concept can be extended where a hyperplane exists which almost separates the classes, using what is known as a soft margin . The generalization of the maximal margin classifier to the non-separable case is known as the support vector classifier, where a small proportion of the training sample is allowed to cross the margins or even the separating hyperplane. Rather than looking for the largest possible margin so that every observation is on the correct side of the margin, thereby making the margins very narrow or non-existent, some observations are allowed to be on the incorrect side of the margins. The margin is soft as a small number of observations violate the margin. The softness is controlled by slack variables which control the position of the observations relative to the margins and separating hyperplane. The support vector classifier maximizes a soft margin. The optimization problem can be modified as

\[ y_i (\theta_0 + \theta_1 x_{1i} + \theta_2 x_{2i} + \cdots + \theta_n x_{ni}) \ge 1 – \epsilon_i \text{ for every observation}\] \[ \text{Where} \\\\ \epsilon_i \ge 0 \\\\ \text{and} \sum_{i=1}^{n}\epsilon_i \le C \]

The εi is the slack corresponding to \(i^{th}\) observation and C is a regularization parameter set by the user. The larger value of C leads to a larger penalty for errors.

However, there will be situations when a linear boundary simply does not work.

11.2 When Data is Linearly Separable

Let us start with a simple two-class problem when data is clearly linearly separable as shown in the diagram below.

Let the i-th data point be represented by ( \(X_i\) , \(y_i\) ) where \(X_i\) represents the feature vector and \(y_i\) is the associated class label, taking two possible values +1 or -1. In the diagram above the balls having red color has class label +1 and the blue balls have a class label -1, say. A straight line can be drawn to separate all the members belonging to class +1 from all the members belonging to the class -1. The two-dimensional data above are clearly linearly separable.

In fact, an infinite number of straight lines can be drawn to separate the blue balls from the red balls.

The problem, therefore, is which among the infinite straight lines is optimal, in the sense that it is expected to have minimum classification error on a new observation. The straight line is based on the training sample and is expected to classify one or more test samples correctly.

As an illustration, if we consider the black, red and green lines in the diagram above, is any one of them better than the other two? Or are all three of them equally well suited to classify? How is optimality defined here? Intuitively it is clear that if a line passes too close to any of the points, that line will be more sensitive to small changes in one or more points. The green line is close to a red ball. The red line is close to a blue ball. If the red ball changes its position slightly, it may fall on the other side of the green line. Similarly, if the blue ball changes its position slightly, it may be misclassified. Both the green and red lines are more sensitive to small changes in the observations. The black line on the other hand is less sensitive and less susceptible to model variance.

In an n-dimensional space, a hyperplane is a flat subspace of dimension n – 1. For example, in two dimensions a straight line is a one-dimensional hyperplane, as shown in the diagram. In three dimensions, a hyperplane is a flat two-dimensional subspace, i.e. a plane. Mathematically in n dimensions a separating hyperplane is a linear combination of all dimensions equated to 0; i.e., \[\theta_0 + \theta_1 x_1 + \theta_2 x_2 + … + \theta_n x_n = 0\] The scalar \(\theta_0\) is often referred to as a bias. If \(\theta_0 = 0\) , then the hyperplane goes through the origin.

A hyperplane acts as a separator. The points lying on two different sides of the hyperplane will make up two different groups.

Basic idea of support vector machines is to find out the optimal hyperplane for linearly separable patterns. A natural choice of separating hyperplane is optimal margin hyperplane (also known as optimal separating hyperplane) which is farthest from the observations. The perpendicular distance from each observation to a given separating hyperplane is computed. The smallest of all those distances is a measure of how close the hyperplane is to the group of observations. This minimum distance is known as the margin. The operation of the SVM algorithm is based on finding the hyperplane that gives the largest minimum distance to the training examples, i.e. to find the maximum margin. This is known as the maximal margin classifier.

A separating hyperplane in two dimension can be expressed as \[\theta_0 + \theta_1 x_1 + \theta_2 x_2 = 0\] Hence, any point that lies above the hyperplane, satisfies \[\theta_0 + \theta_1 x_1 + \theta_2 x_2 \> 0\] and any point that lies below the hyperplane, satisfies \[\theta_0 + \theta_1 x_1 + \theta_2 x_2 < 0\] The coefficients or weights \(θ_1\) and \(θ_2\) can be adjusted so that the boundaries of the margin can be written as \[H_1: \theta_0 + \theta_1 x_{1i} + \theta_2 x_{2i} \ge 1, \text{for} y_i = +1\] \[H_2: \theta_0 + θ\theta_1 x_{1i} + \theta_2 x_{2i} \le -1, \text{for} y_i = -1\] This is to ascertain that any observation that falls on or above \(H_1\) belongs to class +1 and any observation that falls on or below \(H_2\) , belongs to class -1. Alternatively, we may write \[y_i (\theta_0 + \theta_1 x_{1i} + \theta_2 x_{2i}) \le \text{for every observation}\] The boundaries of the margins, \(H_1\) and \(H_2\) , are themselves hyperplanes too. The training data that falls exactly on the boundaries of the margin are called the support vectors as they support the maximal margin hyperplane in the sense that if these points are shifted slightly, then the maximal margin hyperplane will also shift.

Note that the maximal margin hyperplane depends directly only on these support vectors.

If any of the other points change, the maximal margin hyperplane does not change until the movement affects the boundary conditions or the support vectors. The support vectors are the most difficult to classify and give the most information regarding classification. Since the support vectors lie on or closest to the decision boundary, they are the most essential or critical data points in the training set.

For a general n-dimensional feature space, the defining equation becomes \[y_i (\theta_0 + \theta_1 x_{2i} + \theta_2 x_{2i} + … + θn x_ni)\ge 1, \text{for every observation}\] If the vector of the weights is denoted by \(\Theta\) and \(|\Theta|\) is the norm of this vector, then it is easy to see that the size of the maximal margin is \(\dfrac{2}{|\Theta|}\) . Finding the maximal margin hyperplanes and support vectors is a problem of convex quadratic optimization. It is important to note that the complexity of SVM is characterized by the number of support vectors, rather than the dimension of the feature space. That is the reason SVM has a comparatively less tendency to overfit. If all data points other than the support vectors are removed from the training data set, and the training algorithm is repeated, the same separating hyperplane would be found. The number of support vectors provides an upper bound to the expected error rate of the SVM classifier, which happens to be independent of data dimensionality. An SVM with a small number of support vectors has good generalization, even when the data has high dimensionality.

11.3 When Data is NOT Linearly Separable

SVM is quite intuitive when the data is linearly separable. However, when they are not, as shown in the diagram below, SVM can be extended to perform well.

There are two main steps for nonlinear generalization of SVM. The first step involves the transformation of the original training (input) data into a higher dimensional data using a nonlinear mapping. Once the data is transformed into the new higher dimension, the second step involves finding a linear separating hyperplane in the new space. The maximal marginal hyperplane found in the new space corresponds to a nonlinear separating hypersurface in the original space.

Example: Feature Expansion

Suppose the original feature space includes two variables \(X_1\) and \(X_2\) . Using polynomial transformation the space is expanded to ( \(X_1, X_2, X_1^2, X_2^2, X_1X_2\) ). Then the hyperplane would be of the form \[\theta_0 + \theta_1 X_1 + \theta_2 X_2 + \theta_3 X_1^2 + \theta_4 X_2^2 + \theta_5 X_1 X_2 = 0\] This will lead to nonlinear decision boundaries in the original feature space. If upto second degree terms are considered, 2 features are expanded to 5. If upto third degree terms are considered the same to features can be expanded to 9 features. The support vector classifier in the expanded space solves the problems in the lower dimension space.

11.4 Kernel Functions

Handling the nonlinear transformation of input data into higher dimension may not be easy. There may be many options available, to begin with, and the procedures may be computationally heavy also. To avoid some of those problems, the concept of Kernel functions is introduced.

It so happens that in solving the quadratic optimization problem of the linear SVM, the training data points contribute through inner products of nonlinear transformations. The inner product of two n-dimensional vectors is defined as \[\sum_{j=1}^{n} x_{1j} x_{2j} \] Where \(X_1 = (x_{11}, x_{12}, \cdots x_{1n})\) and \(X_2 = (x_{21}, x_{22},… x_{2n})\) . The kernel function is a generalization of the inner product of nonlinear transformation and is denoted by K(X1, X2). Anywhere such an inner product appears, it is replaced by the kernel function. In this way, all calculations are made in the original input space, which is lower dimensionality. Some of the common kernels are a polynomial kernel, sigmoid kernel, and Gaussian radial basis function. Each of these will result in a different nonlinear classifier in the original input space. There is no golden rule to determine which kernel will provide the most accurate result in a given situation. In practice, the accuracy of SVM does not depend on the choice of the kernel.

11.5 Multiclass SVM

The SVM as defined so far works for binary classification. What happens if the number of classes is more than two?

One-versus-All : If the number of classes is K > 2 then K different 2-class SVM classifiers are fitted where one class is compared with the rest of the classes combined. A new observation is classified according to where the classifier value is the largest.

One-versus-One : All \(\binom{K}{2}\) pairwise classifiers are fitted and a test observation is classified in the class which wins in the majority of the cases.

The latter method is preferable but if K is too large, the former is to be used.

Source Code

Reset password New user? Sign up

Existing user? Log in

Support Vector Machines

Already have an account? Log in here.

Support vector machines are a supervised learning method used to perform binary classification on data. They are motivated by the principle of optimal separation , the idea that a good classifier finds the largest gap possible between data points of different classes.

For example, an algorithm learning to separate the United States from Europe on a map could correctly learn a boundary 100 miles off the eastern shore of the United States, but a much better boundary would be the one running down the middle of the Atlantic Ocean. Intuitively, this is because the latter boundary maximizes the distance to both the United States and Europe.

Maximum Margin Classifiers

Hard-margin svms.

The original support vector machines ( SVMs ) were invented by Vladimir Vapnik in 1963. They were designed to address a longstanding problem with logistic regression , another machine learning technique used to classify data.

Logistic regression is a probabilistic binary linear classifier, meaning it calculates the probability that a data point belongs to one of two classes. Logistic regression attempts to maximize the probability of the classes of known data points according to the model, and so, may place the classification boundary arbitrarily close to a particular data point. This violates the commonsense notion that a good classifier should not place a boundary near a known data point, since data points that are close to each other should be of the same class.

Support vector machines, on the other hand, are non-probabilistic , so they assign a data point to a class with 100% certainty (though a bad SVM may still assign a data point to the wrong class). This means that two SVMs giving the same class assignment to a set of data points have the same classification accuracy. How then should we determine which of the two is better?

The answer lies in the size of the gap between data points of different classes. If two SVMs give the same class assignment of data points, we would like to choose the model whose closest data point is furthest away from its classification boundary. Ideally, the classification boundary will be a curve that goes right down the middle of the gap between classes, because this would be the classficiation boundary with the largest distance to the closest data point.

In the case of two linearly separable classes in the plane, this boundary would be a line that passes through the middle of the two closest data points from different classes. Passing through the midpoint of the line connecting two data points maximizes the distance to each data point. In more than two dimensions, this boundary is known as a hyperplane . This reasoning, which says that the best linear classifier is the one that maximizes the distance from the boundary to data points from each class, gives what are known as maximum margin classifiers . The classification boundary of a maximum margin classifier is known as a maximum margin hyperplane . Support vector machines are one such example of maximum margin classifiers.

The distance from the SVM's classification boundary to the nearest data point is known as the margin . The data points from each class that lie closest to the classification boundary are known as support vectors . If an SVM is given a data point closer to the classification boundary than the support vectors, the SVM declares that data point to be too close for accurate classification. This defines a 'no-man's land' for all points within the margin of the classification boundary. Since the support vectors are the data points closest to this 'no-man's land' without being in it, intuitively they are also the points most likely to be misclassified.

Thus, SVMs can be defined as linear classifiers under the following two assumptions:

The margin should be as large as possible. The support vectors are the most useful data points because they are the ones most likely to be incorrectly classified.

The second assumption leads to a desirable property of SVMs. After training, the SVM can throw away all other data points, and just perform classification using the support vectors. This means that once classification is done, an SVM can predict a data point's class very efficiently, since it only needs to use a handful of support vectors, instead of the entire dataset. This means that the primary goal of training SVMs is to find support vectors in the dataset that both separate the data and find the maximum margin between classes.

Training an SVM is easiest to visualize in two dimensions when the classes are linearly separable. Suppose we are given a dataset \((x_1, y_1), (x_2, y_2), ..., (x_m, y_m),\) where \(y_i=-1\) for inputs \(x_i\) in class 0 and \(y_i=1\) for inputs \(x_i\) in class 1. Recalling the vector equation for a line in two dimensions, the classification boundary is defined as \(\vec{w} \cdot \vec{x}+b=0\), where \(\vec{w}\) and \(\vec{x}\) are two dimensional vectors. Furthermore, define the negative support vector to be the input vector \(\vec{x_n}\) from class 0 and the positive support vector to be the input vector \(\vec{x_p}\) from class 1.

Again recalling the vector equation for a line, define the negative classification boundary to be \(\vec{w} \cdot \vec{x_n}+b=-1\) and the positive classification boundary to be \(\vec{w} \cdot \vec{x_p}+b=1\). Then, the distance between the negative and positive classification boundaries is \(\frac{2}{||\vec{w}||}\). Thus, the size of the margin \(M\) is \(\frac{1}{||\vec{w}||}\).

Since we want to maximize \(M\), we have to minimize \(\vec{w}\). However, we also want to make sure that no points fall in the 'no-man's land', so we also need to introduce the constraints that \(\vec{w} \cdot \vec{x_i} + b \le -1\) for all \(\vec{x}_i\) in class 0 and \(\vec{w} \cdot \vec{x_i} + b \ge 1\) for all \(\vec{x_i}\) in class 1. This leads to following optimization problem:

Minimize \(||\vec{w}||\) subject to \(y_i(w \cdot x_i - b) \ge 1\) for \(i=1, ..., n.\)

This optimization problem can be solved using linear programming techniques.

Problem Loading...

Note Loading...

Set Loading...

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

support-vector-machines

Here are 1,403 public repositories matching this topic..., avik-jain / 100-days-of-ml-code.

100 Days of ML Coding

• Updated Dec 29, 2023

liuruoze / EasyPR

(CGCSTCD'2017) An easy, flexible, and accurate plate recognition project for Chinese licenses in unconstrained situations. CGCSTCD = China Graduate Contest on Smart-city Technology and Creative Design

• Updated Jun 4, 2024

accord-net / framework

Machine learning, computer vision, statistics and general scientific computing for .NET

• Updated Nov 18, 2020

anfederico / clairvoyant

Software designed to identify and monitor social/historical cues for short term stock movement

• Updated Jun 24, 2021

kk7nc / Text_Classification

Text Classification Algorithms: A Survey

• Updated Nov 14, 2022

nsoojin / coursera-ml-py

Python programming assignments for Machine Learning by Prof. Andrew Ng in Coursera

• Updated Sep 2, 2020

mikeroyal / Machine-Learning-Guide

Machine learning Guide. Learn all about Machine Learning Tools, Libraries, Frameworks, Large Language Models (LLMs), and Training Models.

• Updated Jan 4, 2024

jmartinezheras / 2018-MachineLearning-Lectures-ESA

Machine Learning Lectures at the European Space Agency (ESA) in 2018

• Updated Sep 18, 2023
• Jupyter Notebook

fukuball / fuku-ml

Simple machine learning library / 簡單易用的機器學習套件

• Updated Jun 21, 2022

gionanide / Speech_Signal_Processing_and_Classification

Front-end speech processing aims at extracting proper features from short- term segments of a speech utterance, known as frames. It is a pre-requisite step toward any pattern recognition problem employing speech or audio (e.g., music). Here, we are interesting in voice disorder classification. That is, to develop two-class classifiers, which can…

• Updated Mar 3, 2023

snrazavi / Machine_Learning_2018

Codes and Project for Machine Learning Course, Fall 2018, University of Tabriz

• Updated Sep 16, 2021

Madhu009 / Deep-math-machine-learning.ai

A blog which talks about machine learning, deep learning algorithms and the Math. and Machine learning algorithms written from scratch.

• Updated Mar 15, 2019

DoubangoTelecom / compv

Insanely fast Open Source Computer Vision library for ARM and x86 devices (Up to #50 times faster than OpenCV)

• Updated May 10, 2024

sharmapratik88 / AIML-Projects

Projects I completed as a part of Great Learning's PGP - Artificial Intelligence and Machine Learning

• Updated Aug 23, 2021

GeorgeSeif / Python-Machine-Learning

Python Machine Learning Algorithms

• Updated May 31, 2023

tiskw / random-fourier-features

Implementation of random Fourier features for kernel method, like support vector machine and Gaussian process model

• Updated May 2, 2024

mithi / vehicle-tracking-2

A vehicle detection and tracking pipeline with OpenCV, histogram of oriented gradients (HOG), and support vector machines (SVM).

• Updated Sep 23, 2018

Mamcose / NSL-KDD-Network-Intrusion-Detection

Machine Learning Algorithms on NSL-KDD dataset

• Updated May 30, 2019

hiroyuki-kasai / ClassifierToolbox

A MATLAB toolbox for classifier: Version 1.0.7

• Updated Jan 5, 2023

shawn-terryah / Twitter_Geolocation

Geolocating twitter users by the content of their tweets

• Updated Jan 8, 2021

Improve this page

Add a description, image, and links to the support-vector-machines topic page so that developers can more easily learn about it.

Curate this topic

Add this topic to your repo

To associate your repository with the support-vector-machines topic, visit your repo's landing page and select "manage topics."

• Data Science
• Data Analysis
• Data Visualization
• Machine Learning
• Deep Learning
• Computer Vision
• Artificial Intelligence
• AI ML DS Interview Series
• AI ML DS Projects series
• Data Engineering
• Web Scrapping

Introduction to Support Vector Machines (SVM)

Introduction:.

Support Vector Machines (SVMs) are a type of supervised learning algorithm that can be used for classification or regression tasks. The main idea behind SVMs is to find a hyperplane that maximally separates the different classes in the training data. This is done by finding the hyperplane that has the largest margin, which is defined as the distance between the hyperplane and the closest data points from each class. Once the hyperplane is determined, new data can be classified by determining on which side of the hyperplane it falls. SVMs are particularly useful when the data has many features, and/or when there is a clear margin of separation in the data.

What are Support Vector Machines? Support Vector Machine (SVM) is a relatively simple Supervised Machine Learning Algorithm used for classification and/or regression. It is more preferred for classification but is sometimes very useful for regression as well. Basically, SVM finds a hyper-plane that creates a boundary between the types of data. In 2-dimensional space, this hyper-plane is nothing but a line. In SVM, we plot each data item in the dataset in an N-dimensional space, where N is the number of features/attributes in the data. Next, find the optimal hyperplane to separate the data. So by this, you must have understood that inherently, SVM can only perform binary classification (i.e., choose between two classes). However, there are various techniques to use for multi-class problems. Support Vector Machine for Multi-CLass Problems To perform SVM on multi-class problems, we can create a binary classifier for each class of the data. The two results of each classifier will be :

• The data point belongs to that class OR
• The data point does not belong to that class.

For example, in a class of fruits, to perform multi-class classification, we can create a binary classifier for each fruit. For say, the ‘mango’ class, there will be a binary classifier to predict if it IS a mango OR it is NOT a mango. The classifier with the highest score is chosen as the output of the SVM. SVM for complex (Non Linearly Separable) SVM works very well without any modifications for linearly separable data. Linearly Separable Data is any data that can be plotted in a graph and can be separated into classes using a straight line.

A: Linearly Separable Data B: Non-Linearly Separable Data

We use Kernelized SVM for non-linearly separable data. Say, we have some non-linearly separable data in one dimension. We can transform this data into two dimensions and the data will become linearly separable in two dimensions. This is done by mapping each 1-D data point to a corresponding 2-D ordered pair. So for any non-linearly separable data in any dimension, we can just map the data to a higher dimension and then make it linearly separable. This is a very powerful and general transformation. A kernel is nothing but a measure of similarity between data points. The kernel function in a kernelized SVM tells you, that given two data points in the original feature space, what the similarity is between the points in the newly transformed feature space. There are various kernel functions available, but two are very popular :

• Radial Basis Function Kernel (RBF): The similarity between two points in the transformed feature space is an exponentially decaying function of the distance between the vectors and the original input space as shown below. RBF is the default kernel used in SVM.

• Polynomial Kernel: The Polynomial kernel takes an additional parameter, ‘degree’ that controls the model’s complexity and computational cost of the transformation

A very interesting fact is that SVM does not actually have to perform this actual transformation on the data points to the new high dimensional feature space. This is called the kernel trick . The Kernel Trick: Internally, the kernelized SVM can compute these complex transformations just in terms of similarity calculations between pairs of points in the higher dimensional feature space where the transformed feature representation is implicit. This similarity function, which is mathematically a kind of complex dot product is actually the kernel of a kernelized SVM. This makes it practical to apply SVM when the underlying feature space is complex or even infinite-dimensional. The kernel trick itself is quite complex and is beyond the scope of this article. Important Parameters in Kernelized SVC ( Support Vector Classifier)

• The Kernel : The kernel, is selected based on the type of data and also the type of transformation. By default, the kernel is Radial Basis Function Kernel (RBF).
• Gamma : This parameter decides how far the influence of a single training example reaches during transformation, which in turn affects how tightly the decision boundaries end up surrounding points in the input space. If there is a small value of gamma, points farther apart are considered similar. So more points are grouped together and have smoother decision boundaries (maybe less accurate). Larger values of gamma cause points to be closer together (may cause overfitting).
• The ‘C’ parameter : This parameter controls the amount of regularization applied to the data. Large values of C mean low regularization which in turn causes the training data to fit very well (may cause overfitting). Lower values of C mean higher regularization which causes the model to be more tolerant of errors (may lead to lower accuracy).

Pros of Kernelized SVM: 

• They perform very well on a range of datasets.
• They are versatile: different kernel functions can be specified, or custom kernels can also be defined for specific datatypes.
• They work well for both high and low dimensional data.

Cons of Kernelized SVM: 

• Efficiency (running time and memory usage) decreases as the size of the training set increases.
• Needs careful normalization of input data and parameter tuning.
• Does not provide a direct probability estimator.
• Difficult to interpret why a prediction was made.

Conclusion: Now that you know the basics of how an SVM works, you can go to the following link to learn how to implement SVM to classify items using Python: https://www.geeksforgeeks.org/classifying-data-using-support-vector-machinessvms-in-python/

Please Login to comment...

Similar reads.

• AI-ML-DS With Python
• Top Android Apps for 2024
• Top Cell Phone Signal Boosters in 2024
• Best Travel Apps (Paid & Free) in 2024
• The Best Smart Home Devices for 2024
• 15 Most Important Aptitude Topics For Placements [2024]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Weighted least squares twin support vector machine based on density peaks

• Theoretical Advances
• Published: 03 September 2024
• Volume 27 , article number  106 , ( 2024 )

Cite this article

• Li Lv 1 , 4 ,
• Zhipeng He 1 ,
• Juan Chen 1 ,
• Fayang Duan 1 ,
• Shenyu Qiu 2 &
• Jeng-Shyang Pan 3  

The least-squares twin support vector machine integrates all samples equally into the quadratic programming problem to calculate the optimal classification hyperplane, and does not distinguish the noise points in the samples, which causes the model to be sensitive to noise points and affected by the overlapping samples of positive and negative classes, and reduces the classification accuracy. To address the above problems, this paper proposes a weighted least squares twin support vector machine based on density peaks. Firstly, the algorithm combines the idea of density peaks to construct a new density weighting strategy, which gives a suitable weight value to this sample through the local density of the sample as well as the relative distance together to highlight the importance of the local center and reduce the influence of noise on the model; secondly, the separability between classes is defined according to the local density matrix, which reduces the influence of positive and negative class overlapping samples on the model and enhances the inter-class separability of the model; finally, an extensive weighting strategy is used in the model to assign weight values to both classes of samples to improve the robustness of the model to cross samples. The comparison experiments on the artificial dataset and the UCI dataset show that the algorithm in this paper can assign appropriate weights to different samples to improve the classification accuracy, while the experiments on the MNIST dataset demonstrate the effectiveness of the algorithm in this paper for real classification problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Explore related subjects

• Artificial Intelligence

Data availability

The data used to support the experiments and findings of this study will be made available upon publication of the article.

Cortes C, Vapnik V (1995) Support-vector networks. Mach learn 20:273–297

Article   Google Scholar  

Richhariya B, Tanveer MEEG (2018) Signal classification using universum support vector machine. Expert Syst Appl 106:169–182

Baldomero-Naranjo M, Martinez-Merino LI, Rodriguez-Chia AM (2021) A robust SVM-based approach with feature selection and outliers detection for classification problems. Expert Syst Appl 178:115017. https://doi.org/10.1016/j.eswa.2021.115017

Ali L, Wajahat I, Amiri Golilarz N et al (2021) LDA–GA–SVM: improved hepatocellular carcinoma prediction through dimensionality reduction and genetically optimized support vector machine. Neural Comput Appl 33(7):2783–2792

Khemchandani R, Chandra S (2007) Twin support vector machines for pattern classification. IEEE Trans Pattern Anal Mach Intell 29(5):905–910

Kumar MA, Gopal M (2009) Least squares twin support vector machines for pattern classification. Expert Syst Appl 36(4):7535–7543

Tanveer M, Sharma A, Suganthan PN (2019) General twin support vector machine with pinball loss function. Inf Sci 494:311–327

Article   MathSciNet   Google Scholar  

Panagopoulos OP, Xanthopoulos P, Razzaghi T et al (2019) Relaxed support vector regression. Ann Oper Res 276(1):191–210

Wang H, Liu Y, Zhang S (2023) Smooth and semi-smooth pinball twin support vector machine. Expert Syst Appl 226:120189

Ye Q, Zhao C, Ye N (2012) Least squares twin support vector machine classification via maximum one-class within class variance. Optim methods softw 27(1):53–69

Huang X-Y, Zhai G-J, Sui L-F et al (2011) the influence of optimized train samples on elimination of sounding outliers in the LS-SVM arithmetic. J Geod Geoinf Sci 40(1):22

Google Scholar  

Tanveer M, Sharma A, Suganthan PN (2021) Least squares KNN-based weighted multiclass twin SVM. Neurocomputing 459:454–464

Chu MX, Wang AN, Gong RF (2014) Improvement on least squares twin support vector machine for pattern classification. Acta Electron Sin 42(5):998–1003

Xu J, Wang H, Zhang L et al (2023) Robust twin depth support vector machine based on average depth. Knowl-Based Syst 274:110627

Qiu Y, Wang T, Dai X (2022) Doubly feature-weighted fuzzy support vector machine. J Comput Appl 42(3):683

Wang Y, Yu W, Fang Z (2020) Multiple kernel-based SVM classification of hyperspectral images by combining spectral, spatial, and semantic information. Remote Sens 12(1):120

Yuan C, Yang L (2021) Capped L2, p-norm metric based robust least squares twin support vector machine for pattern classification. Neural Netw 142:457–478

Tanveer M, Sharma S, Muhammad K (2021) Large-scale least squares twin svms. ACM Transac Internet Technol (TOIT) 21(2):1–19

Zhao J, Wang G, Pan JS et al (2023) Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets. Pattern Recogn 139:109406

Zhao J, Yao ZF, Lv L et al (2021) Density peaks clustering based on mutual neighbor degree. Control Decis 36(3):543–552

Yan H, Qi Y, Ye Q et al (2021) Robust least squares twin support vector regression with adaptive FOA and PSO for short-term traffic flow prediction. IEEE Trans Intell Transp Syst 23(9):14542–14556

Cai D, He X, Zhou K, Han J, Bao H (2007) Locality sensitive discriminant analysis. InIJCAI 2007:1713–1726

Richhariya B, Tanveer M (2021) A fuzzy universum least squares twin support vector machine (FULSTSVM). Neural Comput Appl 2021:1–12

Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344(6191):1492–1496

Zhao J, Tang J, Fan T et al (2020) Density peaks clustering based on circular partition and grid similarity. Concurr Comput Pract Exp 32(7):e5567

Du M, Ding S, Xu X et al (2018) Density peaks clustering using geodesic distances. Int J Mach Learn Cybern 9:1335–1349

Zhao J, Wang G, Lv L et al (2022) Geodesic distance and cosine inverse nearest neighbour density peak clustering algorithm for manifold data. Acta Electron Sinica 50(11):2730–2737

Xie X, Sun F, Qian J et al (2023) Laplacian Lp norm least squares twin support vector machine. Pattern Recogn 136:109192

Chen S, Cao J, Chen F et al (2020) Entropy-based fuzzy least squares twin support vector machine for pattern classification. Neural Process Lett 51:41–66

Xie F, Xu Y (2019) An efficient regularized K-nearest neighbor structural twin support vector machine. Appl Intell 49:4258–4275

Xie J, Hone K, Xie W et al (2013) Extending twin support vector machine classifier for multi-category classification problems. Intell Data Anal 17(4):649–664

Zhang XK, Ding SF (2016) Mahalanobis distance-based Twin Multi-class classification support vector machine. Comput Sci 43(3):49–53

Ali J, Aldhaifallah M, Nisar KS et al (2022) Regularized least squares twin svm for multiclass classification. Big Data Res 27:100295

Xu Y, Guo R, Wang L (2013) A twin multi-class classification support vector machine. Cogn Comput 5(4):580–588

Xu Y (2016) K-nearest neighbor-based weighted multi-class twin support vector machine. Neurocomputing 205:430–438

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China with No. 62066030.

Author information

Authors and affiliations.

College of Information Engineering, Nanchang Institute of Technology, Nanchang, Jiangxi, 330099, People’s Republic of China

Li Lv, Zhipeng He, Juan Chen & Fayang Duan

College of Science, Nanchang Institute of Technology, Nanchang, Jiangxi, 330099, People’s Republic of China

College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong, 266000, People’s Republic of China

Jeng-Shyang Pan

Nanchang Key Laboratory of IoT Perception and Collaborative Computing for Smart City, Nanchang Institute of Technology, Nanchang, Jiangxi, 330099, People’s Republic of China

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Li Lv .

Ethics declarations

Conflict of interest.

The authors declare that they have no competing interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Lv, L., He, Z., Chen, J. et al. Weighted least squares twin support vector machine based on density peaks. Pattern Anal Applic 27 , 106 (2024). https://doi.org/10.1007/s10044-024-01311-x

Download citation

Received : 20 April 2023

Accepted : 22 July 2024

Published : 03 September 2024

DOI : https://doi.org/10.1007/s10044-024-01311-x

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Twin support vector machines
• Density weighting strategy
• Density peaks
• Extensive weights
• Inter-class separability metric matrix
• Find a journal
• Publish with us
• Track your research