Reproducing kernel Hilbert space

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Figure illustrates related but varying approaches to viewing RKHS

In functional analysis (a branch of mathematics), a reproducing kernel Hilbert space (RKHS) is a Hilbert space associated with a kernel that reproduces every function in the space or, equivalently, where every evaluation functional is bounded. The reproducing kernel was first introduced in the 1907 work of Stanisław Zaremba concerning boundary value problems for harmonic and biharmonic functions. James Mercer simultaneously examined functions which satisfy the reproducing property in the theory of integral equations. The idea of the reproducing kernel remained untouched for nearly twenty years until it appeared in the dissertations of Gábor Szegő, Stefan Bergman, and Salomon Bochner. The subject was eventually systematically developed in the early 1950s by Nachman Aronszajn and Stefan Bergman. [1]

These spaces have wide applications, including complex analysis, harmonic analysis, and quantum mechanics. Reproducing kernel Hilbert spaces are particularly important in the field of statistical learning theory because of the celebrated Representer theorem which states that every function in an RKHS can be written as a linear combination of the kernel function evaluated at the training points. This is a practically useful result as it effectively simplifies the empirical risk minimization problem from an infinite dimensional to a finite dimensional optimization problem.

For ease of understanding, we provide the framework for real-valued Hilbert spaces. The theory can be easily extended to spaces of complex-valued functions and hence include the many important examples of reproducing kernel Hilbert spaces that are spaces of analytic functions. [2]

Definition[edit]

Let X be an arbitrary set and H a Hilbert space of real-valued functions on X. The evaluation functional over the Hilbert space of functions H is a linear functional that evaluates each function at a point x,

 L_{x} : f \mapsto f(x)  \text{   } \forall f \in H.

We say that H is a reproducing kernel Hilbert space if  L_{x} is a continuous function for any x in X or, equivalently, if  L_x is a bounded operator so that for any x in X there exists some M > 0 such that

 L_{x}[f] = f(x) \le M \|f(x)\|_H \text{   } \forall f \in H. \,

 

 

 

 

(1)

While property (1) is the weakest condition that ensures both the existence of an inner product and the evaluation of every function in H at every point in the domain, it does not lend itself to easy application in practice. A more intuitive definition of the RKHS can be obtained by observing that this property guarantees that the evaluation functional can be represented by taking the inner product of  f with a function  K_x in H . This function is the so-called reproducing kernel for the Hilbert space H from which the RKHS takes its name. More formally, the Riesz representation theorem implies that for all x in X there exists a unique element  K_x of H with the reproducing property,

  f(x) = L_{x}(f) = \langle f,\ K_x \rangle \quad \forall f \in H.

 

 

 

 

(2)

Since  K_x is itself a function in H we have that for each x in X

 K_x(y) = \langle K_y,\ K_x \rangle_H.

This allows us to define the reproducing kernel of H as a function  K: X \times X \to \mathbb{R} by

 K(x,y) = K_x(y).

From this definition it is easy to see that a function  K: X \times X \to \mathbb{R} is a reproducing kernel if it is both symmetric and positive definite, i.e.

 \sum_{i,j =1}^n c_i c_j K(x_i, x_j) \ge  0

for any  n \in \mathbb{N}, x_1, \dots, x_n \in X, \text{ and } c_1, \dots, c_n \in \mathbb{R}. [3]

Example, Counterexample[edit]

To gain intuition for the RKHS we first consider the space of square integrable functions  L_2[a,b] . While a Hilbert space,  L_2[a,b] is not a RKHS as the evaluation functional is not bounded. Let  c be a real number in  [a,b] ,  \delta be the Delta function and define

f(x) = x^2 + \delta(x - c).

Then  f(x) is an element of  L_2[a,b] but there is no  M such that (1) holds as  f(c) = \infty . In fact this function is not even defined pointwise.

On the other hand, the space of bandlimited functions  H is a RKHS by shrinking the space of square integrable real-valued functions to include only those with Fourier transforms with bounded support. That is, let

 H = \{ f \in L_2(\mathbb{R}) | F(\omega) \in [-a,a], a < \infty \}

where  F(\omega) = \int f(t) e^{-i\omega t} dt is the Fourier transform of  f. One can show that if f \in H then

 f(x) = \frac{1}{2 \pi} \int_{-a}^{a} \phi(\omega) e^{ix \omega} d\omega

for  \phi \in L_2[-a,a]. It then follows that

 |f(x)| \le  \sqrt{\frac{1}{2 \pi}} \sqrt{ \frac{1}{2\pi} \int_{-a}^{a} |\phi(\omega)| ^2 d\omega} = \sqrt{\frac{1}{2 \pi}} \|f \|.

