Джонсон-Линденштраус: сохраняем расстояния, сокращая координаты

Если различаешь попарную гарантию конечного набора и изометрию всего пространства, листай до «Теперь сам».

Как думаешь, какие координаты можно выбросить

У каждого документа сотни тысяч признаков. Нужно сравнивать их евклидовы расстояния, но хранение и передача векторов дороги. Просто оставить первые сто признаков нельзя: различие может находиться в отброшенной части. Случайная проекция смешивает все координаты, так что заранее выбранное направление не оказывается полностью забытым из-за своего номера.

На что это похоже

Представь несколько фотографий одного объекта с разных случайных направлений. Один снимок может скрыть важное различие, зато набор независимых ракурсов уменьшает риск пропустить его во всех измерениях. Проекция тоже собирает несколько измерений исходного вектора; каждый смешивает все его признаки, а не выбирает один заранее любимый столбец.

Механизм: сначала один вектор, затем все пары

Возьмём матрицу R размера k×d, элементы которой независимы и имеют нормальное распределение со средним ноль и дисперсией 1/k. Образ y=Rx. Для фиксированного x каждая координата образа имеет дисперсию ||x||²/k. Поэтому сумма квадратов координат в среднем равна ||x||²; нормировка 1/√k необходима именно для этого масштаба.

Концентрация квадрата длины около ожидания даёт вероятность большого относительного отклонения не больше 2 exp(-c·ε²k) при 0<ε<1 и некоторой положительной константе c. Расстояние между двумя точками - длина их разности, а линейность даёт R(x-z)=Rx-Rz. Применим эту границу к каждой паре и объединим события ошибки. Пар меньше N², поэтому достаточно сделать экспоненциально малую вероятность на пару порядка δ/N².

После взятия логарифма появляется k порядка ε⁻² log(N/δ). Логарифм возник из числа проверяемых пар, а квадрат обратной точности - из концентрации. Это объясняет форму формулы, но скрытая константа не позволяет без уточнения объявить конкретные сто координат достаточными для любого входа.

Правило

Одна независимо выбранная нормированная матрица применяется ко всему фиксированному набору. Гарантия касается квадратов евклидовых расстояний и заданных ε,δ. В потоковой задаче общий линейный образ обновляется теми же линейными обновлениями, что и исходный вектор.

Разбор: опыт с общей матрицей

from random import Random
from math import sqrt
from itertools import combinations

rng = Random(829)
d, k, count = 200, 80, 12
matrix = [[rng.gauss(0, 1 / sqrt(k)) for _ in range(d)]
          for _ in range(k)]
points = [[rng.randrange(-3, 4) for _ in range(d)]
          for _ in range(count)]


def project(x):
    return [sum(a*b for a, b in zip(row, x)) for row in matrix]


def distance2(a, b):
    return sum((x-y)**2 for x, y in zip(a, b))


images = [project(x) for x in points]
ratios = []
for i, j in combinations(range(count), 2):
    before = distance2(points[i], points[j])
    after = distance2(images[i], images[j])
    if before == 0:
        assert after == 0
    else:
        ratios.append(after / before)
print("Размеры:", d, k, "точек:", count)
print("Пар:", len(ratios))
print("Диапазон квадратов расстояний:",
      f"{min(ratios):.6f}", f"{max(ratios):.6f}")
x, z = points[0], points[1]
combined = project([a+b for a, b in zip(x, z)])
separate = [a+b for a, b in zip(project(x), project(z))]
error = max(abs(a-b) for a, b in zip(combined, separate))
assert error < 1e-10
print("Линейность проверена:", error < 1e-10)

Размеры: 200 80 точек: 12
Пар: 66
Диапазон квадратов расстояний: 0.684698 1.417874
Линейность проверена: True

Код сообщает минимальное и максимальное отношения квадратов расстояний на одном опыте. Это проверка конкретного преобразования, не доказательство теоремы и не вывод константы в O. Масштабирование в квадрате важно: оценка для квадратов переводится в границы для расстояний через квадратные корни, а не простым копированием тех же чисел.

Слияние линейных образов проверяется отдельно: образ суммы равен сумме образов с точностью округления. Это свойство линейности не требует вероятностного успеха; вероятность относится к сохранению геометрии.

Разбор: почему нельзя сохранить всё пространство

Если k<d, у линейного отображения есть ненулевой вектор ядра: некоторое направление переходит в ноль. Значит для всех возможных векторов сохранить ненулевую длину нельзя. Противник, увидевший матрицу и выбравший такой вектор, немедленно разрушит относительную гарантию. Теорема допускает конечный набор, фиксированный независимо от выбора матрицы, и платит логарифмом его размера.

Другой крайний случай - две одинаковые точки. Их расстояние ноль, образы также совпадают. Делить при диагностике на исходное расстояние нельзя: такую пару проверяют отдельно. Наш набор содержит случайные целочисленные точки, но в рабочей проверке нулевые расстояния всё равно обработаны явно.

Что ломается без этого

Убери нормировку - длины увеличатся примерно в √k раз. Сгенерируй для каждой точки свою матрицу - уже сама пара точек не имеет общего отображения, и доказательство через разность неприменимо. Возьми обычное число координат для всех желаемых точностей - увеличение точности потребует пересмотреть размер сводки.

Зачем это в работе

Передача и хранение высокоразмерных признаков становятся дешевле, когда downstream-задаче нужны приближённые расстояния между конечным набором объектов. Та же идея даёт линейные сводки для потоковых векторов. Но сохранение евклидовой геометрии не обещает сохранить манхэттенское расстояние, каждый отдельный признак или смысл наиболее важного слова документа.

Теперь сам

Если требуемую относительную точность уменьшили с ε до ε/2, как меняется порядок числа координат при том же наборе и вероятности отказа? Почему зависимость логарифмическая от числа точек?