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

and the paper http://users.cecs.anu.edu.au/~williams/papers/P132.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 question has an open bounty worth +100 reputation from Creator ending in 2 days.

This question has not received enough attention.

Please help me to analyst the problem.

  • 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 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 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 7 hours ago

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.

New contributor
Sumit is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • I wrote something in quora. I know what you told, but not sure I got the difference clear. For instance if I give you the code for the SMO for SVM, what minimum change would require to make the code suitable for one class SMO? – Creator Nov 10 at 7:46
  • See Section 3.3 in ieeexplore.ieee.org/document/4344146 – Sumit Nov 10 at 16:42
  • They gave the algorithm for a fast SMO not the difference as asked in the question. – Creator 2 days ago

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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