PaperlayerView exact revision on arXiv

Source-linked AI summary

Support vector machines on the D-Wave quantum annealer

Dennis Willsch, Madita Willsch, Hans De Raedt, Kristel Michielsen

arXiv:1906.06283v3cs.LGquant-phstat.ML

TL;DR

The paper asks whether kernel-based SVMs can be trained effectively on a D-Wave quantum annealer and whether their solutions generalize better than classical SVM optima. It formulates SVM training as a QUBO and evaluates quantum-derived classifier ensembles on synthetic and biological data, finding frequent advantages, especially with limited data and subset-combination training.

  • Problem

    The paper investigates whether quantum-annealing SVM solutions can improve test-data generalization over the single classical SVM optimum, particularly when training data are limited.

  • Method

    The authors formulate kernel-based SVM training as a QUBO for a D-Wave 2000Q and evaluate ensembles of returned classifiers on synthetic and biological datasets.

  • Results

    The quantum-annealer ensemble often surpasses the classical SVM on AUROC, AUPRC, and accuracy, while combining classifiers trained on data subsets almost always surpasses the classical SVM.

  • Takeaways & Limitations

    Quantum annealing’s distribution of close-to-optimal classifiers can provide stronger generalization than a single classical optimum, including when larger datasets are handled through subset combinations.

Abstract

from arXiv · show

Kernel-based support vector machines (SVMs) are supervised machine learning algorithms for classification and regression problems. We introduce a method to train SVMs on a D-Wave 2000Q quantum annealer and study its performance in comparison to SVMs trained on conventional computers. The method is applied to both synthetic data and real data obtained from biology experiments. We find that the quantum annealer produces an ensemble of different solutions that often generalizes better to unseen data than the single global minimum of an SVM trained on a conventional computer, especially in cases where only limited training data is available. For cases with more training data than currently fits on the quantum annealer, we show that a combination of classifiers for subsets of the data almost always produces stronger joint classifiers than the conventional SVM for the same parameters.

I. INTRODUCTION

The paper formulates kernel-based SVM training for a D-Wave quantum annealer and compares it with classical SVMs on synthetic and biological data. Its central premise is that ensembles of close-to-optimal quantum solutions may generalize better than a classical global optimum.

  • I. INTRODUCTION: The method replaces a previously studied linear classifier with the nonlinear kernel-based SVM approach.The paper applies the resulting method to both synthetic data and real biology experiments.
  • I. INTRODUCTION: Quantum annealers return diverse close-to-optimal solutions, motivating ensembles that may outperform the classical SVM’s single training optimum on test data.The classical SVM reaches the global optimum for the training set, but that optimum need not generalize best.
  • I. INTRODUCTION: The study introduces a QUBO formulation for training kernel-based SVMs on a D-Wave 2000Q quantum annealer.The formulation is designed for quantum annealing, which requires quadratic unconstrained binary optimization.

II. SVMS ON A QUANTUM ANNEALER

This section introduces classical SVMs, the quantum-annealing formulation, and the metrics used to evaluate both approaches.

  • II. SVMS ON A QUANTUM ANNEALER: The paper first reviews classical SVMs, then introduces the quantum-annealing SVM, and finally defines evaluation methods for later applications.The section prepares the comparison between the two SVM formulations.

A. The classical SVM

A classical SVM learns a binary decision boundary through kernelized quadratic optimization. Kernel functions enable nonlinear boundaries, while regularization and kernel parameters control the resulting classifier.

  • A. The classical SVM: An SVM is a supervised-learning algorithm that classifies or regresses data using learned model parameters.Here the paper focuses on binary labels, assigning positive or negative classes to feature vectors.
  • A. The classical SVM: Classical SVM training solves a convex quadratic program over coefficients α_n, with C controlling regularization and k defining the kernel.The resulting coefficients determine the decision boundary and its support vectors.
  • A. The classical SVM: The classical formulation has a global training optimum, but that optimum need not be optimal for generalization to unseen test data.Classical implementations used in the paper produced identical global optima of the convex optimization problem.
  • A. The classical SVM: Kernel-based SVMs can form nonlinear decision boundaries while avoiding explicit dependence on the higher-dimensional feature-space representation.The kernel trick means that only kernel values enter the problem specification.
  • A. The classical SVM: The experiments use radial-basis-function kernels for γ > 0 and explicitly include a linear kernel through γ = −1.The parameter γ is selected during calibration for Gaussian kernels, while the linear case is represented separately.

B. The quantum SVM