As this inequality shows that the evaluation functional is bounded and  H is also a Hilbert space,  H is indeed a RKHS.

Moore-Aronszajn Theorem[edit]

We have seen how a reproducing kernel Hilbert space defines a reproducing kernel function that is both symmetric and positive definite. The Moore-Aronszajn theorem goes in the other direction; it states that every symmetric, positive definite kernel defines a unique reproducing kernel Hilbert space. The theorem first appeared in Aronszajn's Theory of Reproducing Kernels, although he attributes it to E. H. Moore.

Theorem. Suppose K is a symmetric, positive definite kernel on a set X. Then there is a unique Hilbert space of functions on X for which K is a reproducing kernel.

Proof. For all x in X, define Kx = K(x, ⋅ ). Let H0 be the linear span of {Kx : xX}. Define an inner product on H0 by

 \left\langle \sum_{j=1}^n b_j K_{y_j}, \sum_{i=1}^m a_i K_{x_i} \right \rangle = \sum_{i=1}^m \sum_{j=1}^n {a_i} b_j K(y_j, x_i).

The symmetry of this inner product follows from the symmetry of K and the non-degeneracy follows from the fact that K is positive definite.

Let H be the completion of H0 with respect to this inner product. Then H consists of functions of the form

 f(x) = \sum_{i=1}^\infty a_i K_{x_i} (x)

where \sum_{i=1}^\infty a_i^2 K (x_i, x_i) < \infty. The fact that the above sum converges for every x follows from the Cauchy-Schwarz inequality.

Now we can check the reproducing property (2):

\langle f, K_x \rangle = \left \langle \sum_{i=1}^\infty a_i K_{x_i}, K_x \right \rangle= \sum_{i=1}^\infty a_i K (x_i, x) = f(x).

To prove uniqueness, let G be another Hilbert space of functions for which K is a reproducing kernel. For any x and y in X, (2) implies that

\langle K_x, K_y \rangle_H = K(x, y) = \langle K_x, K_y \rangle_G. \,

By linearity, \langle \cdot, \cdot \rangle_H = \langle \cdot, \cdot \rangle_G on the span of {Kx : xX}. Then G = H by the uniqueness of the completion.

Integral Operators and Mercer's Theorem[edit]

We may characterize a symmetric positive definite kernel  K via the integral operator using Mercer's theorem and obtain an additional view of the RKHS. Let  X be a compact space equipped with a strictly positive finite Borel measure  \mu and  K: X \times X \to \mathbb{R} a continuous, symmetric, and positive definite function. Define the integral operator  T_K: L_2(X) \rightarrow L_2(X) as

 [T_K f](\cdot) =\int_X  K(\cdot,t) f(t)\, d\mu(t)

where  L_2(X) is the space of square integrable functions with respect to  \mu .

Mercer's theorem states that the spectral decomposition of the integral operator  T_K of  K yields a series representation of  K in terms of the eigenvalues and eigenfunctions of  T_K . This then implies that  K is a reproducing kernel so that the corresponding RKHS can be defined in terms of these eigenvalues and eigenfunctions. We provide the details below.

Under these assumptions  T_k is a compact, continuous, self-adjoint, and positive operator. The spectral theorem for self-adjoint operators implies that there is an at most countable decreasing sequence  (\sigma_i)_i \geq 0 such that  \lim_{i \to \infty}\sigma_i = 0 and  T_K\phi_i(x) = \sigma_i\phi_i(x) , where the  \{\phi_i\} form an orthonormal basis of  L_2(X) . By the positivity  T_k ,  \sigma_i > 0 \text{  } \forall i . One can also show that  T_k maps continuously into the space of continuous functions  C(X) and therefore we may choose continuous functions as the eigenvectors, that is,  \phi_i \in C(X) \text{  } \forall i . Then by Mercer's theorem  K may be written in terms of the eigenvalues and continuous eigenfunctions as

 K(x,y) = \sum_{j=1}^\infty \sigma_j \, \phi_j(x) \, \phi_j(y)

for all x, y in  X such that  \lim_{n \to \infty}\sup_{u,v}|K(u,v) - \sum_{j=1}^n \sigma_j \, \phi_j(u) \, \phi_j(v)| = 0. This above series representation is referred to as a Mercer kernel or Mercer representation of  K .

Furthermore, it can be shown that the RKHS  H of  K is given by

 H = \left\{f {\in}L_2(X)\mathrel{\Bigg|} \sum_{i=1}^\infty\frac{\left\langle f,\phi_i\right\rangle^2}{\sigma_i} < \infty\right\}

