How many lines can be drawn to distinguish the sample points?

: There are countless lines that can be drawn, the difference is that Good effect.

For example, the green line is not good, the blue line is okay, and the red line looks better.

What we hope to findBest effect lineKnown as Dividing the hyperplane

Why is it called "hyperplane"?

: Because the features of the sample are likely to be high-dimensional, the division of the sample space at this time requires a "hyperplane".

What is the standard for drawing lines? / What makes this line work well?

: SVM will look for two classes that can distinguish and enable Maximum margin Hyper plane, ie  Dividing the hyperplane.

What is the margin?

: Margin is the sum of the distances of a line from the nearest points on both sides of it.

For example, the band-shaped area formed by the two dashed lines in the figure below is margin, and the dashed line is determined by the two points closest to the central solid line. However, the margin is relatively small at this time. If you use the second method to draw, the margin becomes significantly larger and closer to our goal

Why make the margin as large as possible?

: Because the big margin is less likely to make mistakes

How to choose the Max Margin Hyperplane (MMH)?

: Distance from hyperplane to nearest point on one sideequalThe distance to the nearest point on the other side, the two hyperplanes on both sides are parallel

SVM algorithm characteristics

The algorithm complexity of the trained model is determined byDetermine the number of support vectors, Not by the dimensions of the data. So SVM is less prone to overfitting.

Model trained by SVMTotally dependent on support vectorsEven if all non-support vector points in the training set are removed and the training process is repeated, the result will still get the exact same model.

If the number of support vectors trained by an SVM is relatively small, the model trained by the SVM is easier to generalize.

SVM definition and formula establishment

A hyperplane can be defined as:

                                                         wT X+b=0

W: weight vector,   

X: training example

b: bias Assume a 2-dimensional feature vector: X=( x 1 ,x 2 )

Think of b as extra wight, and write it as    w0

The hyperplane equation is: 

The upper right points of all hyperplanes satisfy:

All points on the lower left of the hyperplane satisfy: 

                                                                 w0​+w1​x1​+w2​x2​<0

Adjust the weight so that the hyperplane is defined as follows:H

                                        H1:w0​+w1​x1​+w2​x2​≥1     for yi​=+1

                                        H2:w0​+w1​x1​+w2​x2​≤−1     for yi​=−1

Combining the above two formulas, we get:

                                     y i∗(w 0+w 1x 1 +w 2x 2 )≥1, ∀i

All points that lie on the marginal hyperplane are called (support vectors)

Meaning: A support vector is a point that is just pasted on the plane where the margin is located. They are used to define the margin and are the 划分超平面closest points.

Role: The support vector supports the marginal region and is used to establish the division hyperplane.

Note: There may be more than one support vector on one side, and there may be multiple points on one side all attached to the marginal plane.

Divide the distance between the hyperplane and any point on the marginal hyperplane on both sides of it by   1/∣∣w∣∣

                                          (ie: where   ∣∣w∣∣ is the norm of a vector (norm))

Therefore, the maximum marginal distance is: 2/|| w ||

The derivation process is to be supplemented.

SVM solution process

How does SVM find the hyperplane with the largest margin (MMH)?

Use some mathematical derivation, formula 

 y i∗( w0+w 1 x 1+w 2x 2)≥1 , ∀ i can become a restricted quadratic optimization problem

Using Karush-Kuhn-Tucker (KKT) conditions and Lagrangian formula, it can be deduced that MMH can be expressed as the following "decision boundary"

This equation represents the marginally maximized division of the hyperplane.

1. L  is the number of support vector points, because most points are not support vector points, and only some points on the marginal hyperplane are support vector points. Then we only sum the points that belong to the support vector;
2. XiEigenvalues ​​of support vector points;
3. yi  Is the support vector point Xi The class label, such as +1 or -1;
4. X ^ T   is the instance to be tested. I want to know which category it belongs to, and bring it into the equation.
5. α i And  b0Are single numerical parameters, which are obtained by the above-mentioned optimal algorithm, αi Is the Lagrangian multiplier.

Whenever there is a new test sample X , bring it into the equation, see if the value of the equation is positive or negative, and categorize by sign.

SVM solution case

Take a look at how SVM finds a partitioned hyperplane.

We already know the two support vector points (1,1) and (2,3), set the weight to w = (a, 2a ) , then the coordinates of the two support vector points are brought into the formula respectively   w ^ Tx + b = \  ± 1 , you can get:

Bring back the weight vector w has: w=

Then divided hyperplane x_1
Finally, you can verify with the point (2,0) at the division hyperplane classification results. 

SVM application examples

Because the implementation of the SVM algorithm itself is very complicated, we do not study how to implement SVM ourselves, but still use the sklearn library to help us learn the application problem of SVM.

# sklearn import svm module

from sklearn import svm

# Define three points and labels

X = [[2, 0], [1, 1], [2,3]] y = [0, 0, 1]

# Define classifier, clf means classifier, which is the traditional name of classifier

clf = svm.SVC(kernel = 'linear') # .SVC（） is the SVM equation, and the parameter kernel is a linear kernel function

# Training classifier

clf.fit(X, y) # Call the fit function of the classifier to build the model

(that is, calculate the hyperplane division and all relevant attributes are

stored in the classifier cls)

# Print a series of parameters of classifier clf

আউটপুট ফলাফল:

print(__doc__)

# Import related packages

import numpy as np import pylab as pl # Drawing function

from sklearn import svm

# Create 40 points

np.random.seed(0)

X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]

# Two categories each with 20 points, Y is a column vector of 40 rows and 1 column20 টি পয়েন্ট সহ প্রতিটি দুটি বিভাগ, ওয়াই হ'ল 40 টি সারি এবং 1 কলামের কলাম ভেক্টর.

# Create svm model

clf = svm.SVC(kernel='linear') clf.fit(X, Y)

Automatically created module for IPython interactive environment

w:  [0.90230696 0.64821811]

a:  -1.391980476255765

support_vectors_:  [[-1.02126202  0.2408932 ]

 [-0.46722079 -0.53064123]

 [ 0.95144703  0.57998206]]

clf.coef_:  [[0.90230696 0.64821811]]

kernel trick

Motivation to use nuclear methods

Formulas that are solved when converted to an optimization problem in a linear SVM are calculated usingInner product(dot product), where ϕ( X)\ phi (X)ϕ ( X ) is a vector point in the training set that is transformed into a high-dimensional non-linear mapping function.Algorithm complexity is very largeTherefore, we use the kernel function instead of calculating the inner product of the non-linear mapping function.

The inner product of the following kernel functions and non-linear mapping functions is equivalent, but the operation of the kernel function K is much less than the inner product.

How do I choose which kernel to use?

1. According to prior knowledge, such as image classification, RBF (Gaussian Radial Basis Function) is usually used, and RBF is not used for text.
2. Try different kernels, depending on the accuracy of the results. Try different kernels, depending on the accuracy of the results.

Examples of kernel functions

Related concepts supplement

Linear distinguishable and linear indistinguishable

Linear points can be used to classify sample points, otherwise they are linear inseparable.

The following three examples are all linearly indistinguishable, that is, two types of sample points cannot be distinguished by a straight line.

In the case of linear inseparability, the corresponding vector of the data set in space cannot be distinguished by a hyperplane, how to deal with it?

: Two steps to solve:

1. Use a non-linear mapping to transform the vector points in the original data set into a higher dimensional space (for example, the following figure maps points in two-dimensional space to three-dimensional space)
2. Get a linear space in this high-dimensional processing according to the hyperplane linearly separable case