Shattering & Dimensi VC

Ketika Ruang Hipotesis Menjadi Tak Terhingga

Batas m ≥ (1/ε)(ln|H| + ln(1/δ)) rusak ketika |H| = ∞. Kebanyakan kelas hipotesis yang berguna (klasifikasi linear di ℝᵈ, decision tree, neural net) memiliki kandidat yang tak terhingga banyaknya. Vapnik & Chervonenkis menyelesaikan masalah ini sekitar tahun 1971 dengan ukuran kompleksitas yang lebih kaya: VC dimension.

Shattering

Sebuah kelas hipotesis H shatters suatu himpunan n titik jika H dapat menghasilkan setiap kemungkinan pelabelan dari n titik tersebut (semua 2ⁿ dikotomi). Klasifikasi linear di ℝ² dapat merusak (shatter) sembarang 3 titik yang berada dalam posisi umum: untuk setiap 8 kemungkinan pelabelan +/− dari ketiga titik tersebut, terdapat garis yang memisahkan mereka dengan benar.

Namun pengklasifikasi linear di ℝ² tidak dapat menghancurkan 4 titik yang disusun dalam konfigurasi XOR. Tidak ada garis lurus yang memisahkan pasangan diagonal dari pasangan anti-diagonal.

Dimensi VC

VC(H) = bilangan n terbesar sedemikian sehingga H menghancurkan suatu himpunan n titik. Untuk pengklasifikasi linear 2D: VC = 3. Untuk persegi panjang sejajar sumbu di 2D: VC = 4. Untuk jaringan saraf dengan W bobot: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Kompleksitas Sampel dengan Dimensi VC

Ganti ln|H| dalam batas PAC kita dengan dimensi VC d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

VC dimension bertindak sebagai 'kompleksitas efektif' dari kelas tak hingga. Kelas hipotesis dengan VC dimension rendah dapat menggeneralisasi dari sedikit sampel; kelas dengan VC dimension tinggi membutuhkan lebih banyak data.

VC Dimension sebagai Jumlah Hipotesis Efektif

Sebuah jaringan saraf memiliki W = 10⁹ bobot. Berdasarkan Bartlett-Anthony bound, VC ≤ O(W² log W). Aproksimasikan VC ≈ W² log₂ W.

Menghilangkan Realizability, Posterior atas Hipotesis

Dua Generalisasi Penting

PAC klasik mengasumsikan konsep target c berada di dalam kelas hipotesis H kita. Data nyata membawa noise, label yang salah, & konsep yang tidak dapat direpresentasikan oleh kelas kita. Dua ekstensi menangani hal ini.

Agnostic PAC

Hapus asumsi bahwa c ∈ H. Sekarang kita bersaing melawan hipotesis terbaik-dalam-kelas kita h* = argmin_{h ∈ H} risk(h). Bentuk bound berubah: alih-alih mendekati sempurna, kita mendekati yang-terbaik-mungkin-dalam-H.

Bound Agnostic: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ dengan kompleksitas sampel m = O(1/ε² × (VC(H) + log(1/δ))). Perhatikan ε² alih-alih ε di penyebut: pembelajaran agnostic membutuhkan lebih banyak sampel untuk presisi yang sama.

PAC-Bayes (McAllester 1999)

Beralih dari memilih satu hipotesis tunggal ke memilih distribusi atas hipotesis. Mulai dengan prior P. Amati data. Turunkan posterior Q. PAC-Bayes membatasi risiko yang diharapkan di bawah Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) mengukur seberapa jauh posterior kita bergerak dari prior kita. Dua interpretasi:

1. Pandangan kompresi. Posterior yang dekat dengan priornya (KL kecil) akan menggeneralisasi dengan baik — biaya informasi kecil = celah generalisasi kecil.

2. Pandangan Bayesian. Prior kuat + pembaruan data lemah = bound ketat; prior lemah + pembaruan data berat = bound lebih longgar.

Mengapa PAC-Bayes penting. Empirical PAC-Bayes bounds (Catoni 2007, Dziugaite & Roy 2017) memberikan jaminan generalisasi yang bermakna secara numerik untuk jaringan neural nyata, di mana bound PAC klasik menjadi kosong. Mereka tetap menjadi pegangan teoretis paling ketat kita terhadap generalisasi yang overparameterized.

Membaca Batas PAC-Bayes

