Dichotomies trên Đám mây Điểm

Shattering Trông Như Thế Nào

Đặt n điểm trong mặt phẳng của chúng ta. Chọn một lớp giả thuyết (bộ phân loại tuyến tính = đường thẳng). Đếm có bao nhiêu cách riêng biệt lớp này có thể gán nhãn cho n điểm đó (+/− trên mỗi bên của một đường thẳng). Gọi số lượng này là Π_H(n).

Nếu Π_H(n) = 2ⁿ, lớp của chúng ta shatters tập điểm đó — nó có thể tạo ra mỗi gán nhãn có thể. Nếu Π_H(n) < 2ⁿ, một số gán nhãn không thể xảy ra.

Ba Điểm Ở Vị trí Chung

Bộ phân loại tuyến tính trong ℝ² shatters bất kỳ 3 điểm không cộng tuyến. 2³ = 8 gán nhãn; tất cả 8 đạt được bằng một số đường thẳng. Chọn bất kỳ 3 điểm nào; cho mỗi ±/± gán nhãn, vẽ một đường thẳng tách những điểm dương từ những điểm âm.

Bốn Điểm Từ chối Shattering

Đặt 4 điểm tại các góc của một hình vuông. Cố gắng gán nhãn cặp đường chéo là dương & cặp đường chéo đối là âm (gán nhãn XOR). Không có đường thẳng tách chúng. Vì vậy Π_H(4) ≤ 14 < 16 = 2⁴.

Chiều VC như Kích thước Tối đa Shattering

VC(tuyến tính ℝ²) = 3. Chúng ta có thể shatter 3 điểm; chúng ta không thể shatter 4. VC đếm công suất dichotomy tối đa của lớp giả thuyết của chúng ta.

Trực giác Hình học

VC cao hơn = lớp của chúng ta vẽ các ranh giới quyết định phức tạp hơn. Tuyến tính (VC = d+1 trong d chiều) vẽ siêu phẳng. Đa thức vẽ đường cong. Mạng nơ-ron vẽ các đa tạp gập cao. Tính gập cao hơn = hơn dichotomies = VC cao hơn = yêu cầu mẫu cao hơn.

Đếm Dichotomies

Xem xét các bộ phân loại tuyến tính trong ℝ² (đường thẳng). Chúng ta có 5 điểm được đặt ở vị trí chung (không có 3 cộng tuyến, không có gì dư thừa).

Khối lượng Xác suất trên Đa tạp Giả thuyết

Hình ảnh PAC-Bayes

Hình dung không gian giả thuyết của chúng ta như một đa tạp chiều cao. Mỗi điểm trên đa tạp này tương ứng với một cấu hình trọng số của mạng nơ-ron. Prior P gán một phân phối xác suất trên đa tạp của chúng ta (thường là Gaussian tập trung tại khởi tạo). Posterior Q tập trung khối lượng xác suất nơi dữ liệu huấn luyện dẫn trọng số của chúng ta.

KL Divergence như Khoảng cách Hình học

KL(Q‖P) đo mức độ Q lệch khỏi P. Đọc hình học: Q cloud di chuyển bao xa khỏi P cloud, có trọng số bằng cách mỗi vùng posterior không có khả năng như thế nào dưới prior của chúng ta.

KL nhỏ = Q chồng lấp P nặng nề. Posterior gần như chưa di chuyển. Khoảng cách tổng quát nhỏ.

KL lớn = Q tập trung vào các vùng P gán ít khối lượng. Posterior di chuyển nhiều. Khoảng cách tổng quát tăng.

Tại sao Hình học này Quan trọng

Hãy tưởng tượng SGD như một quỹ đạo tìm kiếm trên đa tạp giả thuyết của chúng ta. Quỹ đạo kết thúc tại một bể của mất mát huấn luyện thấp. PAC-Bayes hỏi: bể này rộng bao nhiêu?

Bể rộng = nhiều cấu hình trọng số lân cận cũng đạt được mất mát huấn luyện thấp. Posterior Q có thể lan rộng trên một vùng rộng & vẫn có rủi ro thấp. KL(Q‖P) vẫn bị ràng buộc. Khoảng cách tổng quát nhỏ.

Bể hẹp = chỉ có một tập hợp mỏng của các trọng số đạt được mất mát thấp. Posterior phải tập trung sắc nét. KL tăng. Khoảng cách tổng quát mở rộng.

