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,然后讨论我们对非线性内核的方法的概括性。理论分析表明,我们的算法可以在数据空间的维度和低级、低质号和高维度数据矩阵的数据点数上任意成功地进行分类。

0
下载
关闭预览

相关内容

在机器学习中,支持向量机(SVM,也称为支持向量网络)是带有相关学习算法的监督学习模型,该算法分析用于分类和回归分析的数据。支持向量机(SVM)算法是一种流行的机器学习工具,可为分类和回归问题提供解决方案。给定一组训练示例,每个训练示例都标记为属于两个类别中的一个或另一个,则SVM训练算法会构建一个模型,该模型将新示例分配给一个类别或另一个类别,使其成为非概率二进制线性分类器(尽管方法存在诸如Platt缩放的问题,以便在概率分类设置中使用SVM)。SVM模型是将示例表示为空间中的点,并进行了映射,以使各个类别的示例被尽可能宽的明显间隙分开。然后,将新示例映射到相同的空间,并根据它们落入的间隙的侧面来预测属于一个类别。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
专知会员服务
159+阅读 · 2020年1月16日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
零基础学SVM—Support Vector Machine系列之一
AI研习社
7+阅读 · 2017年11月10日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
18+阅读 · 2019年1月16日
Phrase-Based & Neural Unsupervised Machine Translation
VIP会员
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
零基础学SVM—Support Vector Machine系列之一
AI研习社
7+阅读 · 2017年11月10日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Top
微信扫码咨询专知VIP会员