0
$\begingroup$

I have found the following example:

As an example consider the case when the input space $ {\mathcal{X}}$ consists of images of $ 16\times 16$ pixels, i.e. $ 256$ dimensional vectors, and we choose $ 5$th order monomials as non-linear features. The dimensionality of such space would be

$\displaystyle \left(\begin{array}{c}5+256-1\\ 5\end{array}\right) \approx 10^{10} \;$

Such a mapping would clearly be intractable to carry out explicitly. We are not only facing the technical problem of storing the data and doing the computations, but we are also introducing problems due to the fact that we are now working in an extremely sparse sampled space. By the use of the SRM principle, we can be less sensitive to the dimensionality of the space and achieve good generalization.

The problems concerning the storage and the manipulation of the high dimensional data can be avoided. It turns out that for a certain class of mappings we are well able to compute scalar products in this new space even if it is extremely high dimensional. Simplifying the above example of computing all $ 5$th order products of $ 256$ pixels to that of computing all $ 2$nd order products of two ''pixels'', i.e.

$\displaystyle {\boldsymbol{x}} = (x_1,x_2)$ and$\displaystyle \quad\Phi({\boldsymbol{x}}) = \left(x_1^2,\sqrt{2}x_1x_2,x_2^2\right)\;$

The problem that I have is in understanding the last formula, from where does the author gets those values for the individual transformation? To me, it seems that he is applying the formula of analytical geometry of a circle, but I am not quite sure.

Also how does the author apply the transformation from $ {\mathcal{X}}$ to $\displaystyle\quad\Phi({\boldsymbol{x}})$?

$\endgroup$
  • $\begingroup$ You need to give a little context here. Where in CS are we right now, are my tag choices right? $\endgroup$ – Raphael Mar 21 '15 at 11:40
2
$\begingroup$

This is just the explicit form of the feature map for a homogenous, degree 2 polynomial kernel. Here your input space is $\mathbb{R}^2$ and the feature space can be identified with $\mathbb{R}^3$. The point the author is making is that instead of computing the feature map explicitly, and then taking the Euclidean inner product $\langle \Phi(p),\Phi(q)\rangle$, you can just compute $\langle p,q\rangle^2$.

$\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.