Thang logarit của giai thừa
Xấp xỉ Stirling chuyển đổi một tích thành một tổng, đó là bước cơ bản làm cho toán học lớn-n có thể xử lý được:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Công thức này xuất phát từ việc xấp xỉ tổng Σ ln(k) với k=1..n bằng tích phân của ln(x), sau đó áp dụng quy tắc hình thang để giới hạn lỗi.
Tại sao điều này quan trọng về mặt hình học
Công thức thể tích n-mặt cầu liên quan đến Γ(n/2 + 1), bằng (n/2)! hoặc tích các nửa số nguyên với số nguyên n. Stirling cho phép chúng ta ước tính những giá trị này cho n lớn mà không cần tính từng giá trị trực tiếp.
Xấp xỉ Stirling cho log(n!) ≈ n·log(n) − n·log(e) trong ký hiệu cơ số 10, hữu ích cho các ước tính độ lớn.
Với n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (thực: 15.104).
Với n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (thực: 363.74).
Stirling tại n=20
Một phép tính trực tiếp: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Công thức thể tích
Thể tích của một mặt cầu n-chiều với bán kính r:
V_n(r) = C_n · r^n trong đó C_n = π^(n/2) / Γ(n/2 + 1)
Các giá trị C_n cho n nhỏ tuân theo một mô hình sử dụng Γ(1/2) = √π và công thức rút gọn:
- 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
Chú ý: C_n đạt cực đại gần n=5 (≈ 5.264) sau đó giảm. Với n lớn, C_n → 0.
Cực đại tại n=5
C_5 = 8π²/15. Với π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Để xác minh đây là cực đại: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Vì vậy C_6 < C_5 — đỉnh xuất hiện tại n=5.
Phần thể tích trong góc
Nghịch lý góc được định lượng: bao nhiêu phần của siêu lập phương đơn vị n-chiều [−1,1]^n nằm ngoài mặt cầu nội tiếp bán kính 1?
Phần góc = 1 − C_n / 2^n
| n | C_n | 2^n | Phần mặt cầu | Phần góc | |---|---|---|---|---| | 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% |
Ý nghĩa cho tối ưu hóa
Nghịch lý góc có hậu quả trực tiếp cho tối ưu hóa trong không gian cao chiều:
Tìm kiếm ngẫu nhiên thất bại. Một điểm ngẫu nhiên trong không gian thông số n-chiều gần như chắc chắn rơi vào một góc — xa gốc tọa độ, với các giá trị thông số cực trị. Nếu các giải pháp tốt tập trung gần các giá trị thông số vừa phải, tìm kiếm ngẫu nhiên gần như sẽ không bao giờ tìm thấy chúng.
Giảm dốc thành công. Bằng cách theo dõi gradient cục bộ, bạn điều hướng hình học một cách có hệ thống hơn là lấy mẫu nó một cách mù quáng. Lời nguyền của chiều cao tác động đến các phương pháp ngẫu nhiên; các phương pháp có cấu trúc thích ứng.
Khoảng cách tập trung. Trong không gian cao chiều, tất cả các khoảng cách cặp giữa các điểm ngẫu nhiên tập trung xung quanh cùng một giá trị: tất cả chúng xấp xỉ √(2n/3) cho các điểm đồng nhất trong [0,1]^n. Các phương pháp láng giềng gần nhất bị phá vỡ vì "gần nhất" và "xa nhất" trở nên không phân biệt được.
Đơn vị dự báo của Hamming: hiểu hình học trước khi tin tưởng vào trực giác của bạn. Trong không gian cao chiều, hình học là phản trực giác, và toán học là hướng dẫn duy nhất đáng tin cậy.