Дихотомії на хмарах точок

Як виглядає розбиття

Розмістіть n точок у нашій площині. Виберіть клас гіпотез (лінійні класифікатори = прямі лінії). Порахуйте скільки різних способів наш клас може позначити ці n точок (+/− з обох сторін прямої). Назвіть цей рахунок Π_H(n).

Якщо Π_H(n) = 2ⁿ, наш клас розбиває цей набір точок — він може створити кожне можливе позначення. Якщо Π_H(n) < 2ⁿ, деякі позначення не можуть відбутися.

Три точки в загальному положенні

Лінійні класифікатори в ℝ² розбивають будь-які 3 не-колінеарні точки. 2³ = 8 позначень; усі 8 досяжні деякою прямою. Виберіть будь-які 3 точки; для кожного ±/± позначення накресліть пряму, яка розділяє позитив від негативу.

Чотири точки відмовляються розбиватися

Розмістіть 4 точки в кутках квадрату. Спробуйте позначити діагональну пару як позитив & анти-діагональну пару як негатив (XOR позначення). Жодна пряма лінія не розділяє їх. Тому Π_H(4) ≤ 14 < 16 = 2⁴.

VC-розмірність як максимальний розмір розбиття

VC(лінійна ℝ²) = 3. Ми можемо розбити 3 точки; ми не можемо розбити 4. VC рахує максимальну дихотомну ємність нашого класу гіпотез.

Геометрична інтуїція

Вищий VC = наш клас малює більш складні межи рішень. Лінійна (VC = d+1 в d вимірах) малює гіперплощини. Поліноми малюють криві. Нейромережі малюють сильно зігнуті різноманітності. Більше складності = більше дихотомій = вищий VC = вища вимога вибірки.

Подрахунок дихотомій

Розглянемо лінійні класифікатори в ℝ² (лінії). Маємо 5 точок розміщених в загальному положенні (жодні 3 не-колінеарні, жодна не-зайва).

Ймовірнісна маса на різноманітності гіпотез

Малювання PAC-Bayes

Уявіть простір гіпотез як високовимірну різноманітність. Кожна точка на цій різноманітності відповідає одній конфігурації ваг нейромережі. Prior P призначає розподіл ймовірності по різноманітності (часто Гауса центрований на ініціалізації). Posterior Q концентрує ймовірнісну масу де дані тренування спрямували наші ваги.

KL Розбіжність як геометрична відстань

KL(Q‖P) вимірює наскільки далеко Q дрейфувала від P. Геометричне читання: наскільки далеко наша задня хмара посунулася від prior хмари, зважена на те наскільки малоймовірна кожна задня область була під prior.

Мала KL = Q сильно перекривається P. Posterior ледь рухнув. Розрив узагальнення залишається малий.

Велика KL = Q зосереджена в регіонах P призначила малу масу. Posterior рухнув багато. Розрив узагальнення зростає.

Чому ця геометрія має значення

Уявіть SGD як траєкторію пошуку по різноманітності гіпотез. Траєкторія закінчується в басейні низької тренувальної втрати. PAC-Bayes запитує: наскільки широкий цей басейн?

Широкий басейн = багато сусідніх конфігурацій ваг також досягають низької тренувальної втрати. Posterior Q може розтягнутися по широкому регіону & все ще мати низький ризик. KL(Q‖P) залишається обмежена. Розрив узагальнення малий.

Вузький басейн = тільки тонка множина ваг досягає низької втрати. Posterior повинна зосередитися гостро. KL зростає. Розрив узагальнення розширюється.

Це пов'язує безпосередньо з дискусом про плоскі-vs-гострі мініми (Hochreiter & Schmidhuber 1997, Keskar та ін 2017). Плоскі мініми узагальнюють краще, тому що вони підтримують ширші posteriory з меншим KL.

Читання ширини басейну

Два тренованих моделі досягають однакової тренувальної втрати, але живуть у різних басейнах:

