Maximum Margin Methods

Karush-Kuhn-Tucker (KKT) Conditions

KKT conditions first-order necessary conditions for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Inequality Constrained Optimization, general Problem:

The Lagrangian:

The KKT conditions are

Support Vector Machine (SVM)

Separable case

Consider an input space with , the target space , and let be the target function.

Geometric Margin The geometric margin of a linear classifier at a point is its Euclidean distance to the hyperplane :

The geometric margin of a linear classifier for a sample is the minimum geometric margin over the points in the sample, , that is the distance of the hyperplane defining to the closest sample points.

Primal optimization problem By definition of the geometric margin, the maximum margin of a separating hyperplane is given by

The second equality follows from the fact that, since the sample is linearly separable, for the maximizing pair must be non-negative for all . Now, observe that the last expression is invariant to multiplication of by a positive scalar. Thus, we can restrict ourselves to pairs scaled such that :

The second equality results from the fact that for the maximizing pair , the minimum of is 1.

Since maximizing is equivalent to minimzing , the pair returned by SVM in the separable case is the solution of the following convex optimization problem:

The Lagrangian

The KKT conditions are obtained by setting the gradient of the Lagrangian with respect to the primal variables and to zero and by writing the complementarity conditions:

and its dual optimization problem is:

Non-separable Case

For any hyperplane , there exists such that

While, a relaxed version of these constraints can indeed hold, that is, for each , there exist such that . So the primal optimization problem becomes:

Then the Lagrangian is defined as:

References

[1] @misc{ wiki:xxx, author = "{Wikipedia contributors}", title = "Karush–Kuhn–Tucker conditions --- {Wikipedia}{,} The Free Encyclopedia", year = "2020", url = "https://en.wikipedia.org/w/index.php?title=Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions&oldid=983546575", note = "[Online; accessed 31-October-2020]" }

[2] @book{mohri2018foundations, title={Foundations of machine learning}, author={Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet}, year={2018} }