Probably Approximately Correct
Valiant’ın Sorusu (1984)
Leslie Valiant, aldatıcı derecede basit bir soru sordu: bir makinenin öğrenmesi ne anlama gelir? “Ezberleyebilir mi?” ya da “mükemmel tahmin edebilir mi?” değil. Bunun yerine: sonlu bir örnekten, polinom zamanda, yüksek olasılıkla yaklaşık olarak iyi öğrenebilir mi?
Bu çerçeve ona 2010’da Turing Ödülü kazandırdı ve hesaplamalı öğrenme teorisinin temelini attı.
İki Düğme
ε (epsilon) — hata toleransı. Yaklaşık olarak doğru, hatanın ≤ ε olduğu anlamına gelir. Daha küçük ε = daha katı öğrenme.
δ (delta) — güven parametresi. Muhtemelen başarı olasılığının ≥ 1 − δ olduğu anlamına gelir. Daha küçük δ = daha fazla güven gereklidir.
Tanım
Bir kavram sınıfı C, PAC-öğrenilebilir sayılır eğer şu koşulu sağlayan bir algoritma varsa: herhangi bir veri dağılımı D ve C içindeki herhangi bir hedef kavram c ∈ C için, D’den çekilen ve c tarafından etiketlenen m örnek verildiğinde, algoritma şu koşulu sağlayan bir hipotez h döndürür:
P[error(h) ≤ ε] ≥ 1 − δ
burada m, 1/ε, 1/δ ve kavram boyutunun polinom fonksiyonudur.
İngilizce: Yeterince örnek besleyin ve yeterince sıklıkla yeterince yakına gelir, ve 'yeterli' üstel olarak patlamaz.
Sonlu Hipotez Uzayları için Örnek Karmaşıklığı
Hipotez uzayımız H sonlu sayıda aday hipotez içeriyorsa, klasik analiz şu sonucu verir:
m ≥ (1/ε)(ln|H| + ln(1/δ))
Bu formülü bir bütçe olarak okuyun. ε'yi yarıya indirmek gereken örnek sayısını iki katına çıkarır. δ'yı yarıya indirmek sabit bir ekleme yapar. |H|'yi iki katına çıkarmak ln(2) örnek ekler — logaritmik ölçeklenme, güzelce uysal bir büyüme.
Bir Hipotez Sınıfı İçin Örnek Boyutu Belirleme [BLOCK_TYPE CONTENT classical_pac/pac_sample_calc]
Bir spam filtresi |H| = 1.000.000 aday kural kümesi arasından seçim yapar. Hata ε ≤ 0,05 ve güven 1 − δ = 0,99 (yani δ = 0,01) istiyoruz. [BLOCK_TYPE QUESTION classical_pac/pac_sample_calc]
Kırma (Shattering) ve VC Boyutu
Hipotez Uzayları Sonsuz Olduğunda
m ≥ (1/ε)(ln|H| + ln(1/δ)) sınırı |H| = ∞ olduğunda bozulur. Çoğu kullanışlı hipotez sınıfı (ℝᵈ içindeki doğrusal sınıflandırıcılar, karar ağaçları, sinir ağları) sonsuz sayıda aday içerir. Vapnik & Chervonenkis bu sorunu 1971 civarında daha zengin bir karmaşıklık ölçüsüyle çözdü: VC boyutu.
Parçalama (Shattering)
Bir hipotez sınıfı H, n noktalık bir kümeyi parçalar (shatters) eğer H o n noktanın tüm olası etiketlemelerini üretebiliyorsa (tüm 2ⁿ ikilik ayrım). ℝ² içindeki doğrusal sınıflandırıcılar, genel konumdaki herhangi 3 noktayı parçalar: bu 3 noktanın 8 olası +/− etiketlemesinin her biri için, onları doğru ayıran bir doğru vardır.
Ancak ℝ²’deki doğrusal sınıflandırıcılar, XOR düzeninde yerleştirilmiş 4 noktayı shatter edemez. Hiçbir düz çizgi, köşegen çiftini köşegen karşıtı çiftten ayıramaz.
VC Boyutu
VC(H) = H’nin bazı n-noktalı kümeyi shatter edebildiği en büyük n değeridir. 2B doğrusal sınıflandırıcılar için: VC = 3. 2B eksen hizalı dikdörtgenler için: VC = 4. W ağırlıklı sinir ağları için: VC ≤ O(W² log W) (Bartlett & Anthony 1999).
VC Boyutu ile Örnek Karmaşıklığı
PAC sınırımızdaki ln|H| ifadesini VC boyutu d ile değiştirin:
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
VC boyutu, sonsuz bir sınıfın 'etkili karmaşıklığı' olarak işlev görür. Düşük VC boyutuna sahip bir hipotez sınıfı az sayıda örnekten genelleme yapabilir; yüksek VC boyutuna sahip bir sınıf ise daha fazla veri gerektirir.
VC Boyutu Etkili Hipotez Sayısı Olarak
Bir sinir ağının W = 10⁹ ağırlığı vardır. Bartlett-Anthony sınırına göre VC ≤ O(W² log W). Yaklaşık VC ≈ W² log₂ W.
Gerçeklenebilirlik Varsayımının Bırakılması, Hipotezler Üzerinde Posterior Dağılımlar
İki Önemli Genelleme
Klasik PAC, hedef kavram c’nin hipotez sınıfımız H içinde yer aldığını varsayar. Gerçek veriler gürültü, yanlış etiketler ve sınıfımızın temsil edemediği kavramlar içerir. Bu durumu ele almak için iki genişletme kullanılır.
Agnostic PAC
c ∈ H varsayımını bırak. Şimdi en iyi sınıf hipotezimiz h* = argmin_{h ∈ H} risk(h) ile yarış. Sınır şekli değişir: mükemmele yaklaşmak yerine, H içinde mümkün olan en iyiye yaklaşırız.
Agnostik sınır: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ ve örnek karmaşıklığı m = O(1/ε² × (VC(H) + log(1/δ))). Paydada ε yerine ε² olduğuna dikkat edin: agnostik öğrenme aynı kesinlik için daha fazla örnek gerektirir.
PAC-Bayes (McAllester 1999)
Tek bir hipotez seçmekten hipotezler üzerinde bir dağılım seçmeye geç. Önce önsel P ile başla. Veriyi gözlemle. Sonsal Q’yu türet. PAC-Bayes, Q altında beklenen riski sınırlar:
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P), posterior’umuzun prior’ımızdan ne kadar uzaklaştığını ölçer. İki yorum:
1. Sıkıştırma görünümü. Prior’ına yakın bir posterior (küçük KL) iyi genelleme yapar — küçük bilgi maliyeti = küçük genelleme boşluğu.
2. Bayesçi görünüm. Güçlü prior + zayıf veri güncellemesi = sıkı sınır; zayıf prior + ağır veri güncellemesi = daha gevşek sınır.
PAC-Bayes neden önemlidir. Ampirik PAC-Bayes sınırları (Catoni 2007, Dziugaite & Roy 2017), klasik PAC sınırlarının boş kaldığı gerçek sinir ağları için sayısal olarak anlamlı genelleme garantileri sağlar. Aşırı parametreli genelleme konusunda hâlâ en sıkı teorik aracımızdır.
PAC-Bayes Sınırını Okumak
Bir ağı n = 50.000 etiketli örnek üzerinde eğittik. Eğitim sonrası, ağırlıklar üzerindeki posterior Q’nun, Gauss prior P’ye göre KL(Q‖P) = 200 nat. Q altındaki ampirik risk 0.10. δ = 0.05 olarak ayarlandı.
Aşırı Parametrelendirme & Çift İniş
Klasik PAC'ın Öngördüğü Felaket
Klasik PAC öngörüsü: parametre sayısı örnek sayısından fazla olduğunda = felaket niteliğinde aşırı uyum. Eğitim verisinde mükemmel öğrenme, test verisinde rastgele genelleme. VC sınırı ezberleme olmadan öğrenme öngörür.
Modern sinir ağları rutin olarak eğitim örneklerinden 10× ila 1000× daha fazla parametreye sahiptir ve yine de genelleme yapar. Bu, klasik teoriye göre olmamalıdır. Yine de olur.
Bize Öğretilen U-Eğrisi
Klasik bias-variance: model kapasitesi arttıkça eğitim hatası monoton olarak düşer; test hatası önce düşer (daha az underfit), bir minimuma ulaşır, sonra yükselir (overfit). VC teorisi tarafından öngörülen U-şekli.
Gerçekte Ne Oluyor — Double Descent
Belkin ve ark. (2019), test hatasının interpolasyon eşiğine (kapasite = örnek sayısı) kadar klasik U-eğrisi izlediğini, bu eşiğin ötesinde ise tekrar DÜŞTÜĞÜNÜ gösterdi. Aşırı parametreli modeller, tam yeterli büyüklükteki modellere göre daha iyi genelleme yapar.
Klasik PAC Neden Bunu Kaçırıyor
1. Dağılımdan-bağımsız varsayım aşırı kötümser. Gerçek veriler yapı içerir (düşük içsel boyut, manifold geometrisi). PAC sınırları en kötü durum dağılımları için geçerlidir; gerçek dağılımlar, SGD’nin de kullandığı yapıyı sömürür.
2. Örtük düzenlileştirme. Aşırı parametreli ağlarda SGD, rastgele çözümler yerine minimum-norm veya minimum-karmaşıklıkta interpolasyon yapan çözümler bulur. Klasik teori en kötü durum ampirik risk minimizer’ını varsayar; gerçek algoritmalar daha iyi huylu çözümleri seçer.
3. Hipotez sınıfı tanımı yanlıştır. SGD tarafından keşfedilen etkin hipotez sınıfı, nominal ağırlık uzayından çok daha küçüktür. PAC-Bayes ardılları bunu yakalar; VC boyutu yakalayamaz.
Modern teorik çalışmalar (Bartlett, Long, Lugosi, Tsigler 2020 iyi huylu aşırı uyum üzerine; Nakkiran ve ark. 2020 çift iniş üzerine) aşırı parametreli rejimimizi hesaba katan PAC sonrası genelleme teorisi oluşturmaktadır.
Klasik PAC’ın Başarısızlığının Teşhisi
Bir araştırma ekibi, 100.000 etiketli örnek üzerinde 1 milyar parametreli bir ağ eğitir. Klasik PAC boş (vacuous) sınırlar öngörür. Ampirik olarak test doğruluğu %95’e ulaşır.
Kaplan, Chinchilla ve Otomatik Genel Zekânın Boyutlandırılması
Sınır Değerlerden Ampirik Ölçekleme Yasalarına
Klasik PAC veri kümesi boyutunu teorik olarak öngörür ve sonuçlar boş çıkar. Ampirik ölçekleme yasaları veri kümesi boyutunu gözlemden öngörür ve gerçekten işe yarar. Büyük modeller için pratik boyutlandırma aracı olarak PAC’nin yerini almışlardır.
Kaplan et al (2020)
Kayıp, parametreler N, veri kümesi token’ları D ve hesaplama C için kuvvet yasasına uyar:
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
Parametreleri ikiye katlamak kaybı sabit bir çarpanla düşürür. Veriyi ikiye katlamak kaybı başka bir sabit çarpanla düşürür. Bu üsler (αN, αD, αC) birçok büyüklük mertebesi boyunca öncü davranışları ölçer ve öngörür.
Hoffmann ve ark. 2022 (Chinchilla)
Chinchilla, Kaplan’ın üstel katsayılarının parametreleri veriye göre fazla ağırlıklandırdığını gösterdi. Hesaplamasal olarak en uygun eğitim için yaklaşık parametre başına 20 token gerekir:
D_opt ≈ 20 × N
GPT-3 (175B parametre) yaklaşık 300B token ile eğitildi — Chinchilla hesaplamasına göre ciddi şekilde yetersiz eğitilmişti. Hesaplamasal olarak en uygun 175B parametreli bir model yaklaşık 3,5 trilyon token ister.
Veri Duvarı
Parametre sayımızı ölçeklendirmek için token sayımızı da orantılı şekilde ölçeklendirmemiz gerekir. Kamuya açık web taramaları yaklaşık 10¹³ faydalı token üretir. Varsayımsal 10¹⁵ parametreli otomatik genel zeka modeli ise yaklaşık 2×10¹⁶ token ister — mevcut web verilerinin üç katman ötesinde.
Bu bizim veri duvarımızdır. Ölçeklendirme yasaları, bir hesaplama sıkıntısından çok daha önce bir külliyat sıkıntısına çarpacağımızı öngörür. Sentetik veri, çok modlu külliyatlar (video, ses, sensör akışları) ve ortamdan RL, bu duvarı aşmayı hedefler.
Klasik PAC bize (yanlış olarak) 10²¹ örneğe ihtiyacımız olduğunu söylemişti. Ölçeklendirme yasaları ise (gerçeğe kalibre edilmiş olarak) 2×10¹⁶ örneğe ihtiyacımız olduğunu söyler. Her iki sayı da mevcut metin verisinin üzerindedir. Günümüz öncü çalışmaları bu açığı kapatma mücadelesi vermektedir.
Otomatik Genel Zeka Külliyatını Tahmin Etme
Bir öncü laboratuvar 10¹⁴ parametreli bir model öneriyor ve bunun otomatik genel zekaya ulaşacağını iddia ediyor. Chinchilla kuralına göre eğitim külliyatını boyutlandırmak istiyoruz.
Teorik Sınırlardan Üretim Ölçümlerine
Sınırları Hesaplamayı Bırak; Ölçmeye Başla
Klasik PAC sınırları boş çıkıyor. PAC-Bayes sınırları doğrulanması zor varsayımlar altında sıkılaşıyor. Pratik bir alternatif: ε’yi gerçek dağılımınız üzerinde ampirik olarak ölçün ve sistem çalışırken güncelleyin.
Fikir 1 — Kapsamı Ampirik PAC Olarak Oluştur
Bir make coverage hedefi, sorgu sisteminiz üzerinden N adet ayrılmış soruyu çalıştırır ve iki oranı ölçer:
- cache_hit_rate — sisteminizin bilinen bir cevap bulduğu kesir
- i_dont_know_rate — sisteminizin dürüstçe ertelediği kesir
Her ölçüm = Bernoulli denemesi. Gözlemlenen sayımlardan, gerçek oran için bir Wilson güven aralığı hesaplanır. Örnek: N = 1000 sorgu, gözlemlenen i_dont_know_rate = 0.20 → %95 GA ≈ [0.177, 0.226]. Üst sınır 0.226, δ = 0.05 için tam olarak bir PAC ε gibi işlev görür; en kötü durum teorik analizinden ziyade gerçek dağılım üzerindeki gerçek verilerden türetilmiştir.
Klasik PAC sözcük dağarcığı geçerlidir (ε, δ, güven). Farklı mekanizma (binomial konsantrasyon vs. VC teorisi). Gerçek dağılımlar sömürülebilir yapı taşıdığı için daha sıkı sonuç.
Fikir 2 — Falsifikasyon Olayları ile PAC-Bayes Denetimi
Her falsifikasyonu (sistemin cevabının açıkça yanlış olduğu durum) gerçek hata oranı ε üzerindeki posterioru güncelleyen kanıt olarak ele al:
1. Önsel: ε ~ Beta(α₀, β₀). Zayıf bir önsel seçin, örn. Beta(1, 1) = düzgün dağılım.
2. Her sorgu, Bernoulli sonucu üretir: sahte (1) veya tutulan (0).
3. n sorguda k sahtecilik sonrası posterior: Beta(α₀ + k, β₀ + n − k).
4. Posterior ortalama: (α₀ + k) / (α₀ + β₀ + n) → n → ∞ iken ampirik sahtecilik oranına yaklaşır.
5. %95 güvenilir aralık ε üzerinde 1/√n ile daralır.
Bu Bize Ne Sağlar
- Gerçek dünyadan ε₀ tahmini, en kötü durum teorisi yerine gerçek dağıtım verisinden elde edilir
- Her zaman geçerli alarm: arka dağılımın güvenilir aralığı sözleşme eşiğini aştığında birine sayfa at
- Monoton güven: daha fazla sorgu gözlemlendikçe → daha dar CI → daha güçlü garanti
Akraba teknikler: çevrimiçi yeniden kalibrasyonlu konformal tahmin (Vovk), sıralı olasılık oranı testleri (Wald), çevrimiçi PAC-Bayes (Haddouche & Guedj 2022). Aynı aile, farklı matematiksel araçlar.
Yanlışlamalar Üzerinde Beta Arka Dağılımı Hesaplama
Ekibimiz üretim sorgu sistemi üzerinde bir kapsama denetimi yürütüyor. Gerçek hata oranı ε için önsel: Beta(1, 1) (düzgün). 200 doğrulama-dışı sorgu sonrasında 8 yanlışlama gözlemledik.