Non‑linear SVM - Ciallo Wiki

A nonlinear support vector machine (SVM) is an extension of the linear SVM that enables the classification of data sets that are not linearly separable in the original feature space. By applying a kernel function, the input data is implicitly mapped into a higher-dimensional space where a separating hyperplane can be found. The method retains the margin-maximization principle of linear SVMs while allowing for complex decision boundaries. Nonlinear SVMs are widely used in pattern recognition, bioinformatics, image classification, and text categorization.

1 Mathematical formulation

1.1 Motivation for nonlinear separation

Many real-world classification problems involve data that cannot be separated by a straight line (or hyperplane) in the original feature space. For instance, data points arranged in concentric circles or interleaved spirals require a decision boundary that is curved or even disconnected. Linear SVMs fail on such problems because they assume a linear decision boundary. The nonlinear SVM overcomes this limitation by transforming the input space into a higher-dimensional feature space where a linear separator becomes viable.

1.2 Feature mapping and the feature space

The core idea is to apply a fixed nonlinear mapping φ: ℝd → ℝD (where D often ≫ d) that sends each input vector x to a transformed vector φ(x) in a possibly much higher-dimensional space. In this new feature space, the data may become linearly separable. The SVM then finds a maximum-margin hyperplane in the feature space. However, explicitly computing φ(x) for high-dimensional D can be computationally prohibitive.

1.3 Kernel trick

1.3.1 Definition of a kernel function

The kernel trick avoids explicit computation of φ(x) by using a kernel function K(x,z) = φ(x)·φ(z), which directly computes the dot product in the feature space without ever constructing φ(x). Any symmetric positive semi-definite function that can be expressed as an inner product in some Hilbert space qualifies as a kernel. Common examples include the polynomial kernel and the radial basis function (RBF) kernel.

1.3.2 Mercer’s condition

Mercer’s condition provides a necessary and sufficient criterion for a symmetric function K(x,z) to be a valid kernel: for any finite set of points {xi}, the matrix Kij = K(xi, xj) must be positive semi-definite (i.e., all eigenvalues non-negative). Kernels satisfying this condition guarantee the existence of an associated feature map φ.

1.4 Dual formulation

1.4.1 Lagrangian and Wolfe dual

The optimization problem for a nonlinear SVM is solved via its dual formulation. The primal problem seeks to minimize ‖w‖² subject to constraints, where w is the weight vector in the feature space. Using Lagrange multipliers αi ≥ 0, the Wolfe dual becomes:

maximize Σi αi – ½ Σi Σj αi αj yi yj K(xi, xj)

subject to Σi αi yi = 0, 0 ≤ αi ≤ C (for the soft-margin case). The dual depends only on the kernel function, not on the explicit feature map.

1.4.2 Support vectors and decision function

Only those training points with αi > 0—called support vectors—influence the decision boundary. The decision function for a new input x is:

f(x) = sign( Σi∈SV αi yi K(xi, x) + b )

where b is the bias term. The kernel function is evaluated between x and each support vector.

2 Common kernel functions

2.1 Polynomial kernel

The polynomial kernel is defined as K(x,z) = (x·z + c)d, where d is the degree and c ≥ 0 is a constant.

2.1.1 Homogeneous vs. inhomogeneous

When c = 0, the kernel is called homogeneous; it yields only monomials of degree d. When c > 0, the kernel is inhomogeneous and includes lower-degree terms as well, effectively expanding the feature space to all monomials up to degree d.

2.2 Radial basis function (RBF) kernel

The RBF kernel, also known as the Gaussian kernel, is defined as K(x,z) = exp(–γ ‖x – z‖²), where γ > 0 is a free parameter. This kernel maps each input point into an infinite-dimensional feature space and is one of the most widely used kernels due to its flexibility.

2.2.1 Parameter γ and its effect

The parameter γ controls the width of the Gaussian: small γ produces a broad kernel (low complexity, smooth decision boundary), while large γ produces a narrow kernel (high complexity, possible overfitting). A very large γ can cause the SVM to treat each training point in isolation, leading to a highly irregular boundary.

2.3 Sigmoid kernel

The sigmoid kernel is defined as K(x,z) = tanh(κ x·z + θ), with parameters κ and θ. It is derived from neural network activation functions. For certain parameter values it satisfies Mercer’s condition, but not universally; its use in SVMs is less common than polynomial or RBF kernels.

2.4 Custom kernels

Beyond standard kernels, domain-specific custom kernels can be designed to exploit structure in the data.

2.4.1 String kernels

String kernels operate on sequences of symbols, such as DNA or text strings. They compute similarity based on common substrings or subsequences. Examples include the spectrum kernel and the substring kernel. These are widely used in bioinformatics for sequence classification.

2.4.2 Graph kernels

Graph kernels measure similarity between graph-structured data. They decompose graphs into substructures (e.g., walks, cycles, or tree patterns) and compare them using an inner product. Applications include cheminformatics (molecule classification) and social network analysis.

3 Training and optimization

3.1 Sequential minimal optimization (SMO)

Training a nonlinear SVM involves solving a quadratic programming (QP) problem with a dense kernel matrix, which can be computationally expensive. Platt’s sequential minimal optimization (SMO) breaks the QP into a series of smallest possible subproblems, each involving only two Lagrange multipliers. SMO solves these subproblems analytically and iterates until convergence. It is efficient and avoids large matrix operations, making it the de facto standard training algorithm for SVMs.

