Understanding Generalized Linear‑Separable Support Vector Machines

Generalized Linear‑Separable Support Vector Machine

When the two classes in a training set are perfectly linearly separable, only the support vectors lie on the decision boundaries while all other samples are outside; the resulting hyperplane is a hard‑margin hyperplane.

If the classes are only approximately linearly separable, some samples violate the hard‑margin constraints. By introducing slack variables we “soften” the margin, allowing points between the two boundaries—these are called boundary support vectors. The convex hulls of the two classes intersect slightly, as illustrated in the figure.

Softening the margin is achieved by adding slack variables to the constraints, which leads to a quadratic programming problem that includes a penalty parameter C.

The Lagrange function for this problem is formulated, and the dual problem is derived accordingly.

Solving the optimization yields the optimal Lagrange multipliers α*. Selecting a positive component 0<α*_j<C allows us to compute the weight vector and bias, thereby constructing the classification hyperplane and the decision function.

Consequently, unknown samples can be classified; when C becomes sufficiently large, the soft‑margin solution converges to the hard‑margin (linearly separable) case.

Reference

司守奎，孙玺菁. Python数学实验与建模