Would Support Vector Machines work on arbitrary Hilbert spaces? I have a few questions,

*

*Has SVM ever been used to classify points in a Hilbert space other than $\mathbb{R}^n$? Say $\ell^2$ or $L^2$? The concepts involved in the derivation (like the margin) all seem to carry over just fine to arbitrary Hilbert spaces (*).

*As far as I understand, the kernel trick relies on the Moore–Aronszajn theorem to work. However, the theorem doesn't say the RKHS associated to a given kernel is one of the $\mathbb{R}^n$. As far as I know, it could be one of the infinite-dimensional ones such as $\ell^2$. Moreover, kernel-SVM consists in sending the data set to another Hilbert space and then applying linear-SVM. Wouldn't this require the justification that linear-SVM works on arbitrary Hilbert spaces? All the derivations I've seen seem to assume that (1) the data set consists of vectors on $\mathbb{R}^n$ and that (2) the inner product is the dot product.

The last question may suggest that I don't understand how the kernel trick works. If that is the case, can someone give me a formal reason so as to why it is fine to change the dot products $\langle x_i, x_j \rangle$ in the optimization problem to kernels $K(x_i, x_j)$? My understanding is that one would be starting the SVM on a whole new space where the algorithm is still applicable, which means the derivation of the algorithm would be the same, just instead of working with $x_1, ..., x_n$ and $\mathbb{R^n}$ one would be working with $\phi(x_1), ..., \phi(x_n)$ and $H$.
(*) I don't know about the quadratic program; how would one differentiate with respect to a sequence?

There is a lot here, so let me unpack each point one-by-one:

*

*Support vector machines are often used to classify points in Hilbert spaces of infinite dimension. All you need is to specify a kernel for which the induced RKHS is infinite dimensional, e.g. the Gaussian or squared exponential kernel $k(x,y)= \exp\{-\|x-y\|^2\} $. Viewing $\ell^2$ as a space of functions $u:\mathbb{N}\rightarrow\mathbb{R}$ it can be readily shown that it is a reproducing kernel Hilbert space (RKHS) with kernel $k(i,j) = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta (i.e. the function that equals $1$ only if $i=j$ and $0$ otherwise). The following is maybe a bit technical: the $L^2$ spaces are not RKHSs, since they consist of equivalence classes of functions - recall that an RKHS is a Hilbert space of functions with the added condition that convergence in norm implies pointwise convergence.

*I wouldn't say the kernel trick relies on the Moore-Aronszajn theorem. All the kernel trick relies on is the following property of a kernel $k$ and its corresponding RKHS $\mathcal{H}_k$:
$$ \langle k(x,\cdot),k(y,\cdot)\rangle_{\mathcal{H}_k} = k(x,y). $$
This property is an example of the reproducing property. Usually one would specify their kernel $k$ and then construct the feature map as $\Phi(x) = k(x,\cdot)$. By definition of the RKHS, $k(x,\cdot) \in \mathcal{H}_k$ and so $\Phi:\mathcal{X}\rightarrow\mathcal{H}_k$, where $\mathcal{X}$ is underlying set in which your data lies. Therefore, embedding your data into $\mathcal{H}_k$ using the above feature map allows one to compute inner products by just evaluating the kernel $k$. That is, we have $\langle \Phi(x_i), \Phi(x_j)\rangle_{\mathcal{H}_k} = \langle k( x_i, \cdot), k( x_j, \cdot)\rangle_{\mathcal{H}_k}  = k(x_i,x_j)$ for all data points $x_i, x_j \in\mathcal{X}$. Thus, applying learning algorithms on the transformed data $\{\Phi(x_i)\}_{i=1}^n$ that rely on computations of the inner product on the data, can be easily computed by only evaluating the reproducing kernel of $\mathcal{H}_k$. The Moore-Aronszjan theorem really just tells us that, for any given a symmetric, positive-definite kernel $k$, there exists a unique corresponding RKHS. The proof is by construction.

I think my second point above answers your question on why taking inner products corresponds to evaluating the kernel. To understand the inner workings of RKHS based algorithms fully requires knowledge of some functional analysis. E.g. the Riesz-representation theorem is crucial in the definition of the kernel and in the Moore-Aronszjan theorem one constructs the RKHS by completion.

Turning now to implementation of SVMs, recall that, for data pairs $\{(x_i,y_i)\}_{i=1}^n$, we want to compute
$$ \inf_{f \in \mathcal{H}_k}\left\{ \frac{1}{n}\sum_{i=1}^n L(x_i, y_i, f(x_i)) + \lambda \| f\|_{\mathcal{H_k}}\right\},$$
where $L$ is a convex non-negative loss function and $\lambda\in\mathbb{R}_{\geq0}$ is a free parameter. The representer theorem is crucial here, since we know that the minimal $f^*$ which solves this optimisation is of the form $f^*(\cdot) = \sum_{i=1}^n \alpha_i k(x_i,\cdot),$ for some scalars $\alpha_i \in\mathbb{R}$ which, for convenience, we group together as a vector $\alpha = (\alpha_1,\ldots,\alpha_n) \in\mathbb{R}^n$. This implies that the optimisation problem can be reduced to
$$ \inf_{\alpha \in \mathbb{R}^n}\left\{ \frac{1}{n}\sum_{i=1}^n L\left(x_i, y_i, \sum_{i=1}^n \alpha_i k(x_i,\cdot)\right) + \lambda \left\| \sum_{i=1}^n \alpha_i k(x_i,\cdot)\right\|_{\mathcal{H_k}}\right\},$$
thus reducing the infinite dimensional optimisation to a finite-dimensional optimisation.