The quantum SVM encodes real-valued SVM coefficients as binary variables in a QUBO for optimization on the D-Wave 2000Q. Its close-to-optimal solution ensemble can outperform the classical SVM’s single global solution, while hardware limits constrain precision and problem size.

  • QUBO formulation: The QA SVM converts the SVM quadratic-program problem into a QUBO using binary encodings for each coefficient and a penalty multiplier for the equality constraint.Each coefficient uses K binary variables with base B, while ξ incorporates the constraint as a squared penalty term.
  • QUBO formulation: Each encoded coefficient can take only 2^K values, so the method trades coefficient precision for a representation that fits quantum-annealing hardware.The authors argue that sparse SVM solutions and the limited importance of coefficient scale can make small B and K sufficient.
  • Limitations: The approach remains limited by finite coefficient precision, available qubits, embedding requirements, and the fixed annealing setup used in the experiments.The authors defer advanced techniques such as reverse annealing, spin-reversal transforms, specialized schedules, and alternative embedding heuristics.
  • Hardware embedding: Large-distance pairs under a Gaussian kernel contribute negligible couplings, reducing embedding complexity and potentially enabling larger or better-solved problems.The implementation removes the smallest couplers when necessary to obtain an embedding on the DW2000Q.
  • Solution ensemble: The qSVM is parameterized by B, K, ξ, and γ, and each run yields multiple low-energy candidates rather than a single classifier.The study retains the twenty lowest-energy samples from 10,000 reads, although the cutoff is arbitrary.
  • Solution ensemble: The ensemble’s diverse close-to-optimal solutions can emphasize different training-data features and collectively generalize better than the classical global minimum.Some candidates have higher training energy than the classical solution but still solve the training classification task.

C. Using accuracy, AUROC, and AUPRC to assess the classification performance

The study evaluates classifiers on held-out data using accuracy, AUROC, and AUPRC. AUROC and AUPRC provide robust threshold-independent performance measures, while training accuracy is used to select the bias for definite predictions.

  • Evaluation procedure: Classifier performance is measured by comparing predictions on disjoint test data with true labels after training on the training subset.The evaluation uses the decision function’s sign to produce binary predictions.
  • Metric limitations: Accuracy alone can reward trivial classifiers on imbalanced binary datasets, such as an all-negative classifier when most examples are negative.Likewise, minimizing FPR alone can select an all-negative classifier with FPR = 0.
  • Robust metrics: AUROC and AUPRC are more robust than single-threshold accuracy because they evaluate performance across bias values rather than one operating point.AUROC plots TPR against FPR, while AUPRC plots Precision against Recall.
  • Bias selection: Training accuracy remains useful for choosing the bias b because AUROC and AUPRC are independent of b, especially when qSVM’s candidate bias is not optimal.The applications report accuracy, AUROC, and AUPRC together.

A. Two-dimensional synthetic data

On a 40-point synthetic dataset with inner positive and outer negative regions, the classical SVM gives the expected maximum-margin boundary, whereas qSVM produces diverse classifiers that capture different training-data features.

  • Dataset: The synthetic dataset contains 40 points arranged as an outer negative region and an inner positive region, providing a visually interpretable nonlinear classification task.Noise is drawn from a normal distribution with standard deviation 0.2.
  • Classical SVM: The classical SVM produces a boundary separating the two regions with maximum margin from the nearest support vectors.The plotted points are the same training points used to fit the classifiers, not a separate test set.
  • Visualization: Figure 1 compares the classical global optimum in panel (a) with three qSVM ensemble solutions in panels (b)–(d), using red squares, blue circles, and background decision-function distance.The comparison uses B = K = 2, ξ = 0, γ = 16, and C = 3.
  • Quantum SVM ensemble: The D-Wave annealer produces multiple alternative classifiers that all solve the training classification task while emphasizing different geometric features.The displayed samples range from a classifier resembling the global minimum to ones with narrower enclosures or sensitivity to gaps in the outer circle.

B. Application to real data

The real-data study tests qSVM and classical SVM on nine protein–DNA binding datasets encoded as 40-dimensional vectors. Each dataset uses a 90% training split and a held-out 10% test split.

  • Biological task: The application classifies whether proteins labeled Mad, Max, or Myc bind to particular DNA sequences.The task is based on biology experiments and includes nine labeled datasets.
  • Datasets: The nine datasets are Mad50, Max50, Myc50, Mad70, Max70, Myc70, Mad80, Max80, and Myc80.Mad, Max, and Myc datasets contain 1655, 1599, and 1584 data points, respectively.
  • Representation: Each DNA sequence is represented by a 40-dimensional vector with entries in {−1, +1}, and labels indicate binding or nonbinding.Binding uses t_n = +1 and nonbinding uses t_n = −1.
  • Evaluation design: The data are divided into 90% training and 10% unseen test examples, with training used for hyperparameter calibration and classifier fitting.The test split is reserved exclusively for evaluation.