- Модель A: плоский басейн, posterior розтягується по регіону з KL(Q_A‖P) = 50 натів.

- Модель B: гострий басейн, posterior концентрується з KL(Q_B‖P) = 500 натів.

Обидві треновані на n = 10,000 прикладах з емпіричним ризиком 0,05, δ = 0,05.

Крива яка падає де теорія передбачала підйом

Класична U-крива

Побудуйте ємність моделі на горизонтальній осі. Побудуйте тестовий ризик на вертикальній осі. Класична теорія зміщення-дисперсії передбачає:

- Низька ємність: висока упередженість, високий тестовий ризик (недостатнє пристосування)

- Середня ємність: низька упередженість + низька дисперсія, низький тестовий ризик (солодка точка)

- Висока ємність: низька упередженість, висока дисперсія, високий тестовий ризик (перепристосування)

Результат: U-подібна крива. Виберіть ємність на її дні.

Що спостерігали Белкін та ін (2019)

Минаючи поріг інтерполяції (ємність де модель точно підходить тренувальним даним з нульовою помилкою), тестовий ризик ПАДАЄ знову. Крива читає: спуск → піку на інтерполяції → другий спуск. Два спуски, одна крива.

Геометричне читання другого спуску

На порозі інтерполяції, модель має рівно достатньо ємності, щоб відповідати тренувальним даним — існує лише одне (або кілька) інтерполюючих рішення & вони мають тенденцію бути невправними. Узагальнення страждає, тому що обране рішення примушене.

Минаючи поріг інтерполяції, БАГАТО інтерполюючих рішень існують. SGD має свободу вибрати гладке (мінімальної норми, низької кривини). Геометрична картина: різноманітність рішень стає ширшою & пласкішою. Неявна регуляризація SGD вибирає доброякісні рішення з цієї плоскої різноманітності. Тестовий ризик падає.

Чому класична теорія це пропускає

VC-розмірність рахує ємність набору рішень, але ігнорує яке рішення буде обране. Класична межа припускає гірший випадок емпіричного мінімізатору ризику. Реальність: SGD надійно вибирає найпласкіше, найгладше інтерполюючи рішення. Коли ми рахуємо ВИБРАНІ РОЗВ'ЯЗУВАЧЕМ рішення замість усіх рішень, другий спуск має сенс.

Геометричний висновок

Ємність має менше значення, ніж геометрія басейну. Широкі плоскі басейни (після інтерполяції) узагальнюють краще, ніж вузькі гострі (на інтерполяції). Сучасна теорія намагається обмежити узагальнення шириною басейну, не за рахунком параметрів.

Пошук двох спусків

На кривій подвійного спуску, три регіони мають значення: (1) недо-параметризований режим, (2) піку інтерполяції, (3) надмірно-параметризований режим.

Поверхня степеневого закону в просторі параметр-токен

3D поверхня

Побудуйте параметри N на одній горизонтальній осі. Побудуйте токени D на другій горизонтальній осі. Побудуйте втрату L на вертикальній. Емпірична втрата вирізьблює поверхню степеневого закону по цій (N, D) площині:

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

Поверхня схилу вниз коли будь-яке N або D зростає. Схили слідують за лог-лінійними степеневими законами (прямі лінії в лог-лог графіку). Асимптота L∞ залишається позитивною — незменшувана втрата яку наша модель не може зменшити за.

Обчислювально-оптимальний гребінь

Фіксуйте загальний обчислювальний бюджет C ∝ N × D (параметри × токени, приблизно). Нарізайте нашу поверхню вздовж цього обмеження. Нарізка розпрямляє 2D криву через 3D поверхню. Дно цієї кривої = обчислювально-оптимальна точка.

