1
$\begingroup$

Support vector machine (SVM) is a supervised learning algorithm. It draws hyperplanes to separate data points of different classes. The objective function involves inner products of pairs of feature vectors. The inner product can be replaced by a non-negative function $K(x,y)\ge0$ symmetric in its two variables $x$, $y$. The kernel function $K$ is a inner product in some abstract Hilbert space. In practice, we compute the similarity matrix using a kernel and the similarity matrix is symmetric and non-negative. The diagonal is the self-similarities which may or may not be constant and depend on the kernel.

However, if I scale the similarity, or the kernel function by a positive constant, does it affect the classification accuracy? My intuition says no. Is it true?

P.S. If the new set of parameters are used then the prediction will probably change; here let's define the accuracy as the optimal accuracy which is unique and independent of the kernel parameters.

P.P.S.

I have tested it on linear kernel SVM using sklearn SVC. The predictions will not change at all if rescale the dot product by $a$ and $C$ parameter by $C'=C/a$. I believe this is true for other kernels as well.

So the short answer, rescaling does change the SVM classification through a trivial reparameterization.

$\endgroup$
3
$\begingroup$

In SVM we have $\hat y_0 = \text{sgn}(\sum_{i=1}^n \alpha_i y_i K(x_i, x_0))$ so if we've already fit our SVM then multiplying $K$ by a positive constant $\gamma$ doesn't affect our decision boundary.

More generally, we know that $K(u, v) = \langle\phi(u), \phi(v) \rangle_H$ where $H$ is our RKHS and $\phi$ is our feature map. If $\gamma > 0$ then we know that $K'(u, v) := \gamma K(u, v) = \langle \sqrt \gamma\phi(u), \sqrt \gamma\phi(v) \rangle_H$ so we are just using a scaled version of the same feature map $\phi$. Our Hilbert space $H$ is closed under scalar multiplication too so $K'$ and $K$ correspond to the exact same Hilbert space although our $n$ representers aren't the exact same. So intuitively we shouldn't be able to do anything different with $K'$ vs $K$.

The vector normal to our hyperplane in $H$ is $$ w = \sum_i \alpha_i y_i \phi(x_i) $$ so if we replace $\phi(x_i)$ with $\sqrt \gamma \phi(x_i)$ we just get $w' = \sqrt \gamma w$, and this has the exact same nullspace and therefore corresponds to the exact same hyperplane.

$ $

Update

This will change the distance between points but by the same amount so that ultimately there is no difference. Our hyperparameters will also need to change but in a predictable way. Suppose we're using the linear kernel $K_L(u,v) = u^T v$. If $K'_L := \gamma K_L$ then all we've done is scale all the distances between our data points by the same amount (it's like using the inner product $\langle u, v \rangle_\gamma := u^T \gamma I v$: the outputted values are different but $\gamma I$ just contracts or expands every dimension equally so relatively nothing changes). So it is true that we will have changed the margin width, but not in a meaningful way since we'll have changed all other distances also.

$\endgroup$
  • $\begingroup$ Thanks! Can I find some references including this argument? $\endgroup$ – Machine Oct 27 '16 at 20:24
  • $\begingroup$ I find umiacs.umd.edu/~hal/docs/daume04rkhs.pdf to be very helpful, especially the part talking about actually constructing the RKHS. I think this explains how $H = H'$. $\endgroup$ – jld Oct 27 '16 at 20:25
  • $\begingroup$ One difference is that the regularizer $\lVert w \rVert^2$ will change: $\lVert w' \rVert^2 = \gamma \lVert w \rVert^2$, so that applying a scaling $\gamma$ effectively scales $C$ as well. $\endgroup$ – Dougal Oct 27 '16 at 20:27
  • $\begingroup$ But here is a counter example citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Machine Oct 27 '16 at 20:32
  • 1
    $\begingroup$ @ChenChao At this point it looks like it is true that the decision boundary is unchanged but scaling can affect the margin so there can be a change in performance. I'll follow up and update my answer as I read more of the paper you linked to. $\endgroup$ – jld Oct 27 '16 at 21:10

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.