शैटरिंग और VC डाइमेंशन

जब हाइपोथेसिस स्पेस अनंत हो जाए

बाउंड m ≥ (1/ε)(ln|H| + ln(1/δ)) तब टूट जाता है जब |H| = ∞. अधिकांश उपयोगी हाइपोथेसिस क्लासेस (ℝᵈ में रैखिक वर्गीकरणकर्ता, डिसीजन ट्री, न्यूरल नेट) अनंत उम्मीदवार रखती हैं। Vapnik & Chervonenkis ने 1971 के आसपास इस समस्या को हल किया एक समृद्ध जटिलता माप के साथ: VC dimension.

Shattering

एक हाइपोथेसिस क्लास H n बिंदुओं के सेट को shatter करती है यदि H उन n बिंदुओं के हर संभव लेबलिंग (सभी 2ⁿ द्विभाजन) उत्पन्न कर सके। ℝ² में रैखिक वर्गीकरणकर्ता सामान्य स्थिति वाले किसी भी 3 बिंदुओं को shatter करते हैं: उन 3 बिंदुओं के 8 संभावित +/− लेबलिंग में से प्रत्येक के लिए कोई रेखा उन्हें सही ढंग से अलग करती है।

लेकिन ℝ² में रैखिक वर्गीकरणकर्ता 4 बिंदुओं को XOR कॉन्फ़िगरेशन में व्यवस्थित करने पर shatter नहीं कर सकते। कोई भी सीधी रेखा विकर्ण जोड़ी को प्रतिविकर्ण जोड़ी से अलग नहीं कर सकती।

VC Dimension

VC(H) = सबसे बड़ा n जिसके लिए H किसी n-बिंदु समुच्चय को shatter कर सके। 2D रैखिक वर्गीकरणकर्ताओं के लिए: VC = 3। 2D में अक्ष-संरेख आयतों के लिए: VC = 4। W भारों वाले तंत्रिका जालों के लिए: VC ≤ O(W² log W) (Bartlett & Anthony 1999)।

VC Dimension के साथ नमूना जटिलता

हमारे PAC बाउंड में ln|H| को VC dimension d से बदलें:

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

VC dimension हमारे 'effective complexity' के रूप में कार्य करता है। कम VC dimension वाली hypothesis class कुछ samples से ही generalize कर लेती है; उच्च VC dimension वाली class को अधिक data की आवश्यकता होती है।

VC Dimension as Effective Hypothesis Count

एक neural network में W = 10⁹ weights हैं। Bartlett-Anthony bound के अनुसार VC ≤ O(W² log W)। अनुमानित VC ≈ W² log₂ W।

Realizability को छोड़ना, Hypotheses पर Posteriors

दो महत्वपूर्ण सामान्यीकरण

Classical PAC मानता है कि हमारा target concept c हमारी hypothesis class H के अंदर रहता है। वास्तविक डेटा में noise, mislabels और ऐसे concepts होते हैं जिन्हें हमारी class represent नहीं कर सकती। इसको संभालने के लिए दो extensions हैं।

एग्नॉस्टिक PAC

अब हमारी यह धारणा छोड़ दें कि c ∈ H. अब हम अपने best-in-class हाइपोथेसिस h* = argmin_{h ∈ H} risk(h) के विरुद्ध प्रतिस्पर्धा करते हैं। बाउंड का स्वरूप बदल जाता है: पूर्णता के निकट पहुँचने के बजाय, हम H के भीतर सर्वोत्तम संभव के निकट पहुँचते हैं।

एग्नॉस्टिक बाउंड: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ नमूना जटिलता m = O(1/ε² × (VC(H) + log(1/δ))) के साथ। ध्यान दें कि हमारे हर में ε² है न कि ε: एग्नॉस्टिक लर्निंग में समान परिशुद्धता के लिए अधिक नमूनों की आवश्यकता होती है।

PAC-Bayes (McAllester 1999)

एकल हाइपोथेसिस चुनने से हटकर हाइपोथेसिस पर वितरण चुनने की ओर बढ़ें। प्रायोर P से शुरू करें। डेटा देखें। पोस्टीरियर Q प्राप्त करें। PAC-Bayes Q के अंतर्गत अपेक्षित जोखिम को बाउंड करता है:

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

