1 Kernel Functions - Princeton University

1 STA561: Probabilistic machine learningKernels and Kernel Methods (10/09/13)Lecturer: Barbara EngelhardtScribes: Yue Dai, Li Lu, Will Wu1 Kernel What are Kernels?Kernelsare a way to represent your data samples flexibly so that you can compare the samples in a complexspace. Kernels have shown great utility in comparing images of different sizes protein sequences of different lengths object 3D structures networks with different numbers of edges and/or nodes text documents of different lengths and of these objects have different numbers and types of features. We want to be able to cluster data samplesto find which pairs are neighbors in this complex, high dimensional space. A Kernel is an arbitrary functionthat lets us map objects in this complex space to a high dimensional space that enables comparisons of thesecomplex features in a simple way. We have anXspace of our samples, and a feature space that we defineby first defining a Kernel function.

2 This helps with:1. Comparing: it may be hard to compare two different text documents with different number of properly-defined Kernel gives us a metric by which we can quantify the similarities between twoobjects;2. Classification: even if we can quantify similarity in our feature space, simple classifiers may not performwell in this space. We may want to project our data to a different space and classify our samples inthis in class, we used a fixed set of features and a probabilistic modeling approach. We turn to largemargin classifiers and a Kernel -based approach in this Kernel some abstract spaceX( , documents, images, proteins, etc.), function :X X 7 Ris called akernel function. Kernel Functions are used to quantify similarity between a pair of objectsxandx and Kernel MethodsA Kernel function typically satisfies the following two properties (but this is not required for all kernelmethods). A Kernel with these properties will loosely have the interpretation as a similarity quantificationbetween the two objects.

3 (symmetric) x,x X, (x,x ) = (x ,x),(non-negative) x,x X, (x,x ) Mercer KernelsLetX={x1,..,xn}be a finite set ofnsamples fromX. TheGram matrixofXis defined asK(X; ) Rn n, orKfor short, such that (K)ij= (xi,xj). If X X, the matrixKis positive definite, is called aMercer Kernel , or apositive definite Kernel . A Mercer Kernel will be symmetric by definition ( ,K=KT).Mercer s the Gram matrix is positive definite, we can compute an eigenvector decompositionof the Gram matrix as:K=UT U(1)where =diag( 1,.., n) ( iis thei-th eigenvalue ofKand will be greater than 0 because the matrix ispositive definite). Consider an element ofK, we have a dot product between two vectors:Kij= ( 1/2U:,i)T( 1/2U:,j)(2)Define (xi) = 1/2U:,i. The equation above can be re-written asKij= (xi)T (xj)(3)Let s think about this function: each element of the Kernel can be described as the inner product of a function ( ) applied to objectsx,x . Each element of the Mercer Kernel lives in the Hilbert space, where a Hilbertspace is an abstract vector space defined by the inner product of two arbitrary , if our Kernel is a Mercer Kernel , then there exists a function :X 7 Dsuch that (x,x ) = (x)T (x ).

4 (4)To foreshadow upcoming concepts, we will call ( ) abasis function, and we will describe the spaceDasfeature space. We can then say that we map our objects to a feature space using a basis function ( ) (for a Mercer Kernel ) can be written as a linear combination of eigen Functions of .There are absolutely no restrictions on the dimensionality of feature spaceD; in fact,Dis potentiallyinfinite dimensional. Note that: Many Kernel methods do not require us to explicitly compute (x), but instead we will compute then nGram matrix using the Kernel function ( , ). In other words, we are able to build classifiersin arbitrarily complexDfeature space, but we do not have to compute any element of that spaceexplicitly. Whereas computing (x) from may be difficult (and is often unnecessary), it is straightforward touse intuitive basis Functions (x) to construct the Kernel (x,x ). We will see examples of this and Kernel Power of KernelsLet s say we havenscalar objects ( , a one dimensional input space), and a kernelized linear can we separate s and s with one line?

5 The idea is to project them to a higher dimension, and usea linear classifier in that feature (xi) = [xi,x2i], and, by definition, (xi,xj) =xixj+x2ix2j. This example projects an object in inputspace into a two-dimensional feature space using the basis function ( ), which is easy to compute. Now alinear classifier can separate the two classes perfectly (Figure 1).(a) No linear classifier can separate s and s in 1-d(b) Linear classifier after mapping each 1-d pointxito 2-d as (xi,x2i)Figure 1: Example showing the power of kernels for idea behind Kernel methods is to take a set of observations and project each of them to a space withinwhich comparisons between points are straightforward. Because the dimension of the feature space is arbi-trarily high, we can often use simple classifiers within this complex feature space, but we will need to becareful about testing for over fitting (although this comes later).2 Examples of Linear KernelsLet (x) =x, we get thelinear Kernel , defined by just the dot product between the two object vectors: (x,x ) =xTx (5)The dimension of the feature spaceDof a linear Kernel is the same as the dimension of the input spaceX,equivalent to the number of features of each object, and (x) = might use a linear Kernel when it is not necessary to work in an alternative feature space, if, for example,the original data are already high dimensional, comparable, and may be linearly separable into respectiveclasses within the input kernels are good for objects represented by a large number of features of a fixed length, , bag-of-words.

