2
$\begingroup$

I was reading through "kernel trick" since I wasn't familiar with it. It is my understanding that apart from a better classification boundary (literally the geometric boundary) there should be some form of computational advantage.

However if $\mathcal{X} = \left\{x_1,\ldots,x_n \right\}$ are our training data and $\tilde{\mathcal{X}} = \left\{ \phi(x_1),\ldots,\phi(x_n)\right\}$ Is some transformation applied it is my understanding that the kernel is computed as

$$ \left( K \right)_{i,j} = \left\langle \phi(x_i),\phi(x_j)\right\rangle $$

Where $K$ is a matrix. This allow to express the classifier

$$ w^T \phi(x) = \sum_{j} \left(\alpha^TK^T\right)\phi(x) $$

It seems to me at this point that the actual "computational trick" is to precompute this matrix that depends from the training data.

Am I right?

$\endgroup$
2
$\begingroup$

The computational advantage comes from the fact that the matrix $K$ (and all other evaluations of the form $\langle \phi(x),\phi(y)\rangle$) can be computed extremely efficiently - you don't have to actually calculate $\phi(x)$ and $\phi(y)$, which may be complicated objects in a possibly infinite-dimensional space, and then take their inner product, which may be a complicated mathematical operation without an explicit formula. Instead, the upper inner product is given by the kernel evaluation $$ \langle \phi(x),\phi(y)\rangle = k(x,y), $$ where $k$ denotes the kernel and is chosen such that it can be easily computed.

How exactly this enters in the algorithms, depends, of course, on the application you have in mind. But algorithms using the kernel trick never have to explicitly evaluate the map $\phi$ or the inner product in the feature space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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