un — Hình học của các Ứng dụng Máy tính

un

khách

1 / ?

trở lại bài học

Suy diễn Phương trình Logistic

Đường cong S của Hamming có một suy diễn toán học chính xác. Bắt đầu với hai quan sát về việc áp dụng công nghệ:

1. Tốc độ áp dụng tăng tốc với mức áp dụng hiện tại (truyền miệng, hiệu ứng mạng): dP/dt ∝ P

2. Tốc độ áp dụng giảm tốc khi thị trường bão hòa: dP/dt ∝ (1 − P)

Kết hợp: dP/dt = r · P · (1 − P)

Đây là phương trình vi phân logistic. Nó tách biến được: phân tích phân số riêng cho phép tích phân trực tiếp.

Suy diễn

Tách biến: dP / [P(1−P)] = r dt

Phân số riêng: 1/[P(1−P)] = 1/P + 1/(1−P)

Tích phân hai vế: ln(P) − ln(1−P) = rt + C

ln[P/(1−P)] = rt + C

P/(1−P) = e^(rt+C) = e^C · e^(rt)

Đặt K = e^C. Giải P: P = K·e^(rt) / (1 + K·e^(rt))

Tương đương: P(t) = 1 / (1 + e^(−r(t − t₀)))

trong đó t₀ = (ln K)/r là điểm uốn.

Điểm Uốn

Tại t = t₀: P = 0.5. Đạo hàm bậc hai d²P/dt² = 0: tốc độ tăng trưởng tối đa. Trước t₀: lõm lên (tăng tốc). Sau t₀: lõm xuống (giảm tốc).

Hình học Ứng dụng Máy tính: Metcalfe & Bề mặt Tối ưu hóa

Khớp Logistic với Dữ liệu

Cho hai điểm dữ liệu trên một đường cong logistic, bạn có thể giải cả r và t₀.

Áp dụng Internet: P(1995) = 0.01 (1% hộ gia đình Hoa Kỳ), P(2005) = 0.70 (70%).

Sử dụng P(t) = 1/(1 + e^(−r(t−t₀))), thiết lập hai phương trình từ các điểm dữ liệu P(1995)=0.01 và P(2005)=0.70. Từ P(2005)=0.70: tính t₀ bằng ln[P/(1−P)] = r(t−t₀). Sau đó dùng cả hai phương trình để giải r. Trình bày tất cả đại số. Giá trị r của bạn dự đoán P(2010) là gì?

Giá trị Mạng như một Đếm Hình học

Hamming lưu ý rằng các ứng dụng thúc đẩy việc áp dụng máy tính nhiều hơn phần cứng hay phần mềm. Các ứng dụng phụ thuộc mạng tuân theo một mô hình tăng trưởng cụ thể: giá trị tăng nhanh hơn chi phí.

Định luật Metcalfe

Giá trị của một mạng với n người dùng tỷ lệ với số kết nối có thể giữa các người dùng:

V(n) = k · n(n−1)/2 ≈ k · n²/2 (với n lớn)

trong đó k là giá trị một kết nối. Chi phí mạng: C(n) ∝ n (xấp xỉ tuyến tính theo số người dùng).

Tỷ lệ giá trị-chi phí: V/C ∝ n²/n = n. Khi n tăng, tỷ lệ tăng tuyến tính. Một mạng có 10x người dùng cung cấp khoảng 100x giá trị với chỉ 10x chi phí.

Bức tranh Hình học

Với n nút, số cạnh trong đồ thị đầy đủ K_n là C(n,2) = n(n−1)/2. Đây là một công thức tổ hợp: chọn 2 nút từ n. Với n=10: C(10,2)=45. Với n=100: C(100,2)=4950. Với n=1000: C(1000,2)=499,500.

Đường cong S và Định luật Metcalfe tương tác: trong giai đoạn 2 áp dụng nhanh, n tăng nhanh, và V(n) tăng theo n². Điểm uốn giá trị xảy ra trước điểm uốn áp dụng — giá trị tăng tốc trước áp dụng, kéo theo nhiều áp dụng hơn trong vòng phản hồi tích cực.

