15.097 Lecture 13: Kernels

Kernels MIT 15.097 Course Notes Cynthia Rudin Credits: Bartlett, Schölkopf and Smola, Cristianini and Shawe-Taylor The kernel trick that I’m going to show you applies much more broadly than SVM, but we’ll use it for SVM’s. Warning: This lecture is technical. Try to get the basic idea even if you don’t catch all the details. Basic idea: If you can’t separate positives from negatives in a low-dimensional space using a hyperplane, then map everything to a higher dimensional space where you can separate them. The picture looks like this but it’s going to be a little confusing at this point: f F X o x f(o) x o x f(x) f(x) f(o) o f(o) o f(o) x f(x) f(x) Image by MIT OpenCourseWare. or it might look like this: 1 Input Space Feature Space Image by MIT OpenCourseWare. Say I want to predict whether a house on the real-estate market will sell today or not:   x= x(1) |{z} x(2) |{z} , house’s list price x(3) |{z} , estimated worth length of time on market , x(4) |{z} , ... . in a good area We might want to consider something more complicated than a linear model:
  Example 1: [x(1) , x(2) ] → Φ [x(1) , x(2) ] = x(1)2 , x(2)2 , x(1) x(2) The 2d space gets mapped to a 3d space. We could have the inner product in the 3d space: Φ(x)T Φ(z) = x(1)2 z (1)2 + x(2)2 z (2)2 + x(1) x(2) z (1) z (2) . Example 2:  [x , x , x ] → Φ [x , x , x ] (1) (2) (3)  (1) (2) (3) = [x(1)2 , x(1) x(2) , x(1) x(3) , x(2) x(1) , x(2)2 , x(2) x(3) , x(3) x(1) , x(3) x(2) , x(3)2 ] and we can take inner products in the 9d space, similarly to the last example. 2 Rather than apply SVM to the original x’s, apply it to the Φ(x)’s instead. The kernel trick is that if you have an algorithm (like SVM) where the examples appear only in inner products, you can freely replace the inner product with a different one. (And it works just as well as if you designed the SVM with some map Φ(x) in mind in the first place, and took the inner product in Φ’s space instead.) Remember the optimization problem for SVM? max α m X i=1 m 1X αi − αi αj yi yk xTi xk ← inner product 2 i,k=1 s.t. 0 ≤ αi ≤ C, i = 1, ..., m and m X α i yi = 0 i=1 You can replace this inner product with another one, without even knowing Φ. In fact there can be many different feature maps that correspond to the same inner product. In other words, we’ll replace xT z (i.e., hx, ziRn ) with k(xi , xj ), where k happens to be an inner product in some feature space, hΦ(x), Φ(x)iHk . Note that k is also called the kernel (you’ll see why later). Example 3: We could make k(x, z) the square of the usual inner product: !2 n X n n X X (j) (j) 2 = x(j) x(k) z (j) z (k) . k(x, z) = hx, ziRn = x z j=1 j=1 k=1 But how do I know that the square of the inner product is itself an inner product in some feature space? We’ll show a general way to check this later, but for now, let’s see if we can find such a feature space.
  Well, for n = 2, if we used Φ [x(1) , x(2) ] = x(1)2 , x(2)2 , x(1) x(2) , x(2) x(1) to map into a 4d feature space, then the inner product would be: Φ(x)T Φ(z) = x(1)2 z (1)2 + x(2)2 z (2)2 + 2x(1) x(2) z (1) z (2) = hx, zi2R2 . 3 So we showed that k is an inner product for n = 2 because we found a feature space corresponding to it. For n = 3 we can also find a feature space, namely the 9d feature space from Example 2 would give us the inner product k. That is, Φ(x) = (x(1)2 , x(1) x(2) , ..., x(3)2 ), and Φ(z) = (z (1)2 , z (1) z (2) , ..., z (3)2 ), hΦ(x), Φ(z)iR9 = hx, zi2R3 . That’s nice. We can even add a constant, so that k is the inner product plus a constant squared. Example 4: n X k(x, z) = (xT z + c)2 = ! x(j) z (j) + c j=1 = = n n X X ! x(`) z (`) + c `=1 x(j) x(`) z (j) z (`) + 2c j=1 `=1 n X (j) (`) n X n X x(j) z (j) + c2 j=1 n X √ √ (x x )(z z ) + ( 2cx(j) )( 2cz (j) ) + c2 , (j) (`) j=1 j,`=1 and in n = 3 dimensions, one possible feature map is: √ √ √ Φ(x) = [x(1)2 , x(1) x(2) , ..., x(3)2 , 2cx(1) , 2cx(2) , 2cx(3) , c] and c controls the relative weight of the linear and quadratic terms in the inner product. Even more generally, if you wanted to, you could choose the kernel to be any higher power of the regular inner product. Example 5: For any integer d ≥ 2 k(x, z) = (xT z + c)d , 4
where the feature space Φ(x) will be of degree n+d d , with terms for all monomials up to and including degree d. The decision boundary in the feature space (of course) is a hyperplane, whereas in the input space it’s a polynomial of degree d. Now do you understand that figure at the beginning of the lecture? Because these kernels give rise to polynomial decision boundaries, they are called polynomial kernels. They are very popular. Courtesy of Dr. Hagen Knaf. Used with permission. Beyond these examples, it is possible to construct very complicated kernels, even ones that have infinite dimensional feature spaces, that provide a lot of modeling power: 5 © mlpy Developers. All rights reserved. SVMs with these kinds of fancy kernels are among the most powerful ML algorithms currently (a lot of people say the most powerful). But the solution to the optimization problem is still a simple linear combination, even if the feature space is very high dimensional. How do I evaluate f (x) for a test example x then? If we’re going to replace xTi xk everywhere with some function of xi and xk that is hopefully an inner product from some other space (a kernel), we need to ensure that it really is an inner product. More generally, we’d like to know how to construct functions that are guaranteed to be inner products in some space. We need to know some functional analysis to do that. 6 Roadmap 1. make some definitions (inner product, Hilbert space, kernel) 2. give some intuition by doing a calculation in a space with a finite number of states 3. design a general Hilbert space whose inner product is the kernel 4. show it has a reproducing property - now it’s a Reproducing Kernel Hilbert space 5. create a totally different representation of the space, which is a more intuitive to express the kernel (similar to the finite state one) 6. prove a cool representer theorem for SVM-like algorithms 7. show you some nice properties of kernels, and how you might construct them Definitions An inner product takes two elements of a vector space X and outputs number. P a (i) 0 An inner product could be a usual dot product: hu, vi = u v = i u v (i) , or it could be something fancier. An inner product h·, ·i must satisfy the following conditions: 1. Symmetry hu, vi = hv, ui ∀u, v ∈ X 2. Bilinearity hαu + βv, wi = αhu, wi + βhv, wi ∀u, v, w ∈ X , ∀α, β ∈ R 3. Strict Positive Definiteness hu, ui ≥ 0 ∀x ∈ X hu, ui = 0 ⇐⇒ u = 0. 7 An inner product space (or pre-Hilbert space) is a vector space together with an inner product. A Hilbert space is a complete inner product space. (‘Complete’ means sequences converge to elements of the space - there aren’t any “holes” in the space.) Examples of Hilbert spaces include: • The vector space Rn with hu, viRn = uT v, the vector dot product of u and v. • The space `2 of square summable sequences, with inner product hu, vi`2 = P∞ i=1 ui vi • The space L2 (X , µ) of square integrable functions, that is, Rfunctions f such R that f (x)2 dµ(x) < ∞, with inner product hf, giL2 (X ,µ) = f (x)g(x)dµ(x). Finite States Say we have a finite input space {x1 , ..., xm }. So there’s only m possible states for the xi ’s. (Think of the bag-of-words example where there are 2(#words) possible states.) I want to be able to take inner products between any two of them using my function k as the inner product. Inner products by definition are symmetric, so k(xi , xj ) = k(xj , xi ). In other words, in order for us to even consider k as a valid kernel function, the matrix: needs to be symmetric, and this means we can diagonalize it, and the eigendecomposition takes this form: K = VΛV0 where V is an orthogonal matrix where the columns of V are eigenvectors, vt , and Λ is a diagonal matrix with eigenvalues λt on the diagonal. This fact (that 8 real symmetric matrices can always be diagonalized) isn’t difficult to prove, but requires some linear algebra. For now, assume all λt ’s are nonnegative, and consider this feature map: p (i) p (i) p (i) Φ(xi ) = [ λ1 v1 , ..., λt vt , ..., λm vm ]. (writing it for xj too): p (j) p (j) p (j) ]. Φ(xj ) = [ λ1 v1 , ..., λt vt , ..., λm vm With this choice, k is just a dot product in Rm : m X (i) (j) hΦ(xi ), Φ(xj )iRm = λt vt vt = (VΛV0 )ij = Kij = k(xi , xj ). t=1 Why did we need the λt ’s to be nonnegative? Say λs < 0. Form a point in feature space that is a special linear combination of the Φ(xi )’s: z= m X vs(i) Φ(xi ). (coeffs are elements of vs ) i=1 Then calculate kzk22 = hz, ziRm = XX i vs(i) Φ(xi )T Φ(xj ) vs(j) = j XX i vs(i) Kij vs(j) j = vsT Kvs = λs < 0 which conflicts with the geometry of the feature space. We just showed that if k has any chance of being an inner product in a feature space, then matrix K needs to be positive semi-definite (needs to have nonnegative eigenvalues). In fact, we’ll just define kernels in the first place to be positive semi-definite, since they can’t be inner products without that. In the infinite state case, we can’t write out a Gram matrix (like K in the finite state case) for the whole space, because the x’s can take infinitely many values. We’ll just get to pick m examples - we want to make sure the Gram matrix for those examples is positive semi-definite, no matter what examples we get! Let us officially define a kernel. A function k : X × X → R is a kernel if 9 • k is symmetric: k(x, y) = k(y, x). • k gives rise to a positive semi-definite “Gram matrix,” i.e., for any m ∈ N and any x1 , ..., xm chosen from X , the Gram matrix K defined by Kij = k(xi , xj ) is positive semidefinite. Another way to show that a matrix K is positive semi-definite is to show that ∀c ∈ Rm , cT Kc ≥ 0. (1) (This is equivalent to all the eigenvalues being nonnegative, which again is not hard to show but requires some calculations.) Here are some nice properties of k: • k(u, u) ≥ 0 (Think about the Gram matrix of m = 1.) p • k(u, v) ≤ k(u, u)k(v, v) (This is the Cauchy-Schwarz inequality.) The second property is not hard to show for m = 2. The Gram matrix   k(u, u) k(u, v) K= k(v, u) k(v, v) is positive semi-definite whenever cT Kc ≥ 0 ∀c. Choose in particular   k(v, v) c= . −k(u, v) Then since K is positive semi-definite, 0 ≤ cT Kc = [k(v, v)k(u, u) − k(u, v)2 ]k(v, v) (where I skipped a little bit of simplifying in the equality) so we must then have k(v, v)k(u, u) ≥ k(u, v)2 . That’s it! Building a Rather Special Hilbert Space Define RX := {f : X → R}, the space of functions that map X to R. Let’s define the feature map Φ : X → RX so that it maps x to k(·, x) : Φ : x 7−→ k(·, x). So, Φ(x) is a function, and for a point z ∈ X , the function assigns k(z, x) to it. 10 F x F(x) x' F(x') Image by MIT OpenCourseWare. So we turned each x into a function on the domain X . Those functions could be thought of as infinite dimensional vectors. These functions will be elements of our Hilbert space. We want to have k be an inner product in feature space. To do this we need to: 1. Define feature map Φ : X → RX , which we’ve done already. Then we need to turn the image of Φ into a vector space. 2. Define an inner product h, iHk . 3. Show that the inner product satisfies: k(x, z) = hΦ(x), Φ(z)iHk . That’ll make sure that the feature space is a pre-Hilbert space. Let’s do the rest of step 1. Elements in the vector space will look like this, they’ll be in the span of the Φ(xi )’s: f (·) = m X αi k(·, xi ) ← “vectors” i=1 where m, αi and x1 ...xm ∈ X can be anything. (We have addition and multiplication, so it’s a vector space.) The vector space is: ( ) m X span ({Φ(x) : x ∈ X }) = f (·) = αi k(·, xi ) : m ∈ N, xi ∈ X , αi ∈ R . i=1 11 For step 2, let’s grab functions f (·) = and define the inner product: Pm i=1 αi k(·, xi ) and g(·) = Pm0 0 j=1 βj k(·, xj ), 0 hf, giHk = m X m X αi βj k(xi , x0j ). i=1 j=1 Is it well-defined? Well, it’s symmetric, since k is symmetric: 0 hg, f iHk = m X m X βj αi k(x0j , xi ) = hf, giHk . j=1 i=1 It’s also bilinear, look at this: 0 hf, giHk = m X βj j=1 m X 0 αi k(xi , x0j ) = i=1 m X βj f (x0j ) j=1 so we have 0 hf1 + f2 , giHk = m X βj f1 (x0j ) + f2 (x0j )
j=1 0 = m X 0 βj f1 (x0j ) + j=1 m X βj f2 (x0j ) j=1 = hf1 , giHk + hf2 , giHk (look just above) (We can do the same calculation to show hf, g1 + g2 iHk = hf, g1 iHk + hf, g2 iHk .) So it’s bilinear. It’s also positive semi-definite, since k gives rise to positive semi-definite Gram matrices. To see this, for function f , hf, f iHk = m X αi αj k(xi , xj ) = αT Kα ij=1 and we said earlier in (1) that since K is positive semi-definite, it means that for any αi ’s we choose, the sum above is ≥ 0. 12 So, k is almost a inner product! (What’s missing?) We’ll get to that in a minute. For step 3, something totally cool happens, namely that the inner product of k(·, x) and f is just the evaluation of f at x. hk(·, x), f iHk = f (x). How did that happen? And then this is a special case: hk(·, x), k(·, x0 )iHk = k(x, x0 ). This is why k is called a reproducing kernel, and the Hilbert space is a RKHS. Oops! We forgot to show that one last thing, which is that h, iHk is strictly positive definite, so that it’s an inner product. Let’s use the reproducing property. For any x, |f (x)|2 = |hk(·, x), f iHk |2 ≤ hk(·, x), k(·, x)iHk · hf, f iHk = k(x, x)hf, f iHk which means that hf, f iHk = 0 ⇒ f = 0 for all x. Ok, it’s positive definite, and thus, an inner product. Now we have an inner product space. In order to make it a Hilbert space, we need to make it complete. The completion is actually not a big deal, we just create a norm: p kf kHk = hf, f iHk and just add to Hk the limit points of sequences that converge in that norm. Once we do that, X Hk = {f : f = αi k(·, xi )} i is a Reproducing Kernel Hilbert space (RKHS). Here’s a formal (simplified) definition of RKHS: 13 We are given a (compact) X ⊆ Rd and a Hilbert space H of functions f : X → R. We say H is a Reproducing Kernel Hilbert Space if there exists a k : X → R, such that 1. k has the reproducing property, i.e., f (x) = hf (·), k(·, x)iH 2. k spans H, that is, H = span{k(·, x) : x ∈ X } So whenPwe do the kernel trick, we could think that we’re implicitly mapping x to f = i αi k(·, x) in the RKHS Hk . Neat, huh? The RKHS we described is the one from the Moore-Aronszajn Theorem (1950) that states that for every positive definite function k(·, ·) there exists a unique RKHS. We could stop there, but we won’t. We’re going to define another Hilbert space that has a one-to-one mapping (an isometric isomorphism) to the first one. Mercer’s Theorem The inspiration of the name “kernel” comes from the study of integral operators, studied by Hilbert and others. Function k which gives rise to an operator Tk via: Z (Tk f )(x) = k(x, x0 )f (x0 )dx0 X is called the kernel of Tk . Think about an operator Tk : L2 (X ) → L2 (X ). If you don’t know this notation, don’t worry about it. Just think about Tk eating a function and spitting out another one. Think of Tk as an infinite matrix, which maps infinite dimensional vectors to other infinite dimensional vectors. Remember earlier we analyzed the finite state case? It’s just like that.1 And, just like in the finite state case, because Tk is going to be positive semidefinite, it has an eigen-decomposition into eigenfunctions and eigenvalues that 1 If you know the notation, you’ll see that I’m missing the measure on L2 in the notation. Feel free to put it back in as you like. 14 are nonnegative. The following theorem from functional analysis is very similar to what we proved in the finite state case. This theorem is important - it helps people construct kernels (though I admit myself I find the other representation more helpful). Basically, the theorem says that if we have a kernel k that is positive (defined somehow), we can expand k in terms of eigenfunctions and eigenvalues of a positive operator that comes from k. Mercer’s Theorem (Simplified) Let X be a compact subset of Rn . Suppose k is a continuous symmetric function such that the integral operator Tk : L2 (X ) → L2 (X ) defined by Z (Tk f )(·) = k(·, x)f (x)dx X is positive; which here means ∀f ∈ L2 (X ), Z k(x, z)f (x)f (z)dxdz ≥ 0, X ×X then we can expand k(x, z) in a uniformly convergent series in terms of Tk ’s eigenfunctions ψj ∈ L2 (X ), normalized so that kψkL2 = 1, and positive associated eigenvalues λj ≥ 0, ∞ X k(x, z) = λj ψj (x)ψj (z). j=1 The definition of positive semi-definite here is equivalent to the ones we gave earlier.2 So this looks just like what we did in the finite case. So we could define a feature map as in the finite case this way: p p Φ(x) = [ λ1 ψ1 (x), ..., λj ψj (x), ...]. 2 To see the equivalence,R for this direction ⇐, choose f as a weighted sum of δ functions at each x. For this direction ⇒, say that X ×X k(x, z)f (x)f (z)dxdz ≥ 0 doesn’t hold for some f and show the contrapositive. Approximate the integral with a finite sum over a mesh of inputs {x1 , ..., xm } chosen sufficiently finely, then let v be the values of f on the mesh, and as long as the mesh is fine enough, we’ll have v0 Kv < 0, so K isn’t positive semi-definite. 15 So that’s a cool property of the RKHS that we can define a feature space according to Mercer’s Theorem. Now for another cool property of SVM problems, having to do with RKHS. Representer Theorem Recall that the SVM optimization problem can be expressed as follows: f ∗ = argminf ∈Hk Rtrain (f ) where R train (f ) := m X hingeloss(f (xi ), yi ) + Ckf k2Hk . i=1 Or, you could even think about using a generic loss function: R train (f ) := m X `(f (xi ), yi ) + Ckf k2Hk . i=1 The following theorem is kind of a big surprise. It says that the solutions to any problem of this type - no matter what the loss function is! - all have a solution in a rather nice form. Representer Theorem (Kimeldorf and Wahba, 1971, Simplified) Fix a set X , a kernel k, and let Hk be the corresponding RKHS. For any function ` : R2 → R, the solutions of the optimization problem: ∗ f ∈ argminf ∈Hk m X `(f (xi ), yi ) + kf k2Hk i=1 can all be expressed in the form: ∗ f = m X αi k(xi , ·). i=1 This shows that to solve the SVM optimization problem, we only need to solve for the αi , which agrees with the solution from the Lagrangian formulation for SVM. It says that even if we’re trying to solve an optimization problem in an infinite dimensional space Hk containing linear combinations of kernels centered 16 on arbitrary x0i s, then the solution lies in the span of the m kernels centered on the xi ’s. I hope you grasp how cool this is! Proof. Suppose we project f onto the subspace: span{k(xi , ·) : 1 ≤ i ≤ m} obtaining fs (the component along the subspace) and f⊥ (the component perpendicular to the subspace). We have: f = fs + f⊥ ⇒ kf k2Hk = kfs k2Hk + kf⊥ k2Hk ≥ kfs k2Hk . This implies that kf kHk is minimized if f lies in the subspace. Furthermore, since the kernel k has the reproducing property, we have for each i: f (xi ) = hf, k(xi , ·)iHk = hfs , k(xi , ·)iHk +hf⊥ , k(xi , ·)iHk = hfs , k(xi , ·)iHk = fs (xi ). So, m X `(f (xi ), yi ) = m X i=1 `(fs (xi ), yi ). i=1 In other words, the loss depends only on the component of f lying in the subspace. To minimize, we can just let kf⊥ kHk be 0 and we can express the minimizer as: ∗ f (·) = m X αi k(xi , ·). i=1 That’s it!  Draw some bumps on xi ’s Constructing Kernels Let’s construct new kernels from previously defined kernels. Suppose we have k1 and k2 . Then the following are also valid kernels: 1. k(x, z) = αk1 (x, z) + βk2 (x, z) for α, β ≥ 0 17 Proof. k1 has its feature map Φ1 and inner product hiHk1 and k2 has its feature map Φ2 and inner product hiHk2 . By linearity, we can have: p p √ √ αk1 (x, z) = h αΦ1 (x), αΦ1 (z)iHk1 and βk2 (x, z) = h βΦ2 (x), βΦ2 (z)iHk2 Then: k(x, z) = αk1 (x, z) + βk2 (x, z) p p √ √ = h αΦ1 (x), αΦ1 (z)iHk1 + h βΦ2 (x), βΦ1 (z)iHk2 p p √ √ =: h[ αΦ1 (x), βΦ2 (x)], [ αΦ1 (z), βΦ2 (z)]iHnew and that means that k(x, z) can be expressed as an inner product. 2. k(x, z) = k1 (x, z)k2 (x, z) Proof omitted - it’s a little fiddly. 3. k(x, z) = k1 (h(x), h(z)), where h : X → X . Proof. Since h is a transformation in the same domain, k is simply a different kernel in that domain: k(x, z) = k1 (h(x), h(z)) = hΦ(h(x)), Φ(h(z))iHk1 =: hΦh (x), Φh (z)iHnew 4. k(x, z) = g(x)g(z) for g : X → R. Proof omitted, again this one is a little tricky. 5. k(x, z) = h(k1 (x, z)) where h is a polynomial with positive coefficients Proof. Since each polynomial term is a product of kernels with a positive coefficient, the proof follows by applying 1 and 2. 6. k(x, z) = exp(k1 (x, z)) Proof Since:  exp(x) = lim i→∞ xi 1 + x + ··· + i! the proof basically follows from 5.  −kx−zk2  `2 7. k(x, z) = exp “Gaussian kernel” σ2 18  Proof. ! ! −kx − zk2`2 −kxk2`2 − kzk2`2 + 2xT z k(x, z) = exp = exp σ2 σ2       T  −kxk`2 −kzk`2 2x z = exp exp exp σ2 σ2 σ2 g(x)g(z) is a kernel according to 4, and exp(k1 (x, z)) is a kernel according to 6. According to 2, the product of two kernels is a valid kernel. Note that the Gaussian kernel is translation invariant, since it only depends on x − z. This picture helps with the intuition about Gaussian kernels if you think of the first representation of the RKHS I showed you: ! −kx − ·k2`2 Φ(x) = k(x, ·) = exp σ2 F x F(x) x' F(x') Image by MIT OpenCourseWare. Gaussian kernels can be very powerful: 19 Bernhard Schölkopf, Christopher J.C. Burges, and Alexander J. Smola, ADVANCES IN KERNEL METHODS: SUPPORT VECTOR LEARNING, published by the MIT Press. Used with permission. Don’t make the σ 2 too small or you’ll overfit! 20