Example: stock market

1 Reproducing Kernel Hilbert Spaces - People

CS281B/Stat241B (Spring 2008) Statistical Learning TheoryLecture: 7 Reproducing Kernel Hilbert SpacesLecturer: Peter BartlettScribe: Chunhui Gu1 Reproducing Kernel Hilbert Hilbert Space and KernelAn inner product u,v can be1. a usual dot product: u,v =v w= iviwi2. a Kernel product: u,v =k(v,w) = (v) (w) (where (u) may have infinite dimensions)However, an inner product , must satisfy the following conditions:1. Symmetry u,v = v,u u,v X2. Bilinearity u+ v,w = u,w + v,w u,v,w X, , R3. Positive definiteness u,u 0, u X u,u = 0 u= 0 Now we can define the notion of a Hilbert Spaceis an inner product space that is complete and separable with respect to thenorm defined by the inner of Hilbert Spaces include:1. The vector spaceRnwith a,b =a b, the vector dot product The spacel2of square summable sequences, with inner product x,y = i=1xiyi3. The spaceL2of square integrable functions ( , sf(x)2dx < ), with inner product f,g = sf(x)g(x) ( , ) is areproducing kernelof a Hilbert spaceHif f H,f(x) = k(x, ),f( ).

1. khas the reproducing property, i.e., f(x) = hf(·),k(·,x)i 2. kspans H = span{k(·,x) : x∈ X} 1.3 Mercer’s Theorem Another way to characterize a symmetric positive semi-definite kernel kis via the Mercer’s Theorem. Theorem 1.1 (Mercer’s). Suppose kis a continuous positive semi-definite kernel on a compact set X, and the integral ...

Tags:

  Kernel, Khas, Reproducing kernel, Reproducing

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of 1 Reproducing Kernel Hilbert Spaces - People

1 CS281B/Stat241B (Spring 2008) Statistical Learning TheoryLecture: 7 Reproducing Kernel Hilbert SpacesLecturer: Peter BartlettScribe: Chunhui Gu1 Reproducing Kernel Hilbert Hilbert Space and KernelAn inner product u,v can be1. a usual dot product: u,v =v w= iviwi2. a Kernel product: u,v =k(v,w) = (v) (w) (where (u) may have infinite dimensions)However, an inner product , must satisfy the following conditions:1. Symmetry u,v = v,u u,v X2. Bilinearity u+ v,w = u,w + v,w u,v,w X, , R3. Positive definiteness u,u 0, u X u,u = 0 u= 0 Now we can define the notion of a Hilbert Spaceis an inner product space that is complete and separable with respect to thenorm defined by the inner of Hilbert Spaces include:1. The vector spaceRnwith a,b =a b, the vector dot product The spacel2of square summable sequences, with inner product x,y = i=1xiyi3. The spaceL2of square integrable functions ( , sf(x)2dx < ), with inner product f,g = sf(x)g(x) ( , ) is areproducing kernelof a Hilbert spaceHif f H,f(x) = k(x, ),f( ).

2 12 Reproducing Kernel Hilbert SpacesA Reproducing Kernel Hilbert Space (RKHS) is a Hilbert spaceHwith a Reproducing Kernel whose spanis dense inH. We could equivalently define an RKHS as a Hilbert space of functions with all evaluationfunctionals bounded and instance, theL2space is a Hilbert space, but not an RKHS because the delta function which has thereproducing propertyf(x) = s (x u)f(u)dudoes not satisfy the square integrable condition, that is, s (u)2du6< ,thus the delta function is not let us define a :X X Ris symmetric:k(x,y) =k(y,x). positive semi-definite, , x1,x2,..,xn X, the Gram Matrix Kdefined byKij=k(xi,xj) ispositive semi-definite. (A matrixM Rn nis positive semi-definite if a Rn,a Ma 0.)Here are some properties of a Kernel that are worth (x,x) 0. (Think about the Gram matrix ofn= 1) (u,v) k(u,u)k(v,v). (This is the Cauchy-Schwarz inequality.)To see why the second property holds, we consider the case whenn= 2:Leta=[k(v,v) k(u,v)].

3 The Gram matrixK=(k(u,u)k(u,v)k(v,u)k(v,v)) 0 a Ka 0 [k(v,v)k(u,u) k(u,v)2]k(v,v) the first property we knowk(v,v) 0, sok(v,v)k(u,u) k(u,v) Build an Reproducing Kernel Hilbert Space (RKHS)Given a kernelk, define the Reproducing Kernel feature map :X RXas: (x) =k( ,x)Consider the vector space:span({ (x) :x X}) ={f( ) =n i=1 ik( ,xi) :n N,xi X, i R}Forf= i ik( ,ui) andg= i ik( ,vi), define f,g = i,j i jk(ui,vj).Note that: f,k( ,x) = i ik(x,ui) =f(x), , khas the Reproducing show that f,g is an inner product by checking the following conditions: Reproducing Kernel Hilbert Spaces31. Symmetry: f,g = i,j i jk(ui,vj) = i,j j ik(vj,ui) = g,f 2. Bilinearity: f,g = i ig(ui) = j jf(vj)3. Positive definiteness: f,f = K 0 with equality ifff= 3 we can also derive:1. f,g 2 f,f g,g Proof. a R, af+g,af+g =a2 f,f + 2a f,g + g,g 0. This implies that the quadraticexpression has a non-positive discriminant.

4 Therefore, f,g 2 f,f g,g 02.|f(x)|2= k( ,x),f 2 k(x,x) f,f , which implies that if f,f = 0 thenfis identically we have defined an inner product space , . Complete it to give the Hilbert a (compact)X Rd, and a Hilbert spaceHof functionsf:X R, we sayHis aReproducing Kernel Hilbert Spaceif k:X R, the Reproducing property, ,f(x) = f( ),k( ,x) {k( ,x) :x X} Mercer s TheoremAnother way to characterize a symmetric positive semi-definite kernelkis via the Mercer s (Mercer s).Supposekis a continuous positive semi-definite Kernel on a compact setX, andthe integral operatorTk:L2(X) L2(X) defined by(Tkf)( ) = Xk( ,x)f(x)dxis positive semi-definite, that is, f L2(X), Xk(u,v)f(u)f(v)dudv 0 Then there is an orthonormal basis{ i}ofL2(X) consisting of eigenfunctions ofTksuch that the correspond-ing sequence of eigenvalues{ i}are non-negative. The eigenfunctions corresponding to non-zero eigenvaluesare continuous onXandk(u,v) has the representationk(u,v) = i=1 i i(u) i(v)where the convergence is absolute and uniform, that is,limn supu,v|k(u,v) n i=1 i i(u) i(v)|= 04 Reproducing Kernel Hilbert SpacesTo take an analogue in the finite case, that is,X={x1.}

5 ,xn}. LetKij=k(xi,xj), andf:X Rnwithfi=f(xi). Then,Tkf=n i=1k( ,xi)fi f, f Kf 0 K 0 K= iviv iHence,k(xi,xj) =Kij= (V V )ij=n k=1 kvkivkj=n k=1 k k(xi) k(xj) k(xi) = (vk)iWe summarize several equivalent conditions on continuous, symmetrickdefined on compactX:1. Every Gram matrix is positive positive be expressed ask(u,v) = i i i(u) i(v). the Reproducing Kernel of an RKHS of functions onX.


Related search queries