I am interested in theoretical results for the generalization ability of Support Vector Machines, e.g. bounds on the probability of classification error and on the Vapnik-Chervonenkis (VC) dimension of these machines. However, reading through the literature I have had the impression that some similar recurring results tend to differ slightly from author to author, particularly regarding the technical conditions required for a given bound to hold.
In the following I will recall the structure of the SVM problem and state 3 of the main generalization results that I have recurrently found in one form or another $-$ I give 3 main references throughout the exposition.
Problem setting:
Assume we have a data sample of independent and identically distributed (i.i.d.) pairs $(x_i,y_i)_{1\leq i\leq n}$ where for all $i$, $x_i \in \mathbb{R}^p$ and $y_i \in \{-1,1\}$. We construct a support vector machine (SVM) that maximizes the minimal margin $m^*$ between the separating hyperplane defined by $\{x : w \cdot x + b = 0\}$, $w \in \mathbb{R}^p$ and $b \in \mathbb{R}$, and the closest point among $x_1,\cdots,x_n$ so as to separate the two classes defined by $y = -1$ and $y = 1$. We let the SVM admit some errors through a soft margin by introducing slack variables $\xi_1,\cdots,\xi_n$ $-$ but for notational simplicity we ignore the possibility of kernels. The solution parameters $w^*$ and $b^*$ are obtained by solving the following convex quadratic optimization program:
$$\begin{align} \min_{w, \, b, \, \xi_1, \, \cdots, \, \xi_n} \; & \; \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n\xi_i \\ \text{s.t.} \; : \; & \; y_i(w\cdot x_i+b) \geq 1 - \xi_i \, & , \, \forall \, i \in \{1,\cdots,n\} \\ & \; \xi_i \geq 0\, & , \, \forall \, i \in \{1,\cdots,n\} \end{align}$$
We are interested in the generalization ability of this machine.
Vapnik-Chervonenkis dimension $VC$ :
A first result is due to (Vapnik, 2000), in which he bounds the VC dimension of a separating hyperplane, theorem 5.1. Letting $R = \max_{x_i} \|x_i\|$, we have:
$$VC \leq \min \left( \left( \frac{R}{m^*}\right)^2, \, p\right) + 1$$
This result can again be found in (Burges, 1998), theorem 6. However, it seems Burges' theorem is more restrictive than the same result by Vapnik, as he needs to define a special category of classifiers, known as gap-tolerant classifiers $-$ to which the SVM belongs $-$, to state the theorem.
Bounds on probability of errors:
In (Vapnik, 2000), theorem 5.2 in page 139 gives the following bound on the SVM generalization ability:
$$\mathbb{E}[P_{\text{error}}] \leq \frac{1}{n}\mathbb{E} \left[ \min\left(p,n_{SV},(R \, \|w\|)^2 \right) \right]$$
where $n_{SV}$ is the number of support vectors of the SVM. This results seems to be found again in (Burges, 1998), equations (86) and (93) respectively. But again, Burges seems to differ from Vapnik as he separates the components within the minimum function above in different theorems, with different conditions.
Another result appearing in (Vapnik, 2000), p.133, is the following. Assuming again that, for all $i$, $\|x_i\|^2 \leq R^2$ and letting $h \equiv VC$ and $\epsilon \in [0,1]$, we define $\zeta$ to be equal to:
$$ \zeta = 4 \frac{h\left( \text{ln}\frac{2n}{h} + 1\right) - \text{ln}\frac{\epsilon}{4}}{n}$$
We also define $n_{\text{error}}$ to be the number of misclassified training examples by the SVM. Then with probability $1-\epsilon$ we can assert that the probability that a test example will not be separated correctly by the $m^*$-margin hyperplane $-$ i.e. SVM with margin $m^*$ $-$ has the bound:
$$ P_{\text{error}} \leq \frac{n_{\text{error}}}{n} + \frac{\zeta}{2} \left( 1 + \sqrt{1+ \frac{4 \, n_{\text{error}}}{n \, \zeta}} \right)$$
However, in (Hastie, Tibshirani and Friedman, 2009), p.438, a very similar result is found:
$$ \text{Error}_{\text{Test}} \leq \zeta $$
Conclusion:
It seems to me that there is a certain degree of conflict between these results. On the other hand, two of these references, although canonical in the SVM literature, start to be slightly old (1998 and 2000), especially if we consider that research into the SVM algorithm started in the mid-nineties.
My questions are:
- Are these results still valid today, or have they been proved wrong?
- Have tighter bounds with relatively loose conditions been derived since then? If so, by whom and where can I found them?
- Finally, is there any reference material which synthetises the main generalization results about the SVM?
References:
Vapnik, V. N. (1998). Statistical Learning Theory, 1st edition, John Wiley & Sons
Vapnik, V. N. (2000). The Nature of Statistical Learning Theory, 2nd edition, Springer