KL(Q‖P) हमारे posterior को prior से कितना दूर ले गया है, इसे मापता है। दो व्याख्याएँ:

1. Compression view. एक posterior जो अपने prior के करीब है (छोटा KL) अच्छा generalize करता है — छोटी सूचना लागत = छोटा generalization gap.

2. Bayesian view. मजबूत prior + कमजोर डेटा अपडेट = कड़ी bound; कमजोर prior + भारी डेटा अपडेट = ढीली bound.

Why PAC-Bayes matters. Empirical PAC-Bayes bounds (Catoni 2007, Dziugaite & Roy 2017) वास्तविक neural networks के लिए संख्यात्मक रूप से सार्थक generalization guarantees देते हैं, जहाँ classical PAC bounds व्यर्थ हो जाते हैं। वे overparameterized generalization पर हमारी सबसे कड़ी सैद्धांतिक पकड़ बने हुए हैं.

PAC-Bayes बाउंड पढ़ना

मान लीजिए हम n = 50,000 लेबल्ड उदाहरणों पर एक नेटवर्क को ट्रेन करते हैं। ट्रेनिंग के बाद, हमारे वज़न पर पोस्टीरियर Q का KL(Q‖P) = 200 नाट्स है, जो गॉसियन प्रायर P के सापेक्ष है। Q के अंतर्गत एम्पिरिकल रिस्क 0.10 है। δ = 0.05 सेट करें।

ओवरपैरामीटराइजेशन और डबल डिसेंट

क्लासिकल PAC की भविष्यवाणी की तबाही

क्लासिकल PAC भविष्यवाणी करता है: पैरामीटर्स की संख्या सैंपल्स से अधिक होने पर = भयावह ओवरफिटिंग। ट्रेनिंग डेटा पर पूरी तरह सीखना, टेस्ट डेटा पर रैंडम तरीके से सामान्यीकरण। VC बाउंड मेमोराइजेशन की भविष्यवाणी करता है बिना सीखे।

आधुनिक न्यूरल नेटवर्क्स में आमतौर पर ट्रेनिंग सैंपल्स से 10× से 1000× अधिक पैरामीटर्स होते हैं और फिर भी वे सामान्यीकरण करते हैं। क्लासिकल थ्योरी के अनुसार यह नहीं होना चाहिए। फिर भी ऐसा होता है।

वह U-कर्व जिसे हमने पढ़ाया गया

क्लासिकल बायस-वैरिएंस: जैसे-जैसे मॉडल क्षमता बढ़ती है, ट्रेनिंग एरर लगातार घटता जाता है; टेस्ट एरर पहले घटता है (अंडरफिट कम होता है), एक न्यूनतम बिंदु पर पहुँचता है, फिर बढ़ने लगता है (ओवरफिट)। VC थ्योरी द्वारा U-आकार की भविष्यवाणी की जाती है।

वास्तव में क्या होता है — डबल डिसेंट