where the inner product of  H given by  \left\langle f,g \right\rangle_H = \sum_{i=1}^\infty \frac{\left\langle f,\phi_i \right\rangle_{L_2}\left\langle g,\phi_i \right\rangle_{L_2}}{\sigma_i}. This representation of the RKHS has application in probability and statistics, for example to the Karhunen-Loeve representation for stochastic processes and kernel PCA.

Feature Maps[edit]

A feature map is a map  \varphi: X \rightarrow F , where  F is a Hilbert space which we will call the feature space. The first sections presented the connection between bounded/continuous evaluation functions, positive definite functions, and integral operators and in this section we provide another representation of the RKHS in terms of feature maps.

We first note that every feature map defines a kernel via

 K(x,y) = \langle \varphi(x), \varphi(y) \rangle.

 

 

 

 

(3)

Clearly  K is symmetric and positive definiteness follows from the properties of inner product in  F . Conversely, every positive definite function and corresponding reproducing kernel Hilbert space has infinitely many associated feature maps such that (3) holds.

For example, we can trivially take  F = H and  \varphi(x) = K_x for all  x \in X . Then (3) is satisfied by the reproducing property. Another classical example of a feature map relates to the previous section regarding integral operators by taking  F = \ell^2 and  \varphi(x) (\sqrt(\sigma_i)\phi_i(x))_i .

This connection between kernels and feature maps provides us with a new way to understand positive definite functions and hence reproducing kernels as inner products in  H . Moreover, every feature map can naturally define a RKHS by means of the definition of a positive definite function.

Lastly, feature maps allow us to construct function spaces that reveal another perspective on the RKHS. Consider the linear space

 H_{\varphi} = \{ f: X \to \mathbb{R} | \exists w \in F, f(x) = \langle w, \varphi(x) \rangle_{F}, \forall \text{  } x \in X \} .

We can define a norm on  H_{\varphi} by

 ||f||_{\varphi} = \text{inf} \{||w||_F : w \in F, f(x) = \langle w, \varphi(x)\rangle_F, \forall \text{  } x \in X \} .

It can be shown that  H_{\varphi} is a RKHS with kernel defined by  K(x,y) = \langle\varphi(x), \varphi(y)\rangle . This representation implies that the elements of the RKHS are inner products of elements in the feature space and can accordingly be seen as hyperplanes. This view of the RKHS is related to the kernel trick in machine learning. [4]

Properties[edit]

The following properties of RKHSs may be useful to readers.

  • Let  (X_i)_{i=1}^p be a sequence of sets and  (K_i)_{i=1}^p be a collection of corresponding positive definite functions on  (X_i)_{i=1}^p . It then follows that
 K((x_1,\dots ,x_p),(y_1,\dots,y_p)) = K_1(x_1,y_1)\dots K_p(x_p,y_p)

is a kernel on  X = X_1 \times \dots \times X_p.

  • Let  X_0 \subset X , then the restriction of  K to X_0 \times X_0 is also a reproducing kernel.
  • Consider a normalized kernel  K such that  K(x, x) = 1 for all  x \in X . Define a pseudo-metric on X as
 d_K(x,y) = ||K_x - K_y||_H^2 = 2(1-K(x,y)) \text{  } \forall x \in X .

By the Cauchy-Schwartz inequality,

 K(x,y)^2 \le K(x, x)K(y, y) \text{  } \forall x,y \in X.

This inequality allows us to view K as a measure of similarity between inputs. If x,y \in X are similar then K(x,y) will be closer to 1 while if x,y \in X are dissimilar then K(x,y) will be closer to 0.

  • The closure of the span of  \{ K_x | x \in X \} coincides with  H . [5]

Examples[edit]

Common examples of kernels include:

  • Linear Kernel:
 K(x,y) = \langle x,y\rangle
  • Polynomial Kernel:
 K(x,y) = (\alpha\langle x,y \rangle + 1)^d, \alpha {\in} \mathbb{R}, d {\in} \mathbb{N}

Other common examples are kernels which satisfy  K(x,y) = K(\|x - y\|) . These are the radial basis function kernels.

  • Radial Basis Function Kernels:
  • Gaussian Kernel:
Sometimes referred to as the Radial basis function kernel, or squared exponential kernel
 K(x,y) = e^{-\frac{\|x - y\|^2}{2\sigma^2}}, \sigma > 0
  • Laplacian Kernel:
 K(x,y) = e^{-\frac{\|x - y\|}{\sigma}}, \sigma > 0

We also provide examples of Bergman kernels. Let X be finite and let H consist of all complex-valued functions on X. Then an element of H can be represented as an array of complex numbers. If the usual inner product is used, then Kx is the function whose value is 1 at x and 0 everywhere else, and K(x,y) can be thought of as an identity matrix since K(x,y)=1 when x=y and K(x,y)=0 otherwise. In this case, H is isomorphic to Cn.

