Непопулярные статьи, выпуск 1

Одной из причин, почему я хотел завести свой канал, было желание делиться не очень известными статьями, на которые я набредаю в ходе своей работы. Первой в этом списке по праву будет "On the Behavior of Intrinsically High-Dimensional Spaces: Distances, Direct and Reverse Nearest Neighbors, and Hubness" авторства Fabrizio Angiulli (без всяких там et aliī). В статье длиной в 60 страниц и 38 теорем – которые, между прочим, все аккуратно доказываются в конце – скурпулёзно разбирается то, как работают расстояния до ближайших соседей в пространствах высокой размерности для случайных данных.

Почему это важная статья? Потому что даже в текущем мире с гигантскими языковыми моделями поиск ближайших соседей – одна из самых базовых операций, на которой работают практически все сервисы рекомендации контента и поиска в мире. На практике оказывается, что очень сложно задать конкретный порог ε для поиска ближайших соседей для произвольной точки – даже для равномерно распределённых данных мы с высокой вероятностью получим либо ноль, либо кучу соседей. Скорее всего, в реальных данных с кучей кластеров дела обстоят только хуже. В статье также разбираются несколько случаев расстояний до k-го ближайшего соседа в данных с разными распределениями.

Отдельно стоит отметить аккуратно выписанные доказательства в конце статьи и эмпирическую проверку того, насколько близко предсказания теорем в экспериментах на синтетических данных. Становится сильно понятнее, насколько вообще практичные теоремы доказываются в этой статье.

Ссылка на статью: https://www.jmlr.org/papers/volume18/17-151/17-151.pdf