3
$\begingroup$

Why use the kernel trick in a support vector machine as opposed to just transforming the data and then using a linear classifier? Certainly, we'll approximately double the amount of memory required to hold the data, original plus transformed, but beyond that it seems like the amount of computation remains about the same. What are the other considerations?

$\endgroup$
  • $\begingroup$ The main purpose is to categorize the datas.Some datas are not linear separable(like xor),so we have to map it into higher dimensional spaces. $\endgroup$ – Muse_China Jun 23 '17 at 11:36
  • $\begingroup$ @Muse_China I very much agree. However, it's not clear to me why this needs to occur using the kernel trick. We could just pretransform the data, so that it's linearly separable even if the dimension of the result is increased or decreased. Certainly, this costs memory, but I'd like to know if it costs anything more or if there are other considerations. $\endgroup$ – wyer33 Jun 23 '17 at 11:56
  • $\begingroup$ In my opinion its aim is to classify data which can not be classified in lower-dimension spaces,some computation will be an addition. $\endgroup$ – Muse_China Jun 24 '17 at 8:06
1
$\begingroup$

The kernel trick says that given your data $x_i \in \mathbb{R}^n, i \in \{1 \ldots m\}$ and a kernel $k : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ having the good properties (*) there is a non-linear transformation $\phi : \mathbb{R}^n \to \mathbb{R}^{m}$ such that $k(x_i,x_j) = \langle \phi(x_i),\phi(x_j)\rangle$.

Let $K_{ij} = k(x_i,x_j)$ the $m \times m$ dot product matrix. Then the good property of $k(.,.)$ is that $K$ is semi-definite positive, so we can diagonalize it to obtain $K = P D P^T$. Letting $Y = P D^{1/2}$ we have $Y Y^T = P D^{1/2} (D^{1/2} P^T) = P D P^T = K$ ie. $\phi(x_i) = Y_{i.}$ (the $i$th row).

That is to say you can do what you said when $m$ is small, but usually $n$ is small but $m$ is very large, so it is not praticable to actually compute $P,D$ and $\phi$ (instead we will compute the first few largest eigenvalues of $K$ in the case of kernel-PCA and spectral clustering)

$\endgroup$
1
$\begingroup$

You can use infinite-dimensional spaces with the kernel trick.

You might want to read my SVM summary and especially What is an example of a SVM kernel, where one implicitly uses an infinity-dimensional space?

$\endgroup$
1
$\begingroup$

Given all the existing answers, I would like to add more to this story. In fact, in modern large-scale systems people do use data transformation directly instead of the classical kernel trick, which takes $O(N^3)$ time to compute and is way too slow.

However, as typical kernels (e.g, RBF) are infinite-dimensional, one cannot expect to accurately compute $x\mapsto \phi(x)$ as the image of the mapping is infinite-dimensional. Instead, approximations $x\mapsto\tilde \phi(x)$ are used, such that $\langle\tilde\phi,\tilde\phi'\rangle_{\mathcal H}\approx \langle\phi,\phi'\rangle_{\mathcal H}$, and that $\tilde\phi$ has a smaller dimension. This approach is called random Fourier features, or more interestingly random kitchen sink. You can google both of them to get a good idea of what they are doing.

$\endgroup$
0
$\begingroup$

The typical kernels used for kernel method induce an infinite dimensional reproducing kernel Hilbert spaces! It's not just double the memory, it's infinite memory.

$\endgroup$
  • $\begingroup$ Wait. Why? Say we want to transform our data with the transformation $\phi(x)=(x_1,x_2,x_1^2+x_2^2)$, then $k(x,y)=\langle \phi(x),\phi(y)\rangle=x_1y_1+x_2y_2+(x_1^2+x_2^2)(y_1^2+y_2^2)$ when using $\langle x,y\rangle=x^Ty$. I don't see how this requires and/or saves an infinite amount of memory. $\endgroup$ – wyer33 Jun 23 '17 at 14:26
  • $\begingroup$ that's because that kernel has finite dimensional feature space. Squared exponential kernel has infinite dim. $\endgroup$ – Memming Jun 23 '17 at 15:19
  • $\begingroup$ Alright, so essentially we have a mapping $\phi:\mathbb{R}^m\rightarrow L^2(\mathbb{R}^n)$ and the inner product $\langle\cdot,\cdot\rangle : L^2(\mathbb{R}^n)\times L^2(\mathbb{R}^n)\rightarrow \mathbb{R}$. The composition is $x,y\mapsto \langle\phi(x),\phi(y)\rangle : \mathbb{R}^m\rightarrow \mathbb{R}$, so we can compute it, but the result of $\phi$ is a function, so it's difficult to precompute in general. Does that sound about right? In other words, we often lift our data into a function space and that's hard to precompute? $\endgroup$ – wyer33 Jun 23 '17 at 15:41
  • $\begingroup$ (See my answer, the space becomes finite dimensional when we consider a finite dataset) $\endgroup$ – reuns Jun 23 '17 at 18:06
0
$\begingroup$

Kernel methods allow you to separate your data in a higher dimensional space without having to actually transform the data. This often does result in less computation compared to actually transforming the data first. The idea is that you only care about how the vectors compare in the other space, i.e. you only care about their inner products, not what the actual representations of those vectors are in that space. A good example to illustrate why this is better is if your kernel is a radial basis function. This is a projection to an infinite dimensional space which you certainly can't do to your data directly.

So, your reasoning is correct, that you could just transform the data to get the same result. But the assumption that the computations are basically the same is not right.

$\endgroup$
  • $\begingroup$ Does whether or not the kernel method is more efficient depend on whether $\langle \phi(x),\phi(y)\rangle$ can be computed more efficiently than $\phi$ and $\langle \cdot,\cdot\rangle$ separately? If the composition can not be computed much more efficiently than the individual operations, is the cost about the same? $\endgroup$ – wyer33 Jun 23 '17 at 13:38
  • $\begingroup$ The idea is that you only care about how the vectors compare in the other space, i.e. you only care about their inner products. Not what the actual representations of those vectors in that space are. I do not know under what (if any) conditions transforming the data first would be less computationally expensive. $\endgroup$ – dt688 Jun 23 '17 at 13:57
  • $\begingroup$ I understand that we only need the inner products in the transformed space. What's not clear to me is that there's a dramatic difference in performance. The cost of a kernel function is that there's more code to maintain. In addition, I often like to look at the transformed data in order to assess the behavior of the classifier. Generally, the mantra is use a kernel function because it's more efficient, but I've not seen a good analysis as to how much this is true, which is why I'm asking. From what I can tell, it's basically the same unless the composition can be implemented more efficiently. $\endgroup$ – wyer33 Jun 23 '17 at 14:07
  • $\begingroup$ Well, one example where it would be "more efficient" would be if your kernel is a radial basis function. This is a projection to an infinite dimensional space which you certainly can't do to your data directly. $\endgroup$ – dt688 Jun 23 '17 at 14:22
  • $\begingroup$ Ah, ok. This is more to the point. From what this looks like, we're allowed to project our data into a space of functions and then redefine our inner product to work on this space. For example, in the RBF example, we're projecting our data into the space $L^2(\mathbb{R}^m)$ and then using the inner product $\langle f,g\rangle=\int fg$. This composition is just a number, which can be implemented in code, but it's difficult to represent these functions directly in memory. Does that sound about right? $\endgroup$ – wyer33 Jun 23 '17 at 14:37

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.