Почему факториалы важны
Хэмминг начинает главу 9 с замечания, что все инженерные задачи проектирования живут в n-мерном пространстве, где n — количество независимых параметров. Понимание этого пространства требует понимания факториалов — они появляются внутри формулы объёма для каждой n-мерной сферы.
Аппроксимация Стирлинга
Прямое вычисление n! становится невозможным для больших n. Формула Стирлинга даёт точное приближение:
n! ≈ √(2πn) · (n/e)^n
Взяв логарифмы (что делает Хэмминг, чтобы преобразовать произведение в сумму):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Приближение улучшается по мере роста n: отношение Stirling(n)/n! → 1 при n → ∞. Однако абсолютная разница растёт без границ. Оба факта верны одновременно.
Подход Хэмминга при выводе: аппроксимировать сумму Σ ln(k) для k=1..n интегралом ∫ ln(x) dx от 1 до n с помощью правила трапеций, затем взять экспоненту. Константа √(2π) возникает из предельного поведения ошибки трапеций.
| n | Стирлинг | Истинный n! | Отношение | |---|---|---|---| | 5 | 118.02 | 120 | 0.9835 | | 10 | 3,598,696 | 3,628,800 | 0.9917 | | 20 | ~2.423×10^18 | ~2.432×10^18 | 0.9958 |
Использование формулы Стирлинга
Логарифмический вид формулы Стирлинга наиболее полезен для вычисления отношений, где абсолютный масштаб сокращается:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Гамма-функция
Факториал n! имеет смысл только для неотрицательных целых чисел. Хэммингу нужна формула объёма сферы для всех положительных вещественных n, поэтому он вводит гамма-функцию:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (сходится при n > 0)
Интегрирование по частям даёт формулу редукции: Γ(n) = (n−1) · Γ(n−1).
При положительных целых числах: Γ(n) = (n−1)! поэтому Γ(5) = 4! = 24.
При полуцелых: Γ(1/2) = √π ≈ 1.772. Это возникает из гауссова интеграла ∫₋∞^∞ e^(−x²) dx = √π.
Значения, которые нам нужны для объёма сферы: Γ(n/2 + 1) при полуцелых аргументах.
| n | n/2 + 1 | Γ(n/2 + 1) | |---|---|---| | 1 | 3/2 | √π/2 ≈ 0.886 | | 2 | 2 | 1! = 1 | | 3 | 5/2 | 3√π/4 ≈ 1.329 | | 4 | 3 | 2! = 2 | | 5 | 7/2 | 15√π/8 ≈ 3.323 |
Формула & парадокс
С аппроксимацией Стирлинга и гамма-функцией в руках, Хэмминг выводит объём n-мерной сферы радиуса r:
V_n(r) = C_n · r^n где C_n = π^(n/2) / Γ(n/2 + 1)
Константа C_n зависит только от n, не от r. Первые значения:
| n | C_n | |---|---| | 1 | 2 | | 2 | π ≈ 3.142 | | 3 | 4π/3 ≈ 4.189 | | 4 | π²/2 ≈ 4.935 | | 5 | 8π²/15 ≈ 5.264 | | 6 | π³/6 ≈ 5.168 | | 8 | π⁴/24 ≈ 4.059 | | 10 | π⁵/120 ≈ 2.550 |
Парадокс: C_n растёт до максимума около n=5 (C_5 ≈ 5.264), затем падает обратно к нулю. Единичная сфера в очень высоких размерностях по сути не имеет объёма — даже хотя интуитивно добавление размерностей должно добавлять пространство.
Почему объём коллапсирует?
Ключ: объём = C_n · r^n. Когда r < 1, r^n → 0 экспоненциально. Ограничение на радиус убивает объём быстрее, чем размерность растёт. Почти весь объём n-мерного единичного гиперкуба находится в его углах, вне вписанной сферы.
Парадокс углов
В 2D: единичный квадрат [−1,1]^2 имеет площадь 4. Вписанный круг имеет площадь π ≈ 3.14. Круг занимает 78% квадрата.
В 3D: единичный куб [−1,1]^3 имеет объём 8. Вписанная сфера имеет объём 4π/3 ≈ 4.19. Сфера занимает 52%.
В n размерностях: единичный гиперкуб [−1,1]^n имеет объём 2^n. Вписанная сфера имеет объём C_n. Доля внутри сферы:
f(n) = C_n / 2^n
По мере роста n: C_n → 0 в то время как 2^n → ∞. Таким образом f(n) → 0 быстро. В 10D сфера занимает менее 0.3% куба.
Инженерное следствие: в высоко-мерном пространстве проектирования, нельзя исследовать путём выбора случайных точек. Почти все случайные точки приземлятся в углах, далеко от центра. Ваша интуиция, построенная в 3D, полностью не работает.
Почему 3D интуиция не работает
Центральное послание Хэмминга в главе 9: каждая инженерная система с n независимыми параметрами живёт в n-мерном пространстве. Аэродинамика, системы управления, проектирование чипов, молекулы лекарств — все включают пространства параметров с n >> 3.
Три специфических отказа 3D интуиции в высоких размерностях:
1. Диагональные расстояния. В 3D диагональ единичного куба имеет длину √3 ≈ 1.73. В n-мерном единичном гиперкубе диагональ имеет длину √n. Для n=100 длина диагонали 10 — всё ещё каждая координата бежит от 0 к 1. Точки, которые выглядят 'рядом' в любой единственной размерности, далеко друг от друга в n-мерном пространстве.
2. Концентрация объёма. Как показано выше: объём концентрируется в углах, не в центральной сфере. Ваша интуиция, что центр пространства типичен, разрушается.
3. Подсчёт соседей. В 2D точка имеет примерно πr² соседей в пределах радиуса r. В nD, подсчёт соседей масштабируется как C_n·r^n, которое для большого n по сути равно нулю для малого r. Окрестности коллапсируют.
Заключение Хэмминга: 'Вы просто не можете визуализировать, что происходит в n-пространстве.' Вы должны полагаться на математику — на формулы для объёма, расстояния и вероятности — не на воображение.
Применение геометрии
Коллапс объёма сферы имеет конкретные последствия для современной практики:
Оптимизация: градиентный спуск в высоко-мерных пространствах параметров работает лучше, чем случайный поиск именно потому, что он использует информацию локального градиента для навигации по структуре углов-и-пустот.
Машинное обучение: пространства весов нейронных сетей имеют миллионы размерностей. Геометрия предсказывает, что случайная инициализация редко приземляется рядом с хорошим решением — всё же процесс обучения навигирует к одному через структурированные шаги градиента.
Проектирование экспериментов: покрытие высоко-мерного пространства параметров выборками требует экспоненциально много точек. Это мотивирует структурированные экспериментальные проекты (латинские гиперкубы, пространство-заполняющие проекты) над случайной выборкой.