为什么密集覆盖空间的训练点数量会随着维度呈指数增长?

人工智能 分类 k-最近邻 维数诅咒
2021-10-20 06:19:21

本次讲座(第 42 分钟)中,教授说,我们需要密集覆盖训练向量空间的训练样例数量随着空间的维度呈指数增长。所以我们需要42=16如果我们正在研究,训练数据点2D空间。我想问为什么这是真的,它是如何证明/实现的?教授之前在谈论 K-Nearest Neighbors 并且他正在使用L1L2指标。我不认为这些指标会导致拓扑结构使一组离散的点在环境空间中密集。

1个回答

首先,当我们说我们想要“密集覆盖”一个d维空间Rd的实数。为简单起见,我们假设所有维度中的所有值都限制在[0,1]. 即使只有一个维度d=1, 实际上已经有无数个不同的可能值,即使在这样一个受限的[0,1]范围。

但通常我们实际上并不关心从字面上覆盖每一个可能的值。一般来说,我们期望这点d彼此“接近”的维空间也“表现”类似,即存在某种程度的“连续性”。因此,为了获得“足够”或“良好”或“密集”的空间覆盖,您可以稍微非正式地假设您拥有的每个数据点都占据了它周围的一些空间。这是 Lutz Lehmann 在您的问题下评论背后的直觉:您可以将每一点视为d-维度立方体占据你的一些体积d维空间。

现在,如果你有一个d-尺寸空间[0,1]沿着每个维度,并且您有占据该空间一部分的小立方体(例如,大小的立方体0.1在每个维度),您确实会发现填充空间所需的立方体数量呈指数增长d. 基本思想是:如果有一些立方体K足以填满d-维空间,然后如果将维数增加到d+1, 你需要dK立方体来填充新空间。当您添加一个新维度时,完整的先前空间本质上只是新空间的一个“切片”。

对于尺寸d=1,2,3,这很容易可视化。如果你有d=1,你的空间实际上只是一条线,或者如果你将值限制在一个线段[0,1]. 如果你有一个[0,1]线段,你的长度很小0.1,您只需要其中的十个即可填满线路。

现在假设您添加了第二个维度。突然间,你的线变成了整个平面,或者10×10方格。10立方体现在只能填满一行,你必须重复这个10多次填满整个2D空间;你需要102=100立方体。

现在假设您添加了第三个维度。曾经是一个平面的东西被“拉”成一个完整的 3D 立方体——一个大立方体,需要许多小立方体来填充!我们之前拥有的飞机再次只是这个更大的平面中的一个平面3D 空间,并且将不得不重复填充飞机的整个策略10多次填满10这样的切片3D空间;这现在需要103=1000立方体。

过去的3维度,故事以完全相同的方式继续,但对我们人类来说更难想象。