大家有没有发现,今天介绍的这个量子支持矩阵机算法QSMM跟上一期介绍的量子支持向量机QSVM非常的相似?唯一不同的是将QSVM中的向量vector换成了矩阵matrix。这个算法同样是用于分类的。那么,在经典机器学习中,支持矩阵机和支持向量机有什么关系?在量子机器学习中,这两个算法又有哪些不同?未来几期咱们就来具体的解释下。

Preliminaries

SMM:Support Matrix Machine, 支持矩阵机;

QSMM: Quantum Support Matrix Machine, 量子支持矩阵机;

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

本期大纲

  1. SMM概述
  2. SMM分类模型
  3. ADMM for SMM

SMM概述

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

量子支持矩阵机QSMM(一)-量子客
图1 SVM & SMM

在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的应用、数学表达以及优势。

量子支持矩阵机QSMM(一)-量子客
图2 SMM概述

SMM分类模型

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

量子支持矩阵机QSMM(一)-量子客
图3 Related work

图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所示。

量子支持矩阵机QSMM(一)-量子客
图4 SMM分类模型

如图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 for SMM

作者采用了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所示。

量子支持矩阵机QSMM(一)-量子客
图5 ADMM for SMM

从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
校对:量豆豆
本文原创,首发在《量子机器学习》微信公众号,欢迎关注。
量子支持矩阵机QSMM(一)-量子客