ICML 2019 | 第四范式提出快速张量补全新方法
近日，来自第四范式的姚权铭与来自香港科技大学和"日本理化研究所"的研究者提出的“Efficient Nonconvex Regularized Tensor Completion with Structure-aware Proximal Iterations"，入选了 ICML 2019 中选论文榜单。
论文：https://arxiv.org/pdf/1807.08725.pdf
源码：https://github.com/quanmingyao/FasTer
PPT和5分钟介绍视频（英文版本）：
https://icml.cc/Conferences/2019/Schedule?showEvent=5191
全文综述
非凸正则化器已成功地应用于低阶矩阵学习。在这篇论文中，我们将此扩展到更具挑战性的低秩张量补全（Tensor completion）问题。在 Proximal Average 算法（Bauschke et al., 2008; Yu, 2013）的基础上，提出了一种有效的求解方法，避免了昂贵的张量折叠和展开。
在整个迭代过程中保持一种特殊的“稀疏加低秩”结构，这对于快速计算单个近端步骤至关重要。我们还结合了自适应动量来进一步加速经验收敛。在平滑度和 Kurdyka-Lojasiweicz 条件下，给出了临界点的收敛结果。
对多个合成数据集和真实数据集的实验结果表明，该算法在时间和空间上都具有较高的效率，而且比现有的算法更精确。
研究方向
什么是张量补全
张量可以看作是高阶矩阵，可以用来描述数据中的多行关系。它们广泛用于计算机视觉、推荐系统和信号处理等领域。其中许多是三阶张量，例如包括彩色图像和高光谱图像，这是本文的研究重点。
在 YouTube 中，用户可以互相跟踪，并且可以属于同一订阅频道。通过将通道视为第三维度，用户的共同订阅网络可以再次表示为三阶张量。
▲ 图1. 张量可以视为更高维度的向量和矩阵，因此也能捕捉数据中更高阶的交互性质
传统的方法（例如 ICA、PCA、SVD 和 NMF）对于维数比较高的数据，一般将数据展成二维的数据形式（矩阵）进行处理，这种处理方式使得数据的结构信息丢失（比如说图像的邻域信息丢失），而求得的解很差。而采用张量对数据进行存储，能够保留数据的结构信息。
在许多应用中，只显示出少数张量项，张量的数据细节缺失较多。例如，每个 YouTube 用户通常只与其他几个用户交互。张量补全，是利用张量中已有的数据细节来填补缺失的数据细节。在矩阵分解的相关任务中，底层分解矩阵的不同行/列通常具有相似的特征。这样的矩阵是低秩的，秩是非零奇异值之和。
我们可以利用矩阵的低秩特性，用较低秩的矩阵来近似观测到的实际矩阵，达到预测效果。核范数是指矩阵奇异值的和，广泛用作低秩矩阵完成中矩阵秩的替代物。在张量补全中，低阶假设还可以捕获不同张量维度中的相关性。然而，张量比矩阵在更加复杂。张量补全通常是从数据中提取一个低秩的结构。
▲ 图2. 张量补全的三种典型应用场景：彩色图像恢复，高光谱图像的处理和时空数据的预测
已有张量补全方法
近年来，人们提出了许多基于矩阵核范数的凸近似约束项目来解决张量补全问题，包括用于张量的 trace norm、overlapped nuclear norm (Definition 1) 和 latent nuclear norm。特别是，overlapped nuclear norm 最受欢迎，因为它可以精确计算具有更好的低秩近似值，并精确的恢复。
overlapped nuclear norm 的问题在于：
1. 它会惩罚所有的奇异值，但是，较大的奇异值通常更具信息性，实际应减少惩罚。
2. 为了求解 overlapped nuclear norm 我们需要反复折叠和展开张量，这将导致巨大的计算复杂度。
本论文中的方法
基于自适应非凸正则化器在矩阵分解中的成功应用，我们提出了一种用于张量补全的 overlapped nuclear norm 正则化器的非凸变体。同时解决 overlapped nuclear norm 的以上两点问题。
特别的，我们的贡献在于：
1. 将非凸正则项引入 overlapped nuclear norm 中；
2. 基于 proximal average 算法，我们开发了一种高效的时间和空间复杂度更好的方法。
成功的关键在于：
避免昂贵的张量折叠和展开
在迭代中保持“稀疏加低秩”结构
结合 adaptive momentum
对于第一点，我们引入以下优化目标函数：
其中：
常见的非凸正则项如下，因此如右图所示，它们能更少的去惩罚更大的特征值。
对于第二点，我们提出的算法核心思路如下（算法细节请参照论文）：
基于以上迭代，我们得出一下算法流程：
相对比标准的 Proximal Average 算法，我们改进之后的时空复杂度对比如下：
其中
在平滑度（Theorem 3.5）和 Kurdyka-Lojasiewicz 条件（Theorem 3.7）下提供临界点的收敛保证。
对比实验
我们在模拟数据和实际应用数据上对我们的方法 NORT 进行了测试。
1. 模拟实验
我们使用了三种非凸惩罚项：capped-l1，LSP 和 TNN。
我们与 PA-APG（用于解决凸 overlapped nuclear norm 最小化问题），GDPAN（直接使用 proximal avergae 算法）进行比较。我们还额外比较了一个不使用 adaptive momentum 的 NORT，标记为 sNORT。实验结果如下图 1 所示：
▲ 图3. 在模拟数据上得到的测试RMSE，CPU时间和空间需求（三项指标均越小越好）。左边是张量第三维度较小的情况，右边张量第三维度较大的情况
可以看到，PA-APG 的 RMSE 是最高的，这是由于凸约束项不如非凸约束项有效。不同的非凸惩罚项有着相似的 RMSE。对于空间需求，我们的方法 NORT 和 sNORT 是最小的，因为它们不需要在计算时构建稠密张量。而对于 CPU 时间，NORT 是最快的，sNORT 其次。这是因为 sNORT 利用了稀疏加低秩的结构，而 NORT 进一步使用了 adaptive momentum。
2. 实际应用数据
1) 彩色图像补全
彩色图像补全通常是用于老旧图片数码化后的破损修复，使得修复后的图片没有明显的失真。对于一张 RGB 图片，它有三个通道分别记录红色（R）、绿色（G）和蓝色（B）的像素值，因此构成一个三维张量。我们对三张 1000*1000*3 的彩色图片进行重建。实验效果如下图 2 所示。
▲ 图4. 彩色图像上的测试RMSE随CPU时间的变化
如图 2 所示，NORT 有着最低的 RMSE 和最快的收敛速度。
2) 卫星遥感图像处理
卫星遥感图像由于空气折射率、云层遮挡等外界因素的影响，导致图像噪声很高，因此数据张量的形式存在时，会缺失大量数据的细节。运用该技术可对此类数据更好的处理，大幅提升图像中识别的精度。
我们在三张高维卫星遥感图像上进行测试：Cabbage (1312×432×49), Scene (1312×951×49) 和 Female (592×409×148)。实验结果见图 5。
▲ 图5. 卫星遥感图像上的测试RMSE
再一次，我们可以看到，NORT比其他方法有更好的重建效果，它获得的测试 RMSE 远低于其他方法。
3) 社交网络
最后我们将多关系的链接预测问题建模成了张量补全问题。我们在 Youtube 数据集上进行了测试。它包含 15,088 个用户，并记录了 5 种用户间的交互。在这一数据集上构建的张量围度为 15088×15088×5，其中有 27,257,790 个非 0 数值。
特别的，由于部分方法没有办法处理整个 YouTube 数据集，我们随机抽取了 1000 个用户的数据作为数据集 subset 进行测试。从图 4 可以看出，NORT 预测效果最好，速度最快。
▲ 图6. YouTube上的测试RMSE随CPU时间的变化
点击以下标题查看更多往期内容：
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。
📝 来稿标准：
• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向）
• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志
📬 投稿邮箱：
• 投稿邮箱：hr@paperweekly.site
• 所有文章配图，请单独在附件中发送
• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 获取最新论文推荐
相关内容
微信扫码咨询专知VIP会员