2
$\begingroup$

Why setting $C>1$ does not affect the result (compared to $C=1$) according to:

https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/#libsvm_for_svdd_and_finding_the_smallest_sphere_containing_all_data

However in their reference paper [1] the optimization is

$$\min_{R,\mathbf{a},\boldsymbol\eta}\ (R^2 + C \sum_{i=1 \dots \ell} \eta_i)$$

subject to $$(\phi(\mathbf{x}_i)-\mathbf{a})^2 \leq R^2 + \eta_i,\ \ \ \eta_i> 0, \ \ \ i = 1,\dots,\ell $$.

[1] https://www.csie.ntu.edu.tw/~cjlin/papers/svdd.pdf A Revisit to Support Vector Data Description

$\endgroup$

1 Answer 1

1
$\begingroup$

So this is Theorem 6 in that paper. They then provide the following text:

For SVM, it is known that if the training instances are separable, there is a $\bar{C}$ such that for all $C > \bar{C}$, the solution is the same as that of the problem without the loss term; see, for example, Lin (2001). This $\bar{C}$ is problem dependent, but for SVDD, we have shown that $\bar{C}$ is one.

The proof of this basically relies on the fact that when $C \geq \frac{1}{\ell}$, that $0 \leq \alpha_i \leq 1$ (because $\sum \alpha_i = 1$ in this case). This in turn implies that $\gamma_i > 0$ (since $C = \alpha_i + \gamma_i$) which then results in $\xi_i = 0$, in other words the data is "separable".

Since this is for SVDD - this is saying that basically for $C > 1$, the result is always the same - namely the smallest sphere containing all of the data.

Note though that this is for the version of SVDD that has $\bar{R}$ and not $R^2$ in terms of the optimization (they explain numerous issues with the version with $R^2$).

To give some additional intuition into the result, consider that $\sum_i \alpha_i = 1$ at the optimum (for $C \geq \frac{1}{\ell}$). Then consider that for all points which lie outside the sphere, $\xi_i > 0 \Rightarrow \gamma_i = 0 \Rightarrow \alpha_i = C$. Therefore, the number of points that can lie outside the sphere is at most $\frac{1}{C}$. Thus, if $C > 1$, the number of points that can lie outside the sphere must be less than 1. Thus, when $C > 1$, no points can lie outside the sphere, and thus the solution is always the smallest sphere(s) containing all of the points (regardless of uniqueness of the result).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.