vlambda博客
学习文章列表

本文Unified Graph and Low-rank Tensor Learning for Multi-view Clustering近期被计算机视觉顶级会议AAAI Conference on Artificial Intelligence (AAAI 2020) 接收。

对于低秩张量分解，我们不仅要定义相关的秩，同时还要对张量的秩找到一个紧的凸松弛作为核范数。基于张量的奇异值分解所定义的张量核范数被证明是张量多秩（multi-rank）的范数的最紧的凸松弛[1]，故而我们采用了此分解定义张量的秩。我们首先介绍一些张量相关的表示和定义。

对于一个三阶张量, 我们记为张量的第i个前切面， 为沿第三个维度对此张量作快速傅里叶变换，为其块矢量化。其块循环矩阵 的定义为：

同时，我们介绍如下定义。

定义1（张量乘积t-product）. 记和分别为大小为和的两个张量，则和的张量乘积（t-product）定义为：

定义2（f-对角张量）. 如果一个张量的每一个前切面均为对角矩阵，那么这个张量被称为 f-对角（f-diagonal）张量。

定义3（单位张量）. 对于单位张量（identity tensor），其第一个前切面为大小为n×n的单位矩阵，其它所有的前切面的元素值均为零。

定义4（正交张量）. 如果一个张量满足如下条件，那么它是一个正交张量（orthogonal tensor）：

定义5（张量奇异值分解）. 对于张量，其奇异值分解（t-SVD) 如下：

其中和为正交张量，为f-对角张量。

定义6（基于张量奇异值分解的张量核范数）. 对于张量，其基于张量奇异值分解的张量核范数定义为的所有前切面矩阵的奇异值之和：

其中通过对的前切面矩阵作奇异值分解计算得到。

（2）模型构建

记 为第v个视角(v=1,⋯,V)的特征矩阵，其中 为第v个视角的特征向量的维度，N为样本的个数，V为视角的个数。对于多视角聚类而言，我们需要针对每个视角构建一个邻接矩阵。尽管我们可以简单地通过高斯核函数的形式计算相似度矩阵，但是此种方法将相似度矩阵的构建与后续的优化分离开来，进而导致最终学习得到的邻接矩阵是次优的。针对此问题，我们希望相似度矩阵的构建能够与后续的多视角学习进行联合优化以计算得到最优解。故而我们考虑通过图学习的方式计算样本间的距离然后对相似度进行赋值。

通过图学习来学习样本间相似度 的基本模型为：

其中γ为平衡常数，为一个列向量，其第i个元素为，和分别为元素全为1和0的列向量。二次项约束用于避免平凡解。一般而言，如果两个样本间的距离很小，那么其对应的相似度的值将对应很大。

在实际计算中，特征维度 可能会非常高，故而在原特征空间计算欧氏距离可能并不合适。而高维数据的处理本身是一项非常难的任务，尤其是与其他任务相结合时。针对此问题，我们考虑将输入特征降维到一个低维空间中，然后计算对应的邻接矩阵。进而图学习的目标函数将被转化为：

其中 I 为单位矩阵，为视角相关的投影矩阵，M为降维后特征的维度。类似于典型相关分析，我们同样采用了正交子空间约束来学习最优的视角相关的投影矩阵。

基于视角相关的相似度矩阵，我们希望从中学习得到一个可以保留多视角中一致性和互补性信息的本质特征表示。相比于矩阵对之间的信息探究，张量的形式更有益于探究多视角之间的高阶相关性。所有我们将所有视角所对应的邻接矩阵堆叠到一起构成一个张量，然后将其旋转得到 . 张量旋转操作既可以大幅度降低计算复杂度，又有利于不同视角之间的关系探究。

考虑到不同视角的特征是从同一个样本中提取得到的，因此不同视角下的相似度矩阵 包含部分相似的信息。另一方面，类别中心的个数要远小于样本的个数。所以，邻接张量 S应该具有低秩特性。基于张量奇异值分解的张量核范数 被证明是张量multi-rank的 范数的最紧的凸松弛，所以我们采用了基于张量奇异值分解的张量核范数来约束低秩邻接张量。同时考虑到噪声的影响，我们希望学习得到一个低秩张量来逼近原始的邻接矩阵。低秩张量的学习可以归结为:

其中α为平衡常数来控制噪声项的影响，张量的 范数用来惩罚噪声项。