Chinchilla (Hoffmann та ін 2022) обчислили це дно аналітично: D_opt ≈ 20 × N. Крива вздовж обчислювального бюджету = гребінь. Ходіння вздовж гребня: рівний обчислювальний бюджет, зменшуюча втрата. Ходіння від гребня (більше параметрів, ніж 20× токенів, або менше): розтрачений обчислювальний бюджет.

Геометричне читання GPT-3 vs Chinchilla

GPT-3: 175B параметрів, 300B токенів. Chinchilla-оптимальна би хотіла 175B × 20 = 3500B токенів. GPT-3 сидить далеко від обчислювально-оптимального гребня в нашому параметр-важкому напрямку. Chinchilla сама: 70B параметрів, тренована на 1400B токенах. 1400 / 70 = 20 — рівно на гребні. Chinchilla перемогла GPT-3 з менш як половиною рахунку параметрів сидячи на геометричному оптимумі.

Стіна даних як вертикальна площина

Публічна мережа ~10¹³ корисних токенів. Це побудує вертикальну стіну на D = 10¹³ на нашій параметр-токен площині. За цією стіною, обчислювально-оптимальне тренування потребує N ≤ D / 20 = 5 × 10¹¹ параметрів. Стіни за N = 5 × 10¹¹ або недо-тренуються (від-гребня) або потребують синтетичних / мультимодальних / RL даних для штовхання стіни назовні.

Ходіння обчислювально-оптимального гребня

Ми сидимо в координатах GPT-3: N = 175B параметрів, D = 300B токенів. Обчислювальний проксі C = N × D = 5,25 × 10²² параметр-токени.

Beta Posterior, що звужується в голку

Щільність ймовірності на [0, 1]

Beta(α, β) — щільність ймовірності над одиничним інтервалом [0, 1]. Змінна: ε = істинна коефіцієнт помилки. Форма: α керує масою на високо-ε стороні; β керує масою на низько-ε стороні.

Beta(1, 1): рівномірна — немає інформації, плоска щільність по [0, 1].

Beta(α, β) з α + β великим: сконцентрована вершина на α / (α + β).

Ширина Beta вершини звужується як 1/√(α+β). Додавання 100 спостережень до нашого prior стискує вершину на множник √100 = 10. Додавання 10000 спостережень стискує на √10000 = 100.

Геометричне читання аудит-запуску

Почніть: Beta(1, 1) = плоский прямокутник на [0, 1]. Максимальна невизначеність про ε.

Після 200 запитів з 8 помилками: Beta(9, 193). Середнє = 9/202 ≈ 0,045. Щільність тепер гострий горб сконцентрований близько 0,045 з характеристичною шириною σ ≈ 0,014.

Після 2000 запитів з 80 помилками: Beta(81, 1921). Середнє все ще ≈ 0,045, але ширина σ ≈ 0,0046. Горб три раза гострішим.

Після 200,000 запитів з 8000 помилками: Beta(8001, 192,001). Середнє ≈ 0,040, ширина σ ≈ 0,0004. Горб стає голкою.

Геометрична конвергенція до точкової маси

Коли n → ∞, Beta posterior колапсує до Dirac delta на істинному ε. Геометрія: прямокутник → широкий горб → вузький горб → голка → точка. Кожний запит стискує нашо розподіл на 1/√n.

Чому це перемагає теоретичні PAC-межі

Теоретичні PAC-межі дають СТАТИЧНУ ε оцінку засновану на розмірі класу гіпотез. Beta posterior дає ДИНАМІЧНУ ε оцінку що звужується з кожним спостереженням, калібровану проти вашого дійсного розподілу. Теоретична межа = гарантія під гіршим-випадком припущеннями. Емпіричний аудит = вимірювання дійсної реальності.

На скільки запитів, щоб половинити інтервал довіри?

Ми тепер сидимо на Beta(9, 193) після 200 запитів: середнє ε ≈ 0,045, σ ≈ 0,014. Ми хочемо половинити ширину інтервалу довіри до σ ≈ 0,007.