Source-linked AI summary
Laplacian Support Vector Machines Trained in the Primal
Stefano Melacci, Mikhail Belkin
TL;DR
The paper addresses issues in the original dual training of LapSVMs for semi-supervised classification with unlabeled data. It solves LapSVMs in the primal using preconditioned conjugate gradient and classifier-based early stopping, reducing computational cost while retaining roughly the optimal classification accuracy.
Problem
LapSVM training in the dual involves a two-step procedure, motivating a simpler approach for exploiting labeled and unlabeled data in semi-supervised classification.
Method
The paper solves the primal LapSVM problem with preconditioned conjugate gradient and stops early based on prediction stability on unlabeled data or accuracy on labeled validation examples.
Results
The proposed approach reduces computational cost from O(n^3) to O(n^2), and approximate solutions achieve roughly the same classification accuracy as optimal ones.
Takeaways & Limitations
Primal LapSVM training provides a useful starting point for incremental classifier building, sparser kernel expansions, and applying the fast solution to LapRLSC.
Takeaways & Limitations
Common gradient-based stopping conditions are difficult to tune because their thresholds depend strongly on the problem and can behave unstably as error-vector states change.
Abstract
from arXiv · showhide
In the last few years, due to the growing ubiquity of unlabeled data, much effort has been spent by the machine learning community to develop better understanding and improve the quality of classifiers exploiting unlabeled data. Following the manifold regularization approach, Laplacian Support Vector Machines (LapSVMs) have shown the state of the art performance in semi--supervised classification. In this paper we present two strategies to solve the primal LapSVM problem, in order to overcome some issues of the original dual formulation. Whereas training a LapSVM in the dual requires two steps, using the primal form allows us to collapse training to a single step. Moreover, the computational complexity of the training algorithm is reduced from O(n^3) to O(n^2) using preconditioned conjugate gradient, where n is the combined number of labeled and unlabeled examples. We speed up training by using an early stopping strategy based on the prediction on unlabeled data or, if available, on labeled validation examples. This allows the algorithm to quickly compute approximate solutions with roughly the same classification accuracy as the optimal ones, considerably reducing the training time. Due to its simplicity, training LapSVM in the primal can be the starting point for additional enhancements of the original LapSVM formulation, such as those for dealing with large datasets. We present an extensive experimental evaluation on real world data showing the benefits of the proposed approach.
1. Introduction
The paper targets computational and approximation issues in dual LapSVM training by solving the problem in the primal. It proposes iterative and data-based stopping strategies to reduce training time while preserving accuracy.
- LapSVM exploits unlabeled data through manifold regularization and has achieved state-of-the-art performance in semi-supervised classification.
- O(n^3) dual training uses a labeled-point optimization followed by an n-variable linear system for the final coefficients.
- Two primal methods collapse training onto the whole variable set in a single step, although the intrinsic regularizer reduces Newton’s advantages compared with supervised SVMs.
- Primal training directly controls approximate solutions through conjugate-gradient iterations, avoiding the indirect relation between dual approximations and the target function.
- Prediction stability on unlabeled data or validation accuracy provides an early-stopping criterion that achieves optimal-like accuracy with substantially reduced training time.
- The primal LapSVM solution also connects to LapRLSC, allowing the proposed fast solution to be applied to that classifier.
2. Manifold Regularization
Manifold regularization incorporates the geometry of labeled and unlabeled data into classification by encouraging smoothness along an estimated manifold. LapSVM implements this principle, but its dual formulation requires a costly two-step computation.
- Manifold Regularization: The graph Laplacian is built from the data graph, while the kernel Gram matrix represents pairwise evaluations among all n training points.
- Manifold Regularization: Manifold regularization assumes nearby points in the intrinsic geometry should have similar labels, with the manifold estimated from labeled and unlabeled data using a graph Laplacian.
- Manifold Regularization: Ambient regularization enforces smoothness in the RKHS, whereas intrinsic regularization enforces smoothness along the sampled manifold.
- Manifold Regularization: Manifold regularization produces a classification boundary more aligned with marginal-data geometry than maximum-margin supervised classification on the clock dataset.
- Manifold Regularization: The intrinsic norm transduces function values along the manifold, but requiring equal values at nearby points can over-constrain the classifier.
- LapSVM: LapSVM uses a linear hinge loss, whose well-classified labeled examples are not penalized regardless of the target-function value.
- LapSVM: Dual LapSVM training first optimizes l variables and then solves an n-variable linear system to obtain the coefficients defining the target function.
- LapSVM: O(n^3) dual complexity arises from matrix inversion, and a generally dense n-coefficient expansion remains even when the dual coefficients are sparse.
3. Training in the Primal
The paper develops primal optimization strategies for nonlinear LapSVMs, replacing the original dual two-step structure with a compact formulation over the full variable set. Newton’s method and preconditioned conjugate gradient are analyzed, with PCG offering efficient approximate optimization while intrinsic regularization complicates Newton’s advantages and convergence control.
- Primal formulation: Primal LapSVM optimization provides a single-step formulation over the whole variable set instead of the original dual two-step approach.The primal formulation directly manipulates the α coefficients without passing through dual β variables.
- Objective and derivatives: The primal problem uses a squared hinge loss for labeled examples, making the objective continuous and differentiable in f and α.The generalized Hessian handles the hinge breakpoint, with the loss contribution applying to error vectors only.
- Newton’s method: Newton’s method has the same complexity as the original dual LapSVM solution, retaining mainly the benefits of a compact formulation without the two-step procedure.The intrinsic norm makes the Hessian full, so LapSVM does not retain the useful block inversion available for standard SVMs.
- Preconditioned conjugate gradient: PCG updates α through Kα products with O(n^2) complexity, while sparse kernel structure can reduce complexity to O(nnz).The method avoids explicitly computing the LK product and instead uses matrix-vector products, exploiting sparsity in L.
- Convergence and stopping: A near-optimal solution can often be obtained in far fewer than the theoretical O(n) PCG steps, but convergence depends on conditioning and kernel bandwidth choices.A Gaussian bandwidth producing a kernel matrix close to identity can accelerate convergence while yielding insufficient classifier accuracy.
4. Approximating the Optimal Solution
The paper uses PCG to obtain useful approximate LapSVM solutions and proposes prediction-based stopping rules because standard gradient criteria may continue after classification has stabilized. On the two-moons example, four iterations already achieve perfect classification with a boundary near the Newton optimum.
- Approximating the Optimal Solution: Fixing stopping thresholds and maximum iterations in advance can stop too early or waste iterations without improving classification accuracy.The appropriate trade-off depends on the problem and on the shape of the objective around its optimum.
- Approximating the Optimal Solution: Four PCG iterations achieve perfect classification on the two-moons dataset with a separating boundary near the Newton-computed optimum.The iterations show label diffusion along the manifold before the solution reaches its final optimum.
- Approximating the Optimal Solution: Standard stopping criteria may misjudge progress because objective values can stabilize later than classifier quality.On the two-moons example, the objective becomes more stable after about 16 iterations, although classification had already improved substantially.
- Early Stopping Conditions: The proposed stopping rules monitor prediction stability on unlabeled data, validation error, or both, rather than relying only on optimization quantities.Predictions are compared every θ iterations within tolerance η; validation error need not decrease monotonically.
- Early Stopping Conditions: The stability and validation checks add limited computation because kernel products are already required for PCG iterations.Unlabeled predictions cost O(u), while validation evaluation costs O(|V| · n), described as negligible relative to a PCG iteration.
5. Laplacian Regularized Least Squares
LapRLSC provides a closely related least-squares formulation whose linear system can be solved directly or with the proposed PCG and early-stopping machinery. The paper reports similar classification performance among LapRLSC, LapSVM, and primal LapSVM.
- Laplacian Regularized Least Squares: LapRLSC penalizes wrongly classified examples with squared loss and obtains its coefficients and bias by solving a linear system.Its labeled-example indicator matrix IL has ones for labeled points and zeros for unlabeled points.
- Laplacian Regularized Least Squares: LapRLSC fixes the error-vector set to the labeled examples because it interpolates their targets to avoid a penalty.If all labeled examples remain in the LapSVM error set during primal training, the two solutions coincide.
- Laplacian Regularized Least Squares: LapRLSC can be solved by matrix inversion or by directly applying the proposed PCG and early-stopping conditions.Its line search can be computed in closed form because the gradient and Hessian no longer depend on the error set.
- Laplacian Regularized Least Squares: LapRLSC, LapSVM, and primal LapSVM achieve similar classification performances in the cited studies and experiments.The LapSVM formulation additionally separates regularization effects from the loss gradient on correctly classified points.
6. Experimental results
Experiments across eight datasets show that early-stopped PCG trains primal LapSVMs substantially faster while usually retaining accuracy comparable to Newton’s method. The experiments also examine dataset effects, validation strategies, convergence behavior, and limitations of generic stopping criteria.
- Experimental protocol: Eight datasets were evaluated using repeated data splits, supervised and semi-supervised baselines, and comparisons among dual, Newton, and PCG-trained LapSVMs.Results were averaged over 12 splits when four-fold cross-validation was used; MNIST3VS8 and FACEMIT used their predefined splits.
- Training speed: Early-stopped PCG noticeably reduces LapSVM training time on all datasets, dropping MNIST3VS8 from roughly half an hour to two minutes.On PCMAC, training time falls from 15 seconds to 2 seconds; memory requirements are also reduced.
- Classification accuracy: Semi-supervised methods substantially improve over supervised classifiers, while primal LapSVM and LapRLSC achieve closely matched error rates.The comparison uses primal LapSVM solved optimally with Newton’s method, dual LapSVM, and LapRLSC.
- Convergence and early stopping: The accuracy of early-stopped PCG generally matches Newton’s solution after far fewer than n iterations, with only COIL20 showing a less-close match.The stopping conditions are based on classifier behavior and can produce comparable accuracy without completing optimization.
- Limitations: Stopping criteria based on gradient norms are strongly problem-dependent and can become unstable when the active set changes, complicating generic threshold selection.The issue is reported especially for PCMAC and USPST(B), while polynomial-kernel structure also affects gradient behavior in MNIST.
- Parameter selection: Validation can select larger γA or γI values when PCG convergence is enhanced, while PCG with the proposed heuristics still supports reliable and fast cross-validation in most datasets.The reported parameter changes occur in USPST(B), COIL20(B), and MNIST3VS8.
7. Conclusions and future work
The primal LapSVM strategies achieve fast training through PCG and early stopping, while retaining classification performance comparable to optimal Newton solutions. The approach also reduces memory demands and supports future extensions for larger datasets.
- Conclusions: O(n^3) to O(n^2) reduces the computational cost of solving the primal LapSVM problem.The reduction applies when n counts both labeled and unlabeled training points.
- Conclusions: Early-stopped PCG substantially reduces training time while producing classification errors comparable to Newton’s method.The experiments compare average training times, PCG iterations, line-search iterations, and classification error rates.
- Experimental evaluation: The evaluation uses LapSVMs trained by Newton’s method and PCG, with unlabeled data used for training and labeled validation and test sets for evaluation.Results on the labeled training set are omitted because all algorithms correctly classify the few labeled training points.
- Future work: The method avoids storing the Hessian matrix and its inverse, with training times especially reduced as the amount of training data increases.The authors identify the approach as a starting point for greedy incremental classifiers and sparser kernel expansions.
Appendix A.
The appendix documents parameter-selection and comparison procedures for primal LapSVM experiments. It reports that PCG-selected parameters are usually similar to Newton-selected values, while appropriate tuning improves convergence speed and accuracy.
- Appendix A.: The appendix collects parameters selected by the experimental protocol and refers to the cross-validation procedure described in Section 6.Tables 8 and 9 provide the selected parameters for reproducibility.
- Appendix A.: PCG-selected parameter values remain substantially similar to Newton-selected values on most datasets, supporting fast cross-validation with PCG and early stopping.USPST(B), COIL20(B), and MNIST3VS8 instead select larger γA or γI values with PCG.
- Appendix A.: Appropriate parameter selection improves both PCG convergence speed and classification accuracy.The comparison uses training times and error rates for PCG with parameters tuned by Newton’s method.