ML10 self study notes SVM

SVM（ Classification problem ）

SVM deduction

Want the maximum distance between the two classes

To calculate the distance . Suppose the decision boundary is such a plane , That is to calculate the distance from this point to the straight line .
Definition of plane ：W^TX=b.W^T For the normal vector . All we have to do is dist(x,h), But direct calculation is troublesome , Usually, it is calculated in this way .
Find two points in the plane x^’ and x^’’, These two points can be brought into the plane formula , Two points form a vector ,dist This vector is related to x^’ and x^’’ The vector formed is vertical . Such as ② Formula , The normal vector is perpendicular to any vector in the plane .
Because it is difficult to calculate the straight-line distance , So calculate the distance between two points instead , You can calculate X And X^’ The distance between them can be obtained by projecting in the vertical direction dist(x,h), Such as the formula in the last line . Then an equal sign is used to simplify , take X^’ use ① Formula substitution .

data

y(x_i) It's the forecast ,Y_i It's the tag value .

Objective function

The original distance is |w^tx+b|, With absolute value , But in the previous decision equation y(x_i) And y_i The product of is always positive , Therefore, the absolute value can be directly removed after multiplication in the formula in this section .

min Next is the required point closest to the decision boundary （ sample ）, Find the distance ,max Is the greatest distance , This maximizes the distance obtained just now . What is the goal w Make this objective function maximum .

Objective function solution

Be practical w The minimum value of . Because of the demand w and w² The minimum value of is the same , So we need 1/2w² The minimum value of is the same .

Use Lagrange multiplier method to solve .

There is a dual property . Minimum required , You can find the partial derivative .

Like what? w,b bring L Minimum , And then put w,b Replace the original formula

next step , What kind of α_i Make the whole largest . Usually, the maximum value will be converted into the minimum value （ Plus a minus sign ）.

SVM Solving examples

Dot product in brackets is inner product . That is, substitute the data .

solve , Finding partial derivatives . Because all α_i, Must be greater than zero ( constraint condition ), But when right α₂ When the partial derivative equals zero , The obtained value is complex , So the best value is on the boundary , Make α₁ and α₂ Take zero respectively . The second satisfaction , It can be obtained from the previous formula α₃.

Bring back w solve . For sample points , as long as α It's zero , Then he is meaningless , No more calculations , According to the previous image ,x₂ It won't be included in the calculation formula , The final result is composed of samples on the boundary , therefore x₂ Points on non boundary are not included in the calculation formula .

Soft space

The objective function has also changed .

Additional parameters .

Nuclear transformation

It was linear , Not used Φ(x) function , Just use a simple x,

Because mapping to high dimensions is sometimes difficult to calculate , First map to the high dimension , It is troublesome to calculate the inner product of high-dimensional multiple data , But by first finding the inner product and then mapping , First find the inner product , Then mapping can achieve the same effect , But the computational complexity is reduced .

When there is no kernel function , Classification is not very good （ That solid line ）, The classification is better after using Gaussian kernel function , loops . The kernel function is to make the low dimension indivisible , Convert to high dimensional separable .