Reproducing Kernel Hilbert SpacesLorenzo Rosasco9.520 Class 03February 9, 2011L. Rosasco RKHSAbout this classGoal To introduce a particularly useful family ofhypothesis spaces called Reproducing KernelHilbert Spaces (RKHS) and to derive the generalsolution of Tikhonov regularization in RKHS: therepresenter theorem.L. Rosasco RKHSRegularizationThe basic idea of regularization (originally introducedindependently of the learning problem) is to restorewell-posedness of ERM by constraining the hypothesis spaceH.RegularizationA possible way to do this is considering regularized empiricalrisk minimization, that is we look for solutions minimizing a twoterm functionalERR(f )| {z }empirical error+λ R(f )|{z}regularizerthe regularization parameter λ trade-offs the two terms.L. Rosasco RKHSTikhonov RegularizationTikhonov regularization amounts to minimize1nnXi=1V (f (xi), yi) + λR(f ) λ > 0 (1)V (f (x), y) is the loss function, that is the price we paywhen we predict f (x) in place of yR(f ) is a regularizer– often R(f ) = k · kH, the norm in thefunction space HThe regularizer should encode some notion of smoothness of f .L. Rosasco RKHSThe "Ingredients" of Tikhonov RegularizationThe scheme we just described is very general and bychoosing different loss functions V (f (x), y) we can recoverdifferent algorithmsThe main point we want to discuss is how to choose anorm encoding some notion of smoothness/complexity ofthe solutionReproducing Kernel Hilbert Spaces allow us to do this in avery powerful wayL. Rosasco RKHSDifferent Views on RKHSL. Rosasco RKHSPart I: Evaluation FunctionalsL. Rosasco RKHSSome Functional AnalysisA function space F is a space whose elements are functionsf , for example f : Rd→ R.A norm is a nonnegative function k · k such that ∀f , g ∈ F andα ∈ R1kf k ≥ 0 and kf k = 0 iff f = 0;2kf + gk ≤ kf k + kgk;3kαf k = |α| kf k.A norm can be defined via a inner product kf k =phf , f i.A Hilbert space is a complete inner product space.L. Rosasco RKHSSome Functional AnalysisA function space F is a space whose elements are functionsf , for example f : Rd→ R.A norm is a nonnegative function k · k such that ∀f , g ∈ F andα ∈ R1kf k ≥ 0 and kf k = 0 iff f = 0;2kf + gk ≤ kf k + kgk;3kαf k = |α| kf k.A norm can be defined via a inner product kf k =phf , f i.A Hilbert space is a complete inner product space.L. Rosasco RKHSSome Functional AnalysisA function space F is a space whose elements are functionsf , for example f : Rd→ R.A norm is a nonnegative function k · k such that ∀f , g ∈ F andα ∈ R1kf k ≥ 0 and kf k = 0 iff f = 0;2kf + gk ≤ kf k + kgk;3kαf k = |α| kf k.A norm can be defined via a inner product kf k =phf , f i.A Hilbert space is a complete inner product space.L. Rosasco RKHSSome Functional AnalysisA function space F is a space whose elements are functionsf , for example f : Rd→ R.A norm is a nonnegative function k · k such that ∀f , g ∈ F andα ∈ R1kf k ≥ 0 and kf k = 0 iff f = 0;2kf + gk ≤ kf k + kgk;3kαf k = |α| kf k.A norm can be defined via a inner product kf k =phf , f i.A Hilbert space is a complete inner product space.L. Rosasco RKHSExamplesContinuous functions C[a, b] :a norm can be established by definingkf k = maxa≤x≤b|f (x)|(not a Hilbert space!)Square integrable functions L2[a, b]:it is a Hilbert space where the norm is induced by the dotproducthf , gi =Zbaf (x)g(x)dxL. Rosasco RKHSExamplesContinuous functions C[a, b] :a norm can be established by definingkf k = maxa≤x≤b|f (x)|(not a Hilbert space!)Square integrable functions L2[a, b]:it is a Hilbert space where the norm is induced by the dotproducthf , gi =Zbaf (x)g(x)dxL. Rosasco RKHSHypothesis Space: DesiderataHilbert Space.Point-wise defined functions.L. Rosasco RKHSHypothesis Space: DesiderataHilbert Space.Point-wise defined functions.L. Rosasco RKHSRKHSAn evaluation functional over the Hilbert space of functions H isa linear functional Ft: H → R that evaluates each function inthe space at the point t, orFt[f ] = f (t).DefinitionA Hilbert space H is a reproducing kernel Hilbert space(RKHS) if the evaluation functionals are bounded andcontinuous, i.e. if there exists a M s.t.|Ft[f ]| = |f (t)| ≤ Mkf kH∀f ∈ HL. Rosasco RKHSRKHSAn evaluation functional over the Hilbert space of functions H isa linear functional Ft: H → R that evaluates each function inthe space at the point t, orFt[f ] = f (t).DefinitionA Hilbert space H is a reproducing kernel Hilbert space(RKHS) if the evaluation functionals are bounded andcontinuous, i.e. if there exists a M s.t.|Ft[f ]| = |f (t)| ≤ Mkf kH∀f ∈ HL. Rosasco RKHSEvaluation functionalsEvaluation functionals are not always bounded.Consider L2[a, b]:Each element of the space is an equivalence class offunctions with the same integralR|f (x)|2dx.An integral remains the same if we change the function ina countable set of points.L. Rosasco RKHSNorms in RKHS and SmoothnessChoosing different kernels one can show that the norm in thecorresponding RKHS encodes different notions of smoothness.Band limited functions. Consider the set of functionsH := {f ∈ L2(R) | F(ω) ∈ [−a, a], a < ∞}with the usual L2inner product. the function at every pointis given by the convolution with a sinc function sin(ax)/ax.The normkf k2H=Zf (x)2dx =Zaa|F (ω)|2dωWhere F (ω) = F{f }(ω) =R∞−∞f (t)e−iωtdt is the Fouriertranform of f .L. Rosasco RKHSNorms in RKHS and SmoothnessChoosing different kernels one can show that the norm in thecorresponding RKHS encodes different notions of smoothness.Band limited functions. Consider the set of functionsH := {f ∈ L2(R) | F(ω) ∈ [−a, a], a < ∞}with the usual L2inner product. the function at every pointis given by the convolution with a sinc function sin(ax)/ax.The normkf k2H=Zf (x)2dx =Zaa|F (ω)|2dωWhere F (ω) = F{f }(ω) =R∞−∞f (t)e−iωtdt is the Fouriertranform of f .L. Rosasco RKHSNorms in RKHS and SmoothnessSobolev Space: consider f : [0, 1] → R withf (0) = f (1) = 0. The normkf k2H=Z(f0(x))2dx =Zω2|F (ω)|2dωGaussian Space: the norm can be written askf k2H=12πdZ|F (ω)|2expσ2ω22dωL. Rosasco RKHSNorms in RKHS and SmoothnessSobolev Space: consider f : [0, 1] → R withf (0) = f (1) = 0. The normkf k2H=Z(f0(x))2dx =Zω2|F (ω)|2dωGaussian Space: the norm can be written askf k2H=12πdZ|F (ω)|2expσ2ω22dωL. Rosasco RKHSNorms in RKHS and SmoothnessSobolev Space: consider f : [0, 1] → R withf (0) = f (1) = 0. The normkf