6 Consider a vocabularyVwith|V|=mdistinct words. A feature vectorx Rmrepresents adocumentDusing the count of each word ofVin the document (Figure 2). Note that, despite the documentspossibly having very different word lengths, the feature vector for every document in a collection is and Kernel MethodsFigure 2: Feature vectors for Gaussian KernelsTheGaussian Kernel , (also known as thesquared exponential Kernel SE Kernel orradial basis function RBF) is defined by (x,x ) = exp( 12(x x )T 1(x x ))(6) , the covariance of each feature across observations, is ap-dimensional matrix. When is a diagonalmatrix, this Kernel can be written as (x,x ) = exp 12p j=11 2j.(xj x j)2 (7) jcan be interpreted as defining thecharacteristic length scaleof featurej. Furthermore, if is spherical, , j= , j, (x,x ) = exp( ||x x ||22 2)(8)For this Kernel , the dimension of the feature space defined by ( ) isD= . Our methods will allow usto avoid explicit computation of ( ).

7 We can easily compute then nGram matrix using this relative ofthe Mahalanobis Distance, even though we have implicitly projected our objects to an infinite dimensionalfeature String KernelsIf we re interested in matching all substrings (for example) instead of representing an object as a bag ofwords, we can use astring Kernel :The quick brownfox ..Yesterday I went to an alphabet, ,{a,..,z}, andA = [A,A2,..,Am], wheremis the length of the longeststring we would like to match. Then, just as in the bag-of-words scenario, a basis function (x) will map astringxto a vector of length|A |, where each elementjis the number of times we observe substringA jinstringx, wherej= 1 :|A |.11 Superscripts here are regular expression the set of all possible strings of lengthi, with each positionoccupied by any character from the alphabetA. is known as the Kleene star and Kernel Methods5 Figure 3: Fitting a linear logistic regression classifier using a Gaussian Kernel with centroids specified by the4 black kernelmeasures the similarity of two stringsxandx : (x,x ) = s A ws s(x) s(x )(9)where s(x) denotes the number of occurrences of substringsin size of the underlying space,|A |is very large.

8 Regardless of the size of the substring spaceA , (x,x )can be computed inO(|x|+|x |), or linear time, for fixed weight functionw, using suffix trees. A suffix treecontains all possible suffixes in a particular string. To compute (x,x ), build amlevel suffix tree using onestringx, and search in that tree for matches with the second stringx . This is a linear time can design our Kernel for our application by setting the weightswto specific values. Here are a coupleof special cases for the choice of weight functionw. ws= 0 for|s|>1: comparing the alphabet between strings (substrings of length one) w= 0 for all words outside of a vocabulary: equivalent to (weighted) bag-of-words Fisher KernelsWe can construct a Kernel based on a chosen generative model using the concept of a Fisher Kernel . The ideais that this Kernel represents the distance in likelihood space between different objects for a fitted generativemodel. AFisher kernelis defined as (x,x ) =g(x)TF 1g(x )(10)wheregis the gradient of the log likelihood, evaluated at MLE, andFis the Hessian, (x) = logp(x| )| MLEandF= logp(x| )| MLE6 Kernels and Kernel MethodsFigure 4: Fitting a 1D data set usingD= 10 uniformly spaced Gaussian prototypes, with varying lengthscale 2( , , 50 from top to bottom)3 Applications of Kernelized Machine (x) = [ (x, 1), (x, 2).]

9 , (x, D)](11)where d Xare a set ofDcentroids. (x) is called akernelized feature vector projects a new data pointxinto theD-dimensional feature space by computing the similaritybetweenxand each centroid 1:Dvia ( , ). Then we can use thiskernelized feature vectorfor logisticregression by definingp(y|x, ) = Ber(wT (x)). (x) cannot be computed using the Kernel trick (see below) and must be computed explicitly, soDmust bea reasonable size for computation. The kerneled feature vector quantifies the distance of a particularxtoeach of the predefined centroids. This provides a simple way to define a non-linear decision boundary usinga linear classifier like logistic regression, as shown in Figure 3, using (for example) a Gaussian Kernel withfour can also use the kernelized feature vector inside linear regression model by definingp(y|x, ) =N( T (x), 2).Figure 4 shows the result of fitting a 1D data set withD= 10 uniformly spaced Gaussian prototypes, withvarying length scale.

10 Too small ( = ) overfitting. generalizeable ( = ) right line nice generalization properties too large ( = 50) and Kernel Methods7 Consider the transition from high-dimension linear classifier to a one-dimension linear classifier. We firstmap the input one- dimensional spacexup to a very high-dimensional feature space and fit a hyperplanein feature space that is the linear classifier. The hyperplane projected back onto the one-dimensional inputspace is not necessarily linear, as we see in this trickRecall that our basis function (x) projects ourxinto feature space. In the above twomethods, we define our feature vector in terms of the basis function, (x). In a number of other methodsand statistical models, the feature vectorxonly enters the model through comparisons with other featurevectorsxTx . If wekernelizethese inner products, we get (x)T (x) = (x,x ). When we are allowed tocompute only (x,x ) in computation, and avoid working in feature space, we enable large, possibly infinite-dimensional, feature spaces (m n), whereas because we are using the kernelized inner products, we workin ann nspace (the Gram matrix).