使用归一化流估计数据的内在维度

Intrinsic dimensionality estimation using normalizing flows使用归一化流估计内在维度

https://proceedings.neurips.cc/paper_files/paper/2022/file/4f918fa3a7c38b2d9b8b484bcc433334-Paper-Conference.pdf

摘要

一个由M个样本组成的数据集嵌入在空间中有多少自由度？这个数字，正式称为内在维度，可以使用最近邻统计来估计。然而，最近邻统计在大数据集上无法扩展，因为它们的复杂度随着M的增加呈二次方增长，即。此外，基于最近邻统计的方法在处理嵌入在高维空间中的数据集时表现不佳，尤其是当时。在本文中，我们提出了一种新的方法来估计内在维度，即使用归一化流（Normalizing Flows），这种方法可以扩展到大型数据集和高维空间。该方法基于一些简单的信封背面计算，预测当用不同噪声幅度扩展数据集时，流的雅可比矩阵的奇异值会如何变化。与法线方向相关的奇异值与切线方向相关的奇异值的演变方式不同。我们在包括64x64 RGB图像在内的各种数据集上测试了我们的方法，并取得了最先进的结果。

1 引言

在大数据时代，学习高维数据的低维表示变得越来越重要。因此，表示学习是一个非常活跃的研究领域，其应用范围广泛，从神经科学[27]、分子生物学[28]、生物信息学[12]到图像分析[21]。但是，究竟需要多少低维变量才能准确描述原始数据呢？不幸的是，这个数字通常不知道，需要估计——这项任务正式称为内在维度（ID）估计。

此外，估计ID被证明是理解神经网络和生成模型运作的有用工具[23, 11, 1, 31]。在最近的一项研究中，[29]验证了ID在自然图像的深度学习中扮演着重要角色，因此激发了在这种设置中更好地估计ID的必要性。在生成模型的背景下，ID对应于生成数据的潜在变量的数量。这些生成模型中的一些甚至依赖于知道生成数据的确切潜在变量数量，这限制了它们在现实世界问题中的应用，因为在现实世界问题中这个数字是未知的[3, 16]。

ID估计在数学上是具有挑战性的。大多数方法都依赖于这样的假设：局部地，样本是均匀分布的，因此可以使用最近邻统计来估计ID[4]。然而，这样的最近邻方法不适用于包含M > 1样本的大型数据集，因为复杂度随着而变化，其中D是嵌入空间的维度，并用于计算（欧几里得）距离1。因此，每当嵌入空间D与样本大小M的数量级相同时，这种扩展问题就会被放大，D = O(M)。

此外，最近邻方法还受到维度的诅咒的影响，这意味着在高维空间D > 1时它们的性能表现不佳[5, 4, 32]。在本文中，我们提议通过使用可以扩展到大型数据集和维度的标准归一化流（NFs）来估计内在维度，以克服这些可扩展性问题。

我们的高级思想非常简单，并且基于一些简单的估算，这些估算预测了在训练前注入数据中的噪声量不同，流的特征值会如何变化。对于变化性小的方向（即法线方向），相应的特征值应该按照我们的理论预测的速率减少。然而，对于变化性大的方向（即流形方向），相应的特征值将表现出不同的行为，这使我们能够估计维度d。我们在包括分辨率为64×64的RGB图像在内的各种数据集上展示了我们方法的合理性。

2 问题陈述、背景和符号表示

在这里，我们将简要讨论估计内在维度（ID）的问题，介绍归一化流（NF）的概念，以及将在整个论文中使用的附加符号表示。

估计内在维度（ID）：一个d维流形M是一组点，这些点在局部上与R^d的子集微分同胚，见[22]中流形的正式定义。给定来自嵌入在R^D中的d维流形的M个样本x1, ..., xM，其中d < D，任务是估计d。更一般地，如果数据集位于具有不同内在维度的流形的并集上，任务是对于给定点x*估计d的局部值。然而，对于现实世界的数据集，样本会被噪声污染，使得数据集成为全维的，即d = D。在这种情况下，估计内在维度对应于估计在观察到的数据集中存在多少主要的自由度。在下文中，我们将这些自由度称为大变化性的方向。

3 相关工作

估计内在维度是一个研究充分的问题，有着大量的文献，见[5, 4]进行全面概述。

