3
$\begingroup$

I have a few questions,

  1. 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 (*).
  2. 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?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

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

  1. 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.
  2. 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.

$\endgroup$
10
  • $\begingroup$ Thanks for the answer. First, I think I should note I come from a mathy background (have attended lectures functional analysis, measure theory, etc.), but have attended no machine learning lecture. $\endgroup$ Nov 10, 2021 at 14:50
  • $\begingroup$ Your answer to (1) is what I expected. As for (2), there are somethings you can clarify. First, I've mentioned the Moore-Aronszajn theorem since, in my mind, there would be some useful (in the sense of being used by ML-practitioners) kernels that we only knew to be of the form $\langle \phi(x), \phi(y) \rangle$ due to the theorem. I've becoming to feel this is not the case, and that MA is kinda useless from a practitioners POV. $\endgroup$ Nov 10, 2021 at 14:53
  • $\begingroup$ Second, and now my "serious issue" with Kernel-SVM, how do we know that Linear-SVM works on the infinite dimensional RKHS induced by the Gaussian kernel? I see that the definition of a hyperplane and the margin work just fine on arbitrary Hilbert spaces; but what about the quadratic problem? Can you solve for $w$ in infinite dimensions? You may now quote the representer theorem and say there is nothing to worry. However, for $w$ to be expressed as a finite linear combination of the support vectors, you still have to differentiate the Lagrangian; how would you differentiate w.r.t. (...) $\endgroup$ Nov 10, 2021 at 14:57
  • $\begingroup$ to a function? I already saw that you can do that through functional derivatives, but my question is simpler than this: is the knowledge of functional derivatives necessary to justify the use of Kernel-SVM on these infinite dimensional settings? If not, why not? $\endgroup$ Nov 10, 2021 at 14:59
  • $\begingroup$ Please see my edit. I am wondering what you think the Moore-Aronszjan theorem is. Your proposed function is not a kernel because of the theorem, you can directly show its positive-definite (see the answer here). $\endgroup$ Nov 10, 2021 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.