在本次讲座(第 42 分钟)中,教授说,我们需要密集覆盖训练向量空间的训练样例数量随着空间的维度呈指数增长。所以我们需要如果我们正在研究,训练数据点空间。我想问为什么这是真的,它是如何证明/实现的?教授之前在谈论 K-Nearest Neighbors 并且他正在使用和指标。我不认为这些指标会导致拓扑结构使一组离散的点在环境空间中密集。
为什么密集覆盖空间的训练点数量会随着维度呈指数增长?
首先,当我们说我们想要“密集覆盖”一个维空间的实数。为简单起见,我们假设所有维度中的所有值都限制在. 即使只有一个维度, 实际上已经有无数个不同的可能值,即使在这样一个受限的范围。
但通常我们实际上并不关心从字面上覆盖每一个可能的值。一般来说,我们期望这点彼此“接近”的维空间也“表现”类似,即存在某种程度的“连续性”。因此,为了获得“足够”或“良好”或“密集”的空间覆盖,您可以稍微非正式地假设您拥有的每个数据点都占据了它周围的一些空间。这是 Lutz Lehmann 在您的问题下评论背后的直觉:您可以将每一点视为-维度立方体占据你的一些体积维空间。
现在,如果你有一个-尺寸空间沿着每个维度,并且您有占据该空间一部分的小立方体(例如,大小的立方体在每个维度),您确实会发现填充空间所需的立方体数量呈指数增长. 基本思想是:如果有一些立方体足以填满-维空间,然后如果将维数增加到, 你需要立方体来填充新空间。当您添加一个新维度时,完整的先前空间本质上只是新空间的一个“切片”。
对于尺寸,这很容易可视化。如果你有,你的空间实际上只是一条线,或者如果你将值限制在一个线段. 如果你有一个线段,你的长度很小,您只需要其中的十个即可填满线路。
现在假设您添加了第二个维度。突然间,你的线变成了整个平面,或者方格。这立方体现在只能填满一行,你必须重复这个多次填满整个D空间;你需要立方体。
现在假设您添加了第三个维度。曾经是一个平面的东西被“拉”成一个完整的 3D 立方体——一个大立方体,需要许多小立方体来填充!我们之前拥有的飞机再次只是这个更大的平面中的一个平面D 空间,并且将不得不重复填充飞机的整个策略多次填满这样的切片D空间;这现在需要立方体。
过去的维度,故事以完全相同的方式继续,但对我们人类来说更难想象。