文章汉化系列目录

---

---

摘要

 这篇文章介绍了张量分解在分析多维数据结构中的有效性。然而，大多数这些方法需要一个关键参数：期望的分量数量。在CANDECOMP/PARAFAC分解（CPD）中，理想的分量数量被称为规范秩，它对分解结果的质量有着重要影响。现有方法通过启发式方法或贝叶斯方法来估计这一数值，这些方法通过反复计算CPD来完成估计，导致计算开销非常大。在这项工作中，我们提出了FRAPPE，这是第一个不需要计算CPD就能估计张量规范秩的方法。该方法基于两个关键思想。首先，生成具有已知秩的合成数据比计算CPD更加廉价。其次，我们通过生成与给定输入张量在大小和稀疏性方面匹配的合成数据，可以显著提高模型的泛化能力和速度。然后，我们可以在经过设计的合成张量集上训练一个专门的单次回归模型，并使用该模型估计张量的规范秩——这一过程完全不需要计算昂贵的CPD。FRAPPE比表现最好的基线方法快24倍以上，并且在合成数据集上，MAPE（平均绝对百分比误差）提高了10%。在真实世界的数据集上，它的表现与基线方法相当，甚至更好。
关键词：秩估计 · 张量分解 · 自监督 · CANDECOMP/PARAFAC分解

1 引言

 张量广泛应用于计算机科学领域，并可用于建模各种数据集。张量分解是可以应用于张量的常见方法之一。这些方法的性能通常依赖于一个关键参数——分解中的分量数量，也就是分解的秩。如果我们的分解秩过低，可能无法捕捉到关键信息；但如果秩过高，可能会捕捉到过多的噪声。在流行的CANDECOMP/PARAFAC分解（CPD）（Harshman 1970）中，分解秩的理想值被称为规范秩。然而，找到这个值是一个具有挑战性的任务。一个类似的问题是，找到张量的确切秩（即表示张量所需的最小CPD分量数），已知在有理数集合上这个问题是NP-hard（Håstad 1990；Hillar和Lim 2013）。
 因此，已经提出了各种基于启发式的方法来解决这个问题。Bro和Kiers（2003）提出的一种方法使用核心一致性诊断（CORCONDIA）来评估PARAFAC模型的“适宜性”。AutoTen（Papalexakis 2016）使用CORCONDIA自动选择合适的分量数量。归一化奇异值分解（NSVD）（Tsitsikas和Papalexakis 2020）也试图为张量的秩提供一个启发式方法，但它并非完全自动化，目前仍然需要人工监督。Fernandes等人（2020）提出了NORMO，它计算张量在不同秩下的CPD，查看各个分量之间的平均相关性，并选择没有冗余的最大分量数量。
 另一类方法是基于贝叶斯方法来解决这个问题。Zhao等人（2014）尝试通过贝叶斯推断来自动确定分解的秩。Mørup和Hansen（2009）使用贝叶斯框架与自动相关性确定（ARD）来估计Tucker分解的秩。由于CPD可以被形式化为受限的Tucker分解（Tucker 1966），因此这种方法可以很容易地适应。Zhou等人（2019）计算CPD，并在其分量上使用卷积神经网络（CNN），试图确定张量的规范秩。然而，他们主要集中于图像领域，并在该领域内评估他们的方法。
 这些方法的一个共同点是，它们都需要在所有候选秩上反复计算CPD。这在计算上非常昂贵，对于大型张量来说是不可行的，因此我们希望避免这个步骤。然而，这样做带来了几个挑战：(a) 由于具有已知规范秩的张量稀缺（通常只能通过人工检查来确定），因此很难直接训练一个监督式的机器学习模型；(b) 很难开发一个能够处理来自不同领域和不同大小的张量的模型。
 为了解决(a)问题，我们提议使用合成张量，这些张量的规范秩是已知的。为了解决(b)问题，我们提议使用从每个张量中提取的大小无关的特征。然而，我们发现使用这些数据训练的监督回归模型（见第4.2节）在实际张量上泛化效果较差。为了克服这一局限性，我们提出了FRAPPE：一种完全自监督的模型，它使用专门为给定输入张量量身定制的合成数据。FRAPPE在合成数据上优于现有基线，并且在实际数据上与最佳基线表现相当。它的速度也比表现最好的基线（NORMO）快约24倍（∼24×）。
 我们在三类张量上评估了这两种模型的性能：合成张量、在现有文献中广泛研究过的实际张量（用于确定其秩），以及卷积神经网络的权重张量（用于找到理想的CPD秩，以在保持良好分类准确度的同时压缩权重）。最后，我们还使用这些模型分析哪些特征是张量秩的最佳和最差预测因子。

 我们的贡献包括以下几点：