最近邻方法：历史上，主要发展了两个分支：全局和局部方法[4]。全局方法基于PCA等方法全局估计数据集的维度，而局部方法则局部估计它。一致的局部估计器基于最近邻统计。直观地说，一个d维球体的体积按其半径r的d次方缩放，因此，一个点的r球体内的最近邻数量也应该类似地缩放。这种直觉由[13]形式化，并在[14]中推广。最近，[9]推导出了到第二个最近邻的距离分布——一个以ID为指数的幂律。我们选择这种方法，称为twoNN，作为最近邻方法的代表，并在第5节中比较其与我们方法的性能。

基于NN的方法：神经网络（NN）可以扩展到大型数据集。令人惊讶的是，据我们所知，除了我们的方法外，只有一种方法尝试直接使用基于NN的方法估计ID[32]，称为LIDL（稍后详细描述）。然而，存在不同的间接方法使用性能指标来估计ID。一般的思想是训练具有不同潜在维度的不同模型，并比较它们在选定指标上的性能，见例如[2, 34, 3]。可以说，在该指标上取得最佳结果的模型对应于正确的潜在维度。然而，估计值将是相对于选定的性能指标的，因此可能不反映真实的ID。作为这种相对性的一个例子，我们引用[3]中的图14，该图使用他们基于NF的方法估计CelebA数据集[24]的ID。当使用FID分数[15]或重建误差作为性能指标时，他们得到不同的结果。在[30]中，有人认为自动编码器的编码器的雅可比矩阵可以提供收缩方向的信息。直观地说，流形方向对应于低收缩方向，而流形外方向对应于高收缩方向。这个思想的要点与我们将在第4节中提出的方向非常相似，收缩方向可以直接与编码器雅可比矩阵的奇异值相关。然而，收缩方向的数量只会给出ID的下限。

4 方法

我们如何使用 NF 估计从流形采样的数据的内在维数？

因此，从最简单的情景开始，论证的流程如下，我们观察到：

观察1：在x处评估的NF的雅可比矩阵的大奇异值对应于数据中的小变化方向。然而，大变化方向则对应于小奇异值。

我们如何利用这一观察来估计数据流形的内在维度呢？在对清洁流形数据（即没有内在噪声的流形样本）训练NF时，观察1预测了奇异值在表示流形外和流形上方向时幅度上的明显变化。

实际上，我们可以在各种玩具示例中观察到这种幅度上的变化，见第4.1节。然而，仅基于这一观察来估计d，将需要在这些奇异值的幅度上设定一个任意的阈值。另一方面，在更现实的情景中，现实世界的数据有一些内在的噪声。

带有内在噪声的数据：在与最简单情景相同的设置中，我们现在额外假设内在噪声来自一个具有幅度σ0的标准高斯分布，即。然后，方程（4）变为——（此处原文未完成，无法提供完整的翻译）

对奇异值的平均化本身并没有几何解释。我们只对分隔流形上和流形外方向的奇异值的截止点感兴趣。因此，平均化减少了由于样本量有限或qσ2学习不精确而引入的噪声。

4.1 教学示例

我们在教学示例上说明我们的方法——单位球面上的均匀分布被一些内在高斯噪声污染，噪声幅度。在图1左侧，我们展示了三个奇异值如何在对数-对数尺度上根据不同噪声幅度变化。对于误差条，我们使用了200个干净的训练样本（即没有被噪声污染）。在超过内在噪声幅度（从左数第一个虚线）之后，较大的奇异值以斜率≈-0.5变化，而两个最小的奇异值几乎不变。当噪声幅度超过球体半径（从左数第二个虚线）时，奇异值相互接近。在右侧的图中，我们展示了F(α)及其估计值。右侧图的标题显示了算法4的输出，的参数a2。

4.2 特殊情况：图像

到目前为止，我们的理论假设数据是无界的，以至于如果膨胀噪声趋于无穷大，→ ∞，流的雅可比矩阵的特征值趋向于0，λ → 0。根据我们的理论，这种衰减对于对应于流形方向的奇异值来说，比对应于流形外方向的奇异值要晚很多，表现为衰减起始α的平稳段。根据方程（8），这些起始反映了流形方向中的变化量。

