Логарифмическая шкала факториалов
Приближение Стирлинга преобразует произведение в сумму, что является фундаментальным шагом, делающим математику больших n управляемой:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Эта формула возникает из приближения суммы Σ ln(k) для k=1..n интегралом ln(x), а затем применения правила трапеции для ограничения ошибки.
Почему это имеет геометрическое значение
Формула объема n-мерной сферы включает Γ(n/2 + 1), которая для целого числа n равна (n/2)! или произведениям полуцелых чисел. Приближение Стирлинга позволяет оценить эти значения для больших n без прямого вычисления каждого значения.
Приближение Стирлинга дает log(n!) ≈ n·log(n) − n·log(e) в нотации с основанием 10, полезно для оценок порядка величины.
Для n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (истинное: 15.104).
Для n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (истинное: 363.74).
Приближение Стирлинга при n=20
Прямое вычисление: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Формула объема
Объем n-мерной сферы радиуса r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
Значения C_n для малых n следуют схеме с использованием Γ(1/2) = √π и формулы сведения:
- n=1: C_1 = π^(1/2)/Γ(3/2) = √π/(√π/2) = 2
- n=2: C_2 = π^1/Γ(2) = π/1 = π
- n=3: C_3 = π^(3/2)/Γ(5/2) = π^(3/2)/(3√π/4) = 4π/3
- n=4: C_4 = π²/Γ(3) = π²/2
- n=5: C_5 = π^(5/2)/Γ(7/2) = π^(5/2)/(15√π/8) = 8π²/15
Обратите внимание: C_n достигает пика около n=5 (≈ 5.264), затем уменьшается. Для больших n C_n → 0.
Максимум при n=5
C_5 = 8π²/15. При π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Чтобы убедиться, что это максимум: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Итак, C_6 < C_5 — пик произошел при n=5.
Доля объема в углах
Парадокс углов квантифицирован: какая часть n-мерного единичного гиперкуба [−1,1]^n лежит вне вписанной сферы радиуса 1?
Corner fraction = 1 − C_n / 2^n
| n | C_n | 2^n | Доля сферы | Доля углов | |---|---|---|---|---| | 2 | 3.14 | 4 | 78.5% | 21.5% | | 3 | 4.19 | 8 | 52.4% | 47.6% | | 4 | 4.93 | 16 | 30.8% | 69.2% | | 5 | 5.26 | 32 | 16.4% | 83.6% | | 6 | 5.17 | 64 | 8.1% | 91.9% | | 10 | 2.55 | 1024 | 0.25% | 99.75% |
Последствия для оптимизации
Парадокс углов имеет прямые последствия для оптимизации в высокомерных пространствах:
Случайный поиск не работает. Случайная точка в n-мерном пространстве параметров почти наверняка приземляется в углу — далеко от начала координат, с экстремальными значениями параметров. Если хорошие решения кластеризуются около умеренных значений параметров, случайный поиск почти никогда не найдет их.
Градиентный спуск работает. Следуя локальному градиенту, вы систематически перемещаетесь по геометрии, а не слепо её выборками. Проклятие размерности поражает случайные методы; структурированные методы адаптируются.
Расстояние сосредоточено. В высоких измерениях все попарные расстояния между случайными точками концентрируются вокруг одного и того же значения: они все становятся примерно √(2n/3) для точек, равномерных в [0,1]^n. Методы ближайших соседей нарушаются, потому что 'ближайший' и 'самый дальний' становятся неразличимыми.
Рецепт Хэмминга: поймите геометрию перед тем, как доверять своей интуиции. В высокомерных пространствах геометрия является контринтуитивной, а математика — единственный надежный путеводитель.