5
$\begingroup$

Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems.

$$ \text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 $$

My question is, what linear programming runs on the background for the minimization of the objective function $J$. Is it Simplex?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Its not linear programming. its Quadratic programming, you have here a quadratic function and not a linear one $\endgroup$
    – nir shahar
    Feb 22, 2021 at 15:18
  • 1
    $\begingroup$ A good algorithm to use is the SMO - Sequential Minimal Optimization, which is a technique specifically designed for SVMs $\endgroup$
    – nir shahar
    Feb 22, 2021 at 15:19
  • $\begingroup$ @nirshahar Thanks a lot. I recommend that you post those comments as an answer so I can accept it! $\endgroup$
    – SomeoneSomeoneSomeoneSomeoneSo
    Feb 22, 2021 at 15:24

1 Answer 1

Reset to default
6
$\begingroup$

The SVM problem (and other related problems) can be described as a minimization \ maximization of a quadratic function.

This can be easily solved with the gradient descent algorithm, however I recommend using the SMO algorithm since it is a direct solution (to the dual of the SVM problem), and can be also used for kernelized SVMs

Improve this answer
$\endgroup$
1
  • $\begingroup$ Addition to the above answer: I just came across this paper (link below) that presents PEGASOS algorithm. It claims that with PEGASOS "the number of iterations required to obtain a solution of accuracy $\epsilon$ is $O(1/\epsilon)$, where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs require $Ω(1/\epsilon^2)$ iterations" courses.edx.org/assets/courseware/v1/… $\endgroup$
    – SomeoneSomeoneSomeoneSomeoneSo
    Feb 26, 2021 at 12:49

Your Answer

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

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