3.2 Soft‑margin extension

3.2.1 Slack variables and regularization parameter C

Real data often contain noise or outliers that make perfect separation undesirable. Soft‑margin SVMs introduce slack variables ξi ≥ 0 to allow misclassification of training points. The objective becomes minimizing ½‖w‖² + C Σi ξi, where C > 0 is a regularization parameter. A large C penalizes misclassifications heavily, leading to a more complex boundary; a small C allows more misclassifications but encourages a simpler model.

3.2.2 Bias towards nonlinearity

The soft‑margin formulation applies equally to nonlinear SVMs. Increasing C tends to increase model complexity, which in combination with a flexible kernel (e.g., high-degree polynomial or narrow RBF) can lead to severe overfitting. Conversely, reducing C imposes a bias toward simpler decision boundaries, even in a high-dimensional feature space.

3.3 Computational complexity

The worst-case training complexity of a nonlinear SVM is O(n²) to O(n³) in the number of training samples n, depending on the solver and the kernel matrix sparsity. SMO typically achieves O(n²) in practice. The prediction complexity is O(nSV), where nSV is the number of support vectors, often much smaller than n. For very large data sets, approximate methods or alternative classifiers are often preferred.

4 Practical considerations

4.1 Kernel selection guidelines

4.1.1 Dimensionality vs. sample size

When the number of features d is large relative to the number of samples n, a linear kernel (or a low-degree polynomial) often suffices because the data is likely already separable in the original space. When n is much larger than d, a nonlinear kernel like RBF can capture complex patterns. As a rule of thumb, one should try the RBF kernel first, as it often gives good performance with proper parameter tuning.

4.1.2 Cross‑validation for hyperparameters

The kernel parameters (e.g., γ for RBF, degree for polynomial) and the regularization C are crucial. A common approach is to perform grid search over a logarithmic scale of parameter values, using k‑fold cross‑validation to evaluate performance. The combination yielding the highest validation accuracy is selected.

4.2 Scaling and preprocessing

All features should be scaled to a similar range (e.g., zero mean and unit variance) before training. Kernel functions like the RBF rely on Euclidean distances, so features with large magnitudes can dominate the kernel values without scaling. Scaling also often improves convergence of the optimization algorithm.

4.3 Multi‑class extension

SVMs are inherently binary classifiers. For multi‑class problems, several strategies exist.

4.3.1 One‑vs‑one

One‑vs‑one (OvO) trains k(k–1)/2 binary classifiers, one for every pair of classes. A new point is classified by a voting scheme. OvO is computationally more expensive but often yields better accuracy than OvA, especially when classes are imbalanced.

4.3.2 One‑vs‑all

One‑vs‑all (OvA) trains k binary classifiers, each distinguishing one class from the rest. The class with the highest confidence score (e.g., greatest distance from the hyperplane) is assigned. OvA is simpler and faster but can suffer from class imbalance and ambiguous decision boundaries.

5 Applications in applied sciences

5.1 Bioinformatics (e.g., protein classification)

Nonlinear SVMs are used to classify proteins into functional families based on sequence or structural features. Custom string kernels capture local alignments and motif patterns. The method has been applied to predict protein–protein interactions and subcellular localization.

5.2 Image recognition (e.g., handwritten digit recognition)

The RBF kernel outperforms linear classifiers for image data with high pixel variability. For example, on the MNIST dataset of handwritten digits, a nonlinear SVM with RBF kernel achieved state‑of‑the‑art results before the advent of deep learning. Histogram‑based features combined with kernel methods remain competitive for certain tasks.

5.3 Text and document categorization

Text data often exhibit high dimensionality (bag‑of‑words) but also many irrelevant features. Nonlinear SVMs with linear or polynomial kernels perform well on sentiment analysis, spam filtering, and topic classification. The kernel trick also allows the use of string kernels for direct document comparison without feature extraction.

5.4 Anomaly detection

Nonlinear SVMs can be adapted for one‑class classification, where the goal is to distinguish “normal” data from outliers. By learning a soft boundary around the normal data in a feature space (e.g., using a hypersphere or a hyperplane), the method detects anomalies as points that fall outside this boundary. This approach is used in fraud detection, network intrusion detection, and industrial monitoring.

6 Limitations and alternatives

6.1 Sensitivity to kernel and parameters

Nonlinear SVMs are highly sensitive to the choice of kernel and its hyperparameters. Poor choices can lead to underfitting or overfitting. Parameter tuning via cross‑validation is computationally expensive, and there is no universal rule for selecting the best kernel.

6.2 Interpretability challenges

The decision boundary of a nonlinear SVM is defined implicitly through support vectors and kernel evaluations. Unlike linear models, there is no simple interpretation of feature importance. The “black‑box” nature complicates understanding why a particular decision was made, which is problematic in domains requiring explainability (e.g., medicine, law).

6.3 Alternative nonlinear classifiers (neural networks, random forests)

Neural networks, especially deep learning models, can learn highly complex decision boundaries and scale to very large data sets. Random forests (ensemble of decision trees) offer good performance, handle high‑dimensional data naturally, and provide feature importance measures. Both alternatives avoid the kernel selection burden and often achieve comparable or superior accuracy, though they may require more data or careful architecture design.