《FRAPPE: fast rank approximation with explainable features for tensors》中文校对版

文章汉化系列目录

FRAPPE：基于可解释特征的张量快速秩近似

摘要

 这篇文章介绍了张量分解在分析多维数据结构中的有效性。然而，大多数这些方法需要一个关键参数：期望的分量数量。在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(\mathcal{T})$ 返回张量 $\mathcal{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$ 表示张量的外积。

表1 不同张量秩估计方法的比较。所有速度都是相对于最慢基准方法的评估时间。具体评估时间见表3。†：我们没有与TRN-PD进行基准测试，因为它是为图像数据和图像去噪设计的，而这不是本工作的重点。
NORMO 在一定程度上是可解释的，因为因子之间的较高相关性表明给定秩的选择不好。然而，NORMO 并没有提供任何指示，说明原始张量中哪些属性对较高/较低的预测贡献较大。
2TRN-PD 是为图像设计的，并最初用于基于 CPD 的去噪评估。

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 \mathcal{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$。

4 提出的方法

我们首先描述从张量中提取的精心挑选的特征，以及选择每个特征的理由。接着，我们在该数据集上训练一个回归模型，并展示它存在的一些关键局限性：（a）在合成数据集上表现良好，但在真实数据上的泛化能力较差；（b）训练过程相对较为昂贵。然后，我们提出了我们的方法 FRAPPE，旨在解决这两个问题。

4.1 张量特征

给定一个张量 $\mathcal{T}\in {\mathbb{R}}^{I\times J\times K}$，我们提取112个特征（4维或更高维张量需要一些调整，具体方法如下）：

• 张量维度（特征1–3）: $I,J,K$。我们包括这些特征，以便底层模型能够根据张量的大小调整对其他参数的期望。这使得我们的模型能够对不同的输入尺寸进行泛化。

• 非零值（特征4–13）: 张量中非零值的总数，以及所有可能切片中非零值的最小值、中位数和最大值。也就是说，我们从 $T(i,:,:)$ 对于所有 $i\in [1,I]$，$T(:,j,:)$ 对于所有 $j\in [1,J]$，以及 $T(:,:,k)$ 对于所有 $k\in [1,K]$ 中提取非零值的数量。该特征的直觉是，通常情况下，张量的秩随着其稀疏性增加而增大。通过测量所有可能切片中的非零值数量，我们可以在每个维度上有效地衡量稀疏性。

• 切片的秩（#14-22）：张量所有可能切片的最小秩、中位秩和最大秩。这个特征的直觉是，如果在任何给定的两个维度上，切片的秩通常较低（意味着在奇异值分解（SVD）中需要的成分较少），那么在 CANDECOMP/PARAFAC（CPD） 分解中也可能只需要较少的成分。

• 阈值化的非零值（特征23–103）: 在归一化的张量中，所有小于或等于以下阈值的值的最小值、中位值和最大值：[0.1, 0.2, …, 0.9]，这些值来自张量的所有可能切片（我们使用最小-最大归一化）。这是对稠密张量的非零值数量（特征#4-13）的调整，旨在找出低值条目，这些条目可能是噪声的结果，并且对张量的规范秩影响较小。

• 相关性（特征104–112）: 所有可能切片对之间的最小、最大和中位相关性。该特征的直觉是，切片之间的相关性越高，通常表示在给定的轴上所需的分量越少，结果是更低的规范秩。

请注意，特征的数量是固定的，无论张量的大小如何。这使得该方法能够轻松扩展到大规模张量。接着，我们在这些特征上训练一个LightGBM（Ke et al. 2017）模型，目的是预测目标张量的秩。

4.1.1 为什么选择相关性？

可能不容易理解为什么我们选择使用不同切片之间的相关性。我们之所以选择这样做，是因为矩阵中向量对之间的成对相关性的分布是矩阵秩的一个良好指标。我们在下面从理论上证明了这一点（在某些假设下）。我们假设在张量的情况下这一点仍然成立；虽然很难正式证明，但我们也在图4中展示了该特征在我们的模型中的有效性。

命题
一个矩阵 $M$ 的秩随着其因子之间的成对平均相关性增加而减少。设 $M\in {\mathbb{R}}^{m\times n}$。为了简化起见，我们假设集合 $C$ 包含 $M$ 的所有 $n^2$ 对不重叠的列对，其他所有对的相关性为 0。

证明
首先，我们将矩阵 $M$ 的秩定义为 $k$，其中 $k$ 是满足第 $k$ 个奇异值 ${\sigma }_k>0$ 的最大值。我们假设任意两个向量 $x$ 和 $y$ 的外积 $x{y}^T$ 可以写成 $a{b}^T+N$ 的形式，其中 $N=\gamma {\sigma }_1{u}_1{v}_1^T+{\gamma }_2{\sigma }_2{u}_2{v}_2^T+\cdots +{\gamma }_k{\sigma }_k{u}_k{v}_k^T$，其中 ${\sigma }_i\to 0$ 对所有 $i$ 成立，且 $\text{Corr}(x,y)\to 1\Rightarrow \gamma \to 0$。设 $c=E[\text{Corr}(M(i),M(j))]\forall (M(i),M(j))\in C$，其中 $M(i)$ 是矩阵 $M$ 的第 $i$ 列。然后，我们可以写成 $M=a_1{b}_1^T+a_2{b}_2^T+\cdots +a_{n/2}{b}_{n/2}^T+N_1+N_2+\cdots +N_{n/2}$，其中 $N=N_1+N_2+\cdots +N_{n/2}$。根据我们上面的假设，最多有 $n/2$ 个重复成分，所以 $N$ 的最大奇异值为 $n/2\gamma c$，这仍然小于某个小的常数 $ϵ$，当 $\gamma <2/n$ 时，且对于足够大的 $c$ 成立。因此，随着我们成对平均相关性 $c$ 的增加，$M$ 的秩会减少。

4.1.2 计算复杂度

 特征 #1–13 和 #23–103 的计算非常快速，只需对张量进行一次遍历即可。特征 #14–22 和 #104–112 的计算成本显著更高，因为它们分别需要对张量的不同切片计算奇异值分解（SVD）和相关性。然而，这些操作的速度仍然远快于基准方法，因为基准方法需要重复计算整个张量的完整典型分解（CPD）。表3比较了我们方法与基准方法的速度。
 设 $n=\max (I,J,K)$。特征 #1–13 的计算时间与张量中非零值的数量成线性关系，最坏情况下为 $O(n^3)$（对于稠密张量的情况）。特征 #14–22 的计算时间为 $O((I+J+K)s)=O(ns)$，其中 $s$ 是在张量切片上执行稀疏奇异值分解（SVD）的运行时间。对于完全稠密的张量，这需要 $O((I+J+K)n^3)=O(n^4)$ 的计算时间。
 特征 #23–103 需要首先对张量进行最小-最大归一化，这可以在 $O(n^3)$ 时间内完成。同时，计算每个阈值上下的数值也需要 $O(n^3)$ 的时间。特征 #104–112 需要对 $n(n-1)/2$ 对切片进行计算，所需时间为 $O(n^2)$，最终的运行时间为 $O(n^4)$。
 总体而言，对于稠密张量，这些特征的计算最多需要 $O(n^4)$ 的时间，其中 $n$ 是张量中最大维度的大小。值得注意的是，对于稀疏张量（例如多视图图、知识库、词语共现矩阵），所需的时间将显著更少。这相比于计算一次典型分解（CPD）的运行时间，尤其是与现有方法需要重复运行的情况，已经有了显著的改进。我们在下表3中展示了运行时间的比较。

请注意，由于张量中存在负值（导致基于KL散度的AutoTen失败），我们仅在这些合成示例中使用了基于弗罗贝纽斯范数的AutoTen。这可能会导致较低的准确性，但也会减少评估时间。

4.1.3 扩展到高阶张量

虽然上述特征对于三阶张量效果良好，但对于四阶或更高阶的张量，它们需要进行一些修改。例如，秩特征是针对张量的所有切片计算的。在三阶情况下，这些切片是矩阵，但在四阶（或更高阶）情况下，这些切片是三阶（或更高阶）的子张量。矩阵的秩可以通过奇异值分解（SVD）在多项式时间内计算得到，但三维张量的秩是本文要解决的问题。由于这一问题以及图4中秩特征相对较低的重要性，我们在四维模型中省略了秩特征，发现其仍然表现相当不错。我们在第5.4节中通过对四维AlexNet权重张量的实验进行了实证验证。与现有的规范秩估计方法（Fernandes et al. 2020；Papalexakis 2016）类似，我们主要集中于三阶张量，保留详细评估供未来研究使用。

4.2 初步尝试

我们现在可以使用第4.1节中定义的特征训练一个回归模型。为此，我们首先生成一个合成数据集，其中张量的秩是已知的（见第5.2节）。然后，我们在这个合成数据集上训练一个LightGBM（Ke et al. 2017）模型，并在第5节中的每个评估数据集上对模型进行评估。然而，我们发现LightGBM模型无法很好地推广到合成数据集之外，并且在所有真实世界的数据集上都错误地预测了秩（如第5.3节所述）。这很可能是因为真实世界的张量来自不同的领域。
 这种方法的另一个局限性是，我们必须在一个非常大的数据集上训练模型，以确保能够考虑到不同的秩、稀疏性和噪声水平。虽然这使得预测新张量的秩非常快速，但它大大增加了训练回归模型所需的时间。为了解决这个问题，我们提出了FRAPPE。

FRAPPE 的图示。我们首先根据输入张量的大小和稀疏性生成合成张量，提取特征，训练模型，并使用该模型预测原始输入张量的秩。

4.3 FRAPPE

与第4.2节中描述的方法相比，FRAPPE需要解决的主要问题是朴素回归模型的泛化能力差。这个泛化能力差的问题根本上是由训练数据和输入张量之间的分布差异引起的。我们可以通过确保合成训练数据能够紧密模仿给定的输入张量来解决这个问题。具体来说，我们在生成合成数据集时，尝试匹配输入张量的大小和稀疏性。然后，我们可以为每个待处理的张量训练一个专门的LightGBM模型。这个专门的模型只会在输入张量上执行一次评估，之后即被丢弃。
 生成旨在模仿输入张量的训练数据还解决了长时间训练的问题，因为所需的数据量较少即可实现相同的结果。这大大缩短了训练时间，使我们能够为每个输入张量训练一个一次性的回归模型，同时保持比其他基准模型更快的速度优势。需要注意的是，“训练”发生在评估时，并且不需要外部的训练步骤。FRAPPE在算法1中进行了正式的详细描述。

5 实验评估

评估我们方法的有效性是困难的，因为已知秩的张量非常少，因此我们不能仅依赖于真实世界的数据。因此，我们选择在三种不同类型的数据上评估我们的方法：

1. 合成张量：预测我们生成的具有已知秩的张量的秩（见第5.2节）。
2. 真实世界张量：预测已经被研究过并且具有已知秩的真实世界张量的秩（见第5.3节）。
3. 卷积神经网络（CNN）权重：压缩AlexNet（Krizhevsky et al. 2012）模型最后一层的四维权重（见第5.4节）。

我们将我们的方法与当前的其他最先进方法进行了性能和运行时间的比较。所有的时间实验都在一个具有176个CPU核心和352GB内存的Google Cloud Platform c3-highcpu-176实例上进行。

5.1 基准方法

我们将FRAPPE与三种基准方法进行了比较：NORMO（Fernandes et al. 2020）、AutoTen（Papalexakis 2016）和ARD-Tucker（Mørup 和 Hansen 2009）。这些方法需要考虑一个最大秩。由于这个最大秩会大大影响算法的运行时间，因此我们为这两种算法使用了张量真实秩的两倍。理论上，这样可以限制最大误差，但如果设置得更高，会大大增加基准方法的运行时间和计算成本。我们也为FRAPPE使用了相同的这个限制。
 我们不得不对AutoTen进行一些修改，仅使用基于弗罗贝尼乌斯范数的评估，因为我们的数据集中包含负值，这导致基于KL散度的评估失败。这稍微降低了AutoTen的准确性，但大大提高了其运行时间。我们还需要修改NORMO和AutoTen，以支持4D张量，从而能够在我们的CNN权重张量上运行。我们选择使用NORMO推荐的δ = 0.7值。

5.2 合成数据集

为了生成合成数据集，我们首先通过从均匀随机分布中抽取值来生成CPD因子矩阵A、B、C。为了确保生成一个多样化的数据集，我们通过从以下每个子集（每个子集对应于一个常见的真实世界张量）中生成一定比例的张量来实现这一点：

1. 稀疏张量带稀疏噪声：在因子中引入稀疏性，并将高斯噪声添加到张量中的非零元素的张量。示例：加权时间演化图。
2. 稀疏张量带密集噪声：在因子中引入稀疏性，并将高斯噪声添加到张量中的所有元素的张量。示例：传感器读数的时间演化网格。
3. 密集张量：具有完全密集的张量，并添加密集噪声的张量。示例：荧光计读数的张量。

这些情况代表了真实世界数据集中可以找到的不同类型的张量。在每种情况下，我们添加了2%–10%的噪声，并通过将噪声张量的范数与生成的张量的范数进行比较来调整噪声的量。更正式地说，设α为噪声比率，N为噪声张量，G为生成的张量：

$$\mathcal{G}=\mathcal{G}+\alpha \frac{\Vert \mathcal{G}{\Vert }_F}{\Vert \mathcal{N}{\Vert }_F}\mathcal{N}$$

这种噪声添加过程类似于Tensor Toolbox（Bader和Kolda 2007）中的create_problem函数中的噪声添加过程。

5.3 真实世界数据集

我们在已知秩的数据集上评估了我们的方法和基线方法的有效性。这些数据集包括三个荧光数据集：amino_acid（Bro 1997）、dorrit（Riu 和 Bro 2003）和sugar（Bro 1999）。这些数据集包含自然的三线性数据，并且已知每个化学物质对应于CPD中的一个成分。我们还在reality_mining（Eagle 和（Sandy）Pentland 2006）和enron（Priebe 等人 2005）数据集上评估了我们的方法。这些张量的标准秩不太明确，因为我们必须依赖现有文献，这些文献已经手动分析了数据并确定了大致的秩。
 从表2显示的结果可以看出，FRAPPE能够准确地估计荧光数据集的秩。ARD也能正确估计这些数据集的秩。NORMO和AutoTen表现相当不错，但略有偏差。只有AutoTen能够成功估计enron数据集的秩，但FRAPPE也非常接近。遗憾的是，由于很少有已知秩的真实世界张量，我们在这次评估中可用的数据量有限。尽管由于数据集数量有限，很难得出任何具体结论，但我们可以看到，FRAPPE的表现与其他现有的秩估计方法相当，甚至略有优势。

表 2 实际数据集上秩估计方法的性能。第一列是数据集的已知秩，正确的估计值加粗显示。我们可以看到，FRAPPE 和 AutoTen 通常表现最佳。
加粗的值表示最佳性能。
该数据集中的社区数量在 Papalexakis 等人（2013）的研究中进行了探讨，并估计为 6。社区数量大致对应于张量的规范秩，但与荧光数据集不同，这并不是一个保证。

5.4 基于CNN的评估

 我们评估了我们的网络在分解卷积神经网络（CNN）中的4D权重张量时选择正确秩的表现。我们特别关注的是训练在CIFAR-10（Krizhevsky等，2009）图像数据集上的AlexNet（Krizhevsky等，2012）模型的最后一层（R256×256×3×3）。
 该任务的目标是选择正确的组件数量(秩的值)，以便尽可能压缩权重并保持尽可能高的准确度。这个秩将是秩-准确度曲线的“膝部”。图2显示了该曲线以及通过各种秩估计方法选定的值。

图2 AlexNet性能图： 该图展示了AlexNet模型的最终CNN层在不同秩（rank）下的压缩性能表现。图中还展示了FRAPPE和基准方法所预测的秩值。具体来说，NORMO预测的秩值非常低，而AutoTen则预测了一个非常高的值。相比之下，FRAPPE和FRAPPE预测的秩值似乎是合理的。需要注意的是，ARD-Tucker由于没有及时终止，因此未被包括在图中。

NORMO预测权重张量的秩为3，这是一个较低的估计，而AutoTen预测的最大秩为100。对于这个任务来说，这两个估计都不理想，因为在秩为3时准确度非常低，而在秩为100时准确度提升几乎没有。FRAPPE估计秩为40，虽然不完美，但看起来相当合理，接近曲线的“膝部”。ARD-Tucker在24小时内未能终止，因此被排除在图表之外。

5.5 合成数据集结果

表3显示，FRAPPE在性能上优于基线方法，相比表现最好的基线方法NORMO，FRAPPE在平均绝对百分比误差（MAPE）上提高了约10%，在平均绝对误差（MAE）上提高了约4个秩，在均方误差（MSE）上提高了200。此外，FRAPPE的计算速度比NORMO快约24倍，比AutoTen（最快的基线方法）快约1.6倍。

图3：不同秩估计方法在合成数据集上的运行时间/性能比较。越接近左下角，表示性能越好。

表3 合成数据集上不同模型的平均绝对百分比误差（MAPE）、平均绝对误差（MAE）、均方误差（MSE）和平均运行时间
粗体值表示最佳性能。
注：由于张量中存在负值（导致基于KL散度的AutoTen无法运行），我们在这些合成示例中仅使用了基于Frobenius范数的AutoTen。这可能会导致较低的准确性，但也有助于减少评估时间。

5.6 特征重要性结果

在图4中，我们绘制了不同特征组的重要性（如第4.1节所述）。我们基于特征在LightGBM树分裂中使用的次数来计算特征的重要性。

图4：由在合成数据集上训练的LightGBM模型输出的特征组重要性图表（数值越高，表示越重要）。最重要的特征组是张量切片之间的相关性，其次是阈值为0.2的非零元素数量。我们通过特征在分裂中使用的频率来计算特征组的重要性。特征组的详细描述见第4.1节。

我们可以看到，最重要的特征是不同切片之间的相关性。这是直观合理的，因为沿给定模式切片之间的相关性越高，意味着在该模式下组件之间的关系越紧密，从而需要的组件数就越少。这也是NORMO（基准方法之一）背后的直觉，NORMO关注的是CPD不同因子之间的相关性。
另一个有趣的特征集是阈值化的非零计数。从图4中可以看到，当阈值从0.1增加到0.2时，重要性增加，但在此之后逐渐下降，直到0.9时几乎变得无关紧要。这很可能是因为较低的相对值（由于我们对值进行了归一化处理）更可能是噪声伪影，或者仅仅是分解中不重要的值。较低的值在R秩分解中也更可能被排除，因为排除该值所带来的增量误差比排除较大值时的误差小。

6 其他相关工作

除了上述的CPD秩估计方法外，还为不同的张量分解方法开发了类似的技术。Vesselinov等人（2018）提出了NTFk，这是一种无监督方法，用于执行非负张量分解（NTF）。NTFk使用一种自定义的聚类算法（类似于k-means）来对因子矩阵的列进行聚类，并通过轮廓系数评估其质量。然后，它结合这些评分和重构误差来选择组件数量的合适目标。Nebgen等人（2020）尝试为非负矩阵分解（NMF）解决类似的问题，NMF将一个矩阵V分解为$V=WH$。他们首先反复计算在来自随机均匀分布噪声扰动的数据上进行的NMF。接着，他们使用k-means对W的列进行聚类。然后，他们使用赤池信息准则（AIC）和轮廓系数来计算聚类的质量。最后，他们使用神经网络在AIC和聚类轮廓值的滑动窗口上确定理想的组件数量。

7 结论

在本研究中，我们提出了FRAPPE，一种新颖的张量秩估计方法，能够以自监督的方式估计张量的规范秩，而无需计算昂贵的CPD。该方法的关键理念是，生成已知秩的合成数据要比计算实际的CPD便宜得多。基于这一思路，我们还提出了一组精心设计的特征，能够有效地确定给定张量的秩。
我们发现，简单地在这些数据上训练一个监督回归模型会导致模型在真实世界张量上的泛化能力较差，并且需要较长的训练时间。为了解决这个问题，我们提出了FRAPPE，它首先从输入张量生成具有已知秩的合成张量，并在这些合成张量上训练一个新的模型，从而提高模型的泛化能力，减少所需的训练数据量，并加速模型的训练过程。
我们对FRAPPE进行了广泛的评估，涵盖了三种不同类型的数据：合成张量、真实世界张量以及卷积神经网络（CNN）的权重张量。我们发现，在所有三个数据集上，我们的模型通常优于现有的基准方法，比表现最佳的基准方法（NORMO）快超过24倍，比最快的基准方法（AutoTen）快约1.6倍。
最后，我们分析了用于做出这些预测的特征，并解释了为什么我们认为这些特征在估计张量秩时很重要。我们提供了理论依据和实证证据，说明切片之间的成对相关性是张量秩的一个良好指标。我们相信，这为研究如何估计张量分解的组件数量而无需进行任何分解计算开辟了一个有趣的研究方向。