1
$\begingroup$

I think that so far I understand the crucial concepts of Support Vector Machines: That we represent our data as points in some n-dimensional space, and in the binary case try to separate them by an optimal maximal margin hyperplane (optimality defined with regards of the bias-variance trade-off, see hard or soft margin SVMs). What I do not know yet is how exactly this hyperplane is found - so what is the algorithm? Given we have two datasets, does an algorithm randomly tries out one plane after the other to determine which plane is the optimal one? What does it mean, that for the calculation of the hyperplane only the support vectors are considered?

$\endgroup$
  • 2
    $\begingroup$ Can you check the first several posts under "Related" in the sidebar --> and clarify in your question the ways in which your question is different from those questions or is not answered by any of the answers to them? $\endgroup$ – Glen_b Oct 13 '15 at 4:55
  • $\begingroup$ Well, maybe I am wrong, but they seem to be asking about the concepts - not about how the SVM hyperplane learning algorithm is working step by step.. $\endgroup$ – user24544 Oct 13 '15 at 5:32
  • $\begingroup$ Are you after a step-by-step detailed algorithm from which you could write code? $\endgroup$ – Glen_b Oct 13 '15 at 5:37
  • 1
    $\begingroup$ Not to write code, but understand the method better. I feel I only have a partial understanding by knowing the concepts and the general idea. So what I actually wonder is in how far the calculation of the hyperplane only requires support vectors (that is what our prof said) - to be able to understand this question, I wanted to understand how the search process for the hyperplane is actually carried out.. $\endgroup$ – user24544 Oct 13 '15 at 9:47
  • 2
    $\begingroup$ These days (kernel) SVM's are trained using sequential minimal optimization, which is essentially a customized form of quadratic programming. It's best to start reading there. $\endgroup$ – Marc Claesen Oct 13 '15 at 9:50
3
$\begingroup$

Does an algorithm randomly tries out one plane after the other to determine which plane is the optimal one?

No, that would be terribly inefficient. These days (kernel) SVM's are trained using sequential minimal optimization, which is essentially a customized form of quadratic programming.

Quadratic programming is an instance of the general class of convex optimization. One of the biggest advantages of the fact that training an SVM is a convex problem is the fact it has a global optimum that can efficiently be found, in stark contrast to the training problems associated to neural networks.

What does it mean, that for the calculation of the hyperplane only the support vectors are considered?

Via the (generalized) representer theorem, we know that the separating hyperplane is a linear combination of support vectors. Hence, we only need to consider solutions of that form.

$\endgroup$
  • 1
    $\begingroup$ Thanks so much! I think I have a better idea now: So it is a convex problem which means that local minima = global minima. Hence we start with some initial condition (initial plane) and have good knowledge on algorithms to optimise from there on - only requiring reference to the support vectors in this process if I am correct $\endgroup$ – user24544 Oct 13 '15 at 10:29

Your Answer

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