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, a 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 non-linear 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.
翻译:支持矢量机(SVM)是一个特别强大和灵活且受监督的学习模型,用于分析分类和回归数据,这种模型通常的算法复杂度与数据空间和数据点数的维度是多元的。为了应对大数据挑战,提出了量子SVM算法,据称该算法可以达到最小正方形SVM(LS-SVM)的指数加速率。在这里,在SVM算法的启发下,我们为LS-SVM提供了量子激发的经典算法。在我们的方法中,提出了一种改进的快速取样技术,即间接取样,用于对内核矩阵进行取样和分类。我们首先用线性内核来考虑LS-SVM,然后讨论我们对非线性内核的方法的概括性。理论分析表明,我们的算法可以在数据空间的维度和低级、低质号和高维度数据矩阵的数据点数上任意成功地进行分类。