Dlaczego Istotne Są Faktoriali
Hamming zaczyna rozdział 9 odstrzegając, że wszelkie problemy projektowania inżynierskiego istnieją w przestrzeni n-wymiarowej, gdzie n liczba niezależnych parametrów. Zrozumienie tego wymaga zrozumienia faktoriali — pojawiają się one w formule objętości dla każdej n-wymiarowej sfery.
Aproksymacja Stirlinga
Obliczanie n! bezpośrednio staje się niemożliwe dla dużych n. Formuła Stirlinga daje dokładne aproksymacje:
n! ≈ √(2πn) · (n/e)^n
Biorąc logarytmy (co Hamming robi, aby przekształcić produkt w sumę):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Aproksymacja ulepsza się w miarę jak n rośnie: stosunek Stirling(n)/n! → 1 gdy n → ∞. Jednak różnica bezwzględna rośnie nieskończenie dużo. Obie fakty zachodzą jednocześnie.
Ścieżka Hamminga w derywacji: aproksymuje sumę Σ ln(k) dla k=1..n przez całkę ∫ ln(x) dx od 1 do n za pomocą reguły trapezu, a następnie bierze wykładnik. Stała √(2π) pochodzi z zachowania ostatecznego błędu trapezu.
| n | Stirling | Prawdziwe n! | Stosunek | |---|---|---|---| | 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 |
Wykorzystanie Aproksymacji Stirlinga
Logarytmiczna forma aproksymacji Stirlinga okazuje się najbardziej przydatna w obliczeniach stosunków, gdzie skala absolutna anuluje się:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Funkcja Gamma
Faktorial n! ma sens tylko dla liczb całkowitych nieujemnych. Hamming potrzebuje wzoru na objętość kuli dla wszystkich dodatnich rzeczywistych n, dlatego wprowadza funkcję Gamma:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (konwerguje dla n > 0)
Integracja przez części daje wzór redukcyjny: Γ(n) = (n−1) · Γ(n−1).
Dla liczb całkowitych dodatnich: Γ(n) = (n−1)! więc Γ(5) = 4! = 24.
Dla pół-liczb całkowitych: Γ(1/2) = √π ≈ 1.772. To wynika z integralu Gauss'a ∫₋∞^∞ e^(−x²) dx = √π.
Wartości, które potrzebujemy dla objętości kul: Γ(n/2 + 1) dla argumentów pół-liczb całkowitych.
| 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 |
Formuła i paradoks
Z pomocą Stirlinga i funkcji Gamma, Hamming oblicza objętość n-wymiarowej kuli o promieniu r:
V_n(r) = C_n · r^n gdzie C_n = π^(n/2) / Γ(n/2 + 1)
Stała C_n zależy tylko od n, a nie od r. Pierwsze wartości:
| 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 |
Paradoks: C_n osiąga maksimum w okolicy n=5 (C_5 ≈ 5.264), a następnie spada z powrotem w kierunku zera. Jednostkowa kula w bardzo wysokich wymiarach ma niemalże zerową objętość - nawet choć intuicyjnie dodawanie kolejnych wymiarów powinno dodawać więcej przestrzeni.
Dlaczego objętość się załamuje?
Kluczowe: objętość = C_n · r^n. Gdy r < 1, r^n → 0 wykładniczo. Ograniczenie promienia zabija objętość szybciej niż wzrost wymiarowości. Niemal cała objętość n-wymiarowej hiperkubka leży na krawędziach, poza opisaną kulą.
Paradoks krawędzi
W 2D: prostokąt jednostkowy [−1,1]^2 ma obszar 4. Wspólny krąg ma obszar π ≈ 3,14. Krąg wypełnia 78% prostokąta.
W 3D: prostą jednostkową [−1,1]^3 ma objętość 8. Wspólny kulisty obiekt ma objętość 4π/3 ≈ 4,19. Kula wypełnia 52%.
W n wymiarach: jednostkowy hiperprostokąt [−1,1]^n ma objętość 2^n. Wspólny kulisty obiekt ma objętość C_n. Frakcja wewnątrz kuli:
f(n) = C_n / 2^n
Podczas wzrostu n: C_n → 0 podczas gdy 2^n → ∞. Dlatego f(n) → 0 szybko. W 10D, kula wypełnia mniej niż 0,3% prostokąta.
Skutki dla inżynierii: w przestrzeni projektowej o wysokich wymiarach nie można próbować próbować losowych punktów. Blisko wszystkie punkty losowe wpadną w kąty, daleko od centrum. Intuicja zbudowana w 3D całkowicie się zawodzi.
Dlaczego Intuicja 3D Pada
Podstawowy komunikat Hamminga w rozdziale 9: każde system inżynieryjne o n niezależnych parametrach funkcjonuje w przestrzeni o n wymiarach. Aerodynamika, systemy sterowania, projekt czujników, molekuły leków - wszystko to wiąże się z przestrzeniami parametrów o n >> 3.
Trzy konkretne niepowodzenia intuicji 3D w wysokich wymiarach:
1. Odległości przekątnych. W 3D, przekątna prostokąta jednostkowego ma długość √3 ≈ 1,73. W jednostkowym hiperprostokącie o n wymiarach, przekątna ma długość √n. Gdy n=100, długość przekątnej wynosi 10 - a jednak każdy koordynat biegnie od 0 do 1. Punkty, które wyglądają 'blisko' w dowolnym jednym wymiarze, są daleko od siebie w przestrzeni o n wymiarach.
2. Koncentracja objętości. Jak pokazano wyżej: objętość skupia się w kątach, a nie w centralnym kulistym obiekcie. Twój przekonanie, że centrum przestrzeni jest typowe, zawodzi.
3. Liczenie sąsiedników. W 2D punkt ma około πr² sąsiedników w promieniu r. W nD liczba sąsiedników wzrasta jako C_n·r^n, co dla dużego n jest skutecznie zero dla małego r. Obszary kolapsują.
Zakończenie Hamminga: 'Prostu nie możesz sobie wyobrazić, co się dzieje w przestrzeni n-wymiarowej.' Musisz polegać na matematyce - na wzorach dla objętości, odległości i prawdopodobieństwa - a nie na wyobraźni.
Zastosowanie Geometrii
Kolaps objętości sfery ma konkretne skutki dla współczesnej praktyki:
Optymalizacja: obniżanie się wzdłuż gradientu w przestrzeniach wysokowymiarowych parametrów działa lepiej niż losowy poszukiwanie, dokładnie dlatego, że wykorzystuje lokalne informacje o wektorze gradientu do nawigacji w strukturze kątów i próżni.
Nauka maszynowa: przestrzenie wag sieci neuronowych mają miliony wymiarów. Geometria przewiduje, że inicjalizacja losowa rzadko znajduje się w pobliżu dobrej rozwiązania - jednak proces uczenia się porusza się w kierunku tego lastura przez strukturalne kroki po krok gradientu.
Projekt eksperymentu: pokrycie przestrzeni parametrów wysokowymiarowych próbkami wymaga eksponentialnie wiele punktów. To motywuje strukturalne projekty eksperymentalne (myszki hipерпowierzchniowe, projekty wypełniające przestrzeni)