1. Calibration phase: Results for a small training dataset

The calibration phase uses repeated Monte Carlo cross-validation to select qSVM hyperparameters from small training slices, then compares quantum-annealer solutions with classical SVMs. Initial tests found that qSVM can produce stronger classifiers than cSVM with the same limited data and parameters.

  • Calibration phase: Results for a small training dataset: Hyperparameters were selected through ten shuffled validation rounds using 2% of the training data for fitting and the remainder for validation.The search covered B, K, ξ, and γ, with twenty best quantum solutions evaluated per hyperparameter set.
  • Calibration phase: Results for a small training dataset: qSVM produced almost optimal ROC and PR curves on limited training data, whereas the classical global optimum lacked precision on the larger validation set.The comparison used qSVM(10, 3, 0, −1)#14 versus cSVM(111, −1).
  • Calibration phase: Results for a small training dataset: The calibration procedure generated 200 AUROC, AUPRC, and accuracy values for each hyperparameter set and dataset.These values combine twenty best qSVM solutions with ten Monte Carlo cross-validation repetitions.
  • Calibration phase: Results for a small training dataset: Selecting hyperparameters using both mean AUROC and AUPRC avoided cases where optimizing AUPRC alone yielded AUROC approximately 0.5.The authors describe AUROC ≈0.5 as the result for a random classifier.
  • Calibration phase: Results for a small training dataset: Gaussian kernels were needed for reasonable boundaries on balanced datasets, whereas linear boundaries sufficed for datasets with higher class imbalance.This trend was reported for the Mad, Max, and Myc dataset families.

2. Training and test phase: Results for a larger training dataset

For training sets too large for the DW2000Q, qSVM classifiers trained on disjoint data slices are combined and generally match or outperform cSVM across nine biology datasets.

  • Classifier construction: The combined classifier averages the twenty best annealer solutions for each 2% data slice, then averages the resulting classifiers across 50 disjoint slices.This aggregates both solution diversity within each slice and coverage across the full training dataset.
  • Subset construction: Disjoint equal-sized subsets were preferred to bagging because sampling with replacement can omit about 36.8% of training points and produced larger fluctuations.The authors attribute the preference also to SVM stability, making bagging less suitable for this setting.
  • Bias correction: Accuracy alone could suggest cSVM is better, but AUROC and AUPRC indicate that qSVM classifiers are superior, exposing a suboptimal decision bias.This discrepancy was especially apparent for Max80.
  • Bias correction: Replacing b with a training-accuracy-maximizing b* improves qSVM accuracy for linear kernels with high class imbalance, while leaving AUROC and AUPRC unchanged.The adjustment is an offline scan of one parameter and does not require retraining.
  • Overall comparison: qSVM achieved better or comparable performance than cSVM across all nine datasets on AUROC, AUPRC, and classification accuracy.The comparison used ten repetitions, with results summarized in Fig. 5 and numerical results reported in Table II.

IV. CONCLUSION

The paper implements kernel-based SVM training on a DW2000Q quantum annealer and finds that combining its diverse solutions can outperform a classical SVM, while bias selection remains an accuracy-sensitive constraint.

  • IV. CONCLUSION: The SVM training problem can be straightforwardly expressed as a QUBO with exact-zero and inherent box-constraint advantages.
  • IV. CONCLUSION: The DW2000Q produces distributions of classifiers, and their ensemble often surpasses the classical SVM on AUROC, AUPRC, and accuracy.The proposed QUBO formulation yields multiple close-to-optimal solutions rather than only the training-data global optimum.
  • IV. CONCLUSION: Combining qSVM solutions can produce a classifier different from the classical global optimum, so the classical bias formula may not suit every qSVM solution.The issue affects actual accuracy, whereas AUROC and AUPRC are described as more robust metrics.
  • IV. CONCLUSION: The bias can be adjusted offline using training-data accuracy without retraining qSVM, but test data must not guide that adjustment.
  • IV. CONCLUSION: For Myc70, the training-accuracy-optimal bias is slightly larger than the bias maximizing test accuracy.

Appendix B: Calibration and test results

The calibration and test evaluation compares qSVM and cSVM across the reported SVM metrics. qSVM is often at least as strong during calibration and almost always stronger after combining classifiers from disjoint training subsets.

  • Appendix B: Calibration and test results: After combining classifiers from 50 disjoint training subsets, qSVM almost always surpasses cSVM across all three reported metrics.
  • Appendix B: Calibration and test results: With 2% of the data used for training, qSVM often produces classifiers that are stronger than or equally strong as cSVM.
  • Appendix B: Calibration and test results: Table II reports mean AUROC, mean AUPRC, and mean classification accuracy for the calibration and test phases.
Loading 1906.06283v3…