量子支持矩阵机QSMM（一）

SMM：Support Matrix Machine, 支持矩阵机；

QSMM： Quantum Support Matrix Machine, 量子支持矩阵机；

ADMM：alternating direction method of multipliers, 交替方向乘子法。

2015年，Luo Luo等人提出了一种名为支持矩阵机的分类算法[1]。我们先根据图1简单的了解下SMM与SVM的区别。

在SVM中（见图1左图），样本数为M，特征空间维数为N，每一个样本均可以看作是一个N维的列向量。

而在SMM中（见图1右图），样本分别为$X_1,X_2,…,X_n$，样本数为n，特征空间维数为pq，每一个样本均为一个$p\times q$的矩阵。

以上是两者在数学表达上的不同。

与SVM不同，SMM引入了矩阵作为特征空间的元素（被称为特征矩阵）。从计算复杂角度上，向量的处理会比矩阵更快速和便捷，为什么要引入矩阵作为处理单元呢？

因为在许多应用中，比如图像分类中，像二维图像像素之间会存在一定的空间关系，如果采用SVM进行分类，需要将矩阵先转换成向量的形式，这样就会丢失掉矩阵的结构信息，进一步可能会影响到分类的精度。因此，在这类原始特征空间的输入元素为矩阵的应用中，为了能够有效的保留矩阵的结构信息，作者提出了支持矩阵机的方法。

作者通过实验表示，SMM对原始数据中包含的噪声数据有更强的鲁棒性，与经典的分类方法（如B-SVM和R-GLM）相比，分类的精度也更高。具体可参见文献[1]。小编简单的复原了作者的一个小实验，该方法的效果确实更佳。

最后，图2简单的总结了下SMM的应用、数学表达以及优势。

那么作者又是如何设计SMM的分类模型呢？

图3简单介绍了在作者提出SMM算法之前的一些相关工作。采用soft margin SVM进行求解时，分类模型通常如公式(2)所示。其中绿色部分为hinge loss function，即合页损失函数；w为回归向量，b为偏移量，C为正则化参数。这里由于把样本矩阵Xi转换成了向量$\vec{(X_i^T)}$，因此丢失了矩阵的行列相关信息。

很自然的，如果希望保留原始矩阵信息，可以将向量w由矩阵W替换，即为图3中的公式(3)所示。这里的W为回归矩阵。虽然在形式上看似是矩阵，但在求解时，可以看到公式(3)与(2)等价。这里主要是因为$w = \vec{(W^T)}$，有

$$tr{(W^TX_i)}=\vec{(W^T)^T}{\vec{(X_i^T)}}=w^Tx_i$$

$$tr{(W^TX_i)}=\vec{(W^T)^T}{\vec{(W^T)}}=w^Tw$$

因此公式(3)无法解决行列相关信息丢失的问题。

为了保留相关信息，还可以考虑回归矩阵W的依赖关系。特别的，可以对W强加一个低秩限制以便利用样本Xi的内部信息。如bilinear SVM方法中假设

$$W=W_yW_x^T \qquad(W_x\in{R^{q\times d}},W_y\in{R^{p\times d}})$$

其中，$d<\min(p,q)$。如公式(4)所示。然而该问题对$W_x$和$W_y$均是非凸的。作者针对该问题提出了依次求解$W_x$和$W_y$的迭代法。

虽然W的依赖关系能够通过$rank{(W)}$显示出来，但是在求解过程中直接增加限制W秩的条件会更自然。对W进行秩的限制，一般会转换成矩阵秩最小化问题，前面也提过，它是一个NP难问题。Zhou & Li对此提出了GLM（R-GLM），即在分类模型中增加了矩阵W的奇异值函数作为惩罚项，如图3中公式(5)所示。其中J(W)是一个损失函数，P(W)是一个惩罚函数。P(W)是由W的奇异值来决定，通常设为

$$P(W)=\lambda\parallel{W}\parallel_*$$

其中，λ>0。这里之所以选择核函数||W||*，是因为它是rank(W)的最佳凸近似函数（is the best convex approximation of rank(W) over the unit ball of matrices）。

在上述研究背景下，作者提出了SMM的分类模型，如公式(6)所示。可以看到，公式(6)在公式(3)的基础上增加了蓝色部分，即包含了W奇异值信息的惩罚项。具体表示如图4所示。

如图4所示，SMM矩阵分类模型中包含了两个重要的组成部分：红色的合页损失函数，和蓝色部分的惩罚项：spectral elastic net（谱弹性网）。

作者在选取合页函数作为loss function，是因为它的特性适用于分类应用中：(1) enjoys the large margin principle

(2) embodies sparseness and robustness。

在penalty function的选择上，则是将squared Frobenius范数和核范数相结合形成。将其称为谱弹性网则是由于：

$$tr(W^TW)=\parallel W\parallel_F^2=\sum\nolimits_{i=1}^{min(p,q)}\sigma_i^2(W)$$

$$\parallel W\parallel_*=\sum\nolimits_{i=1}^{min(p,q)}\sigma_i(W)$$

上述SMM构造的一个过程非常的有趣，记录了作者的思考。因此这里小编详细的转述了。有兴趣的朋友请阅读原文[1]。

作者采用了ADMM方法对公式(6)进行求解[1]。该方法引入了矩阵S，增加了限制条件S-W=0，并将惩罚项中的W替换为了S，得到了公式(6)的等价问题：

$$argmin\qquad H(W,b)+G(S)\\s.t. \qquad S-W=0$$

其中，

$$H(W,b)=frac{1}{2}tr(W^TW)+C\sum_{i=1}^{n}{1-y_i[tr(W^TX_i)+B]}_+$$

$$G(S)=\tau\parallel S\parallel_*$$

ADMM求解公式(7)可通过拉格朗日函数求得，如图4所示。我们接下来看一下具体的算法，如图5所示。

从ADMM算法流程可以看出，其中最核心的部分是图中绿色方框圈出的两步操作。这两步操作决定了整个算法的时间复杂度，可以分别看作是求解二次规划和奇异值阈值的问题。更详细的数学推导及证明可参见原文[1]。

小编就是从上述两个问题入手，开始设计量子QSMM算法的。关于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).

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

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