1、Support Vector Machines and Kernels,Adapted from slides by Tim Oates Cognition, Robotics, and Learning (CORAL) Lab University of Maryland Baltimore County,Doing Really Well with Linear Decision Surfaces,Outline,Prediction Why might predictions be wrong? Support vector machines Doing really well with
2、 linear models Kernels Making the non-linear linear,Supervised ML = Prediction,Given training instances (x,y) Learn a model f Such that f(x) = y Use f to predict y for new x Many variations on this basic theme,Why might predictions be wrong?,True Non-Determinism Flip a biased coin p(heads) = Estimat
3、e If 0.5 predict heads, else tails Lots of ML research on problems like this Learn a model Do the best you can in expectation,Why might predictions be wrong?,Partial Observability Something needed to predict y is missing from observation x N-bit parity problem x contains N-1 bits (hard PO) x contain
4、s N bits but learner ignores some of them (soft PO),Why might predictions be wrong?,True non-determinism Partial observability hard, soft Representational bias Algorithmic bias Bounded resources,Representational Bias,Having the right features (x) is crucial,X,O,O,O,O,X,X,X,X,O,O,O,O,X,X,X,Support Ve
5、ctor Machines,Doing Really Well with Linear Decision Surfaces,Strengths of SVMs,Good generalization in theory Good generalization in practice Work well with few training instances Find globally best model Efficient algorithms Amenable to the kernel trick,Linear Separators,Training instances x n y -1
6、, 1 w n b Hyperplane+ b = 0 w1x1 + w2x2 + wnxn + b = 0 Decision function f(x) = sign( + b),Math Review Inner (dot) product:= a b = ai*bi = a1b1 + a2b2 + +anbn,Intuitions,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Intuitions,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Intuitions,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Intuitions,X
7、,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,A “Good” Separator,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Noise in the Observations,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Ruling Out Some Separators,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Lots of Noise,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Maximizing the Margin,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,“
8、Fat” Separators,X,X,O,O,O,O,O,O,X,X,X,X,X,X,O,O,Why Maximize Margin?,Increasing margin reduces capacity Must restrict capacity to generalize m training instances 2m ways to label them What if function class that can separate them all? Shatters the training instances VC Dimension is largest m such th
9、at function class can shatter some set of m points,VC Dimension Example,X,X,X,O,X,X,X,O,X,X,X,O,O,O,X,O,X,O,X,O,O,O,O,O,Bounding Generalization Error,Rf = risk, test error Rempf = empirical risk, train error h = VC dimension m = number of training instances = probability that bound does not hold,Rf
10、Rempf +,Support Vectors,X,X,O,The Math,Training instances x n y -1, 1 Decision function f(x) = sign( + b) w n b Find w and b that Perfectly classify training instances Assuming linear separability Maximize margin,The Math,For perfect classification, we want yi ( + b) 0 for all i Why? To maximize the
11、 margin, we want w that minimizes |w|2,Dual Optimization Problem,Maximize over W() = i i - 1/2 i,j i j yi yj Subject toi 0 i i yi = 0 Decision function f(x) = sign(i i yi + b),What if Data Are Not Perfectly Linearly Separable?,Cannot find w and b that satisfy yi ( + b) 1 for all i Introduce slack va
12、riables i yi ( + b) 1 - i for all i Minimize |w|2 + C i,Strengths of SVMs,Good generalization in theory Good generalization in practice Work well with few training instances Find globally best model Efficient algorithms Amenable to the kernel trick ,What if Surface is Non-Linear?,Image from http:/ M
13、ethods,Making the Non-Linear Linear,When Linear Separators Fail,X,O,O,O,O,X,X,X,x1,x2,Mapping into a New Feature Space,Rather than run SVM on xi, run it on (xi) Find non-linear separator in input space What if (xi) is really big? Use kernels to compute it implicitly!, : x X = (x),(x1,x2) = (x1,x2,x1
14、2,x22,x1x2),Image from http:/web.engr.oregonstate.edu/afern/classes/cs534/,Kernels,Find kernel K such that K(x1,x2) = Computing K(x1,x2) should be efficient, much more so than computing (x1) and (x2) Use K(x1,x2) in SVM algorithm rather than Remarkably, this is possible,The Polynomial Kernel,K(x1,x2
15、) = 2 x1 = (x11, x12) x2 = (x21, x22)= (x11x21 + x12x22)2 = (x112 x212 + x122x222 + 2x11 x12 x21 x22)(x1) = (x112, x122, 2x11 x12)(x2) = (x212, x222, 2x21 x22) K(x1,x2) = ,The Polynomial Kernel,(x) contains all monomials of degree d Useful in visual pattern recognition Number of monomials 16x16 pixe
16、l image 1010 monomials of degree 5 Never explicitly compute (x)! Variation - K(x1,x2) = ( + 1) 2,Kernels,What does it mean to be a kernel? K(x1,x2) = for some What does it take to be a kernel? The Gram matrix Gij = K(xi, xj) Positive definite matrixij ci cj Gij 0 for ci, cj Positive definite kernel
17、For all samples of size m, induces a positive definite Gram matrix,A Few Good Kernels,Dot product kernel K(x1,x2) = Polynomial kernel K(x1,x2) = d (Monomials of degree d) K(x1,x2) = ( + 1)d (All monomials of degree 1,2,d) Gaussian kernel K(x1,x2) = exp(-| x1-x2 |2/22) Radial basis functions Sigmoid
18、kernel K(x1,x2) = tanh( + ) Neural networks Establishing “kernel-hood” from first principles is non-trivial,The Kernel Trick,“Given an algorithm which is formulated in terms of a positive definite kernel K1, one can construct an alternative algorithm by replacing K1 with another positive definite ke
19、rnel K2”,SVMs can use the kernel trick,Using a Different Kernel in the Dual Optimization Problem,For example, using the polynomial kernel with d = 4 (including lower-order terms).Maximize over W() = i i - 1/2 i,j i j yi yj Subject toi 0 i i yi = 0 Decision function f(x) = sign(i i yi + b),( + 1)4,X,( + 1)4,X,So by the kernel trick, we just replace them!,Exotic Kernels,Strings Trees Graphs The hard part is establishing kernel-hood,Application: “Beautification Engine” (Leyvand et al., 2008),Conclusion,SVMs find optimal linear separator The kernel trick makes SVMs non-linear learning algorithms,
