Probably Approximately Correct
Pytanie Valianta (1984)
Leslie Valiant zadał pozornie proste pytanie: co oznacza, że maszyna się uczy? Nie „czy potrafi zapamiętywać?” Nie „czy potrafi przewidywać idealnie?” Zamiast tego: czy potrafi uczyć się w przybliżeniu dobrze, z wysokim prawdopodobieństwem, z skończonej próbki, w czasie wielomianowym?
To ujęcie przyniosło mu Nagrodę Turinga w 2010 roku i zapoczątkowało teorię uczenia obliczeniowego.
Dwa pokrętła
ε (epsilon) — tolerancja błędu. Około poprawne oznacza błąd ≤ ε. Mniejsze ε = surowsze uczenie.
δ (delta) — parametr ufności. Prawdopodobnie oznacza prawdopodobieństwo sukcesu ≥ 1 − δ. Mniejsze δ = wymagana większa pewność.
Definicja
Klasa koncepcji C jest PAC-learnable, jeśli istnieje algorytm taki, że dla dowolnego rozkładu danych D oraz dowolnej koncepcji docelowej c ∈ C, na podstawie m próbek wylosowanych z D i oznaczonych etykietami według c, algorytm zwraca hipotezę h spełniającą:
P[error(h) ≤ ε] ≥ 1 − δ
przy czym m jest wielomianowe względem 1/ε, 1/δ oraz rozmiaru koncepcji.
W języku angielskim: podaj mu wystarczająco dużo przykładów, a będzie wystarczająco często wystarczająco blisko, a „wystarczająco” nie rośnie wykładniczo.
Złożoność próbkowania dla skończonych przestrzeni hipotez
Jeśli nasza przestrzeń hipotez H zawiera skończoną liczbę kandydackich hipotez, klasyczna analiza daje:
m ≥ (1/ε)(ln|H| + ln(1/δ))
Czytaj tę formułę jak budżet. Zmniejszenie ε o połowę podwaja wymaganą liczbę próbek. Zmniejszenie δ o połowę dodaje stałą. Podwojenie |H| dodaje ln(2) próbek — skalowanie logarytmiczne, pięknie łagodny wzrost.
Dobór wielkości próby dla skończonej klasy hipotez
Filtr antyspamowy wybiera spośród |H| = 1 000 000 kandydackich zbiorów reguł. Chcemy, aby błąd ε ≤ 0,05 przy pewności 1 − δ = 0,99 (czyli δ = 0,01).
Rozbijanie i wymiar VC
Gdy przestrzenie hipotez stają się nieskończone
Ograniczenie m ≥ (1/ε)(ln|H| + ln(1/δ)) przestaje działać, gdy |H| = ∞. Większość użytecznych klas hipotez (klasyfikatory liniowe w ℝᵈ, drzewa decyzyjne, sieci neuronowe) zawiera nieskończenie wiele kandydatów. Vapnik i Chervonenkis rozwiązali ten problem około 1971 roku, wprowadzając bogatszą miarę złożoności: wymiar VC.
Rozbijanie (Shattering)
Klasa hipotez H rozbija (shatters) zbiór n punktów, jeśli H potrafi wygenerować każde możliwe etykietowanie tych n punktów (wszystkie 2ⁿ dychotomie). Klasyfikatory liniowe w ℝ² rozbijają dowolne 3 punkty w położeniu ogólnym: dla każdego z 8 możliwych etykietowań +/− tych 3 punktów istnieje linia, która poprawnie je rozdziela.
Ale klasyfikatory liniowe w ℝ² nie mogą rozbić 4 punktów ułożonych w konfiguracji XOR. Żadna prosta linia nie oddziela pary przekątnej od pary anty-przekątnej.
Wymiar VC
VC(H) = największe n takie, że H rozbija pewien zbiór n-punktowy. Dla liniowych klasyfikatorów 2D: VC = 3. Dla prostokątów osiowo-równoległych w 2D: VC = 4. Dla sieci neuronowych z W wagami: VC ≤ O(W² log W) (Bartlett & Anthony 1999).
Złożoność próbkowania z wymiarem VC
Zastąp ln|H| w naszej granicy PAC wymiarem VC d:
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
Wymiar VC działa jako nasza „efektywna złożoność” nieskończonej klasy. Klasa hipotez o niskim wymiarze VC generalizuje z niewielu próbek; klasa o wysokim wymiarze VC wymaga więcej danych.
Wymiar VC jako efektywna liczba hipotez
Sieć neuronowa ma W = 10⁹ wag. Zgodnie z nierównością Bartletta-Anthony’ego VC ≤ O(W² log W). Przybliżamy VC ≈ W² log₂ W.
Odrzucenie realizowalności, rozkłady a posteriori nad hipotezami
Dwa ważne uogólnienia
Klasyczny PAC zakłada, że nasza docelowa koncepcja c znajduje się wewnątrz klasy hipotez H. Rzeczywiste dane niosą szum, błędne etykiety i koncepcje, których nasza klasa nie może reprezentować. Dwa rozszerzenia radzą sobie z tym problemem.
Agnostic PAC
Porzucamy założenie, że c ∈ H. Teraz konkurujemy z naszą najlepszą w klasie hipotezą h* = argmin_{h ∈ H} risk(h). Zmienia się kształt granicy: zamiast zbliżać się do ideału, zbliżamy się do najlepszego możliwego w obrębie H.
Granica agnosticzna: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ z liczbą próbek m = O(1/ε² × (VC(H) + log(1/δ))). Zauważ ε² zamiast ε w mianowniku: uczenie agnosticzne wymaga więcej próbek dla tej samej precyzji.
PAC-Bayes (McAllester 1999)
Przechodzimy od wyboru pojedynczej hipotezy do wyboru rozkładu nad hipotezami. Zaczynamy od rozkładu a priori P. Obserwujemy dane. Wyznaczamy rozkład a posteriori Q. Granice PAC-Bayes dotyczą oczekiwanego ryzyka względem Q:
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) mierzy, jak bardzo nasze posterior oddaliło się od naszego prior. Dwie interpretacje:
1. Widok kompresji. Posterior bliskie swojemu prior (małe KL) dobrze generalizuje — mały koszt informacyjny = mała luka generalizacyjna.
2. Widok bayesowski. Silny prior + słaba aktualizacja danymi = ciasne oszacowanie; słaby prior + silna aktualizacja danymi = luźniejsze oszacowanie.
Dlaczego PAC-Bayes ma znaczenie. Empiryczne oszacowania PAC-Bayes (Catoni 2007, Dziugaite & Roy 2017) dają numerycznie znaczące gwarancje generalizacji dla rzeczywistych sieci neuronowych, gdzie klasyczne oszacowania PAC są puste. Pozostają one naszym najmocniejszym teoretycznym narzędziem do badania generalizacji w modelach nadparametryzowanych.
Odczytywanie PAC-Bayes Bound
Załóżmy, że trenujemy sieć na n = 50 000 oznaczonych przykładów. Po treningu nasza posterior Q nad wagami ma KL(Q‖P) = 200 natów względem gaussowskiego prioru P. Ryzyko empiryczne pod Q wynosi 0,10. Ustaw δ = 0,05.
Nadparametryzacja i podwójne zejście
Klasyczna teoria PAC przewidywała katastrofę
Klasyczna teoria PAC przewiduje: więcej parametrów niż próbek = katastrofalne przeuczenie. Model uczy się idealnie na danych treningowych, a na danych testowych generalizuje losowo. Granica VC przewiduje zapamiętywanie bez uczenia się.
Współczesne sieci neuronowe rutynowo mają od 10× do 1000× więcej parametrów niż próbek treningowych, a mimo to dobrze generalizują. Według klasycznej teorii nie powinno się to zdarzyć. A jednak się dzieje.
Krzywa U, której nas uczono
Klasyczny bias-variance: wraz ze wzrostem pojemności modelu błąd treningowy spada monotonicznie; błąd testowy najpierw spada (mniejsze niedouczenie), osiąga minimum, a następnie rośnie (przeuczenie). Kształt litery U przewidywany przez teorię VC.
Co się dzieje naprawdę — Double Descent
Belkin i in. (2019) pokazali, że błąd testowy podąża za klasyczną krzywą U aż do progu interpolacji (pojemność = liczba próbek), a następnie PONOWNIE SPADA po przekroczeniu tego progu. Silnie nadparametryzowane modele generalizują lepiej niż modele „wystarczająco duże”.
Dlaczego klasyczne PAC tego nie uwzględnia
1. Założenie niezależne od rozkładu jest zbyt pesymistyczne. Rzeczywiste dane mają strukturę (niska wymiarowość wewnętrzna, geometria rozmaitości). Ograniczenia PAC obowiązują dla najgorszych rozkładów; rzeczywiste rozkłady wykorzystują strukturę, którą wykorzystuje również SGD.
2. Ukryta regularyzacja. SGD na sieciach nadparametryzowanych znajduje rozwiązania interpolujące o minimalnej normie lub minimalnej złożoności, a nie dowolne. Klasyczna teoria zakłada najgorszy przypadek minimalizatora ryzyka empirycznego; rzeczywiste algorytmy wybierają rozwiązania łagodne.
3. Błędna definicja klasy hipotez. Efektywna klasa hipotez eksplorowana przez SGD jest znacznie mniejsza niż nominalna przestrzeń wag. Posteriory PAC-Bayes to oddają; wymiar VC nie.
Współczesne prace teoretyczne (Bartlett, Long, Lugosi, Tsigler 2020 na temat łagodnego nadmiernego dopasowania; Nakkiran i in. 2020 na temat podwójnego zejścia) budują post-PAC teorię generalizacji, która uwzględnia nasz reżim nadparametryzowany.
Diagnozowanie porażki klasycznego PAC
Zespół badawczy trenuje sieć z miliardem parametrów na 100 000 oznaczonych przykładów. Klasyczny PAC przewiduje próżne granice. Empirycznie dokładność na zbiorze testowym osiąga 95%.
Kaplan, Chinchilla i wymiarowanie zautomatyzowanej inteligencji ogólnej
Od oszacowań do empirycznych praw skalowania
Klasyczny PAC teoretycznie przewiduje rozmiar zbioru danych i daje próżne wyniki. Empiryczne prawa skalowania przewidują rozmiar zbioru danych na podstawie obserwacji i faktycznie działają. Zastąpiły PAC jako praktyczne narzędzie do określania rozmiaru dużych modeli.
Kaplan i in. (2020)
Strata podąża za prawem potęgowym względem liczby parametrów N, tokenów w zbiorze danych D oraz obliczeń C:
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
Podwojenie liczby parametrów zmniejsza stratę o stały czynnik multiplikatywny. Podwojenie danych zmniejsza stratę o inny stały czynnik. Te wykładniki (αN, αD, αC) mierzą i przewidują zachowanie na granicy możliwości w wielu rzędach wielkości.
Hoffmann et al 2022 (Chinchilla)
Chinchilla pokazało, że wykładniki Kaplana nadmiernie faworyzowały parametry względem danych. Trening optymalny pod względem obliczeniowym wymaga około 20 tokenów na parametr:
D_opt ≈ 20 × N
GPT-3 (175B parametrów) trenowany na ~300B tokenów — mocno niedotrenowany według obliczeń Chinchilla. Model optymalny obliczeniowo o 175 miliardach parametrów wymaga ~3,5 biliona tokenów.
The Data Wall
Skalowanie liczby parametrów wymaga proporcjonalnego skalowania liczby tokenów. Publiczne indeksowanie sieci daje ~10¹³ użytecznych tokenów. Hipotetyczna zautomatyzowana inteligencja ogólna o 10¹⁵ parametrach wymagałaby ~2×10¹⁶ tokenów — o trzy rzędy wielkości więcej niż dostępne dane z sieci.
To jest nasza ściana danych. Zgodnie z prawami skalowania zabraknie nam korpusu znacznie wcześniej niż mocy obliczeniowej. Dane syntetyczne, korpusy multimodalne (wideo, audio, strumienie sensorów) oraz uczenie przez wzmocnienie z otoczenia mają na celu jej pokonanie.
Klasyczna teoria PAC (nieprawidłowo) mówiła, że potrzeba 10²¹ próbek. Prawa skalowania (skalibrowane do rzeczywistości) wskazują, że potrzeba 2×10¹⁶. Obie liczby przekraczają dostępne dane tekstowe. Współczesna praca na poziomie frontier polega na zamykaniu tej luki.
Szacowanie korpusu dla zautomatyzowanej inteligencji ogólnej
Załóżmy, że laboratorium frontier proponuje model o 10¹⁴ parametrach i twierdzi, że osiągnie on zautomatyzowaną inteligencję ogólną. Chcemy oszacować wielkość jego korpusu treningowego zgodnie z regułą Chinchilla.
Od teoretycznych granic do pomiarów produkcyjnych
Przestań obliczać granice; zacznij je mierzyć
Klasyczne granice PAC są puste. Granice PAC-Bayes są ciasne, ale przy założeniach trudnych do zweryfikowania. Praktyczna alternatywa: zmierz ε empirycznie na rzeczywistym rozkładzie i aktualizuj go w trakcie działania systemu.
Idea 1 — Zrób pokrycie jako empiryczny PAC
Cel make coverage uruchamia N pytań z odłożonego zbioru przez Twój system zapytań i mierzy dwie wartości:
- cache_hit_rate — ułamek przypadków, w których system znalazł znaną odpowiedź
- i_dont_know_rate — ułamek przypadków, w których system uczciwie odmówił odpowiedzi
Każdy pomiar = próba Bernoulliego. Na podstawie zaobserwowanych liczebności obliczamy przedział ufności Wilsona dla prawdziwej częstości. Przykład: N = 1000 zapytań, zaobserwowana i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. Górna granica 0.226 działa dokładnie jak PAC ε przy δ = 0.05, wyliczona na podstawie rzeczywistych danych z rzeczywistego rozkładu, a nie najgorszego przypadku analizy teoretycznej.
Klasyczne pojęcia PAC mają zastosowanie (ε, δ, ufność). Inny aparat matematyczny (koncentracja dwumianowa vs. teoria VC). Wynik jest ostrzejszy, ponieważ rzeczywiste rozkłady zawierają strukturę, którą można wykorzystać.
Idea 2 — Audyt PAC-Bayes przez zdarzenia falsyfikacji
Każde zdarzenie falsyfikacji (odpowiedź systemu wyraźnie błędna) traktujemy jako dowód aktualizujący rozkład a posteriori prawdziwej stopy błędu ε:
1. Prior: ε ~ Beta(α₀, β₀). Wybierz słaby prior, np. Beta(1, 1) = rozkład jednostajny.
2. Każde zapytanie daje wynik Bernoulliego: sfałszowane (1) lub utrzymane (0).
3. Rozkład a posteriori po k fałszerstwach w n zapytaniach: Beta(α₀ + k, β₀ + n − k).
4. Średnia rozkładu a posteriori: (α₀ + k) / (α₀ + β₀ + n) → empiryczna stopa fałszerstw przy n → ∞.
5. 95% przedział wiarygodności dla ε zwęża się jak 1/√n.
Co nam to daje
- Rzeczywista estymacja ε₀ z rzeczywistego wdrożenia, a nie teoria najgorszego przypadku
- Alarm anytime-valid: gdy przedział wiarygodności a posteriori przekracza próg kontraktowy, powiadom zespół
- Monotoniczna pewność: więcej obserwacji → węższy CI → silniejsza gwarancja
Techniki pokrewne: predykcja konformalna z online-rekalibracją (Vovk), sekwencyjne testy ilorazu prawdopodobieństwa (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Ta sama rodzina, różne aparaty matematyczne.
Obliczanie rozkładu Beta a posteriori na podstawie falsyfikacji
Nasz zespół przeprowadza audyt pokrycia w produkcyjnym systemie zapytań. Prior na prawdziwą stopę błędów ε: Beta(1, 1) (rozkład jednostajny). Po 200 zapytaniach z hold-out zaobserwowaliśmy 8 falsyfikacji.