量子那些事儿 关注
手机版

量子人工智能之量子支持向量机

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

量子人工智能之量子支持向量机

雪花又一年 2018-05-15 15:01:49 浏览275 评论0

摘要: 量子支持向量机是为数不多的能够指数加速的量子机器学习算法之一,并且已经被实验演示,是量子机器学习算法中为数不多的较为成功的例子。它使得我们能够使用仅n个比特完成对维的经典数据分类,并且时间复杂度只有是一种对于大数据集较为有效的算法。

量子支持向量机是为数不多的能够指数加速的量子机器学习算法之一,并且已经被实验演示,是量子机器学习算法中为数不多的较为成功的例子。它使得我们能够使用仅n个比特完成对2^n维的经典数据分类,并且时间复杂度只有O(\log{N})是一种对于大数据集较为有效的算法。

分类数据

在机器学习中,我们常常会遇到分类的问题,对于二维的数据集,类似于我们常常用手就能完成地,一个比较直观的想法就是在两组数据之间画一根线,线的两边分别是两个不同类型的数据。这样就完成了分类,将来有新的数据,如果它的位置在线的上边,那么就将它归为上边那一类,反之类似。


经典的支持向量机(SVM)

那么一般地一个支持向量机(SVM)是这样构建的:

对于一个训练数据集D = {(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)},y_i\in\{-1,+1\}我们将在这个数据集所在的空间中找到一个超平面,使得能够类似与上述的直线一样分割两种不同的数据。那么线性代数告诉我们,一个超平面可以这样描述

\bm{\omega}^T\bm{x}+b = 0

这里,\bm{\omega} = (\omega_1;\omega_2;\dots;\omega_d),是这个超平面的法向量。它描述了超平面的方向,b是偏移。于是在样本空间中的点到这个平面的距离就可以表示为

r = \frac{|\bm{\omega}^T \bm{x} + b|}{||\bm{\omega}||}

假如这个超平面成功地将这个数据集分开的话,我们就有当\bm{\omega}^T\bm{x}_i+b>0, \text{if } y_i = -1, \bm{\omega}^T\bm{x}_i+b<0, \text{if } y_i = +1,使得

\left\{\begin{array}{ll}     \bm{\omega}^T x_i + b\ge +1, & y_i = +1;\\     \bm{\omega}^T x_i + b\le -1, & y_i = -1;     \end{array}     \right.

显然这个等号只对离超平面最近的样本点才成立,我们称之为支持向量。我们训练的目标就是找到一个能稳定分类数据的超平面。而这个目标可以归结为一个数学优化问题

\begin{array}{lll}     \min\limits_{\bm{\omega},b} & \frac{1}{2} ||\bm{\omega}||^2 & \\     s.t. & y_i (\bm{\omega}^T\bm{x}_i+b) \le 1, & i = 1,2,\dots,m.     \end{array}

从经典到量子支持向量机(QSVM)

或者也可以用这样一个拉格朗日量来描述L(\bm{\omega},b,\bm{\alpha}) = \sum_{j=1}^M y_j\alpha_j - \frac{1}{2}\sum_{j,k=1}^{M} \alpha_j K_{jk} \alpha_k,其中核(Kernel)定义为K_{ij} = x_{i}\cdot x_{j},我们让L(\bm{\omega},b,\bm{\alpha})\bm{\omega}b的偏导数为零,就能够获得前一种形式。定义

F = \left(\begin{array}{ll}     0 & \vec{1}^T \\     \vec{1} & \bm{K}+\gamma^{-1}\bm{1}     \end{array}     \right)

那么求解法向量\vec{\alpha}和偏移b就变成了求解

\left(\begin{array}{l}     b\\     \vec{\alpha}     \end{array}     \right) = F^{-1}\left(\begin{array}{l}     0\\     \vec{y}     \end{array}     \right)

而求一个矩阵的逆是我们已经知道了的,也就是HHL算法(Harrow+Hassidim+Lloyd),这个在下一篇章介绍。

实验实现

2015年,中国科学技术大学的杜江峰老师组率先在一台NMR(核磁共振)实现的量子计算机上演示了这个算法,对MNIST手写笔记中的6和9进行了分类。

Li, Zhaokai and Liu, Xiaomei and Xu, Nanyang and Du, Jiangfeng, Experimental realization of a quantum support vector machine, PRL


原文发布时间为:2016-10-15
本文作者:罗秀哲
本文来源:创见,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注29
关注
是基于语音识别、语音合成、自然语言理解等技术,为企业在多种实际应用场景下,赋予产品“能听、会... 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云9.10会员日

阿里云9.10会员日