1
$\begingroup$

I apologize for the verbose description, but (after searching several places for an answer) maybe the best way to phrase it is to lay things out explicitly.

Say we are trying to build an SVM model for classification, and our data consists of $m$=1000 training examples with $n$=15 features.

We start with the 'Primal' version of the optimization problem, which is defined in terms of the values of the feature-vectors $x_i$.

The Lagrangian dual of the optimization problem is (from Wikipedia):

${\text{maximize}}:\ \ \ \sum _{i=1}^{m}c_{i}-{\frac {1}{2}}\sum _{i=1}^{m}\sum _{j=1}^{m}y_{i}y_{j}c_{i}c_{j}(x_{i}\cdot x_{j})\ ,$ ${\text{subject to }}:\ \ \sum _{i=1}^{m}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2m\lambda }}\;{\text{for all }}i.$

Notably, this is defined only in terms of the pairwise dot-products of the $x_i$ vectors. This helps us use the kernel-trick by replacing $(x_i \cdot x_j$) in the optimization objective with $K(x_i,x_j)$, where $K$ is our choice of kernel function. Let's say we choose the RBF: $K(u,v)=\exp \left(-{\frac {\|u -v \|^2}{2\sigma ^2}}\right)$, and this brings us to:

APPROACH (A)
${\text{maximize}}:\ \ \ \sum _{i=1}^{m}c_{i}-{\frac {1}{2}}\sum _{i=1}^{m}\sum _{j=1}^{m}y_{i}y_{j}c_{i}c_{j}\ K(x_{i}\cdot x_{j})$
This approach works as if we had implicitly mapped all vectors $x_i \in \mathbb{R}^{15}$ to some higher-dimensional feature-set $\phi_i$(in this case, $\phi_i \in \mathbb{R}^\infty$ due to using the RBF), and found an optimal hyperplane to separate the points.

Now consider APPROACH (B), where we use the RBF in a different way:
We map the features $x_i$ to $\mathbb{R}^{m}$, by evaluating for each point its 'nearness' to every $x_i$ using the RBF.
i.e. Each $x_i \in \mathbb{R}^{15}$ is mapped to a $\phi_i \in \mathbb{R}^{1000}$,
where the value of the $d^{th}$ dimension of $\phi_i$ is $\text{RBF}(x_i,x_d)$.
This is not very different from using polynomial-features followed by linear regression.

In both approaches we are using the RBF as a measure of 'similarity'.
My questions are:

  • Is Approach (B) used in practice? Is there anything wrong with using the RBF to compute new features in this way, or does it make it inferior to approach (A)?

  • Intuitively, how is the handling of the pairwise 'similarity' of training points different in the two approaches? Why do 'similarity-functions' work well as choices for kernel functions in the first place?

Improve this question
$\endgroup$
7
  • $\begingroup$ I think you will find something similar here : stats.stackexchange.com/questions/168051/… $\endgroup$ – user83346 Jan 29 '17 at 9:20
  • $\begingroup$ That thread has some very interesting discussion on kernel methods. However, it doesn't quite touch on the differences between the specific approaches I mention here. Specifically, approach B, in which we map our feature set explicitly using the RBF (as opposed to A, in which we use the RBF but are implicitly mapping to some unknown set of features) $\endgroup$ – dhrumeel Jan 30 '17 at 17:46
  • $\begingroup$ Well the $\phi$ in the link is defined in the same way as you define it and the thread shows that both approaches are equivalent (which is exactly what is the idea behind the reproducing kernel hilbert spaces) ? So approach B does the same as A except that it makes the $\phi$ explicit ? $\endgroup$ – user83346 Jan 30 '17 at 19:44
  • $\begingroup$ It does not seem like the 2 approaches are equivalent. In (A), the mapped-to feature space is (implicitly) $\mathbb{R}^\infty$ while in (B) we are explicitly defining features that lie in $\mathbb{R}^{1000}$. $\endgroup$ – dhrumeel Jan 30 '17 at 23:49
  • $\begingroup$ Well in B you define a feature space that is $R^n$ where n is your sample size, as this can be done for samples of any size n, this is $R^\infty$. $\endgroup$ – user83346 Jan 31 '17 at 4:51

Your Answer

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

Browse other questions tagged or ask your own question.