Relative intrinsic dimensionality is intrinsic to learning
Oliver J. Sutton Qinghua Zhou Alexander N. Gorban Ivan Y. Tyukin
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