• 新颖方法：我们提出了FRAPPE——第一个不需要计算CPD就能估计通用张量规范秩的方法。
• 速度：我们展示了FRAPPE在评估时间上比表现最好的基线方法提高了约24倍，比最快的基线方法快约1.6倍。
• 广泛评估：我们在合成生成的张量、已知秩的实际张量和卷积神经网络的权重张量上评估了我们的算法和基线方法。我们展示了FRAPPE在合成数据集上比最好的基线方法提高了约10%的MAPE，并且在实际数据集上表现与基线方法相当或更好。
• 可解释性：我们检查了每个手工挑选特征的重要性，以了解哪些特征对分类结果贡献最大（见图4）。
• 可复现性：我们提供了我们的Python代码，用户可以在线访问：https://github.com/willshiao/frappe。我们还提供了复现基线结果的代码。

2 背景

 在这里，我们提供了本工作的符号和背景概述。我们将集合、张量、矩阵、向量和标量分别表示为 $\mathcal{X}$、$\mathcal{X}$、$\mathbf{X}$、$\mathbf{x}$ 和 $x$。设 $\mathcal{T}(i,j,k)$ 表示三阶张量 $\mathcal{T}$ 在第 $i$、$j$、$k$ 个位置的值，其中分别对应第1、2、3个模式。设 ($:$) 表示在张量索引中给定模式下的所有可能索引（例如，$\mathcal{T}=\mathcal{T}(:,:,:)$ 表示三阶张量 $\mathcal{T}$）。我们将 $\mathcal{T}$ 的 Frobenius 范数表示为 ${||\mathcal{T}||}_F$，其定义如下，适用于大小为 $I\times J\times K$ 的三阶张量：

$${||\mathcal{T}||}_F=\sqrt{\sum _{i=1}^I\sum _{j=1}^J\sum _{k=1}^K{\mathcal{T}}_{i,j,k}^2}\text{\hspace{1em}(1)}$$

我们还定义了几个函数。设 $Zeros(T)$ 返回张量 $T$ 中零值的数量，$Rand(i,j)$ 返回一个大小为 $i\times j$ 的随机矩阵。最后，$\mathcal{T}\sim {\mathcal{N}}_{i\times j\times k}(\mu ,\sigma )$ 表示从均值为 $\mu$、标准差为 $\sigma$ 的正态分布中采样一个大小为 $i\times j\times k$ 的张量。$\circ$ 表示张量的外积。

2.1 CANDECOMP/PARAFAC

其中一种最常见的张量分解方法是典型多项式或 CANDECOMP/PARAFAC 分解（CPD）（Harshman 等人，1970；Carroll 和 Chang，1970）。CPD 将张量 $\mathcal{T}$ 分解为 $R$ 个向量外积的和。形式上，对于一个三阶张量，分解为：

$$\mathcal{T}\approx \sum _{r=1}^R{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r\text{\hspace{1em}(2)}$$

然后，我们可以尝试通过迭代最小化误差的 Frobenius 范数：$\Vert T-{\sum }_{r=1}^R{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r{\Vert }_F$。一种常用的方法是使用交替最小二乘法（ALS）。按照惯例，我们将因子表示为矩阵$\mathbf{A},\mathbf{B},\mathbf{C}$，其中包含相应的向量按水平方向堆叠。例如，$\mathbf{A}$的第 i 列将是向量 ${\mathbf{a}}_i$。该方法的关键组成部分是 R——即分解的秩。如上所述，选择一个合适的 R 值是非常困难的。R 的理想值是张量 $\mathcal{T}$的典型秩，估计该值是本研究的重点。

3 问题定义

我们解决的是预测张量典型秩的问题。正式地，问题可以表述如下：

---

问题定义
 给定一个张量 $X=L+N$，其中 $L$ 是低秩张量，$N$ 是高秩噪声张量，找出 $X$ 的典型秩 $R$，使得我们最小化以下误差的 Frobenius 范数：

$$\Vert L-\sum _{r=1}^R{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r{\Vert }_F$$

其中 $A$、$B$、$C$ 是张量 $X$ 的 CPD 分解因子。

---

需要注意的是，$R$ 与张量的精确秩不同（精确秩是表示 $X$ 所需的最小组件数），而精确秩不在本研究的范围内。

 我们的另一个次要目标是识别在预测张量秩时重要的特征，这有助于我们在未来开发/改进秩预测方法。我们将此任务定义为：

子问题：可解释性
给定一个张量 $X$ 和预测的秩 $\hat{R}$，计算 $X$ 中不同属性对回归结果的贡献重要性分数 $t$。

2、

3、

五、

1、

2、

3、

六、

1、

2、

3、

七、

1、

2、

3、

八、

1、

2、

3、