量子人工智能之量子支持向量机-阿里云开发者社区

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

2018-05-15 1838

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

量子支持向量机是为数不多的能够指数加速的量子机器学习算法之一，并且已经被实验演示，是量子机器学习算法中为数不多的较为成功的例子。它使得我们能够使用仅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$ 的偏导数为零，就能够获得前一种形式。定义