Nokta Bulutları Üzerinde İkili Ayırımlar

Parçalanma Neye Benzer

Düzleme n nokta yerleştirin. Bir hipotez sınıfı seçin (doğrusal sınıflandırıcılar = düz çizgiler). Bu n noktayı sınıflandırabilecek farklı yolların sayısını sayın (+/− bir çizginin her iki tarafında). Bu sayıya Π_H(n) deyin.

Eğer Π_H(n) = 2ⁿ ise, sınıfımız bu nokta setini parçalar — tüm olası etiketlemeleri üretebilir. Eğer Π_H(n) < 2ⁿ ise, bazı etiketlemeler oluşamaz.

Genel Pozisyonda Üç Nokta

ℝ² içinde doğrusal sınıflandırıcılar herhangi 3 eş-doğrusal olmayan noktayı parçalar. 2³ = 8 etiketleme; tümü 8'i ulaşılabilir bir çizgi tarafından oluşturulabilir. Herhangi 3 nokta seçin; her ±/± etiketlemesi için pozitif olanları negatif olanlardan ayıran bir çizgi çizin.

Dört Nokta Parçalanmayı Reddeder

4 noktayı kare köşelerine yerleştirin. Köşegen çifti pozitif olarak ve anti-diyagonal çifti negatif olarak etiketlemeyi deneyin (XOR etiketlemesi). Hiçbir düz çizgi onları ayıramaz. Yani Π_H(4) ≤ 14 < 16 = 2⁴.

VC Boyutu en Fazla Parçalama Boyutu Olarak

VC(doğrusal ℝ²) = 3. 3 noktayı parçalayabiliriz; 4'ü parçalayamayız. VC, hipotez sınıfımızın en fazla ikili ayırım kapasitesini sayar.

Geometrik Sezgi

Daha yüksek VC = sınıfımız daha ayrıntılı karar sınırları çizer. Doğrusal (VC = d+1 d boyutlarında) hiperdüzlemler çizer. Polinomlar eğriler çizer. Sinir ağları yüksek oranda katlanmış manifoldlar çizer. Daha fazla katlama yeteneği = daha fazla ikili ayırım = daha yüksek VC = daha yüksek örneklem gereksinimi.

İkili Ayırımları Sayma

ℝ² içinde doğrusal sınıflandırıcıları (çizgiler) düşünün. 5 noktamız var genel pozisyonda (3 eş-doğrusal değil, hiçbiri redundant değil).

Hipotez Manifoldu Üzerinde Olasılık Kütlesi

PAC-Bayes'i Görselleştirmek

Hipotez uzayını yüksek boyutlu bir manifold olarak görselleştirin. Bu manifold üzerindeki her nokta sinir ağının bir ağırlık konfigürasyonuna karşılık gelir. Ön dağılım P bu manifold genelinde bir olasılık dağılımı atar (genellikle başlatmada merkezlenmiş Gauss). Posterior Q, eğitim verilerinin ağırlıkları nereye sürüklediğini yoğunlaştırdığı yerde olasılık kütlesini konsantre eder.

KL Diverjansı Geometrik Mesafe Olarak

KL(Q‖P), Q'nun P'den ne kadar saptığını ölçer. Geometrik okuma: posterior bulutu ön dağılım bulutundan ne kadar hareket etti, her posterior bölgesinin ön dağılım altında olma olasılığına göre ağırlıklandırılmış.

Küçük KL = Q ve P ağır ölçüde örtüşür. Posterior neredeyse hareket etmedi. Genelleme farkı küçük kalır.

Büyük KL = Q, P'nin az olasılık atadığı bölgelerde yoğunlaştırıldı. Posterior çok hareket etti. Genelleme farkı büyür.

Bu Geometrinin Neden Önemli Olduğu

SGD'yi hipotez manifoldu genelinde bir arama yörüngesi olarak düşünün. Yörünge düşük eğitim kaybı havzasında biter. PAC-Bayes sorar: bu havza ne kadar geniş?

Geniş havza = birçok komşu ağırlık konfigürasyonu da düşük eğitim kaybı elde eder. Posterior Q geniş bir bölgeye yayılabilir ve hala düşük risk taşır. KL(Q‖P) sınırlandırılmış kalır. Genelleme farkı küçüktür.

Dar havza = ağırlıkların sadece ince bir seti düşük kayıp elde eder. Posterior keskinleşmelidir. KL büyür. Genelleme farkı genişler.