Giá trị Mạng ở các Mức Áp dụng Khác nhau

Áp dụng email: năm 1985 (n=100,000 người dùng), k = $0.01 mỗi kết nối-năm. Năm 1995 (n=30,000,000 người dùng).

Tính V(1985) = k · n(n−1)/2 và V(1995) = k · n(n−1)/2 sử dụng các giá trị đã cho. Tỷ số V(1995)/V(1985) là bao nhiêu? Sau đó tính tỷ số tăng trưởng người dùng n(1995)/n(1985). Tỷ số tăng trưởng giá trị so với tăng trưởng người dùng cho biết điều gì về việc tại sao email trở nên không thể thiếu một cách đột ngột vào đầu những năm 1990?

Tối ưu hóa như Hình học

Câu chuyện băng Boeing của Hamming mô tả một sự thất bại tối ưu hóa với ý nghĩa hình học chính xác. Tối ưu hóa một hàm f(x) trên một bề mặt đòi hỏi:

1. Một hàm f được định nghĩa rõ ràng: mục tiêu (lực cản, chi phí, thời gian ra thị trường)

2. Một bề mặt cố định: f được đánh giá ở cùng trạng thái mỗi lần

3. Một gradient: hướng cải thiện dốc nhất

Khi bề mặt thay đổi giữa các phép đo, gradient bạn ước tính có thể chỉ theo một hướng không còn tồn tại khi bạn thực hiện bước tiếp theo. Bạn đang tính gradient(f₁) nhưng bước vào bề mặt f₂.

Gradient Descent

Gradient descent chuẩn: x_{t+1} = x_t − α ∇f(x_t)

trong đó α = kích thước bước (tốc độ học), ∇f = vectơ gradient (đạo hàm riêng phần).

Sự thất bại Boeing: tại thời điểm t, nhóm đo f(x_t). Tại thời điểm t+1, nhóm thay đổi x thành x_t + Δx. Nhưng cơ sở dữ liệu dùng chung cũng thay đổi: f giờ là f' ≠ f. Thay đổi quan sát được: f'(x_t + Δx) − f(x_t). Đây KHÔNG phải là gradient của f, nó bao gồm một số hạng từ sự dịch chuyển bề mặt.

Gradient Ảo

Thay đổi đo được = [f'(x+Δx) − f(x)] = [f(x+Δx) − f(x)] + [f'(x+Δx) − f(x+Δx)]

= gradient thực × Δx + dịch chuyển bề mặt

Nếu sự dịch chuyển bề mặt chiếm ưu thế: nhóm di chuyển về phía cực tiểu trong f' mà là cực đại trong f. Họ tối ưu hóa sai điều, có thể làm cho thiết kế của họ tồi hơn trong khi các phép đo cho thấy sự cải thiện.

Định lượng Lỗi Gradient Ảo

Một nhóm tối ưu hóa lực cản f(θ, s) trong đó θ = góc cánh, s = sải cánh. Gradient thực: ∂f/∂θ = −0.5 (lực cản giảm theo θ), ∂f/∂s = +0.3 (lực cản tăng theo s).

Một nhóm khác đồng thời giảm trọng lượng thân máy bay, làm thay đổi hàm lực cản: f' = f − 0.8. (Thân máy bay nhẹ hơn giảm lực cản 0.8 đơn vị ở tất cả các cấu hình.)

Nhóm đầu tiên đo: f'(θ+Δθ, s) − f(θ, s) = [f(θ+Δθ, s) − 0.8] − f(θ, s) = −0.5·Δθ − 0.8.

Nếu nhóm đầu tiên đặt Δθ = 1 (thay đổi góc cánh 1 đơn vị), thay đổi đo được là bao nhiêu? Họ quy nó cho điều gì? Đóng góp thực tế của sự thay đổi góc cánh của chính họ so với đóng góp ảo từ sự thay đổi thân máy bay là gì? Trình bày phép tính và giải thích: liệu gradient ảo có thể khiến nhóm dừng tối ưu hóa θ sớm không?