量子支持矩阵机QSMM（二）

最原始的SVM是在1963年提出的，而SMM则是在2015年的机器学习大会上提出，时间相隔很久，也许是现今对应用的需求日益增加的原因。而在大数据背景下，样本数量之大，样本维度之高对计算机的处理能力都带来了重大挑战，当然也为量子算法的应用带来了新的机遇。量子算法在一些算法上的显著加速效果，也让小编认为有可能在SMM算法效率提升上能够有所作为。那我们来看一下，量子算法能够加速的究竟是什么？

如图1所示，SMM的训练过程采用了交替方向乘子法（alternating direction method of multipliers, ADMM）进行求解，其中包含了两个核心的求解步骤，分别涉及了二次规划问题和奇异值阈值的求解过程。这些问题能够在多项式的时间复杂度内解决，其中为n训练样本的数量，是pq特征空间的维度。

在大数据的背景下，随着训练样本数量和特征空间的增加，SMM的训练过程耗时较长。量子算法则有望加速SMM的学习过程中这两个核心步骤，在特定条件下，达到经典算法的指数加速。

如图2所示，SMM可以分为学习和分类两个过程。分类算法可以通过量子的swap-test算法完成，我们重点关注SMM学习过程。

图2 QSMM设计思路

针对SMM学习过程中的两个核心步骤，首先，引入最小二乘技术来对二次规划问题进行改写，将其转换为线性规划问题，此时可以通过量子求解线性方程的HHL算法对其进行求解，该方法在输入矩阵满足特定要求时能够达到一个指数级的加速。其次，采用量子奇异值阈值QSVT算法更新ADMM的第二个过程，同样能够实现相比经典算法的指数级加速效果。

针对SMM学习过程中的两个核心步骤，这里首先看第一步的转换。这一步的转换依旧是经典的转换，并未涉及量子算法，但它是应用量子算法的关键。因为量子算法更擅长求解线性问题，因此这里采用了最小二乘技术将原始的二次规划问题转换成了线性规划问题，如图3所示。

图3 最小二乘SMM

这一步是借鉴文献[3]的思想，在经典的SVM中便是采用了该方法实现的转换，以便后续应用量子算法。但不同的是，SMM的转换并没有SVM的简单。

转换的思想是采用平方损失函数代替了原始的合页损失函数，如图3中红色部分所示，图中$e^i$满足：

$y_i[tr(W^TX_i)+b]=1-e_i$

与最小二乘SVM不同，图3中的平方损失函数还涉及了一个参数μ。该函数的作用见图4。图4中蓝色的虚线表示原始目标函数中的合页损失$l^{hinge}$，红色的实线表示引入的平方损失$l^{square}$。从图中可以看出，引入新的参数μ并进行适当调节，可以使$l^{square}$为$l^{hinge}$的严格上界，从而用该函数作为原始合页函数的代理函数。具体证明可参考文献[2]。

关于该问题的求解，非常感谢王冬童鞋。

图4 SMM中的损失函数

通过转换，原始问题可以变更为求解线性方程的问题，如图5所示。

图5 LS for SMM

【结束语】这个算法是小编设计的第一个量子算法，经过一年多的研究有幸发表在Physical Review A上[2]。有关这篇论文的写作及投稿心得可以参见往期文章第一篇小论文的发表心得。希望对大家能有所帮助～

下一期将继续介绍QSMM算法。

参考文献：

[1] Luo L, Xie Y, Zhang Z, et al. Support matrix machines[C]// International Conference on International Conference on Machine Learning. JMLR.org, 2015:938-947.

[2] Bojia Duan, Jiabin Yuan, Ying Liu and Dan Li. Quantum algorithm for support matrix machines. Phys. Rev. A. 96, 032301 (2017).

[3] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum Support Vector Machine for Big Data Classification, Physical Review Letters, 113, 130503 (2014).

注：作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆

本文原创，首发在《量子机器学习》微信公众号，欢迎关注。