Чому факторіали важливі
Гаммінг розпочинає розділ 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 | Stirling | Істинний 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-просторі.' Ви повинні покладатися на математику — на формули для об'єму, відстані та ймовірності — а не на уяву.
Застосування геометрії
Розпад об'єму сфери має конкретні наслідки для сучасної практики:
Оптимізація: градієнтний спуск у високорозмірних просторах параметрів працює краще, ніж випадковий пошук, саме тому, що він використовує інформацію про локальний градієнт, щоб навігувати структуру кутів та порожнеч.
Машинне навчання: простори ваг нейронних мереж мають мільйони розмірностей. Геометрія передбачає, що випадкова ініціалізація рідко приземляється біля гарного рішення — але процес навчання навігує до одного через структуровані кроки градієнта.
Дизайн експериментів: охоплення високорозмірного простору параметрів вибірками вимагає експоненціально багато точок. Це мотивує структуровані експериментальні дизайни (латинські гіперкуби, простори, що заповнюють місце) над випадковою вибіркою.