Skala logarytmiczna silni
Przybliżenie Stirlinga przekształca iloczyn w sumę, co jest fundamentalnym krokiem, który czyni matematykę dla dużych n łatwą do opanowania:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Ten wzór powstaje z przybliżenia sumy Σ ln(k) dla k=1..n przez całkę z ln(x), a następnie stosowania reguły trapezów do ograniczenia błędu.
Dlaczego to ma znaczenie geometryczne
Wzór na objętość sfery n-wymiarowej obejmuje Γ(n/2 + 1), który dla całkowitych n równa się (n/2)! lub iloczynom liczb półcałkowitych. Przybliżenie Stirlinga pozwala nam oszacować je dla dużych n bez bezpośredniego obliczania każdej wartości.
Przybliżenie Stirlinga daje log(n!) ≈ n·log(n) − n·log(e) w notacji o podstawie 10, przydatne do oszacowań rzędu wielkości.
Dla n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (prawda: 15.104).
Dla n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (prawda: 363.74).
Przybliżenie Stirlinga dla n=20
Bezpośrednie obliczenia: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Wzór na objętość
Objętość sfery n-wymiarowej o promieniu r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
Wartości C_n dla małych n następują wzorzec przy użyciu Γ(1/2) = √π i wzoru redukcyjnego:
- 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
Zwróć uwagę: C_n osiąga szczyt blisko n=5 (≈ 5.264), a następnie maleje. Dla dużych n, C_n → 0.
Maksimum dla n=5
C_5 = 8π²/15. Przy π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Aby sprawdzić, że to maksimum: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Zatem C_6 < C_5 — szczyt miał miejsce dla n=5.
Frakcja objętości w narożnikach
Paradoks narożników skwantyfikowany: jaka część n-wymiarowego hipersześcianu jednostkowego [−1,1]^n leży poza wpisaną sferą o promieniu 1?
Corner fraction = 1 − C_n / 2^n
| n | C_n | 2^n | Frakcja sfery | Frakcja narożników | |---|---|---|---|---| | 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% |
Implikacje dla optymalizacji
Paradoks narożników ma bezpośrednie konsekwencje dla optymalizacji w przestrzeniach wysokowymiarowych:
Poszukiwanie losowe zawodzi. Losowy punkt w n-wymiarowej przestrzeni parametrów prawie na pewno wyląduje w narożniku — daleko od początku, z ekstremalnymi wartościami parametrów. Jeśli dobre rozwiązania skupiają się blisko umiarkowanych wartości parametrów, poszukiwanie losowe prawie nigdy ich nie znajdzie.
Spadek gradientu się powiada. Postępując za lokalnym gradientem, poruszasz się przez geometrię systematycznie, a nie poprzez losowe próbkowanie. Przekleństwo wymiarowości dotyczy metod losowych; metody strukturalne się przystosowują.
Odległość się koncentruje. W wysokich wymiarach wszystkie parami odległości między losowymi punktami skupiają się wokół tej samej wartości: wszystkie stają się w przybliżeniu √(2n/3) dla punktów jednorodnych w [0,1]^n. Metody k-najbliższych sąsiadów się psują, ponieważ 'najbliższy' i 'najdalszy' stają się nie do odróżnienia.
Prescripcja Hamminga: zrozum geometrię przed zaufaniem swojej intuicji. W przestrzeniach wysokowymiarowych geometria jest sprzeczna z intuicją, a matematyka jest jedynym niezawodnym przewodnikiem.