Belkin et al (2019) ने दिखाया कि टेस्ट एरर क्लासिकल U-कर्व का अनुसरण करता है इंटरपोलेशन थ्रेशोल्ड (क्षमता = #नमूने) तक, फिर उस थ्रेशोल्ड के बाद फिर से गिरता है। अत्यधिक ओवरपैरामीटराइज्ड मॉडल सिर्फ पर्याप्त बड़े मॉडलों की तुलना में बेहतर सामान्यीकरण करते हैं।

क्लासिकल PAC इसे क्यों नहीं पकड़ पाता

1. डिस्ट्रीब्यूशन-फ्री धारणा बहुत निराशावादी है। वास्तविक डेटा में संरचना होती है (कम आंतरिक आयाम, मैनिफोल्ड ज्यामिति)। PAC बाउंड्स सबसे खराब स्थिति वाले डिस्ट्रीब्यूशन पर लागू होते हैं; वास्तविक डिस्ट्रीब्यूशन उस संरचना का फायदा उठाते हैं जिसका SGD भी फायदा उठाता है।

2. Implicit regularization. SGD on overparameterized networks finds minimum-norm or minimum-complexity interpolating solutions, not arbitrary ones. Classical theory assumes worst-case empirical risk minimizer; real algorithms pick benign ones.

3. Hypothesis class definition is wrong. Effective hypothesis class explored by SGD is far smaller than nominal weight space. PAC-Bayes posteriors capture this; VC dimension does not.

Modern theoretical work (Bartlett, Long, Lugosi, Tsigler 2020 on benign overfitting; Nakkiran et al 2020 on double descent) is building post-PAC generalization theory that accounts for our overparameterized regime.

क्लासिकल PAC की विफलता का निदान

A research team trains a 1-billion-parameter network on 100,000 labeled examples. Classical PAC predicts vacuous bounds. Empirically, test accuracy reaches 95%.

कपलान, चिनचिला, और ऑटोमेटेड जनरल इंटेलिजेंस का आकार निर्धारण

बाउंड्स से एम्पिरिकल स्केलिंग लॉज़ तक

क्लासिकल PAC सैद्धांतिक रूप से डेटासेट साइज़ की भविष्यवाणी करता है और खाली परिणाम देता है। एम्पिरिकल स्केलिंग लॉज़ अवलोकन से डेटासेट साइज़ की भविष्यवाणी करते हैं और वास्तव में काम करते हैं। उन्होंने बड़े मॉडलों के लिए हमारे व्यावहारिक साइज़िंग टूल के रूप में PAC की जगह ले ली है।

Kaplan et al (2020)

Loss N, D और C के साथ पावर लॉ के अनुसार घटता है:

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

पैरामीटर्स को दोगुना करने से loss एक निश्चित गुणक से घटता है। डेटा को दोगुना करने से loss एक अन्य निश्चित गुणक से घटता है। ये एक्सपोनेंट्स (αN, αD, αC) कई ऑर्डर ऑफ़ मैग्निट्यूड में फ्रंटियर व्यवहार को मापते और भविष्यवाणी करते हैं।

हॉफमैन एट अल 2022 (चिनचिला)

चिनचिला ने दिखाया कि कपलान के एक्सपोनेंट्स पैरामीटर्स को डेटा की तुलना में अधिक महत्व देते थे। कम्प्यूट-ऑप्टिमल ट्रेनिंग के लिए लगभग 20 टोकन प्रति पैरामीटर की आवश्यकता होती है:

D_opt ≈ 20 × N

GPT-3 (175B पैरामीटर्स) को ~300B टोकन्स पर ट्रेन किया गया — चिनचिला गणना के अनुसार यह बहुत कम ट्रेन किया गया था। एक कम्प्यूट-ऑप्टिमल 175B-पैरामीटर मॉडल को ~3.5 ट्रिलियन टोकन्स की आवश्यकता होती है।

द डेटा वॉल

हमारे पैरामीटर काउंट को स्केल करने के लिए हमें टोकन काउंट को भी आनुपातिक रूप से स्केल करना होगा। पब्लिक वेब क्रॉल से लगभग ~10¹³ उपयोगी टोकन मिलते हैं। एक काल्पनिक 10¹⁵-पैरामीटर ऑटोमेटेड जनरल इंटेलिजेंस को ~2×10¹⁶ टोकन की आवश्यकता होगी — जो उपलब्ध वेब डेटा से तीन ऑर्डर ऑफ़ मैग्निट्यूड अधिक है।

यह हमारी डेटा वॉल है। स्केलिंग लॉज़ भविष्यवाणी करते हैं कि हम कंप्यूट की कमी से बहुत पहले कॉर्पस की कमी का सामना करेंगे। सिंथेटिक डेटा, मल्टीमॉडल कॉर्पोरा (वीडियो, ऑडियो, सेंसर स्ट्रीम्स), और RL-from-environment सभी इसे पार करने का प्रयास करते हैं।

क्लासिकल PAC ने हमें (गलत तरीके से) बताया था कि हमें 10²¹ सैंपल्स की आवश्यकता है। स्केलिंग लॉज़ हमें (वास्तविकता के अनुसार कैलिब्रेटेड) बताते हैं कि हमें 2×10¹⁶ की आवश्यकता है। दोनों संख्याएँ उपलब्ध टेक्स्ट से अधिक हैं। फ्रंटियर कार्य आज इस अंतर को कम करने के लिए संघर्ष कर रहा है।

ऑटोमेटेड जनरल इंटेलिजेंस कॉर्पस का अनुमान

मान लीजिए एक फ्रंटियर लैब 10¹⁴-पैरामीटर मॉडल का प्रस्ताव रखती है और दावा करती है कि यह ऑटोमेटेड जनरल इंटेलिजेंस तक पहुँचेगा। हम चिंचिला के नियम के अनुसार इसके ट्रेनिंग कॉर्पस का आकार निर्धारित करना चाहते हैं।

सैद्धांतिक बाउंड्स से प्रोडक्शन मेजरमेंट्स तक

बाउंड्स की गणना बंद करें; उन्हें मापना शुरू करें

क्लासिकल PAC बाउंड्स खोखले साबित होते हैं। PAC-Bayes बाउंड्स उन मान्यताओं के तहत टाइट रहते हैं जिन्हें सत्यापित करना कठिन है। एक व्यावहारिक विकल्प: अपने वास्तविक डिस्ट्रीब्यूशन पर ε को एम्पिरिकली मापें और अपने सिस्टम के चलते रहने पर इसे अपडेट करते रहें।

विचार 1 — कवरेज को Empirical PAC के रूप में बनाएं

एक make coverage टारगेट आपके क्वेरी सिस्टम से N होल्ड-आउट प्रश्नों को चलाता है और दो दरें मापता है:

- cache_hit_rate — वह अंश जिसके लिए आपके सिस्टम को ज्ञात उत्तर मिला

- i_dont_know_rate — वह अंश जिसके लिए आपके सिस्टम ने ईमानदारी से मना कर दिया

प्रत्येक माप = एक बर्नोली परीक्षण। देखे गए गणनों से, सही दर पर Wilson confidence interval की गणना करें। उदाहरण: N = 1000 क्वेरीज़, observed i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. ऊपरी सीमा 0.226 ठीक उसी तरह काम करती है जैसे PAC ε δ = 0.05 पर, जो वास्तविक डेटा और वास्तविक वितरण से प्राप्त होता है न कि सबसे खराब स्थिति के सैद्धांतिक विश्लेषण से।

क्लासिकल PAC शब्दावली लागू होती है (ε, δ, confidence)। अलग मशीनरी (binomial concentration बनाम VC theory)। परिणाम अधिक कसा हुआ क्योंकि वास्तविक वितरणों में शोषण योग्य संरचना होती है।

विचार 2 — PAC-Bayes Audit via Falsification Events

प्रत्येक falsification (सिस्टम का उत्तर स्पष्ट रूप से गलत) को सही त्रुटि दर ε पर posterior को अपडेट करने वाले साक्ष्य के रूप में मानें:

1. Prior: ε ~ Beta(α₀, β₀)। कमजोर prior चुनें, उदाहरण Beta(1, 1) = uniform।

2. प्रत्येक क्वेरी एक बर्नौली परिणाम उत्पन्न करती है: falsified (1) या held (0).

3. n क्वेरीज़ में k falsifications के बाद Posterior: Beta(α₀ + k, β₀ + n − k).

4. Posterior mean: (α₀ + k) / (α₀ + β₀ + n) → n → ∞ होने पर empirical falsification rate की ओर अग्रसर।

5. 95% credible interval ε पर 1/√n के अनुसार सिकुड़ता है।

यह हमें क्या देता है

- वास्तविक डिप्लॉयमेंट से प्राप्त वास्तविक ε₀ अनुमान, न कि worst-case सिद्धांत

- Anytime-valid alarm: जब posterior credible interval contract threshold को पार करे, किसी को पेज करें

- Monotone confidence: अधिक queries observe करने पर → CI और संकरी → stronger guarantee

Cousin techniques: online recalibration के साथ conformal prediction (Vovk), sequential probability ratio tests (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Same family, different mathematical machinery.

Computing a Beta Posterior on Falsifications

हमारी टीम एक production query system पर coverage audit चला रही है। true error rate ε पर Prior: Beta(1, 1) (uniform)। 200 held-out queries के बाद 8 falsifications observe किए गए।