Outline (Level 1-2) SVM 2 Linear SVM in LSC o Convex optimization Linear separability and classifier o Linear SVM in LSC Maximum Margin Types of SVM SV and margin boundary Three Types of Margin Lagrange Duality Modeling of SVM Optimization o Dual method of linear SVM in o Primal optimization problem for LSC 10/263
Outline (Level 1-2) 2 Linear SVM in LSC Linear separability and classifier Types of SVM Three Types of Margin Modeling of SVM Optimization Primal optimization problem for SVM Convex optimization Linear SVM in LSC - Maximum Margin SV and margin boundary Lagrange Duality Dual method of linear SVM in LSC 10 / 263
2.Linear SVM in LSC 2.1.Linear separability and classifier Linear separability of datasets Definition:given a data set T={x1,h),(x2,2),,(xw,N)} where,.x∈X=R",y∈Jy={+1,-1},i=1,2,.,N. If there is a hyperplane S w·x+b=0, which can completely and correctly divide the positive and negative samples of dataset to both sides of the hyperplane,that is,for all samples of yi=+1 with wxi+b>0 and for all samples of y;=-1 with w.xi+b<0,then dataset T is called a linearly separable dataset;otherwise,it is said to be linearly inseparable dataset. 11/263
2. Linear SVM in LSC 2.1. Linear separability and classifier ▶ Linear separability of datasets Definition: given a data set T = {(x1, y1),(x2, y2), . . . ,(xN, yN)}, where，xi ∈ X = R n , yi ∈ Y = {+1, −1}, i = 1, 2, . . . , N . If there is a hyperplane S w · x + b = 0, which can completely and correctly divide the positive and negative samples of dataset to both sides of the hyperplane, that is, for all samples of yi = +1 with w · xi + b > 0 and for all samples of yi = −1 with w · xi + b < 0 , then dataset T is called a linearly separable dataset; otherwise, it is said to be linearly inseparable dataset. 11 / 263
Linear classifier Goal of learning linear classifier:find a separation hyperplane S in the feature space to classify samples into different classes,which is: w·x+b=0, Normal vector w and intercept b determine S which divides feature space into two parts.Side to which the normal vector points is positive class and other side is negative class. Different ws for separation planes at the same location: 1.w1=(1,1),b=0 2.2=-w1=(-1,-1)7,b=0 The positive and negative class positions of S represented by wi and w2 are exactly opposite. 12/263
Linear classifier ▶ Goal of learning linear classifier: find a separation hyperplane S in the feature space to classify samples into different classes, which is: w · x + b = 0, ▶ Normal vector w and intercept b determine S which divides feature space into two parts. Side to which the normal vector points is positive class and other side is negative class. ▶ Different ws for separation planes at the same location: 1. w1 = (1, 1)T , b = 0 2. w2 = −w1 = (−1, −1)T , b = 0 The positive and negative class positions of S represented by w1 and w2 are exactly opposite. 12 / 263
Generally,when training data set is linearly separable,there are infinite number of separation hyperplanes that can correctly separate two classes of data. Perceptron:use the minimum misclassification strategy to obtain the separation hyperplane.Thus,there are infinite number of solutions. linear SVM in linearly separable case (LSC):use the maximum margin strategy to find the optimal separation hyperplane.Thus,the solution is unique. 13/263
▶ Generally, when training data set is linearly separable, there are infinite number of separation hyperplanes that can correctly separate two classes of data. ▶ Perceptron: use the minimum misclassification strategy to obtain the separation hyperplane. Thus, there are infinite number of solutions. ▶ linear SVM in linearly separable case (LSC): use the maximum margin strategy to find the optimal separation hyperplane. Thus, the solution is unique. 13 / 263
Outline (Level 1-2) SVM Linear SVM in LSC o Convex optimization Linear separability and classifier o Linear SVM in LSC Maximum Margin Types of SVM SV and margin boundary Three Types of Margin Lagrange Duality Modeling of SVM Optimization o Dual method of linear SVM in o Primal optimization problem for LSC 14/263
Outline (Level 1-2) 2 Linear SVM in LSC Linear separability and classifier Types of SVM Three Types of Margin Modeling of SVM Optimization Primal optimization problem for SVM Convex optimization Linear SVM in LSC - Maximum Margin SV and margin boundary Lagrange Duality Dual method of linear SVM in LSC 14 / 263