Высокоразмерная геометрия

Большинство наших геометрических интуиций сформировалось в 2D и 3D. Но данные о людях, текстах, молекулах живут в пространствах размерности d = 100, 1000, 100000. В этих пространствах всё работает иначе — и понимание «проклятия размерности» критично для ML-практика.

Парадоксы высоких измерений

Объём «скорлупы»: В ℝᵈ объём шара Bᵈ(r) = πᵈ/²rᵈ/Γ(d/2+1). При d → ∞ почти весь объём шара сосредоточен в тонком слое вблизи поверхности. Точнее: для X ~ Uniform(Bᵈ), E[||X||] ≈ r·√(d/(d+2)) → r, а Var(||X||) → 0.

Практическое следствие: все случайные точки в шаре находятся примерно на одном расстоянии от центра → расстояние от центра — не различительный признак.

Случайные векторы почти ортогональны: Для X, Y ~ N(0, Iᵈ/d): cos(∠XY) = Xᵀ Y/(||X|| ||Y||) → N(0, 1/d). При d=1000 стандартное отклонение угла ≈ 1/√1000 ≈ 0.03 радиана ≈ 1.8°. Почти все случайные векторы почти ортогональны — это и хорошо (easy to embed many directions) и плохо (кластеризация неэффективна).

Концентрация меры: Липшицева функция F: ℝᵈ → ℝ (||∇F|| ≤ L) почти константна на высокоразмерной гауссовой мере:

P(|F(X) − EF(X)| ≥ t) ≤ 2 exp(−t²/(2L²))

Практически: среднее значение F(X) почти равно типичному значению. Например: норма ||X|| для X ~ N(0, Iᵈ) концентрируется у √d с отклонением O(1/√d).

Лемма Джонсона–Линденштрауса

Теорема (JL, 1984): Для n точек в ℝᵈ и любого ε ∈ (0, 1/2), случайная линейная проекция в ℝᵏ с k = O(log n / ε²) сохраняет все попарные расстояния с точностью (1±ε) с высокой вероятностью.

Случайная матрица проекции: Rᵢⱼ ~ N(0, 1/k). Для каждой пары (i,j): |(1/k)||R(xᵢ − xⱼ)||² − ||xᵢ − xⱼ||²| ≤ ε||xᵢ − xⱼ||² с вероятностью ≥ 1 − 2exp(−cε²k).

Пример: 10000 документов в TF-IDF пространстве d = 50000 → JL проекция в k = O(log 10000 / ε²) ≈ 1700 измерений (при ε = 0.1), сохраняя все расстояния с точностью 10%.

Применение: LSH (Locality Sensitive Hashing) — быстрый приближённый поиск ближайших соседей, сжатие признаков для ML, ускорение матричных операций.

PCA и метод главных компонент

PCA решает задачу: найти k ортогональных направлений v₁,...,vₖ, максимизирующих дисперсию проекций данных.

Решение: SVD матрицы данных X (n×p): X = UΣVᵀ. Первые k столбцов V — главные компоненты (PC). Проекция: X·V_{1:k} ∈ ℝⁿˣᵏ. Объяснённая дисперсия: Σ_{i≤k} σᵢ²/Σⱼ σⱼ².

Геометрически: PCA поворачивает систему координат так, чтобы наибольшая дисперсия была вдоль первой оси, следующая наибольшая — вдоль второй, и т.д.

Случайные матрицы и PCA: При p/n → c > 0 (много признаков, не так много наблюдений) спектр выборочной ковариационной матрицы следует закону Марченко–Пастура: плотность сингулярных значений сосредоточена в интервале [(1−√c)², (1+√c)²] — «шумовое море». Сигнальные компоненты выше (1+√c)² выступают как «спайки».

Правило BBP (Baik-Ben Arous-Péché): PC достоверно оценивается только если его «сигнал» σ > 1/√c. Иначе оценка PC ортогональна истинному направлению!

Robust PCA и Sparse PCA

Robust PCA (Candès, Li, Ma, Wright, 2011): Дано: X = L + S, где L — низкоранговая матрица, S — разреженная (выбросы). Задача: разложить X. Алгоритм: min rank(L) + λ||S||₀ релаксируется к min ||L||_* + λ||S||₁ (nuclear norm + L1). Точно восстанавливает L и S при определённых условиях. Применение: разделение «фон + движущийся объект» в видео.

Sparse PCA: Стандартные PC — линейные комбинации всех p признаков. Sparse PCA: PC разреженные (мало ненулевых коэффициентов). Интерпретируемость: PC«1» = 0.8·ген_A + 0.6·ген_B (не все тысячи генов). NP-hard в общем, эффективные приближения: ADMM, SCoTLASS.

Численный пример

Данные: 100 наблюдений в 50-мерном пространстве. Истинная размерность = 3 (3 латентных фактора + шум). PCA: первые 3 PC объясняют 78% дисперсии. При p/n = 0.5 (c=0.5), шумовой порог = (1+√0.5)² ≈ 2.9. Если 4-й сингулярный PC ≈ 2.7 < 2.9 — не достоверен.

Задание: Примените PCA к датасету MNIST (784-мерные изображения). Постройте «scree plot» объяснённой дисперсии. Сколько PC нужно для объяснения 95% дисперсии? Визуализируйте первые 2 PC для всех цифр (scatter plot с раскраской по метке). Реализуйте случайную проекцию (JL) в k=50 измерений. Сравните kNN accuracy (k=5) на оригинальных и сжатых признаках.