Free tools Windows power users keep installed
One-click scans. No signup required.
Lagrange multipliers turn the soft-margin SVM’s constrained optimization problem into a dual problem whose variables identify the support vectors. The resulting classifier scores a new point by summing kernel similarities to those support vectors, weighted by their labels and learned coefficients. The Python example below builds that kernel matrix and solves the dual with SciPy’s constrained optimizer; it is an educational implementation, not a replacement for a production SVM solver.
What the SVM is optimizing
Given training examples (xᵢ, yᵢ), with labels yᵢ ∈ {−1,+1}, a support vector machine seeks a separating hyperplane with a large geometric margin. A large margin corresponds to a small norm for its weight vector w. Real data may not be perfectly separable, so a soft-margin SVM adds slack variables ξᵢ that allow examples to violate the margin:
minimize ½‖w‖² + C Σᵢ ξᵢ
subject to yᵢ(wᵀφ(xᵢ)+b) ≥ 1−ξᵢ and ξᵢ ≥ 0.
Here, φ maps examples into a feature space, b is the intercept, and C sets the cost of margin violations relative to keeping w small. A larger C penalizes violations more heavily; it is an inverse regularization parameter in scikit-learn’s formulation. The equivalent primal and dual formulations are documented in the scikit-learn SVM guide.
#1 Best Overall
- Used Book in Good Condition
How Lagrange multipliers produce the dual
Associate a nonnegative Lagrange multiplier αᵢ with each margin constraint and another nonnegative multiplier with each constraint ξᵢ ≥ 0. The Lagrangian combines the objective with these constraints. At an optimum, its derivatives with respect to the primal variables must vanish.
Stationarity gives two key constraints
- Setting the derivative with respect to w to zero gives w = Σᵢ αᵢyᵢφ(xᵢ).
- Setting the derivative with respect to b to zero gives Σᵢ αᵢyᵢ = 0.
- Stationarity with respect to the slack variables, together with nonnegative multipliers, bounds the dual variables: 0 ≤ αᵢ ≤ C.
Substitute the expression for w back into the Lagrangian. The training examples now appear through pairwise feature-space dot products, φ(xᵢ)ᵀφ(xⱼ), rather than through an explicitly computed w. Define a kernel K(xᵢ,xⱼ)=φ(xᵢ)ᵀφ(xⱼ). The soft-margin dual is:
maximize Σᵢ αᵢ − ½Σᵢⱼ αᵢαⱼyᵢyⱼK(xᵢ,xⱼ)
Rank #2
subject to Σᵢ αᵢyᵢ = 0 and 0 ≤ αᵢ ≤ C.
This is a constrained quadratic optimization problem in the coefficients α. A kernel lets the classifier use feature-space similarities without explicitly constructing the mapped vectors. For a linear kernel, K(x,z)=xᵀz; other kernel choices encode other similarity functions. Kernel choice and regularization affect overfitting, so neither a flexible kernel nor a large C guarantees better generalization.
Why the nonzero multipliers identify support vectors
The Karush–Kuhn–Tucker complementarity conditions connect the constraints to the multipliers. If αᵢ=0, example i contributes nothing to w or to the prediction score. Examples with nonzero coefficients are support-vector terms in the classifier. A coefficient strictly between zero and C typically corresponds to an example on the margin under nondegenerate conditions; coefficients at the upper bound can correspond to margin violations. A support vector is therefore not necessarily exactly on a margin boundary.
For a new point x, the decision score is f(x)=Σᵢ yᵢαᵢK(xᵢ,x)+b. Predict +1 when the score is positive and −1 when it is negative. A score of zero lies on the decision boundary. Since coefficients for nonsupport vectors are zero, the sum only needs to include the support vectors.
Implement the dual in Python
The example uses NumPy for arrays and SciPy’s minimize function to solve the dual. SciPy is an explicit dependency; install it alongside NumPy in your environment. The toy data has two classes and uses a linear kernel, keeping the result easy to inspect. The same dual code can use another kernel by replacing the kernel function, provided it produces a suitable positive-semidefinite Gram matrix.
Recommended Free Tools
1. Prepare labels and define a kernel
Labels must be encoded as −1 or +1. Keep feature scaling in mind when using a kernel or distance-sensitive features; this minimal example does not add a preprocessing pipeline.
Rank #4
import numpy as np
from scipy.optimize import minimize
X = np.array([
[2.0, 2.0], [2.0, 3.0], [3.0, 2.0],
[6.0, 6.0], [6.0, 7.0], [7.0, 6.0],
])
y = np.array([-1, -1, -1, 1, 1, 1], dtype=float)
C = 1.0
def linear_kernel(A, B):
return A @ B.T
# K[i, j] = K(x_i, x_j)
K = linear_kernel(X, X)
n = len(y)2. Form and solve the constrained quadratic program
Let Qᵢⱼ = yᵢyⱼK(xᵢ,xⱼ). SciPy’s routine minimizes, so minimize the negative of the dual objective. Its Jacobian is the gradient of that negative objective. The equality constraint enforces yᵀα=0; bounds enforce 0≤αᵢ≤C.
Q = np.outer(y, y) * K
def objective(alpha):
return 0.5 * alpha @ Q @ alpha - np.sum(alpha)
def gradient(alpha):
return Q @ alpha - np.ones_like(alpha)
constraints = {
"type": "eq",
"fun": lambda alpha: y @ alpha,
"jac": lambda alpha: y,
}
result = minimize(
objective,
x0=np.zeros(n),
jac=gradient,
bounds=[(0.0, C)] * n,
constraints=constraints,
method="SLSQP",
options={"ftol": 1e-10, "maxiter": 1000},
)
if not result.success:
raise RuntimeError(f"Dual optimization failed: {result.message}")
alpha = result.xOptimization libraries use finite precision. Before interpreting the coefficients, check both the solver status and the equality constraint. If clipping small numerical excursions, specify a tolerance and then recheck feasibility rather than silently treating arbitrary coefficient changes as harmless.
tol = 1e-7
alpha[np.abs(alpha) < tol] = 0.0
alpha[np.abs(alpha - C) < tol] = C
if not np.isclose(y @ alpha, 0.0, atol=1e-6):
raise RuntimeError("Equality constraint y @ alpha = 0 is not satisfied")
support = alpha > tol
if not np.any(support):
raise RuntimeError("No support vectors found; inspect optimization result")3. Recover the intercept and make predictions
For an interior coefficient, 0<αᵢ<C, the corresponding example is on the margin under usual nondegenerate conditions. Rearranging its margin equality gives an estimate of the intercept. Averaging over interior support vectors reduces sensitivity to small numerical differences.
interior = (alpha > tol) & (alpha < C - tol)
def kernel(A, B):
return linear_kernel(A, B)
if np.any(interior):
decision_at_training = (alpha * y) @ K
b = np.mean(y[interior] - decision_at_training[interior])
else:
# Degenerate/numerically boundary-only case: estimate b from
# the KKT-compatible interval implied by the bound coefficients.
scores_without_b = (alpha * y) @ K
lower, upper = -np.inf, np.inf
for i in range(n):
if y[i] == 1:
if alpha[i] <= tol:
lower = max(lower, 1.0 - scores_without_b[i])
elif alpha[i] >= C - tol:
upper = min(upper, 1.0 - scores_without_b[i])
else:
if alpha[i] <= tol:
upper = min(upper, -1.0 - scores_without_b[i])
elif alpha[i] >= C - tol:
lower = max(lower, -1.0 - scores_without_b[i])
if np.isfinite(lower) and np.isfinite(upper):
b = 0.5 * (lower + upper)
elif np.isfinite(lower):
b = lower
elif np.isfinite(upper):
b = upper
else:
raise RuntimeError("Could not infer intercept from KKT conditions")
def decision_function(X_new):
return (alpha[support] * y[support]) @ kernel(X[support], X_new) + b
def predict(X_new):
return np.where(decision_function(X_new) >= 0.0, 1, -1)
print("support-vector indices:", np.flatnonzero(support))
print("predictions:", predict(np.array([[2.5, 2.5], [6.5, 6.5]])))The fallback estimates an intercept from the KKT-compatible bounds when no coefficient is strictly interior. If those bounds conflict substantially, treat that as a warning about solver tolerance, convergence, or degeneracy and inspect the optimization result rather than trusting the estimate. The code is intended to make the derivation concrete; it does not implement the numerical safeguards and specialized optimization methods expected of a mature SVM library.
Best Value
Linear versus kernel SVMs: what changes in the implementation
The dual formulation stays the same; the kernel matrix and what the model must retain change.
| Choice | Representation and interpretability | Prediction work | Main trade-off |
|---|---|---|---|
| Linear kernel | Recover an explicit vector w=Σᵢαᵢyᵢxᵢ, which can make feature contributions easier to inspect. | Use wᵀx+b, or sum over support vectors. | Simple representation, but it only creates linear decision boundaries in the input representation. |
| Nonlinear kernel | Represent the decision rule through similarities to retained training support vectors rather than an explicit feature-space weight vector. | Evaluate the chosen kernel between a query and each support vector. | Can represent more flexible boundaries, with pairwise similarity computation and model size tied to the support vectors. |
Neither approach is universally faster or more accurate. Those outcomes depend on the data, kernel, number of support vectors, and solver. A Gram matrix for n training examples contains n² pairwise values, so memory and optimization cost can become limiting as the training set grows.
Quick Recap
Practical limits and when to use a library
- Choose kernel and regularization deliberately. The scikit-learn guide cautions that kernel and regularization choices matter for avoiding overfitting, including settings where the feature count greatly exceeds the sample count.
- Probability estimates are not the raw SVM decision. Scikit-learn SVM estimators do not directly provide probability estimates from the margin optimization; its probability option derives them using an expensive five-fold cross-validation procedure. This is specific to that library behavior, not a universal rule for all possible SVM implementations.
- Use a mature solver for real workloads. This example illustrates the mathematics on a small dataset. Established SVM implementations provide more specialized optimization, convergence handling, and production integration than this concise educational solver.
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
