# What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question?

I am trying to understand the difference between the paper : https://pdfs.semanticscholar.org/59ee/e096b49d66f39891eb88a6c84cc89acba12d.pdf

The first paper is about SMO for SVM and the second paper is about SMO for one class. The question is what are the difference between this two algorithms? Also what are the common factors in both the paper?

The second paper has not shown any details of the algorithm so not sure what minimal change to be done on the first to get the second algorithm?

Given the code for the SMO for SVM, what minimum change would require to make the code suitable for one class SMO?

• This sounds too open-ended to me. I imagine there are probably many differences and similarities. If you understand both papers you should be able to identify those. Can you narrow down your question? Is there any specific aspect that you are unclear on? What have you come up with so far? As it stands I don't see how this could be answered in an objective way, and I don't see how it will be useful to others in the future. – D.W. Nov 9 '18 at 19:52
• We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. At minimum I suggest including title, authors, and where published. Thank you! – D.W. Nov 9 '18 at 19:53
• @D.W. Thank you for the interest. But IMHO this question may be other way around. One must already know the two algorithms very thoroughly to find the difference. I have written code for both of them still not sure how to combine in the shortest way. – Creator Nov 13 '18 at 19:45

## 1 Answer

Both the papers attempt to develop Sequential Minimization Optimization (SMO) approaches for two kinds of Support Vector Machine (SVM) formulations, which include the conventional SVM and one-class SVM. The basic idea behind the SMO approach is to make the underlying SVM formulation scalable for larger datasets. This is a challenge since the SVM is a kernel method, and using it for large datasets requires computation of the kernel matrix whose size is of the order of the number of training samples. Thus, there is a high memory and computational requirement, moreover, issues pertaining to matrix stability may arise. In order to address this issue, the SMO approach adopts a method where pair-wise Lagrange multipliers are optimized instead of solving the entire Quadratic Programming Problem (QPP) as in the conventional case. The selection of the Lagrange multipliers may be based on heuristics. This (SMO) makes the approach (SVM) scalable for larger datasets, which is the underlying similarity between the use of SMO for SVM and one-class SVM.

In order to understand the difference between the two, it is important to understand the difference between the purpose of the SVM and one-class SVM, and subsequently the difference in their formulations (the optimization problem for each). This eventually translates into the difference in applying the SMO strategy for each of these cases.

The conventional SVM for binary classification aims to find a separating hyperplane $$w^Tx+b=0$$ with coefficients $$w$$ and bias $$b$$ for training data $$x$$ (and class labels $$y$$) with maximum margin ($$\frac{1}{\|w\|_2}$$) which is at least unit distance from points of the two classes which lie close to the separating hyperplane. This is achieved by the soft-margin formulation involving trade-off using positively constrained slack variables $$\xi$$ and user-defined parameter $$C$$ as below:

$$\min_{w,b,\xi} \frac{1}{2} \|w\|_2^2 + C \sum_i \xi_i$$

subject to

$$y^i (w^T x^i + b) + \xi_i\geq 1$$, $$\xi_i \geq 0$$

In practice, the kernel trick is used to map the data to a high-dimensional kernel space $$K$$ that induces linear separability and the dual of the above formulation in terms of the Lagrange multipliers $$\alpha$$ is solved, which is given as

$$\min_{\alpha} \frac{1}{2} \sum_i \sum_j y^i y^j K(x^i,x^j) \alpha_i \alpha_j - \sum_i \alpha_i$$

subject to

$$\sum_i \alpha_i y^i = 0, \alpha_i \geq 0$$

On the other hand, in case of the one-class SVM, we would like to determine whether the test sample belongs to a specific class, determined by the training data (having $$M$$ samples), or not. Consequently, the one-class SVM is solved by

$$\min_{w,b,\xi} \frac{1}{2} \|w\|_2^2 + \frac{1}{C M} \sum_i \xi_i - b$$

subject to

$$w^T x^i \geq (b - \xi_i)$$, $$\xi_i \geq 0$$

The dual for the one-class SVM is then given as

$$\min_{\alpha} \frac{1}{2} \sum_i \sum_j K(x^i,x^j) \alpha_i \alpha_j$$

subject to

$$0 \leq \alpha_i \leq \frac{1}{CM}, \sum_i \alpha_i = 1$$

The derivation of the SMO algorithm follows the steps presented in the two papers, and the difference arises out of the nature of the two SVM formulations and their corresponding dual problems. Details of the derivation may be found in the respective papers, and newer strategies for selection of the Lagrange multipliers for optimization may also be found in literature.

• See Section 3.3 in ieeexplore.ieee.org/document/4344146 – S_S Nov 10 '18 at 16:42
• They gave the algorithm for a fast SMO not the difference as asked in the question. – Creator Nov 11 '18 at 19:10