Bu, düz-vs-keskin minimalar söylemini doğrudan bağlar (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Düz minimalar daha iyi genelleşir çünkü daha küçük KL ile daha geniş posteriore destek verirler.

Bir Havza Genişliğini Okuma

İki eğitilmiş model aynı eğitim kaybını ulaştı ama farklı havzalarda yaşıyor:

- Model A: geniş havza, posterior KL(Q_A‖P) = 50 nat'a yayılmış.

- Model B: dar havza, posterior KL(Q_B‖P) = 500 nat'a yoğunlaştırılmış.

Her ikisi de n = 10.000 örnek üzerinde eğitildi ve ampirik risk 0,05, δ = 0,05.

Teorinin Yükselişi Öngördüğü Ama Gerçekte Düşen Bir Eğri

Klasik U Eğrisi

Yatay eksene model kapasitesi, dikey eksene test riski çizin. Klasik sapma-varyans teorisi tahmin eder:

- Düşük kapasite: yüksek sapma, yüksek test riski (yetersiz)

- Orta kapasite: düşük sapma + düşük varyans, düşük test riski (tatlı nokta)

- Yüksek kapasite: düşük sapma, yüksek varyans, yüksek test riski (aşırı)

Sonuç: U-şekilli eğri. Kapasiteyi alt noktasında seçin.

Belkin et al (2019) Gözlemi

İnterpolasyon eşiğini (modelin eğitim verilerini sıfır hata ile tam olarak uydurmaya yettiği kapasite) geçtikten sonra, test riski DÜŞER. Eğri okur: iniş → İnterpolasyon tepesi → ikinci iniş. İki iniş, bir eğri.

İkinci İniş'in Geometrik Okuması

İnterpolasyon eşiğinde, modelin eğitim verilerini uydurmaya tam yetkin kapasitesi var — sadece bir (ya da birkaç) enterpolasyon çözümü vardır ve bunlar eğrilik yapmaya meyillidir. Genelleme acı çeker çünkü seçilen çözüm zorunludur.

İnterpolasyon eşiğinin ötesinde, BIRÇOK enterpolasyon çözümü vardır. SGD pürüzsüz birini (minimum-norm, düşük eğrilik) seçme özgürlüğüne sahiptir. Geometrik resim: çözüm manifoldu daha geniş ve daha düz hale gelir. SGD'nin örtülü düzenlemesi bu düz manifold'dan iyi huylu çözümleri seçer. Test riski düşer.

Klasik Teori Bunu Neden Kaçırıyor

VC boyutu çözüm seti kapasitesini sayar ama hangi çözümün seçildiğini görmezden gelir. Klasik sınır en kötü durum ampirik risk minimizerini kabul eder. Gerçeklik: SGD güvenilir şekilde en düz, en pürüzsüz enterpolasyon çözümünü seçer. TÜM çözümleri yerine ÇÖzÜCÜ TARAFINDAN SEÇILEN çözümleri saydığımızda, ikinci iniş mantıklı olur.

Geometrik İçe Akış

Kapasite parametre sayısından daha azını önemser. Geniş düz havzalar (post-interpolasyon) dar keskin olanlardan (interpolasyon'da) daha iyi genelleşir. Modern teori, parametre sayısı yerine havza genişliğine göre genellemeyi sınırlamaya çalışır.

İki İniş'i Yerleştirme

Çift iniş eğrisinde, üç bölge önemlidir: (1) yetersiz parametrize rejimi, (2) interpolasyon tepesi, (3) aşırı parametrize rejimi.

Parameter-Token Uzayında Güç Yasası Yüzeyi

Bir 3B Yüzey

Yatay eksene parametreleri N, ikinci yatay eksene token'ları D, dikey eksene kaybı L çizin. Ampirik kayıp bu (N, D) düzlemi genelinde bir güç yasası yüzeyini oyar:

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

Yüzey N veya D büyüdükçe aşağı eğimlidir. Eğimler log-doğrusal güç yasalarını izler (log-log çiziminde düz çizgiler). Asimptot L∞ pozitif kalır — modelimizin geçişemeyeceği, indirgenemez kayıp.

Compute-Optimal Ridge

Toplam işlem bütçesini C ∝ N × D (parametreler × token'lar, kabaca) sabitleyin. Yüzeyimizi bu kısıtlama boyunca dilimleyin. Dilim izi bu 3B yüzeyde 2B bir eğri çizer. Bu eğrinin alt kısmı = compute-optimal nokta.

Chinchilla (Hoffmann et al 2022) bu alt noktayı analitik olarak hesapladı: D_opt ≈ 20 × N. İşlem bütçesi boyunca eğri = bir ridge. Ridge boyunca yürümek: eşit işlem, düşen kayıp. Ridge'den çıkmak (daha fazla parametre 20× token'larından, ya da daha az): harcanan işlem.

GPT-3 vs Chinchilla'nın Geometrik Okuması

GPT-3: 175B param, 300B token. Chinchilla-optimal 175B × 20 = 3500B token isteyecekti. GPT-3 parameter-yoğun yönde compute-optimal ridge'den uzakta oturur. Chinchilla kendisi: 70B param, 1400B token üzerinde eğitildi. 1400 / 70 = 20 — tam ridge üzerinde. Chinchilla, parametre sayısından yarısından azını kullanarak GPT-3'ü geometrik optimumda oturarak yendi.

Veri Duvarı Dikey Düzlem Olarak

Halka açık web ~10¹³ kullanılabilir token. Bu, parameter-token düzleminde D = 10¹³ noktasında dikey bir duvar olarak çizilir. Bu duvarın ötesinde, compute-optimal eğitim N ≤ D / 20 = 5 × 10¹¹ param gerektirir. N = 5 × 10¹¹'in ötesindeki duvarlar ya eksik eğitilmiş çalışır (ridge dışı) ya da duvarı dışarıya çek için sentetik / çok modal / RL veri gerektirir.

Compute-Optimal Ridge'de Yürüme

GPT-3 koordinatlarında oturuyoruz: N = 175B param, D = 300B token. İşlem vekili C = N × D = 5,25 × 10²² param-token.

Beta Posterior'u Bir İğneye Sıklaştırma

[0, 1] Üzerinde Olasılık Yoğunluğu

Beta(α, β) [0, 1] birim aralığı üzerinde bir olasılık yoğunluğudur. Değişken: ε = gerçek hata oranı. Şekil: α yüksek ε tarafında kütleyi kontrol eder; β düşük ε tarafında kütleyi kontrol eder.

Beta(1, 1): tekdüze — bilgi yok, [0, 1] genelinde düz yoğunluk.

Beta(α, β) α + β büyük: yoğunlaştırılmış tepe α / (α + β)'de.

Beta tepe genişliği 1/√(α+β) olarak küçülür. Ön dağılıma 100 gözlem eklemek tepeyi √100 = 10 faktörü daraltır. 10.000 gözlem eklemek √10000 = 100 kadar daraltır.

Bir Denetim Çalıştırmasının Geometrik Okuması

Başlangıç: Beta(1, 1) = [0, 1] üzerinde düz dikdörtgen. ε hakkında maksimum belirsizlik.

200 sorgudan sonra, 8 yanlışlaştırmayla: Beta(9, 193). Orta = 9/202 ≈ 0,045. Yoğunluk şimdi 0,045 yakınında merkezlenmiş, karakteristik genişlik σ ≈ 0,014 ile keskin bir tümsek.

2000 sorgudan sonra, 80 yanlışlaştırmayla: Beta(81, 1921). Orta hala ≈ 0,045, ama genişlik σ ≈ 0,0046. Tümsek üç kat daha keskin.

200.000 sorgudan sonra, 8000 yanlışlaştırmayla: Beta(8001, 192.001). Orta ≈ 0,040, genişlik σ ≈ 0,0004. Tümsek bir iğne olur.

Bir Nokta Kütlesine Geometrik Yakınsama

n → ∞ olarak, Beta posterior gerçek ε'de Dirac deltasına çöker. Geometri: dikdörtgen → geniş tümsek → dar tümsek → iğne → nokta. Her sorgu dağılımımızı 1/√n kadar sıklaştırır.

Bu Teorik PAC Sınırlarını Neden Yener

Teorik PAC sınırları hipotez sınıfı boyutuna dayalı STATİK bir ε tahmini verir. Beta posterior, her gözlemle sıklaşan, gerçek dünyadaki dağılımınıza göre kalibre edilen DİNAMİK bir ε tahmini verir. Teorik sınır = en kötü durum varsayımları altında bir garanti. Ampirik denetim = gerçek dünyadaki bir ölçüm.

Güvenilir Aralığı Yarıya İndirmek İçin Kaç Sorgu

Şu anda 200 sorgudan sonra Beta(9, 193)'de oturuyoruz: orta ε ≈ 0,045, σ ≈ 0,014. Güvenilir aralık genişliğini yarıya indirmek istiyoruz, σ ≈ 0,007.