在以上计算过程中，相似度张量 和低秩邻接张量 的计算和优化是独立的，从而导致最终得到的邻接矩阵并不是最优的。所以我们将基于图学习的邻接矩阵构建和低秩张量的学习结合到一起，联合优化计算最优解。同样地，我们对每个相似度矩阵 施加对称约束使其为对称矩阵。进而联合图学习和低秩张量表示的多视角聚类（unified graph and low-rank tensor learning，UGLTL）的最终目标函数转变为：

（3）模型优化

针对以上公式中的问题，我们提出了一种高效的算法通过交替求解的方式进行优化。虽然以上优化问题对于变量  、 和W并不是联合凸的，但是当其他变量都固定单独优化每一个变量时优化问题是凸的。 故而我们固定其他变量，交替地对每一个变量进行优化。

优化子问题：固定张量和投影矩阵W，我们通过优化如下子问题来更新张量：

以上问题的最优解可通过如下张量阈值收缩算子计算得到：

其中，表示张量的奇异值分解，并且为一个大小为的f对角张量，其傅里叶域的对角元素为。  

优化子问题：固定张量 和投影矩阵W，我们先对没有对称约束的问题进行求解。优化的拉格朗日函数可以公式化为：

其中 和 为拉格朗日乘子，列向量≥0。 进而张量中的每一个向量的计算可以通过求解如下子问题得到闭式解：

其中 。对以上问题优化求解可得：

基于以上 , 对称约束可以通过如下公式满足：

W优化子问题 ：当相似度张量 和低秩张量 固定的时候，投影矩阵 W的优化问题可以整理为：

以上问题等价于优化如下V个子问题:

其中为第v个视角对应的拉普拉斯（Laplacian）矩阵，为对角元素为的对角矩阵。记, 则以上问题可以转化为：

以上问题可以通过特征值分解进行求解。值得注意的是，在我们计算得到最优的Y^v之后，在后续的优化中我们可以直接利用投影特征代替，故而我们不再需要直接计算投影矩阵的具体形式。

在计算得到最优的低秩张量 之后，我们采用了多视角聚类的常用方式来计算邻接矩阵： 。基于以上邻接矩阵，我们利用谱聚类算法计算最终的聚类结果。

针对算法的计算复杂度，首先沿着第三个维度对大小为N×V×N的三阶段张量进行快速傅里叶变换及其逆变换所需要的复杂度为 。在更新张量 时，我们需要对大小为N×V的每一个前切面矩阵计算奇异值分解，其对应的整体复杂度为 。故而 的优化共需要 的复杂度。而对于整个张量 的更新，共需要 的复杂度。对于子空间投影特征的优化，我们只需要计算每个视角的拉普拉斯矩阵 的 M个最小的特征值及其对应的特征向量，共耗费 。一般而言，视角的个数V要小于投影后的特征维度M。记K为迭代总次数，那么该算法的整体计算度为 ，与其他算法相比表现出高效性。

针对图像聚类任务，本文提出了一种联合图和低秩张量学习的算法。相似度矩阵的构建和多视角邻接矩阵的优化是多视角聚类中两个关键的步骤，如果两者分离则学习得到的表示将是次优的，因此联合学习是非常有必要的。针对此问题，本章提出了联合图学习和低秩张量表示的方法。将多视角特征投影至低维空间，图学习的方法基于样本间的距离学习对应的相似度，构建视角相关的邻接矩阵。基于不同视角的邻接矩阵构成的三阶张量，我们用低秩张量分解的方式学习最优的表示。以上目标组合到一起，联合优化学习最优的投影矩阵、邻接矩阵和低秩张量。在相关数据集上的实验结果表明，本章中联合优化的方式可以进一步提升多视角聚类的结果，进而验证了算法的有效性。

相关论文:

[1] Zemin Zhang, Ely Gregory, Aeron Shuchin et al. Novel methods for multilinear data completion and de-noising based on tensor-SVD. In CVPR, 2014

[2] Yuan Xie, Dacheng Tao, Wenshang Zhang et al. On Unifying Multi-view Self-Representations for Clustering by Tensor Multi-rank Minimization. International Journal of Computer Vision, 2018.

[3] Jianlong Wu, Zhouchen Lin, Hongbin Zha. Essential tensor learning for multi-view spectral clustering. IEEE Transactions on Image Processing, 2019.