Quantum optimization for training support vector machines

被引:61
作者
Anguita, D [1 ]
Ridella, S [1 ]
Rivieccio, F [1 ]
Zunino, R [1 ]
机构
[1] Univ Genoa, DIBE, Dept Biophys & Elect Engn, I-16145 Genoa, Italy
关键词
quantum optimization; support vector machine; quadratic-programming; robust classification;
D O I
10.1016/S0893-6080(03)00087-X
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Refined concepts, such as Rademacher estimates of model complexity and nonlinear criteria for weighting empirical classification errors, represent recent and promising approaches to characterize the generalization ability of Support Vector Machines (SVMs). The advantages of those techniques lie in both improving the SVM representation ability and yielding tighter generalization bounds. On the other hand, they often make Quadratic-Programming algorithms no longer applicable, and SVM training cannot benefit from efficient, specialized optimization techniques. The paper considers the application of Quantum Computing to solve the problem of effective SVM training, especially in the case of digital implementations. The presented research compares the behavioral aspects of conventional and enhanced SVMs; experiments in both a synthetic and real-world problems support the theoretical analysis. At the same time, the related differences between Quadratic-Programming and Quantum-based optimization techniques are considered. (C) 2003 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码:763 / 770
页数:8
相关论文
共 13 条
[1]  
[Anonymous], LIBSVM LIB SUPPORT V
[2]  
Bartlett P. L., 2003, Journal of Machine Learning Research, V3, P463, DOI 10.1162/153244303321897690
[3]   Model selection and error estimation [J].
Bartlett, PL ;
Boucheron, S ;
Lugosi, G .
MACHINE LEARNING, 2002, 48 (1-3) :85-113
[4]  
CORTES C, 1995, MACH LEARN, V20, P273, DOI 10.1023/A:1022627411411
[5]   QUANTUM-THEORY, THE CHURCH-TURING PRINCIPLE AND THE UNIVERSAL QUANTUM COMPUTER [J].
DEUTSCH, D .
PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1985, 400 (1818) :97-117
[6]   2-BIT GATES ARE UNIVERSAL FOR QUANTUM COMPUTATION [J].
DIVINCENZO, DP .
PHYSICAL REVIEW A, 1995, 51 (02) :1015-1022
[7]   Pruning with interval arithmetic perceptron [J].
Drago, GP ;
Ridella, S .
NEUROCOMPUTING, 1998, 18 (1-3) :229-246
[8]  
Durr C., 1996, QUANTUM ALGORITHM FI
[9]  
Fletcher R., 1987, PRACTICAL METHODS OP, DOI [DOI 10.1002/9781118723203, 10.1002/9781118723203]
[10]  
Grover L. K., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC'96, P212, DOI [10.1145/237814.237866, DOI 10.1145/237814.237866]