Zetong Qi

Zetong Qi

MS graduate from UW-Madison

Road to RKHS

8 minute read

Published:

Overview

Reproducing Kernel Hilbert Space(RKHS) is related to kernel trick in machine learning and plays a significant role in representation learning. In this post, I will summarize the mathematical definition of RKHS.

Metric Space

First, we define the notion of a metric space. a metric space is defined as following:

Let $S$ be a set, and suppose $d$ is a function defined for all pairs $(x, y)$ of elements from $S$ satisfying:

  1. Nonnegativity: $d(x, x) = 0$, $\forall x \in S$ and $d(x, y) > 0$ for distinct $x, y \in S$
  2. Symmetry: $d(x, y) = d(y, x)$, $\forall x, y \in S$
  3. Triangle Inequality: $d(x, z) \leq d(x, y) + d(y, z)$, $\forall x, y, z \in S$

Such a function $d$ is called a distance function or a metric on $S$. A metric space $S$ is a set $S$ together with a distance metric $d$ on it. A metric space is often written as a pair $(S, d)$. To summarize, a metric space is a set and the distance between it’s elements can be measured by the distance metric $d$. This means $S$ has a topological structure, which enables us to study notions of continuity and convergence.

Linear Space

Now we introduce the notion of a linear space. A set $S$ or elements $x, y, z, …$ is a linear space if the following conditions are satisfied:

  1. For any two elements $x, y \in S$ there is a uniquely defined a third element $z = x + y$, called their sum, such that:
    1. $x + y = y + x$
    2. $x + (y+z) = (x+y) + z$
    3. there exists an element $0$ having the property that $x + 0 = x$ $\forall x \in S$, and
    4. for every $x \in S$ there exists an element $-x$ such that $x + (-x) = 0$
  2. For an arbitrary number $\alpha$ and element $x \in S$ there is defined an element $\alpha x$ such that:
    1. $\alpha(\beta x) = (\alpha \beta)x$
    2. $1\cdot x = x$
  3. The operation of addition and multiplication are related in the following way:
    1. $(\alpha + \beta)x = \alpha x + \beta x$
    2. $\alpha(x + y) = \alpha x + \alpha y$

Normed Space

With the definition of linear space, we now define the normed space: A linear space $S$ is said to be normed if to each element $x \in S$ there is made to correspond a nonnegative number $\lVert x \rVert$ which is called the norm of $x$ and such that:

  1. $\lVert x \rVert$ iff $x = 0$
  2. $\lVert \alpha x \rVert = \mid \alpha \mid \lVert x \rVert$
  3. $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$

It’s easy to see that a normed space is also a metric space with the distance metric $d(x, y) = \lVert x - y \rVert$.

Banach Space

Equipped with linear space and normed space, we are ready to define a Banach space. But first, we need to define what it means for a space to be complete. Before that, we need to define Cauchy(fundamental) sequence and convergent sequence.

Cauchy Sequence

We call a sequence ${x_n}$ of points of a metric space $S$ a Cauchy(fundamental) sequence if it satisfies the Cauchy criterion: for an arbitrary $\epsilon > 0$ there exists an $N_{\epsilon}$ such that $d(x_{n’}, x_{n’’}) < \epsilon$, $\forall n’, n’’ \geq N_{\epsilon}$.

Convergent Sequence

We call a sequence ${x_n}$ of points of a metric space $S$ a convergent sequence if for an arbitrary $\epsilon > 0$ there exists a number $N_{\epsilon}$ such that $d(x_n, x) < \epsilon$ $\forall n \geq N_{\epsilon}$. We say that $x_n$ converges to $x$. We write $\lim_{n\to \infty} x_n = x$.

Complete Sequence

Now we can define a complete sequence: A metric space $(S, d)$ is said to be complete if every Cauchy sequence in $S$ converges to some element in $S$. That is, every Cauchy sequence in $S$ is a convergent sequence that converges to an element in $S$.

With all those definitions, we can directly define what is a Banach space. A Banach space is a complete normed space. That is, a Banach space contains the limits of all it’s Cauchy sequences.

Hilbert Space

Now we are ready to evolve from Banach space to Hilbert space. A Hilbert space is a Banach space with function called an inner product.

Inner Product

An inner product $(\cdot, \cdot)$ is a real-valued function of pairs of vectors of a linear space satisfying the following conditions:

  1. $(f, g) = (g, f)$
  2. $(f_1+f_2, g) = (f_1, g) + (f_2, g)$
  3. $(\lambda f, g) = \lambda(f, g)$
  4. $(f, f) > 0$ if $f \neq 0$

A vector space with an inner product is called an inner product space. A inner product space is naturally a normed space because a norm can be induced by the inner product: $\lVert x \rVert = (x, x)^{\frac{1}{2}}$

It’s also obvious that normed space, Banach space and Hilbert space are all metric spaces.

Reproducing Kernel Hilbert Space

Now we are ready to define the Reproducing Kernel Hilbert Space(RKHS). Let $\mathcal{H}$ be a Hilbert space of functions mapping from some non-empty set $\mathcal{X}$ to $\mathcal{R}$(we write it as $\mathcal{H} \subset \mathcal{R}^{\mathcal{X}}$). An interesting property of RKHS is that if two functions $f, g$ are close in the norm of $\mathcal{H}$, then $f(x)$ and $g(x)$ are close $\forall x \in \mathcal{X}$.