然而，一些现实世界的数据集是有界的。例如，RGB图像由像素组成，其取值范围在[0, 255]内。因此，对于→ ∞，膨胀后的图像将变得过于嘈杂，以至于关于流形的所有信息都丢失了。现在，假设是在所有图像变得过于嘈杂而失去意义之前可以容忍的最大噪声量。那么，所有大于或等于的起始都将对应于流形方向，因为流形方向中的变化量必须大于。

我们如何以最不随意的方式设置这个呢？在补充材料中，A.4节，我们根据以下理由计算了这种最大噪声量。如果太大，那么基本上所有像素将饱和到下界或上界，因此一个合理的最大噪声量是使50%的像素饱和的量。如果像素值落在区间内（并且我们假设像素值在这个区间上均匀分布），那么。

5 实验

我们将我们的方法与twoNN和LIDL进行了基准测试，见第3节。后者与我们的方法非常相似，因为我们都是用不同的值来膨胀流形，然后使用NF学习qσ2。然而，[32]估计了对数似然随噪声幅度变化的速率，而我们研究了流的雅可比矩阵的特征值是如何演变的。因此，我们依赖于NF能够将p(x)的样本转换为标准高斯分布——这比精确学习膨胀的分布qσ2要简单得多。此外，我们不依赖于的假设，因此我们也不需要微调不同的噪声幅度，见第3节的更多细节。

作为我们方法的缩写，我们使用ID-NF。我们在补充材料中提到了相应的训练细节和额外的图表。使用ID-NF或重现我们的实验的代码可以在这里找到：https://github.com/chrvt/ID-NF。

5.1 低维合成数据集

我们在已知内在维度(ID)的各种合成数据集上测试了我们的方法：球体、环面、双曲面、细螺旋、瑞士卷和Stiefel流形，见表1。我们在这些流形上使用不同的分布来测试对采样分布p(x)的敏感性。我们将我们的方法与第3节中介绍的LIDL和twoNN估计器进行比较。对于这些低维示例，所有方法都表现良好。twoNN和我们的方法准确地估计了所有ID。然而，LIDL方法对采样分布表现出一些敏感性（见球体分布上相关估计的高亮部分），并且略微高估了瑞士卷的维度（见瑞士卷的高亮估计部分）。然而，我们并没有尝试找到σ^2的最佳范围，而是在所有分布中使用了相同的范围。通过这种方式，我们想展示必须为每个分布单独估计正确范围的缺点。

5.2 高维合成数据集

接下来，我们研究这些方法如何扩展到更高的嵌入维度。为此，我们从嵌入在R^D中的S(D/2)中均匀采样，对于不同的偶数D值。为了进行公平比较，我们只对所有方法使用大小为10^4的训练集。在图2左侧，我们展示了不同方法估计维度的方式。ID-NF与LIDL相当，并且优于twoNN。后者受到了第1节中提到的维度的诅咒的影响。

在图2右侧，我们重复实验，但只使用了个样本。ID-NF仍然表现非常好。然而，LIDL的变异性更大，并且在d = 200（即D = 400）时显著低估了ID。这表明了我们方法的另一个好处：与LIDL相比，我们不需要精确地学习密度，这项任务需要更高维度的更多样本。

5.3 StyleGan图像流形

在[3]中，通过使用生成对抗网络的一个变体，StyleGan2[19]，在高质量图像数据集FFHQ数据集[18]上训练，创建了一个图像流形。在生成新图像时，只变化了总共512个潜在变量中的d个，同时保持其他变量不变。注意，这并不一定会产生一个d维的图像流形。实际上，[29]表明，只要生成器是Lipschitz连续的，ID最多为d。我们将这些图像下采样到64×64×3的分辨率，即嵌入空间的维度为D=12288。

我们将我们的方法应用于由和2×图像组成的StyleGan d=2和d=64图像流形。不幸的是，在这些数据集上训练N个流形计算上很昂贵，计算流形雅可比矩阵的特征谱对K个样本也是如此。然而，我们只关心特征值的衰减起始是否发生在σmax=255×0.68之后，见第4.2节。因此，只训练3个NF就足够了：一个在膨胀噪声σ幅度非常小的情况下，一个在σ=255×0.68时，一个在σ非常大时。

