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
The Video Presentation
Link to video of presentation and powerpoint slides.
This paper describes how to make the problem of binary classiﬁcation amenable to quantum computing. A formulation is employed in which the binary classiﬁer is constructed as a thresholded linear superposition of a set of weak classiﬁers. 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 classiﬁers used. No efﬁcient solution to this problem is known. To bring it into a format that allows the applica- tion of adiabatic quantum computing (AQC), we ﬁrst 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 classiﬁers. This allows to effectively formulate the training process as a binary optimization prob- lem. Solving it with heuristic solvers such as tabu search, we ﬁnd that the resulting classiﬁer 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.
0:00 Training a Binary Classifier with the Quantum Adiabatic Algorithm
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
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
Machine learning at wikipedia
The research paper for “Training a Binary Classifier with the Quantum Adiabatic Algorithm”
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.