Evaluation Functional

Let $\mathcal{H}$ be a Hilbert space of functions $f: \mathcal{X} \to \mathcal{R}$, defined on a non-empty set $\mathcal{X}$. For a fixed $x \in \mathcal{X}$, map $\delta_x: \mathcal{H} \to \mathcal{R}$, $\delta_x: f \to f(x)$ is called the (Dirac) evaluation functional at $x$.

Evaluation functionals are always linear: For $f, g \in \mathcal{H}$ and $\alpha, \beta \in \mathcal{R}$, $\delta_x(\alpha f + \beta g) = (\alpha f + \beta g)(x) = \alpha f(x) + \beta g(x) = \alpha \delta_x(f) + \beta \delta_x(g)$. It turns out for a Hilbert space to be a Reproducing Kernel Hilbert Space, the evaluation functional has to be continuous:

RKHS

A Hilbert space of functions $f: \mathcal{X} \to \mathcal{R}$, defined on a non-empty set $\mathcal{X}$ is said to be a Reproducing Kernel Hilbert Space(RKHS) if the evaluation functional $\delta_x$ is continuous $\forall x \in \mathcal{X}$.

As mentioned above, RKHS has a nice properity: if two functions converge in RKHS norm, then they converge at every point of the evaluation function. Mathematically: if $\lim_{n \to \infty} \lVert f_n - f \rVert = 0$, then $\lim_{n \to \infty}f_n(x) = f(x)$, $\forall x \in \mathcal{X}$.

Reproducing Kernels

As you might have noticed, our definition of RKHS doesn’t include kernels. What is the relation between kernels and RKHS? First, lets define the reproducing kernel: Let $\mathcal{H}$ be a space of $\mathcal{R}$-valued functions defined on a non-empty set $\mathcal{X}$. A function $k: \mathcal{X} \times \mathcal{X} \to \mathcal{R}$ is called a reproducing kernel of $\mathcal{H}$ if it satisfies:

  1. $\forall x \in \mathcal{X}$, $k(\cdot, x) \in \mathcal{H}$
  2. $\forall x \in \mathcal{X}$, $\forall f \in \mathcal{H}$, $(f, k(\cdot, x)) = f(x)$ (the reproducing property).

In particular, for any $x, y \in \mathcal{X}$, $k(x, y) = (k(\cdot, x), k(\cdot, y))$.

It turns out, the relationship between reproducing kernel and RKHS is the following:

  1. If a reproducing kernel exists for a Hilbert space $\mathcal{H}$, the reproducing kernel is unique.
  2. $\mathcal{H}$ is a RKHS iff $\mathcal{H}$ has a reproducing kernel.

Also, the reproducing kernels are positive definite functions

Now, we are ready to formally define a kernel as a function which can be represented via inner product:

Kernel

Let $\mathcal{X}$ be a non-empty set. The function $k: \mathcal{X} \times \mathcal{X} \to \mathcal{R}$ if there exists a real Hilbert space $\mathcal{H}$ and a map $\phi: \mathcal{X} \to \mathcal{H}$ such that $\forall x, y \in \mathcal{X}$: $k(x, y) = (\phi(x), \phi(y))$.

Such map $\phi: \mathcal{X} \to \mathcal{H}$ is referred to as the feature map and the space $\mathcal{H}$ as the feature space.

You May Also Enjoy

Variational Autoencoders

9 minute read

Published:

Autoencoder is a type of neural network that learns a lower dimensional latent representation of input data in an unsupervised manner. The learning task is simple: given an input image, the network will try to reconstruct the image at the output. The loss is measured by the distance between two images, e.g., MSE loss.

Finite-dimensional Approximation of Kernel SVM with Random Fourier Features

4 minute read

Published:

Support vector machines are in my opinion the best machine learning algorithm. It generalizes well with less risk to overfitting, it scales well to high-dimensional data, and kernel trick makes it possible to efficiently lift the feature space to higher dimensions, and the optimization problem for SVMs are usually quadratic programs that are efficient to solve and has a global minimum. However, there are a few drawbacks to SVMs. The biggest one is that it doesn’t scale well with large dataset and the inference time depends on the size of the training dataset. For a training set of set $m$, where $x \in \mathcal{R}^d$, the time complexity to compute the gram matrix is $\mathcal{O}(m^2 d)$ and the time complexity to for inference is $\mathcal{O}(md)$. This time complexity scales poorly with large training sets.

Learning with Invariance using Tangent Distance Kernel

5 minute read

Published:

In kernel SVM, most kernel functions relies on some distance metric. A commonly used distance metric is the Euclidean distance. However in fields like pattern recognition, Euclidean distance is not robust to simple transformations that don’t change the class label: rotation, translation and scaling. For example:

Learning with Invariances via RKHS

11 minute read

Published:

In the previous post I introduced the concept and properities of Reproducing Kernel Hilbert Space(RKHS). In this post, I will introduce how to construct RKHS from a kernel function and build learning machines that can learn invariances encoded in the form of bounded linear functionals on the constructed RKHS.