How to determine if the data points are linearly separable from an SVM hyperplane

Question

1. How to know the data points are linearly separable from an SVM hyperplane?

2. How to get the optimal classifier during iteration process?

3. How to calculate the complexity of the SVM model?

Answer 1

I haven't looked into this in ages, but let me give it a shot.

1) fit a linear svm and check that $\hat{y}_i=y_i\forall i$.

2) At iteration $t$, you will get a vector of --currently-- optimal weights $\mathbf{\alpha}^{(t)}$. These weights are the closest I can think to the idea of optimal classifying machine at a given step of the optimization process. How meaningful these interrupted weights are will most likely depend on $t$ as well as what algorithm is used to obtain them: if $t$ is small I would expect the quality of the $\mathbf{\alpha}^{(t)}$ derived from a plain-vanilla QP solver to be much better than those obtained from Platt's SMO, for example.

3)In its most general statement, for a given admissible kernel function $k_{\lambda}(.,.)$, you can rewrite the SVM problem, in dual form, as a convex minimization one:

$$\underset{\alpha_i\geq 0, i = 1, \dots, n}{\arg.\min}\;\;\;L(\mathbf{\alpha}|X,\bf{y},\lambda)$$

where

$$L(\mathbf{\alpha}|X,\bf{y},\lambda)=\frac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)-\sum_{i=1}^n \alpha_i$$

If $\bf{x}_i\in\mathbb{R}^p$ and $\bf{y}\in\{-1,1\}^n$, in general, the maximum complexity of solving such a QP can potentially be of order $O(pn^3)$. But this may not be very relevant. In most cases the average complexity will be much lower --potentially of order $O(pn^2)$-- if one uses clever algorithm designed to take advantage of properties specific to the SVM problem.

The first example is Platt's SMO algorithm (1). It is primilarly based on the observation that the problem can be solved by a series of sequential minimization of the partial objective function:

$$(a)\;\;\;\underset{\alpha_i\geq 0|\alpha_j, j\neq i}{\arg.\min}\;\;\;L(\alpha_i|X,\mathbf{y},\lambda)$$

and the idea that once one of the $k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)$ has been computed to solve (a), it can be stored so it doesn't have to be computed again.

While these two observations are potentially true for any QP, they yield particularly strong gains in the (non-linear) SVM context because, in a nutshell, most of the $k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)$ are negligible.

Over time, more clever tricks have been developed, again potentially lowering average complexities (e.g. 2), but the most important take away is that, often, solving even the non linear kernel SVM problem is quiet feasible even for large datasets.

(1) Platt (2008). Microsoft Research. Technical Report MSR-TR-98-14.

(2) Keerthi, Shevade, Bhattacharyya, Murthy (2001). Improvements to Platt's SMO Algorithm for SVM Classifier Design.