The case of X = D is more sophisticated, here the Bergman space H2(D) is the space of square-integrable holomorphic functions on D. It can be shown that the reproducing kernel for H2(D) is

K(x,y)=\frac{1}{\pi}\frac{1}{(1-x\overline{y})^2}.

Lastly, the space of band limited functions  f in  L^2(\mathbb{R}) with bandwidth  \pi are a RKHS with reproducing kernel

K(x,y)=\frac{\sin \pi (x - y)}{\pi (x-y)}.

Extension to Vector-Valued Functions[edit]

In this section we extend the definition of the RKHS to spaces of vector-valued functions as this extension is particularly important in multi-task learning and manifold regularization. The main difference is that the reproducing kernel  \Gamma is a symmetric function that is now a positive semi-definite matrix for any  x,y in  X . More formally, we define a vector-valued RKHS (vvRKHS) as a Hilbert space of functions  f: X \to \mathbb{R}^T such that for all  c \in \mathbb{R}^T and  x \in X

 \Gamma_xc(y) = \Gamma(x, y)c \in H  \text{ for } y \in X

and

 <f, \Gamma_x c>_{H} = f(x)^\intercal c.

This second property parallels the reproducing property for the scalar-valued case. We note that this definition can also be connected to integral operators, bounded evaluation functions, and feature maps as we saw for the scalar-valued RKHS. We can equivalently define the vvRKHS as a vector-valued Hilbert space with a bounded evaluation functional and show that this implies the existence of a unique reproducing kernel by the Riesz Representation theorem. Mercer's theorem can also be extended to address the vector-valued setting and we can therefore obtain a feature map view of the vvRKHS. Lastly, it can also be shown that the closure of the span of  \{ \Gamma_xc : x \in X, c \in \mathbb{R}^T \} coincides with  H , another property similar to the scalar-valued case.

We can gain intuition for the vvRKHS by taking a component-wise perspective on these spaces. In particular, we find that every vvRKHS is isometrically isomorphic to a scalar-valued RKHS on a particular input space. Let \Lambda = \{1, \dots, T \} . Consider the space  X \times \Lambda and the corresponding reproducing kernel

 \gamma: X \times \Lambda \times X \times \Lambda \to \mathbb{R}.

 

 

 

 

(4)

As noted above, the RKHS associated to this reproducing kernel is given by the closure of the span of \{ \gamma_{(x,t)} : x \in X, t \in \Lambda \} where  \ \gamma_{(x,t)} (y,s)  = \gamma( (x,t), (y,s)) for every set of pairs  (x,t), (y,s) \in  X \times \Lambda .

The connection to the scalar-valued RKHS can then be made by the fact that every matrix-valued kernel can be identified with a kernel of the form of (4) via

 \Gamma(x,y)_{(t,s)} = \gamma((x,t), (y,s)).

Moreover, every kernel with the form of (4) defines a matrix-valued kernel with the above expression. Now letting the map  D: H_{\Gamma} \to H_{\gamma} be defined as

 (Df)(x,t) = <f(x), e_t >_{\mathbb{R}^T}

where  e_t is the  t^{th} component of the canonical basis for  \mathbb{R}^T , one can show that  D is bijective and an isometry between  H_{\Gamma} and  H_{\gamma} .

While this view of the vvRKHS can be quite useful in multi-task learning, it should be noted that this isometry does not reduce the study of the vector-valued case to that of the scalar-valued case. In fact, this isometry procedure can make both the scalar-valued kernel and the input space too difficult to work with in practice as properties of the original kernels are often lost. [6] [7] [8]

An important class of matrix-valued reproducing kernels are separable kernels which can factorized as the product of a scalar valued kernel and a T-dimensional symmetric positive semi-definite matrix. In light of our previous discussion these kernels are of the form

 \gamma((x,t),(y,s)) =  K(x,y) K_T(t,s)

for all x,y in  X and t,s in  T . As the scalar-valued kernel encodes dependencies between the inputs, we can observe that the matrix-valued kernel encodes dependencies among both the inputs and the outputs.

We lastly remark that the above theory can be further extended to spaces of functions with values in function spaces but obtaining kernels for these spaces is a more difficult task. [9]

See also[edit]

Notes[edit]

  1. ^ Okutmustur
  2. ^ Paulson
  3. ^ Durrett
  4. ^ Rosasco
  5. ^ Rosasco
  6. ^ De Vito
  7. ^ Zhang
  8. ^ Alvarez
  9. ^ Rosasco

References[edit]