Dichotomie na chmurach punktów

Jak wygląda rozbijanie

Umieść n punktów na naszej płaszczyźnie. Wybierz klasę hipotez (klasyfikatory liniowe = linie proste). Policz na ile różnych sposobów nasza klasa może etykietować te n punktów (+/− po każdej stronie linii). Nazwij tę liczbę Π_H(n).

Jeśli Π_H(n) = 2ⁿ, nasza klasa rozbiwa ten zbiór punktów — może wytworzyć każde możliwe etykietowanie. Jeśli Π_H(n) < 2ⁿ, niektóre etykietowania nie mogą się pojawić.

Trzy punkty w pozycji ogólnej

Klasyfikatory liniowe w ℝ² rozbijają dowolne 3 punkty nie leżące na jednej linii. 2³ = 8 etykietowań; wszystkie 8 osiągalne przez jakąś linię. Wybierz dowolne 3 punkty; dla każdego ±/± etykietowania narysuj linię, która separuje pozytywne od negatywnych.

Cztery punkty odmawiają rozbijania

Umieść 4 punkty w narożnikach kwadratu. Spróbuj etykietować parę diagonalną jako pozytywną & drugą diagonalną parę jako negatywną (etykietowanie XOR). Żadna linia prosta ich nie separuje. Więc Π_H(4) ≤ 14 < 16 = 2⁴.

Wymiar VC jako maksymalny rozmiar rozbijania

VC(liniowe ℝ²) = 3. Możemy rozbić 3 punkty; nie możemy rozbić 4. VC zlicza maksymalną zdolność dichotomii naszej klasy hipotez.

Intuicja geometryczna

Wyższe VC = nasza klasa rysuje bardziej zaawansowane granice decyzji. Liniowe (VC = d+1 w d wymiarach) rysuje hiperpłaszczyzny. Wielomiany rysują krzywe. Sieci neuronowe rysują wysoce złożone rozmaitości. Większa foldowalność = więcej dichotomii = wyższe VC = wyższy wymóg próbek.

Liczenie dichotomii

Rozważ klasyfikatory liniowe w ℝ² (linie). Mamy 5 punktów umieszczonych w pozycji ogólnej (żadne 3 nie leżą na jednej linii, brak nadmiarowych).

Masa probabilistyczna na rozmaitości hipotez

Obrazowanie PAC-Bayesa

Wyobraź sobie przestrzeń hipotez jako wysokowymiarową rozmaitość. Każdy punkt na tej rozmaitości odpowiada jednej konfiguracji wag sieci neuronowej. Prior P przypisuje rozkład probabilistyczny na naszej rozmaitości (często Gaussowski wyśrodkowany na inicjalizacji). Posterior Q koncentruje masę probabilistyczną tam, gdzie dane treningowe skierowały nasze wagi.

Dywergencja KL jako odległość geometryczna

KL(Q‖P) mierzy jak daleko Q przesunęło się od P. Odczyt geometryczny: jak bardzo chmura posteriori przesunęła się od chmury prior, ważone przez to jak mało prawdopodobna była każda obszar posteriori pod priorem.

Małe KL = Q silnie pokrywa P. Posterior prawie się nie przesunął. Luka generalizacji pozostaje mała.

Duże KL = Q skoncentrowane w regionach którym P przypisał małą masę. Posterior przesunął się wiele. Luka generalizacji rośnie.

Dlaczego ta geometria ma znaczenie

Wyobraź sobie SGD jako trajektorię poszukiwań na naszej rozmaitości hipotez. Trajektoria kończy się w basenie niskiej straty treningowej. PAC-Bayes pyta: jak szeroki jest ten basen?

Szeroki basen = wiele sąsiednich konfiguracji wag osiąga również niską stratę treningową. Posterior Q może rozłożyć się na szerokim regionie & nadal mieć niskie ryzyko. KL(Q‖P) pozostaje ograniczone. Luka generalizacji mała.

Wąski basen = tylko cienki zbiór wag osiąga niską stratę. Posterior musi się skoncentrować ostro. KL rośnie. Luka generalizacji się powiększa.

To łączy się bezpośrednio z dyskursem płaskich-vs-ostrych minimów (Hochreiter & Schmidhuber 1997, Keskar i in. 2017). Płaskie minima lepiej generalizują ponieważ wspierają szersze posteriory z mniejszym KL.

Odczytywanie szerokości basenu

