Pages

March 12, 2009

Google Experimenting with Quantum Computers for Machine Learning

Hartmut Neven of Google is mapping important machine learning problems to D-Wave’s flavor of Adiabatic Quantum Computer.

Binary Classification is described at wikipedia

Binary classification is the task of classifying the members of a given set of objects into two groups on the basis of whether they have some property or not. Some typical binary classification tasks are:

* medical testing to determine if a patient has certain disease or not (the classification property is the disease)
* quality control in factories; i.e. deciding if a new product is good enough to be sold, or if it should be discarded (the classification property is being good enough)
* deciding whether a page or an article should be in the result set of a search or not (the classification property is the relevance of the article - typically the presence of a certain word in it)

The desired goals:
* Exponential speed-ups over classical approaches for certain typical-case NP-hard problems
* Could have large impact on fundamental machine learning problems as well

Training a Binary Classifier with the Quantum Adiabatic Algorithm Conclusions
* Global optimization competes successfully with greedy methods
* Bit-constrained learning machines often exhibit lower generalization error
* Intrinsic regularization
* Required bit precision grows only logarithmically with SN
* Training benefits from being treated as an integer program
* Good news for cell phones, sensor networks, early quantum chips
* Training problem manifestly NP-hard: motivates using AQC
* Next steps
* Experiment with 128-qubit D-Wave hardware
* Adaptive dictionaries
* Co-training of classifiers with feature sharing

Modifications to allow the application of the quantum adiabatic algorithm for Training a Binary Classifier
















Implementation details





The Video Presentation

Link to video of presentation and powerpoint slides.

This paper describes how to make the problem of binary classification amenable to quantum computing. A formulation is employed in which the binary classifier is constructed as a thresholded linear superposition of a set of weak classifiers. The weights in the superposition are optimized in a learning process that strives to min- imize the training error as well as the number of weak classifiers used. No efficient solution to this problem is known. To bring it into a format that allows the applica- tion of adiabatic quantum computing (AQC), we first show that the bit-precision with which the weights need to be represented only grows logarithmically with the ratio of the number of training examples to the number of weak classifiers. This allows to effectively formulate the training process as a binary optimization prob- lem. Solving it with heuristic solvers such as tabu search, we find that the resulting classifier outperforms a widely used state-of-the-art method, AdaBoost, on a va- riety of benchmark problems. Moreover, we discovered the interesting fact that bit-constrained learning machines often exhibit lower generalization error rates. Changing the loss function that measures the training error from 0-1 loss to least squares maps the training to quadratic unconstrained binary optimization. This corresponds to the format required by D-Wave’s implementation of AQC. Simu- lations with heuristic solvers again yield results better than those obtained with boosting approaches. Since the resulting quadratic binary program is NP-hard, additional gains can be expected from applying the actual quantum processor.

Slides
0:00 Training a Binary Classifier with the Quantum Adiabatic Algorithm
0:05 Outline
0:25 Solving hard optimization problems using adiabatic quantum computing - 1
2:30 Solving hard optimization problems using adiabatic quantum computing - 2
4:07 The adiabatic theorem
5:46 Why bother using AQC?
6:06 D-Wave’s hardware - 1
7:22 D-Wave’s hardware - 2
9:13 Training a binary classifier
10:54 Hyperplanes
11:17 Hyperplanes in N = 3
12:42 Modifications I: reduce bits to represent weights
14:01 Modifications II: quadratic loss
14:57 Implementation details: dictionaries
15:48 Implementation details: classical optimization methods
17:19 Experiments I: Synthetic data
18:00 Results for synthetic data with order 1 dictionary
19:27 Results for synthetic data with order 2 dictionary
19:41 Experiments II: Natural data
20:10 Conclusions

FURTHER READING
Machine learning at wikipedia

The research paper for "Training a Binary Classifier with the Quantum Adiabatic Algorithm"

blog comments powered by Disqus