Dikotomi pada Awan Titik

Apa Shattering Terlihat Seperti

Tempatkan n titik di bidang kami. Pilih kelas hipotesis (pengklasif linear = garis lurus). Hitung berapa banyak cara berbeda kelas kami dapat memberi label titik-titik tersebut (+/− di setiap sisi garis). Sebut hitungan ini Π_H(n).

Jika Π_H(n) = 2ⁿ, kelas kami shatters set titik tersebut — dapat menghasilkan setiap kemungkinan pelabelan. Jika Π_H(n) < 2ⁿ, beberapa pelabelan tidak dapat terjadi.

Tiga Titik dalam Posisi Umum

Pengklasif linear dalam ℝ² shatters titik 3 yang tidak kolinear. 2³ = 8 pelabelan; semua 8 dapat dicapai oleh beberapa garis. Pilih titik apa pun 3; untuk setiap ±/± pelabelan, gambar garis yang memisahkan positif dari negatif.

Empat Titik Menolak Shattering

Tempatkan 4 titik di sudut persegi. Coba beri label pasangan diagonal sebagai positif & pasangan anti-diagonal sebagai negatif (pelabelan XOR). Tidak ada garis lurus yang memisahkan mereka. Jadi Π_H(4) ≤ 14 < 16 = 2⁴.

Dimensi VC sebagai Ukuran Shattering Maksimum

VC(linear ℝ²) = 3. Kami dapat shattering 3 titik; kami tidak dapat shattering 4. VC menghitung kapasitas dikotomi maksimum dari kelas hipotesis kami.

Intuisi Geometris

VC lebih tinggi = kelas kami menggambar batas keputusan yang lebih rumit. Linear (VC = d+1 dalam d dimensi) menggambar hiperplane. Polinomial menggambar kurva. Jaringan neural menggambar manifold yang sangat terlipat. Lipatan lebih = lebih banyak dikotomi = VC lebih tinggi = persyaratan sampel lebih tinggi.

Menghitung Dikotomi

Pertimbangkan pengklasif linear dalam ℝ² (garis). Kami memiliki 5 titik yang ditempatkan dalam posisi umum (tidak ada 3 kolinear, tidak ada yang berlebihan).

Massa Probabilitas pada Manifold Hipotesis

Membayangkan PAC-Bayes

Bayangkan ruang hipotesis kami sebagai manifold berdimensi tinggi. Setiap titik pada manifold ini sesuai dengan satu konfigurasi bobot jaringan neural. Prior P menetapkan distribusi probabilitas di seluruh manifold kami (sering Gaussian yang berpusat pada inisialisasi). Posterior Q memusatkan massa probabilitas di mana data pelatihan mendorong bobot kami.

Perbedaan KL sebagai Jarak Geometris

KL(Q‖P) mengukur seberapa jauh Q bergerak dari P. Bacaan geometris: seberapa jauh awan posterior kami bergerak dari awan prior, diboboti oleh seberapa tidak mungkin setiap wilayah posterior di bawah prior kami.

KL kecil = Q tumpang tindih P banyak. Posterior hampir tidak bergerak. Celah generalisasi tetap kecil.

KL besar = Q terkonsentrasi dalam wilayah yang P berikan sedikit massa ke. Posterior bergerak banyak. Celah generalisasi tumbuh.

Mengapa Geometri Ini Penting

Bayangkan SGD sebagai lintasan pencarian di seluruh manifold hipotesis kami. Lintasan berakhir di cekungan kehilangan pelatihan rendah. PAC-Bayes bertanya: seberapa lebar cekungan ini?

Cekungan lebar = banyak konfigurasi bobot tetangga juga mencapai kehilangan pelatihan rendah. Posterior Q dapat menyebar di wilayah lebar & masih memiliki risiko rendah. KL(Q‖P) tetap terbatas. Celah generalisasi kecil.

Cekungan sempit = hanya set bobot tipis yang mencapai kehilangan rendah. Posterior harus berkonsentrasi tajam. KL tumbuh. Celah generalisasi melebar.

