图 书 馆
用量子绝热算法训练二值分类器Training a Binary Classifier with the Quantum Adiabatic Algorithm |
|
| 课程网址: | http://videolectures.net/opt08_neven_tabcwt/ |
| 主讲教师: | Hartmut Neven |
| 开课单位: | 谷歌公司 |
| 开课时间: | 2008-12-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 二进制分类问题; 量子计算; 格式绝热量子计算 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-09-09：cjy |
| 阅读次数: | 41 |