A bunch of questions about Kernels in Machine Learning

Question

i've read many topics on this platform about this topic but i still have some questions, mainly theoretical. We are dealing with ML, so if we are here means that we have to classify with linear classifier, some non linearly separable data. I'm generally speaking, i do not associate Kernels to any algo as SVM, Perceptron and so on.

1)Suppose we have n observations, which are vectors, each one composed by m features. So an m dimensional space. Kernel is a function that takes 2 input and return a scalar. So i have to apply kernel for each of my n observations couple-by-couple?

2)Suppose we have a mapping $\varphi \, : \, \mathbb R^m \to \mathbb R^z$ that brings our vectors in $\mathbb R^m$ to some feature space $\mathbb R^z$. Then the dot product of $\mathbf x$ and $\mathbf y$ in this space is $\varphi(\mathbf x)^T \varphi(\mathbf y)$. A kernel is a function $k$ that corresponds to this dot product, i.e. $k(\mathbf x, \mathbf y) = \varphi(\mathbf x)^T \varphi(\mathbf y)$. I don't understand the story about the φ mapping function. It seems to be implicit during the dot product operation? Why we said that we do not know the φ mapping fucntion?

3) For example, consider a simple polynomial kernel $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2$ with $\mathbf x, \mathbf y \in \mathbb R^2$. This doesn't seem to correspond to any mapping function $\varphi$, it's just a function that returns a real number. Assuming that $\mathbf x = (x_1, x_2)$ and $\mathbf y = (y_1, y_2)$, let's expand this expression:

$\begin{align} k(\mathbf x, \mathbf y) & = (1 + \mathbf x^T \mathbf y)^2 = (1 + x_1 \, y_1 + x_2 \, y_2)^2 = \\ & = 1 + x_1^2 y_1^2 + x_2^2 y_2^2 + 2 x_1 y_1 + 2 x_2 y_2 + 2 x_1 x_2 y_1 y_2 \end{align}$ (a)

Note that this is nothing else but a dot product between two vectors $(1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$ and $(1, y_1^2, y_2^2, \sqrt{2} y_1, \sqrt{2} y_2, \sqrt{2} y_1 y_2)$,(b) and $\varphi(\mathbf x) = \varphi(x_1, x_2) = (1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$ (c). So the kernel $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2 = \varphi(\mathbf x)^T \varphi(\mathbf y)$ computes a dot product in 6-dimensional space without explicitly visiting this space.

So from here, the polynomial kernel applied to those 2 vectors, returns the equation (a). This can be seen as a dot product between 2 vectors of 6 elements, so 6-dimensional. So those two vectors (b) and (c) would represents ours original vectors transormed in a 6-dimensional space?

4)This can be considered a similarity function because even if it return always the same dot product, the same dot product applied to different vectors, can return to us a measure on how much are correlated the two input vectors?

Thank you very much, need 10 coffes now to return back to life

Answer 1

1)

That's called a kernel matrix. Whether you need to calculate it depends on the method, for example in Kernel PCA you need to do this, and SVMs with kernels don't need this.

2)

The point is to use nonlinear $\phi$ so that decision functions that depend on it are nonlinear, but you don't have to actually compute $\phi$, which possibly even embeds your examples into infinite-dimensional space (as RBF kernel)

3)

Yes. Note that $\varphi(x)$'s components are polynomials in $x$'s entries. That's nonlinearity.

---

For pictorial examples I made these sometimes ago (look for Kernel PCA transform of circles). You can see that, with RBF kernel's $\varphi$, data that is not linearly separable gets mapped to a space in which it is (since it's PCA is linearly separable). Kernelized SVMs depend on this fact, and they do something similar in the image of $\varphi$.