Ini menghubungkan secara langsung ke diskursus minima datar-vs-tajam (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Minima datar menggeneralisasi lebih baik karena mendukung posterior yang lebih lebar dengan KL lebih kecil.

Membaca Lebar Cekungan

Dua model terlatih mencapai kehilangan pelatihan identik tetapi tinggal di cekungan berbeda:

- Model A: cekungan datar, posterior menyebar di wilayah dengan KL(Q_A‖P) = 50 nats.

- Model B: cekungan tajam, posterior berkonsentrasi dengan KL(Q_B‖P) = 500 nats.

Keduanya dilatih pada n = 10.000 contoh dengan risiko empiris 0,05, δ = 0,05.

Kurva yang Jatuh Di Mana Teori Memprediksi Naik

Kurva U Klasik

Plot kapasitas model pada sumbu horizontal. Plot risiko tes pada sumbu vertikal. Teori bias-varians klasik memprediksi:

- Kapasitas rendah: bias tinggi, risiko tes tinggi (underfitting)

- Kapasitas menengah: bias rendah + varians rendah, risiko tes rendah (sweet spot)

- Kapasitas tinggi: bias rendah, varians tinggi, risiko tes tinggi (overfitting)

Hasil: kurva berbentuk U. Pilih kapasitas di bagian bawah kami.

Apa yang Belkin et al (2019) Amati

Melewati ambang interpolasi (kapasitas di mana model cocok dengan data pelatihan dengan kesalahan nol), risiko tes JATUH lagi. Kurva membaca: descent → puncak pada interpolasi → descent kedua. Dua descent, satu kurva.

Bacaan Geometris Descent Kedua

Pada ambang interpolasi, model memiliki cukup kapasitas untuk menyesuaikan data pelatihan — hanya satu (atau sedikit) solusi yang menginterpolasi ada & mereka cenderung bergerigi. Generalisasi menderita karena solusi yang dipilih dipaksa.

Melewati ambang interpolasi, BANYAK solusi yang menginterpolasi ada. SGD memiliki kebebasan untuk memilih yang halus (norma minimum, kurva rendah). Gambar geometris: manifold solusi menjadi lebih lebar & lebih datar. Bias implisit SGD memilih solusi jinak dari manifold datar ini. Risiko tes jatuh.

Mengapa Teori Klasik Melewatkan Ini

Dimensi VC menghitung kapasitas set solusi tetapi mengabaikan solusi mana yang dipilih. Batas klasik mengasumsikan minimizer risiko empiris kasus terburuk. Realitas: SGD secara andal memilih solusi interpolasi paling datar & paling halus kami. Setelah kami menghitung solusi YANG DIPILIH-SOLVER daripada semua solusi, descent kedua masuk akal.

Pengambilan Geometri

Kapasitas penting lebih sedikit daripada geometri cekungan. Cekungan datar lebar (post-interpolasi) menggeneralisasi lebih baik daripada yang sempit tajam (pada interpolasi). Teori modern mencoba membatasi generalisasi dengan lebar cekungan, bukan dengan jumlah parameter.

Menemukan Dua Descent

Pada kurva double descent, tiga wilayah penting: (1) rezim under-parameterized, (2) puncak interpolasi, (3) rezim over-parameterized.

Permukaan Hukum Pangkat dalam Ruang Parameter-Token

Permukaan 3D

Plot parameter N pada sumbu horizontal satu. Plot token D pada sumbu horizontal kedua. Plot kehilangan L pada vertikal. Kehilangan empiris mengukir permukaan hukum pangkat di seluruh bidang (N, D):

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

Permukaan miring ke bawah saat N atau D tumbuh. Kemiringan mengikuti hukum pangkat log-linear (garis lurus dalam plot log-log). Asimptot L∞ tetap positif — kehilangan yang tidak dapat direduksi model kami tidak dapat menyusut melewatinya.

Ridge Compute-Optimal

Perbaiki anggaran compute total C ∝ N × D (parameter × token, kira-kira). Potong permukaan kami sepanjang batasan ini. Trace potongan memotong kurva 2D melalui permukaan 3D. Bagian bawah kurva ini = titik compute-optimal.

Chinchilla (Hoffmann et al 2022) menghitung bagian bawah ini secara analitik: D_opt ≈ 20 × N. Kurva sepanjang anggaran compute = ridge. Berjalan di sepanjang ridge: compute sama, kehilangan berkurang. Berjalan mati ridge (lebih banyak parameter daripada 20× token, atau lebih sedikit): compute terbuang.

Bacaan Geometris GPT-3 vs Chinchilla

GPT-3: 175B params, 300B tokens. Chinchilla-optimal ingin 175B × 20 = 3500B tokens. GPT-3 duduk jauh dari ridge compute-optimal dalam arah parameter-berat kami. Chinchilla itu sendiri: 70B params dilatih pada 1400B tokens. 1400 / 70 = 20 — persis di ridge. Chinchilla mengalahkan GPT-3 dengan kurang dari setengah jumlah parameternya dengan duduk di optimum geometris.

Dinding Data sebagai Bidang Vertikal

Web publik ~10¹³ token yang dapat digunakan. Ini plot sebagai dinding vertikal pada D = 10¹³ di bidang parameter-token kami. Melampaui dinding ini, pelatihan compute-optimal memerlukan N ≤ D / 20 = 5 × 10¹¹ params. Dinding melampaui N = 5 × 10¹¹ baik menjalankan under-trained (off-ridge) atau memerlukan data sintetis / multimodal / RL untuk mendorong dinding ke luar.

Berjalan di Ridge Compute-Optimal

Kami duduk di koordinat GPT-3: N = 175B params, D = 300B tokens. Proxy compute C = N × D = 5,25 × 10²² param-tokens.

Beta Posterior Mengencil Menjadi Jarum

Kepadatan Probabilitas pada [0, 1]

Beta(α, β) adalah kepadatan probabilitas di seluruh interval satuan [0, 1]. Variabel: ε = tingkat kesalahan benar. Bentuk: α mengontrol massa di sisi ε tinggi; β mengontrol massa di sisi ε rendah.

Beta(1, 1): uniform — tidak ada informasi, kepadatan datar di seluruh [0, 1].

Beta(α, β) dengan α + β besar: puncak terkonsentrasi pada α / (α + β).

Lebar puncak Beta menyusut sebagai 1/√(α+β). Menambahkan 100 pengamatan ke prior kami mengencilkan puncak dengan faktor √100 = 10. Menambahkan 10000 pengamatan mengencilkan dengan √10000 = 100.

Bacaan Geometris dari Jalannya Audit

Mulai: Beta(1, 1) = persegi panjang datar pada [0, 1]. Ketidakpastian maksimum tentang ε.

Setelah 200 kueri dengan 8 falsifikasi: Beta(9, 193). Rata-rata = 9/202 ≈ 0,045. Kepadatan sekarang bernyanyi tajam di dekat 0,045 dengan lebar karakteristik σ ≈ 0,014.

Setelah 2000 kueri dengan 80 falsifikasi: Beta(81, 1921). Rata-rata masih ≈ 0,045, tetapi lebar σ ≈ 0,0046. Bernyanyi tiga kali lebih tajam.

Setelah 200.000 kueri dengan 8000 falsifikasi: Beta(8001, 192.001). Rata-rata ≈ 0,040, lebar σ ≈ 0,0004. Bernyanyi menjadi jarum.

Konvergensi Geometris ke Massa Titik

Saat n → ∞, posterior Beta runtuh ke delta Dirac pada ε benar. Geometri: persegi panjang → bernyanyi lebar → bernyanyi sempit → jarum → titik. Setiap kueri mengencilkan distribusi kami dengan 1/√n.

Mengapa Ini Mengalahkan Batas PAC Teoretis

Batas PAC teoretis memberikan estimasi ε STATIS berdasarkan ukuran kelas hipotesis. Posterior Beta memberikan estimasi ε DINAMIS yang mengencil dengan setiap pengamatan, dikalibrasi terhadap distribusi dunia nyata Anda. Batas teoretis = jaminan dalam asumsi kasus terburuk. Audit empiris = pengukuran realitas aktual.

Berapa Banyak Kueri untuk Mengurangi Setengah Interval Kredibel?

Kami saat ini duduk di Beta(9, 193) setelah 200 kueri: rata-rata ε ≈ 0,045, σ ≈ 0,014. Kami ingin mengurangi setengah lebar interval kredibel menjadi σ ≈ 0,007.