1
$\begingroup$

From what I know, one of the strategies employed by an SVM is to increase dimensionality of your data until they are linearly separable. (I guess there's some mathematical proof that your data will always eventually be linearly separable in some high dimensional space)

So for example, if you have two attributes $x$ and $y$, and you have a function $\phi$ that maps these attributes to higher dimensional ones, then part of the SVM's calculation would be the dot product between $\phi(x)$ and $\phi(y)$.

But $\phi(x)$ and $\phi(y)$ are higher dimensional versions of $x$ and $y$ and thus it is more expensive computation and storage wise to compute the dot product between them. That's where the kernel function comes in: instead of calculating $<\phi(x), \phi(y)>$, you calculate $K(x, y)$ , where $K$ is a valid kernel function.

For example, if we use $K(x,y) = (1+x^Ty)^2$, then $K(x, y) = <\phi(x), \phi(y)>$. But $K$ is much cheaper to compute than the dot product between those high dimensional vectors.

However, I never defined how exactly $\phi$ maps vectors to higher dimensional versions of themselves. Does the exact specification of how the mapping happens not matter?

TLDR $K(x, y) = <\phi(x), \phi(y)>$ is said to hold even when $\phi$ hasn't been defined. Why? Doesn't $\phi$ need to be defined?

$\endgroup$
1
$\begingroup$

No, it doesn't matter. It's even ok when more than one possible mappings lead to the same kernel, just as in Gaussian kernel. Because, in the dual formulation of the problem, we can see that the Lagrangian (that is to be maximized wrt $\alpha_i$ subject to KKT conditions), depends on only the dot products of the samples, see here for a complete reference: $$L=\sum\alpha_i-\frac{1}{2}\sum\sum\alpha_i\alpha_jy_iy_j\underbrace{x_i^Tx_j}_{K(x_i,x_j)}$$ The solution is an assignment of $\alpha_i$ that tells you the support vectors.

| cite | improve this answer | |
$\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.