Misalkan kita melatih jaringan pada n = 50.000 contoh berlabel. Setelah pelatihan, posterior Q kita atas bobot memiliki KL(Q‖P) = 200 nats relatif terhadap prior Gaussian P. Risiko empiris di bawah Q adalah 0,10. Tetapkan δ = 0,05.

Overparameterisasi & Double Descent

Prediksi Bencana PAC Klasik

PAC klasik memprediksi: parameter lebih banyak daripada sampel = overfitting katastrofik. Belajar sempurna pada data latih, generalisasi acak pada data uji. VC bound memprediksi hafalan tanpa pembelajaran.

Jaringan saraf modern secara rutin memiliki 10× hingga 1000× lebih banyak parameter daripada sampel pelatihan & tetap dapat menggeneralisasi. Ini seharusnya tidak terjadi menurut teori klasik. Namun tetap terjadi.

Kurva-U yang Kita Pelajari

Bias-varians klasik: saat kapasitas model meningkat, error pelatihan turun secara monoton; error uji pertama-tama turun (kurang underfit), mencapai minimum, lalu naik (overfit). Kurva berbentuk U ini diprediksi oleh teori VC.

Apa yang Sebenarnya Terjadi — Double Descent

Belkin et al (2019) menunjukkan bahwa error uji mengikuti kurva U klasik kita hingga interpolation threshold (kapasitas = #sampel), kemudian TURUN LAGI setelah ambang tersebut. Model yang sangat overparameterized justru menggeneralisasi lebih baik daripada model yang hanya cukup besar.

Mengapa PAC Klasik Melewatkan Ini

1. Asumsi bebas distribusi terlalu pesimis. Data nyata memiliki struktur (dimensi intrinsik rendah, geometri manifold). Batas PAC berlaku untuk distribusi kasus terburuk; distribusi nyata memanfaatkan struktur yang juga dieksploitasi SGD.

2. Regularisasi implisit. SGD pada jaringan overparameterized menemukan solusi interpolasi minimum-norm atau minimum-complexity, bukan solusi sembarang. Teori klasik mengasumsikan empirical risk minimizer terburuk; algoritma nyata memilih solusi yang jinak.

3. Definisi kelas hipotesis salah. Kelas hipotesis efektif yang dieksplorasi SGD jauh lebih kecil daripada ruang bobot nominal. Posterior PAC-Bayes menangkap ini; VC dimension tidak.

Karya teori modern (Bartlett, Long, Lugosi, Tsigler 2020 tentang benign overfitting; Nakkiran et al 2020 tentang double descent) sedang membangun teori generalisasi pasca-PAC yang memperhitungkan rezim overparameterized kita.

Mendiagnosis Kegagalan PAC Klasik

Sebuah tim peneliti melatih jaringan dengan 1 miliar parameter pada 100.000 contoh berlabel. PAC klasik memprediksi bound yang vacuous. Secara empiris, akurasi uji mencapai 95%.

Kaplan, Chinchilla, & Mengukur Automated General Intelligence

Dari Batas ke Hukum Skala Empiris

PAC klasik memprediksi ukuran dataset secara teoretis & hasilnya kosong. Hukum skala empiris memprediksi ukuran dataset dari observasi & benar-benar bekerja. Mereka telah menggantikan PAC sebagai alat ukur praktis kita untuk model besar.

Kaplan et al (2020)

Loss mengikuti hukum pangkat pada parameter N, token dataset D, & komputasi C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Menggandakan parameter menurunkan loss dengan faktor perkalian tetap. Menggandakan data menurunkan loss dengan faktor tetap lainnya. Eksponen ini (αN, αD, αC) mengukur & memprediksi perilaku frontier lintas banyak orde magnitudo.

Hoffmann et al 2022 (Chinchilla)

Chinchilla menunjukkan bahwa eksponen Kaplan terlalu memberatkan parameter dibandingkan data. Pelatihan compute-optimal membutuhkan sekitar 20 token per parameter:

D_opt ≈ 20 × N

GPT-3 (175B parameter) dilatih pada ~300B token — sangat kurang terlatih menurut perhitungan Chinchilla. Model 175B-parameter yang compute-optimal membutuhkan ~3,5 triliun token.

The Data Wall

Menskalakan jumlah parameter kita memerlukan penskalaan jumlah token secara proporsional. Perayapan web publik menghasilkan ~10¹³ token yang berguna. Sebuah kecerdasan umum otomatis hipotetis berparameter 10¹⁵ akan membutuhkan ~2×10¹⁶ token — tiga orde magnitudo di luar data web yang tersedia.

Ini adalah dinding data kita. Hukum penskalaan memprediksi kita akan mengalami kekurangan korpus jauh sebelum mengalami kekurangan komputasi. Data sintetis, korpus multimodal (video, audio, aliran sensor), & RL-dari-lingkungan semuanya bertujuan untuk melewatinya.

PAC klasik memberi tahu kita (secara keliru) bahwa kita membutuhkan 10²¹ sampel. Hukum penskalaan memberi tahu kita (dikalibrasi dengan realitas) bahwa kita membutuhkan 2×10¹⁶. Kedua angka tersebut melebihi teks yang tersedia. Pekerjaan frontier saat ini berupaya menutup kesenjangan tersebut.

Estimasi Korpus Kecerdasan Umum Otomatis

Misalkan sebuah laboratorium frontier mengusulkan model berparameter 10¹⁴ & mengklaim bahwa model tersebut akan mencapai kecerdasan umum otomatis. Kita ingin menentukan ukuran korpus pelatihannya berdasarkan aturan Chinchilla.

Dari Theoretical Bounds ke Production Measurements

Berhenti Menghitung Bounds; Mulai Mengukurnya

Classical PAC bounds menjadi vacuous. PAC-Bayes bounds menjadi tight di bawah asumsi yang sulit diverifikasi. Alternatif praktis: ukur ε secara empiris pada distribusi nyata Anda & perbarui saat sistem berjalan.

Ide 1 — Jadikan Coverage sebagai PAC Empiris

Target make coverage menjalankan N pertanyaan yang ditahan dari sistem query Anda & mengukur dua tingkat:

- cache_hit_rate — fraksi jawaban yang dikenal ditemukan oleh sistem Anda

- i_dont_know_rate — fraksi yang secara jujur ditunda oleh sistem Anda

Setiap pengukuran = percobaan Bernoulli. Dari jumlah yang diamati, hitung interval kepercayaan Wilson untuk laju sebenarnya. Contoh: N = 1000 kueri, observed i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. Batas atas 0.226 berfungsi persis seperti PAC ε pada δ = 0.05, diturunkan dari data nyata pada distribusi nyata, bukan analisis teoretis kasus terburuk.

Kosakata PAC klasik berlaku (ε, δ, confidence). Mesin yang berbeda (konsentrasi binomial vs. teori VC). Hasil lebih ketat karena distribusi nyata memiliki struktur yang dapat dieksploitasi.

Idea 2 — Audit PAC-Bayes melalui Peristiwa Falsifikasi

Perlakukan setiap falsifikasi (jawaban sistem yang terbukti salah) sebagai bukti yang memperbarui posterior atas laju kesalahan sebenarnya ε:

1. Prior: ε ~ Beta(α₀, β₀). Pilih prior lemah, misalnya Beta(1, 1) = seragam.

2. Setiap query menghasilkan hasil Bernoulli: dipalsukan (1) atau dipertahankan (0).

3. Posterior setelah k pemalsuan dalam n query: Beta(α₀ + k, β₀ + n − k).

4. Rata-rata posterior: (α₀ + k) / (α₀ + β₀ + n) → tingkat pemalsuan empiris saat n → ∞.

5. Interval kredibel 95% pada ε menyempit sebagai 1/√n.

Apa Manfaatnya

- Estimasi ε₀ dunia nyata dari penerapan aktual, bukan teori kasus terburuk

- Alarm anytime-valid: ketika interval kredibel posterior melewati ambang kontrak, hubungi seseorang

- Kepercayaan monoton: semakin banyak query yang diamati → CI semakin sempit → jaminan semakin kuat

Teknik serupa: conformal prediction dengan recalibrasi online (Vovk), sequential probability ratio tests (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Keluarga yang sama, mesin matematika berbeda.

Menghitung Posterior Beta pada Falsifikasi

Tim kami menjalankan audit cakupan pada sistem query produksi. Prior pada tingkat kesalahan sejati ε: Beta(1, 1) (seragam). Setelah 200 query hold-out, kami mengamati 8 falsifikasi.