High dimensional data can have a surprising property: pairs of data points
may be easily separated from each other, or even from arbitrary subsets, with
high probability using just simple linear classifiers. However, this is more of
a rule of thumb than a reliable property as high dimensionality alone is
neither necessary nor sufficient for successful learning. Here, we introduce a
new notion of the intrinsic dimension of a data distribution, which precisely
captures the separability properties of the data. For this intrinsic dimension,
the rule of thumb above becomes a law: high intrinsic dimension guarantees
highly separable data. We extend this notion to that of the relative intrinsic
dimension of two data distributions, which we show provides both upper and
lower bounds on the probability of successfully learning and generalising in a
binary classification problem

高维数据具有令人惊讶的特性：仅使用简单的线性分类器就可以高概率地将数据点配对分开，甚至从任意子集中分离出来。我们引入了数据分布的内在维度的新概念，精确地捕捉了数据的可分离性质。对于这个内在维度，以上的经验法则成为一条规律：高内在维度保证了数据的高可分离性。我们将这个概念扩展为两个数据分布的相对内在维度，并证明它提供了成功学习和推广二元分类问题的概率的上下界。