在图3中，我们展示了d=2（左侧）和d=64（右侧）的一个特定示例的所有奇异值曲线的高度和起始点。我们分别用红色突出显示了对应于2个最小和64个最小奇异值的点。虚线垂直线位于σmax=255×0.68处。对于d=2，最小的两个奇异值很好地分开了，尽管我们统计出d̂=4个奇异值，这些奇异值的起始点大于，对于这个特定示例。对于d=64，我们统计出。当对K=50个样本取平均时，我们对d=2的估计值为d̂=4.06，对于d=64，我们有d̂=62.24。

我们还使用LIDL估计了ID，但我们没有得到一个一致的估计器。实际上，取决于用于膨胀噪声的范围，估计值变化很大。

5.4 概念验证应用

我们展示内在维度(ID)可以用来改进潜在变量模型，并观察到分布外(OOD)样本具有更高的ID。

潜在变量模型：最近，基于NF的流形值数据开发了两种潜在变量模型，流形流(M-flow)[3]和去噪归一化流(DNF)[16]。这两种方法都依赖于知道确切的潜在变量数量（即ID），这限制了它们在现实世界问题中的应用。例如，CelebA-HQ[18]的真实ID（如果存在）是未知的，潜在维度被任意设置为512。我们使用我们的方法估计ID，得到 d̂ = 130 。然后，我们使用与原始论文中相同的架构训练了一个DNF，使用130而不是512作为潜在维度。经过300个周期的训练，我们使用Frechet Inception距离(FID)评估生成图像的质量——距离越低越好[15]。我们得到了36.92的FID分数。原始DNF的FID分数为34.14，M-flow为38.07——经过500个周期的训练。因此，我们使用130个潜在维度而不是512个，得到了非常相似的生成能力（以FID分数衡量）。

OOD样本上的ID：在特定数据集上训练后，例如StyleGan 2d图像流形，对于分布外(OOD)样本，ID如何变化？在表2中，我们报告了在Stylegan2d图像流形上训练时，来自不同数据集的K = 50个样本的平均ID估计值。正如我们所看到的，OOD样本的ID显著高于分布内样本。直观地说，OOD样本存在于流形的法线空间上，因此，在d < D/2的情况下，具有更多大变化的方向。我们在补充材料中进行了更多的OOD实验。

6 讨论

我们介绍了一种新的方法来估计内在维度(ID)，利用归一化流(NFs)将数据转换为高斯随机变量的样本。基于一些简单的估算，我们推导了在训练前用高斯噪声膨胀数据时流的雅可比矩阵的奇异值如何演变。对于我们的估计器至关重要的是，与大变化方向（即流形方向）对应的奇异值与小变化方向（即流形外方向）对应的奇异值的演变显著不同。

我们展示了我们能够根据不同的流形和不同的采样分布估计ID。我们将我们的方法与基于最近邻统计的最先进ID估计器twoNN，以及也基于NFs的相关方法LIDL进行了比较。我们在高维（表1）中优于twoNN，在小数据规模（图2）和图像方面优于LIDL，见第5.3节。

与LIDL不同，我们不需要微调噪声幅度。然而，我们需要足够小， 足够大，这可能在计算上很昂贵。

我们展示了我们的方法可以扩展到分辨率为64×64的RGB图像，填充d=2和d=64维流形，我们分别估计 d̂ = 4和 d̂ = 62。然而，这个估计对用于估计d的图像数量K（我们使用了K=50）敏感，对训练的NFs数量（我们认为N=3足够）敏感，以及在图像变得太模糊之前可以容忍的最大噪声量见第4.2节）。尽管如此，据我们所知，这是第一种在如此高分辨率图像流形上一致估计ID的方法。此外，我们展示了估计ID可以帮助改进最近基于NFs的潜在变量模型，知道这个确切数字至关重要。我们还观察到，对于分布外(OOD)数据，ID比流形上的示例更高，这激发了对OOD样本和ID之间关系的进一步研究。

最后，我们的理论推导依赖于数据是无界的假设，尽管我们也适应了有界数据的方法。然而，对于这种情况，需要更多的研究来理解流的雅可比矩阵奇异值在接近边界时的确切行为。一个有趣的研究方向是使目标分布和膨胀噪声适应数据拓扑。对于图像，这相当于将NF的目标分布改为均匀分布而不是高斯分布，并使用均匀噪声而不是高斯噪声。

更广泛的影响：作为一篇理论论文，我们没有预见到我们的工作会带来任何直接的负面社会影响。