Dwa wytrenowane modele osiągają identyczną stratę treningową ale żyją w różnych basenach:

- Model A: płaski basen, posterior rozprzestrzenia się na regionem z KL(Q_A‖P) = 50 nats.

- Model B: ostry basen, posterior koncentruje się z KL(Q_B‖P) = 500 nats.

Oba wytrenowane na n = 10 000 przykładów z empirycznym ryzykiem 0,05, δ = 0,05.

Krzywa która spada tam gdzie teoria przewidywała wzrost

Klasyczna krzywa U

Wykreśl pojemność modelu na osi poziomej. Wykreśl ryzyko testowe na osi pionowej. Klasyczna teoria bias-variance przewiduje:

- Niska pojemność: wysokie obciążenie, wysokie ryzyko testowe (niedouczenie)

- Średnia pojemność: niskie obciążenie + niska wariancja, niskie ryzyko testowe (słodki punkt)

- Wysoka pojemność: niskie obciążenie, wysoka wariancja, wysokie ryzyko testowe (przeuczenie)

Wynik: krzywa w kształcie U. Wybierz pojemność na dnie.

Co obserwowali Belkin i in. (2019)

Poza progiem interpolacji (pojemność gdzie model dokładnie dopasowuje dane treningowe z błędem zerowym), ryzyko testowe SPADA ponownie. Krzywa czyta: zjazd → szczyt na interpolacji → drugi zjazd. Dwa zjazdy, jedna krzywa.

Geometryczne odczytanie drugiego zjazdu

Na progu interpolacji, model ma dokładnie wystarczającą pojemność aby dopasować dane treningowe — istnieje tylko jedno (lub kilka) rozwiązań interpolujących & mają one tendencję do bycia poszarpane. Generalizacja cierpi ponieważ wybrane rozwiązanie jest zmuszone.

Poza progiem interpolacji, WIELE rozwiązań interpolujących istnieje. SGD ma wolność aby wybrać gładkie (minimum-norm, niska-krzywizna). Obraz geometryczny: rozmaitość rozwiązań staje się szersza & bardziej płaska. Niejawna regularyzacja SGD wybiera łagodne rozwiązania z tej płaskiej rozmaitości. Ryzyko testowe spada.

Dlaczego klasyczna teoria to pomijaTo

Wymiar VC zlicza pojemność zboru rozwiązań ale ignoruje które rozwiązanie zostaje wybrane. Klasyczna granica zakłada worst-case empirical risk minimizer. Rzeczywistość: SGD niezawodnie wybiera NAJPŁASZE, NAJGŁADSZE rozwiązanie interpolujące. Raz gdy liczymy ROZWIĄZANIA WYBRANE PRZEZ SOLVER zamiast wszystkich rozwiązań, drugi zjazd ma sens.

Geometryczne wytłumaczenie podsumowania

Pojemność ma mniejsze znaczenie niż geometria basenu. Szerokie płaskie baseny (post-interpolacja) generalizują lepiej niż wąskie ostre (na interpolacji). Nowoczesna teoria stara się ograniczyć generalizację szerokością basenu, nie liczbą parametrów.

Lokalizowanie dwóch zjaz

Na krzywej podwójnego zjazdu, trzy regiony są ważne: (1) regime niewystarczająco sparametryzowany, (2) szczyt interpolacji, (3) regime nadparametryzowany.

Powierzchnia potęgowa w przestrzeni parametr-token

Powierzchnia 3D

Wykreśl parametry N na jednej osi poziomej. Wykreśl tokeny D na drugiej osi poziomej. Wykreśl stratę L na pionowej. Empiryczna strata karze powierzchnię potęgową na tej (N, D) płaszczyźnie:

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

Powierzchnia nachyla się w dół gdy rośnie N lub D. Nachylenia podążają za liniami log-log (proste linie na wykresie log-log). Asymptota L∞ pozostaje pozytywna — nieodwracalna strata którą nasz model nie może zmniejszyć poniżej.

Grzebień compute-optimal

Napraw całkowity budżet obliczeń C ∝ N × D (parametry × tokeny, mniej więcej). Narysuj naszą powierzchnię wzdłuż tego ograniczenia. Narysowanie przecina 2D krzywą przez 3D powierzchnię. Dno tej krzywej = punkt compute-optimal.

