3
$\begingroup$

I understand that this is the dual form of the linear SVM problem (with a hard margin):

$J(\mathbf{\alpha}) = \dfrac{1}{2}\sum\limits_{i=1}^{m}{ \sum\limits_{j=1}^{m}{ \alpha_i \alpha_j y_i y_j {\mathbf{x}_i}^t\cdot\mathbf{x}_j } } \quad - \quad \sum\limits_{i=1}^{m}{\alpha_i}\\ \text{with}\quad \alpha^{(i)} \ge 0 \quad \text{for }i = 1, 2, \cdots, m$

I'm wondering how to solve it using (sub)gradient descent? Perhaps I should remove the constraints first?

$J_{\text{extended}}(\mathbf{\alpha}) = \dfrac{1}{2}\sum\limits_{i=1}^{m}{ \sum\limits_{j=1}^{m}{ \max(0, \alpha_i) \max(0, \alpha_j) y_i y_j {\mathbf{x}_i}^t\cdot\mathbf{x}_j } } \quad - \quad \sum\limits_{i=1}^{m}{\alpha_i}$

Then I can compute the partial subderivatives:

$\dfrac{\partial}{\partial \alpha_k}J_{\text{extended}}(\mathbf{\alpha}) = \begin{cases} \dfrac{1}{2}\sum\limits_{i=1}^{m}\alpha_iy_iy_k{\mathbf{x}_i}^t\cdot\mathbf{x}_k - 1 & \text{ if } \alpha_k \ge 0\\ -1 & if \alpha_k < 0 \end{cases}$

But this does not seem right as the $\alpha_i$ may end up negative. What is the correct approach for this?

$\endgroup$
  • $\begingroup$ The correct approach is to use a QP solver. $\endgroup$ – Sycorax Jun 3 '16 at 15:25
  • $\begingroup$ Thanks for your answer @GeneralAbrial. I'm mostly trying to get a deeper understanding of SVMs. Also, using Scikit-Learn's SGDClassifier with the hinge loss makes it possible to build an online version of the linear SVM classifier. I'm looking for something similar for kernelized SVMs. Is it possible? $\endgroup$ – MiniQuark Jun 3 '16 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.