Quantum-Inspired Support Vector Machine
Quantum-Inspired Support Vector Machine
复制标题
受量子启发的支持向量机
DOI：
10.1109/tnnls.2021.3084467
复制
发表时间：
2021-06-09
影响因子：
10.4
通讯作者：
Huang, He-Liang
中科院分区：
文献类型：
--
作者：
Ding, Chen;Bao, Tian-Yi;Huang, He-Liang
支持向量机（SVM）是一个特别强大且灵活的监督学习模型，可分析分类和回归的数据，其通常的算法复杂性随数据空间的维度和数据点的数量而多一级缩放。为了应对大数据挑战，提出了一种量子SVM算法，据称该算法可以实现最小二乘SVM（LS-SVM）的指数加速。在这里，受量子SVM算法的启发，我们为LS-SVM提出了一种量子启发的经典算法。在我们的方法中，提出了一种改进的快速采样技术，即间接抽样，用于对内核矩阵进行采样和分类。我们首先使用线性内核考虑LS-SVM，然后讨论我们对非线性核的概括。理论分析表明，我们的算法可以在数据空间维度的对数运行时和低等级，低条件数量和高维数据矩阵的数据点的数量中以任意成功的概率进行分类，与量子SVM的运行时间匹配。
Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM algorithm was proposed, which is claimed to achieve exponential speedup for least squares SVM (LS-SVM). Here, inspired by the quantum SVM algorithm, we present a quantum-inspired classical algorithm for LS-SVM. In our approach, an improved fast sampling technique, namely indirect sampling, is proposed for sampling the kernel matrix and classifying. We first consider the LS-SVM with a linear kernel, and then discuss the generalization of our method to nonlinear kernels. Theoretical analysis shows our algorithm can make classification with arbitrary success probability in logarithmic runtime of both the dimension of data space and the number of data points for low rank, low condition number, and high dimensional data matrix, matching the runtime of the quantum SVM.