CODEWITHSUNDEEP
machine-learningsvm
user1599171
user1599171

Reputation:

Does SVM classification always produces unique solution?

Linear classifiers on separable can have more than one boundary for classifying the data. This is the reason we go for SVM to choose boundary which has maximum margin(minimum generalization error on unseen data).

Does SVM classification always produces unique solution(Wont we get two maximum margin boundary in all possible data) ?

Is answer depends on the Hard margin SVM and Soft Margin SVM?

Upvotes: 14

Views: 12220

Answers (2)

ely
ely

Reputation: 77454

Yes, both the soft and hard formulations of standard SVM are convex optimization problems, hence have unique global optima. I suppose if the problem is incredibly huge, approximation methods would be parsimonious enough that you would use them instead of exact solvers, and then your numerical solution technique might not find the global optimum purely because it's trade-off benefit is to reduce search time.

The typical approach to these is sequential minimal optimization -- hold some variables fixed and optimize over a small subset of the variables, then repeat with different variables over and over until you can't improve the objective function. Given that, I find it implausible that anyone would solve these problems in a way that won't yield the global optimum.

Of course, the global optimum you find might not actually be appropriate for your data; that depends on how well your model, noisy class labels, etc. represent the data generating process. So solving this doesn't guarantee you've found the absolute right classifier or anything.

Here are some lecture notes I found about this in a cursory search: (link)

Here is a more direct link regarding the convexity claims: (link)

Upvotes: 13

Hans Scundal
Hans Scundal

Reputation: 496

For hard margin classifiers with no regularization the SVM problem can be converted to a coercive quadratic programming problem with linear constrains (assuming a solution / positive margin exists). Coercive quadratic programming problems with linear constrains have unique global minimums and simple optimization methods (like gradient decent or the perceptron algorithm) are guaranteed to converge to the global minimum. See for example

http://optimization-online.org/DB_FILE/2007/05/1662.pdf

For soft margin SVMs and for SVMs with regularization terms, I think there are unique global minima and the usual techniques converge to the global minimum, but I am not aware of any proofs that cover all the possibilities.

Upvotes: 4

Related Questions