Chinchilla (Hoffmann i in. 2022) obliczył to dno analitycznie: D_opt ≈ 20 × N. Krzywa wzdłuż budżetu obliczeń = grzebień. Chodzenie wzdłuż grzebienia: równe obliczenia, malejąca strata. Chodzenie poza grzebień (więcej parametrów niż 20× tokenów, lub mniej): marnowane obliczenia.

Geometryczne odczytanie GPT-3 vs Chinchilla

GPT-3: 175B parametrów, 300B tokenów. Chinchilla-optimal chciałaby 175B × 20 = 3500B tokenów. GPT-3 siedzi daleko od grzebienia compute-optimal w naszym kierunku bogatym parametrami. Chinchilla sam: 70B parametrów wytrenowanych na 1400B tokenów. 1400 / 70 = 20 — dokładnie na grzebeniu. Chinchilla pokonała GPT-3 z mniej niż połową jej liczby parametrów poprzez siedzianie na geometrycznym optimum.

Mur danych jako płaszczyzna pionowa

Publiczna sieć ~10¹³ użytecznych tokenów. To wykreśla się jako ściana pionowa na D = 10¹³ na naszej płaszczyźnie parametr-token. Poza tą ścianą, trening compute-optimal wymaga N ≤ D / 20 = 5 × 10¹¹ parametrów. Ściany poza N = 5 × 10¹¹ albo biegną niedotrenowane (poza grzebień) albo wymagają syntetycznych / multimodalnych / RL danych aby popchnąć ścianę na zewnątrz.

Chodzenie wzdłuż grzebienia compute-optimal

Siedzimy na współrzędnych GPT-3: N = 175B parametrów, D = 300B tokenów. Pełnomocnik obliczeń C = N × D = 5,25 × 10²² parametr-tokeny.

Posteriori Beta ściskające się w igłę

Gęstość probabilistyczna na [0, 1]

Beta(α, β) jest gęstością probabilistyczną na interwale jednostkowym [0, 1]. Zmienna: ε = rzeczywista stopa błędu. Kształt: α kontroluje masę na stronie wysokiej ε; β kontroluje masę na stronie niskiej ε.

Beta(1, 1): równomierny — brak informacji, płaska gęstość na [0, 1].

Beta(α, β) z α + β duże: skoncentrowany szczyt na α / (α + β).

Szerokość szczytu Beta kurczy się jako 1/√(α+β). Dodanie 100 obserwacji do naszego prior zaciąga szczyt o współczynnik √100 = 10. Dodanie 10000 obserwacji zaciąga o √10000 = 100.

Geometryczne odczytanie przebiegu audyty

Zacznij: Beta(1, 1) = płaski prostokąt na [0, 1]. Maksymalna niepewność o ε.

Po 200 zapytaniach z 8 fałszywymi: Beta(9, 193). Średnia = 9/202 ≈ 0,045. Gęstość teraz ostry garb wyśrodkowany blisko 0,045 z charakterystyczną szerokością σ ≈ 0,014.

Po 2000 zapytaniach z 80 fałszywymi: Beta(81, 1921). Średnia nadal ≈ 0,045, ale szerokość σ ≈ 0,0046. Garb trzy razy ostrzejszy.

Po 200 000 zapytaniach z 8000 fałszywymi: Beta(8001, 192,001). Średnia ≈ 0,040, szerokość σ ≈ 0,0004. Garb staje się igłą.

Geometryczna konwergencja do masy punktowej

Gdy n → ∞, posterior Beta zwija się do Diraca delta na prawdziwej ε. Geometria: prostokąt → szeroki garb → wąski garb → igła → punkt. Każde zapytanie zaciąga naszą dystrybucję o 1/√n.

Dlaczego to bije teoretyczne granice PAC

Teoretyczne granice PAC dają STATYCZNĄ estymację ε opartą na rozmiarze klasy hipotez. Posterior Beta daje DYNAMICZNĄ estymację ε która zaciąga się z każdą obserwacją, kalibrowaną przeciwko twojej rzeczywistej dystrybucji. Teoretyczna granica = gwarancja w worst-case założeniach. Empiryczna audyta = pomiar rzeczywistości.

Ile zapytań aby zmniejszyć o połowę interwał wiarygodności?

Siedzimy teraz na Beta(9, 193) po 200 zapytaniach: średnia ε ≈ 0,045, σ ≈ 0,014. Chcemy zmniejszyć o połowę szerokość interwału wiarygodności do σ ≈ 0,007.