Điều này kết nối trực tiếp với cuộc thảo luận flat-vs-sharp minima (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Minima phẳng tổng quát tốt hơn vì chúng hỗ trợ những posterior rộng hơn với KL nhỏ hơn.

Đọc Chiều rộng Bể

Hai mô hình được huấn luyện đạt được mất mát huấn luyện giống hệt nhau nhưng sống trong các bể khác nhau:

- Model A: bể phẳng, posterior lan rộng trên vùng với KL(Q_A‖P) = 50 nats.

- Model B: bể sắc nét, posterior tập trung với KL(Q_B‖P) = 500 nats.

Cả hai được huấn luyện trên n = 10.000 ví dụ với rủi ro thực nghiệm 0,05, δ = 0,05.

Một Đường cong Rơi Nơi Lý thuyết Dự đoán Sẽ Tăng

U-Curve Cổ điển

Vẽ công suất mô hình trên trục ngang. Vẽ rủi ro kiểm tra trên trục dọc. Lý thuyết bias-variance cổ điển dự đoán:

- Công suất thấp: bias cao, rủi ro kiểm tra cao (underfit)

- Công suất trung bình: bias thấp + phương sai thấp, rủi ro kiểm tra thấp (sweet spot)

- Công suất cao: bias thấp, phương sai cao, rủi ro kiểm tra cao (overfit)

Kết quả: đường cong hình chữ U. Chọn công suất ở dưới cùng của chúng ta.

Những Gì Belkin et al (2019) Quan sát

Quá ngưỡng nội suy (công suất nơi mô hình phù hợp chính xác dữ liệu huấn luyện với lỗi bằng không), rủi ro kiểm tra GIẢM lại. Đường cong đọc: xuống dốc → đỉnh tại nội suy → xuống dốc thứ hai. Hai xuống dốc, một đường cong.

Đọc Hình học của Xuống dốc Thứ hai

Tại ngưỡng nội suy, mô hình có đủ công suất để phù hợp dữ liệu huấn luyện — chỉ một (hoặc ít) các giải pháp nội suy tồn tại & chúng có xu hướng là lồi. Tổng quát hóa bị suy yếu vì giải pháp được chọn là bắt buộc.

Quá ngưỡng nội suy, NHIỀU giải pháp nội suy tồn tại. SGD có tự do để chọn một giải pháp mịn (chuẩn tối thiểu, độ cong thấp). Hình ảnh hình học: đa tạp tập giải pháp trở nên rộng hơn & phẳng hơn. Sự chính quy hóa ngầm của SGD chọn các giải pháp tốtnh từ đa tạp phẳng này. Rủi ro kiểm tra giảm.

Tại sao Lý thuyết Cổ điển Bỏ lỡ Điều này

Chiều VC đếm công suất tập giải pháp nhưng bỏ qua giải pháp nào được chọn. Giới hạn cổ điển giả định trường hợp xấu nhất của những người cực tiểu hóa rủi ro thực nghiệm. Thực tế: SGD đáng tin cậy chọn giải pháp nội suy phẳng, mượt mà nhất. Khi chúng ta đếm các giải pháp được chọn bởi bộ giải THAY VÌ tất cả các giải pháp, xuống dốc thứ hai có ý nghĩa.

Lựa Chọn Hình học-Lấy-Nhà

Công suất quan trọng ít hơn hình học bể. Các bể phẳng rộng (sau nội suy) tổng quát hóa tốt hơn so với những bể hẹp sắc nét (tại nội suy). Lý thuyết hiện đại cố gắng ràng buộc tổng quát hóa bằng chiều rộng bể, không phải bằng số lượng tham số.

Định vị Hai Xuống dốc

Trên một đường cong double descent, ba vùng quan trọng: (1) chế độ under-parameterized, (2) đỉnh nội suy, (3) chế độ over-parameterized.

Bề mặt Luật Lũy thừa trong Không gian Tham số-Token

Một Bề mặt 3D

Vẽ tham số N trên một trục ngang. Vẽ tokens D trên một trục ngang thứ hai. Vẽ mất mát L trên trục dọc. Mất mát thực nghiệm khắc một bề mặt luật lũy thừa trên mặt phẳng (N, D) này:

L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞

Bề mặt dốc xuống khi N hoặc D tăng. Độ dốc tuân theo các luật lũy thừa log-tuyến tính (đường thẳng trong biểu đồ log-log). Tiệm cận L∞ vẫn dương — mất mát không thể giảm được mô hình của chúng ta không thể co lại.

Tính toán-Tối ưu Ridge

Sửa ngân sách tính toán tổng C ∝ N × D (tham số × tokens, đại khái). Cắt bề mặt của chúng ta dọc theo ràng buộc này. Lát cắt theo dõi một đường cong 2D thông qua bề mặt 3D. Dưới cùng của đường cong này = điểm tính toán-tối ưu.

Chinchilla (Hoffmann et al 2022) tính toán dưới cùng này phân tích: D_opt ≈ 20 × N. Đường cong dọc theo ngân sách tính toán = một ridge. Bước dọc theo ridge: tính toán bằng nhau, giảm mất mát. Bước ra ngoài ridge (tham số nhiều hơn 20× tokens, hoặc ít hơn): lãng phí tính toán.

Đọc Hình học của GPT-3 vs Chinchilla

GPT-3: 175B tham số, 300B tokens. Chinchilla-optimal sẽ muốn 175B × 20 = 3500B tokens. GPT-3 ngồi xa ridge tính toán-tối ưu trong hướng nặng tham số của chúng ta. Chinchilla chính nó: 70B tham số được huấn luyện trên 1400B tokens. 1400 / 70 = 20 — chính xác trên ridge. Chinchilla đánh bại GPT-3 với ít hơn nửa số lượng tham số của nó bằng cách ngồi trên tối ưu hình học.

Bức tường Dữ liệu như Máy bay Dọc

Web công cộng ~10¹³ tokens có thể sử dụng được. Điều này vẽ như một bức tường dọc tại D = 10¹³ trên mặt phẳng tham số-token của chúng ta. Vượt qua bức tường này, huấn luyện tính toán-tối ưu yêu cầu N ≤ D / 20 = 5 × 10¹¹ tham số. Bức tường vượt N = 5 × 10¹¹ hoặc chạy dưới-huấn luyện (off-ridge) hoặc yêu cầu dữ liệu tổng hợp / đa phương thức / RL để đẩy bức tường ra ngoài.

Bước trên Ridge Tính toán-Tối ưu

Chúng ta ngồi tại các tọa độ GPT-3: N = 175B tham số, D = 300B tokens. Proxy tính toán C = N × D = 5,25 × 10²² param-tokens.

Posterior Beta Siết chặt thành một Sợi Kim

Mật độ Xác suất trên [0, 1]

Beta(α, β) là một mật độ xác suất trên khoảng đơn vị [0, 1]. Biến: ε = tỷ lệ lỗi thực sự. Hình dạng: α điều khiển khối lượng trên phía ε cao; β điều khiển khối lượng trên phía ε thấp.

Beta(1, 1): đồng đều — không có thông tin, mật độ phẳng trên [0, 1].

Beta(α, β) với α + β lớn: đỉnh tập trung tại α / (α + β).

Chiều rộng của đỉnh Beta thu nhỏ như 1/√(α+β). Thêm 100 quan sát vào prior của chúng ta siết chặt đỉnh theo hệ số √100 = 10. Thêm 10000 quan sát siết chặt theo √10000 = 100.

Đọc Hình học của Một Lần Chạy Kiểm toán

Bắt đầu: Beta(1, 1) = hình chữ nhật phẳng trên [0, 1]. Sự không chắc chắn tối đa về ε.

Sau 200 truy vấn với 8 lần sai vạch: Beta(9, 193). Trung bình = 9/202 ≈ 0,045. Mật độ bây giờ là một bầu sáng tập trung gần 0,045 với chiều rộng đặc trưng σ ≈ 0,014.

Sau 2000 truy vấn với 80 lần sai vạch: Beta(81, 1921). Trung bình vẫn ≈ 0,045, nhưng chiều rộng σ ≈ 0,0046. Bầu ba lần sắc hơn.

Sau 200.000 truy vấn với 8000 lần sai vạch: Beta(8001, 192,001). Trung bình ≈ 0,040, chiều rộng σ ≈ 0,0004. Bầu trở thành một sợi kim.

Hội tụ Hình học đến Một Khối lượng Điểm

Khi n → ∞, posterior Beta sụp xuống một Dirac delta tại ε thực sự. Hình học: hình chữ nhật → bầu rộng → bầu hẹp → sợi kim → điểm. Mỗi truy vấn siết chặt phân phối của chúng ta theo 1/√n.

Tại sao Điều này Đánh Bại Các Giới hạn PAC Lý thuyết

Các giới hạn PAC lý thuyết cung cấp một ước tính ε TĨNH dựa trên kích thước lớp giả thuyết. Posterior Beta cung cấp một ước tính ε ĐỘNG siết chặt với mỗi quan sát, được hiệu chỉnh so với phân phối thế giới thực của chúng ta. Giới hạn lý thuyết = một bảo đảm trong các giả định trường hợp xấu nhất. Kiểm toán thực nghiệm = một phép đo thực tế.

Cần Bao nhiêu Truy vấn để Chia đôi Khoảng Tin cậy?

Chúng ta hiện ngồi tại Beta(9, 193) sau 200 truy vấn: trung bình ε ≈ 0,045, σ ≈ 0,014. Chúng ta muốn chia đôi chiều rộng khoảng tin cậy thành σ ≈ 0,007.