Бритва Оккама

Сеть, которая может всё, выучит и шум

Урок 12 выдал сети лицензию на всё: Feed Forward Neural Network с одним скрытым слоем — universal approximator. Третья лекция открывается слайдом с тем же заголовком, "Neural Networks are Universal Approximators", и той же цитатой (лекция 3, слайд 2): Universal approximation theorem (Kurt Hornik, 1991) повторена слово в слово, а оговорки под ней переписаны. Сначала "Regardless of what function we are learning; a single layer can do it …", затем три продолжения:

• "… but it doesn't mean we can find the necessary weights!" — веса существуют, но их ещё надо найти;
• "… but an exponential number of hidden units may be required" — нейронов может понадобиться экспоненциально много;
• "… but it might be useless in practice if it does not generalize!" — сеть бесполезна, если не умеет обобщать.

Первые два «but» разобраны в уроке 12. Третье в лекции 2 звучало иначе: "The layer may have to be unfeasibly large and may fail to learn and generalize" (лекция 2, слайд 20). Теперь от него осталось главное слово — generalize: хорошо работать на точках, которых при обучении не было. Вся третья глава — про это одно слово.

Начнём с того, из чего сделаны данные. Обучающие точки — не сама закономерность. Это закономерность плюс случайные отклонения:

Сеть получает только числа \(t_n\). Где в каждом из них закономерность, а где случайность, не подписано. Жёсткая модель шум пропустит: ей нечем под него изогнуться. Гибкая модель умеет изобразить что угодно — значит, изобразит и шум.

У двух крайних случаев есть имена. На экзамене они нужны по-английски.

У профессора оба определения сжаты до двух подписей к картинке (лекция 3, слайд 3): "Too simple models Underfit the data ..." и "Too complex models Overfit the data and do not Generalize". Во второй подписи два утверждения сразу: модель подогнала обучающие данные и при этом не обобщает. Сама картинка со слайда — на рис. 2 в следующем разделе.

Конспект сравнивает overfitting с зубрёжкой: кто заучил ответы к прошлогодним задачам, решит их блестяще и провалится на новых. Underfitting — другая беда: тема не понята вовсе, плохо и на старых задачах, и на новых.

Что именно срезает бритва

Из рис. 1 напрашивается правило, которое связывают с именем Уильяма Оккама. У профессора оно стоит сразу под тремя «but», на латыни и рядом с портретом автора (лекция 3, слайд 2): "Entia non sunt multiplicanda praeter necessitatem", подпись — William of Ockham (c 1285 – 1349). Перевод: «не следует умножать сущности без необходимости». Больше про Оккама на слайде ничего нет: что фраза значит для моделей, договаривает конспект (стр. 124 и 126).

Underfitting — не всегда маленькая сеть

У сети причин для underfitting больше, чем у полинома. Конспект перечисляет пять:

• слишком мало нейронов или слоёв;
• обучение остановили слишком рано;
• learning rate слишком велик, и gradient descent не сходится;
• слишком сильная регуляризация: большой weight decay, много dropout;
• неинформативные признаки или забытая нормализация входов.

Две ошибки: на своих точках и на новых

У каждой модели на рис. 1 есть две разные ошибки. Одну мы умеем считать. Другая нам на самом деле нужна.

Посчитать \(E\) нельзя: для этого нужны все возможные точки. Её можно только оценить по точкам, которых модель не видела. Такую оценку называют test error, и ей посвящён следующий урок. Пока вопрос проще: когда маленькая \(\hat E_{\text{train}}\) обещает маленькую \(E\)?

Три слова слайда в обозначениях урока. Solution — найденная модель \(g(x|\vb{w})\): сеть с весами, которые выдало обучение. Target function — истинная функция \(f\); не путай её с target \(t_n\), одним измеренным значением. Unobserved examples — новые точки, которых не было среди обучающих; их же называют unseen data.

Под гипотезой на том же слайде две картинки. Это не украшение: они показывают два способа не выполнить её условие.

Обозначения \(M_1\), \(M_2\), \(M_n\) слайд не расшифровывает. По форме кривых индекс читается как степень полинома — та же ручка сложности, что на рис. 1. \(M_1\) — наша степень 1. \(M_2\) — модель подходящей сложности; на рис. 1 это степень 3, потому что там закономерность — синус, а не парабола. \(M_n\) — степень настолько высокая, что кривая проходит через каждую точку: на рис. 2 для девяти точек это степень 8, в лаборатории ниже для пятнадцати — степень 14. Истинной функции на слайде нет вовсе: её никто не видит, видны только кружки.

Теперь приложи к рис. 2 гипотезу. Прямая \(M_1\) не приближает даже обучающие примеры: посылка не выполнена, и обещать про новые точки нечего. Это underfitting. У \(M_n\) ошибка на обучающих примерах нулевая, но девять точек для модели с девятью коэффициентами — не "sufficiently large set". Посылка снова не выполнена, и вывод не сбывается: между точками кривая уходит от закономерности. Это overfitting. Параболе \(M_2\) с тремя коэффициентами тех же девяти точек хватает.

Отсюда и заголовок слайда — "Model Complexity": хватит ли примеров, зависит от сложности модели, которую по ним подгоняют.

Без этой гипотезы учиться на примерах бессмысленно. На слайде её условие умещается в два слова — "sufficiently large". Конспект (стр. 128) называет три условия, и каждое может сломаться:

• обучающие и новые точки i.i.d. — независимы и взяты из одного распределения. Ломается при distribution shift;
• точек много по сравнению с гибкостью модели. Ломается на маленьком датасете;
• модель ловит закономерность, а не шум. Ломается при слишком высокой сложности.

Откуда третье условие? Если бы веса выбрали заранее, не глядя на данные, \(\hat E_{\text{train}}\) была бы честной оценкой \(E\): среднее по выборке сходится к ожиданию. Но веса выбраны как раз так, чтобы \(\hat E_{\text{train}}\) стала как можно меньше — на этих самых точках. Число, по которому оптимизировали, перестаёт быть честным измерением. Насколько оно занижено, зависит от того, сколько у модели свободы.

Из Applied Statistics это знакомо: \(R^2\) на обучающих данных не убывает, сколько регрессоров ни добавляй, — потому и придумали adjusted \(R^2\). Теперь посмотри на то же самое вживую.

Почему training error не может вырасти? Полином степени \(d + 1\) умеет всё, что умеет полином степени \(d\): достаточно обнулить старший коэффициент. Значит, лучшая подгонка в большем семействе не хуже. С сетью так же: добавь скрытый нейрон с нулевым выходным весом — получится прежняя функция. Поэтому training error годится, чтобы подбирать веса, и не годится, чтобы выбирать сложность.

Training error с ростом сложности только падает; ошибка на новых данных сначала падает, потом растёт.

Что считается сложностью у сети

В лаборатории ручка сложности одна — степень. У сети их несколько, и конспект называет их общий результат словом capacity (ёмкость): способность модели подстроиться под данные.

• Число параметров — весов \(w_{ji}^{(l)}\) вместе со смещениями: больше нейронов, больше свободы.
• Глубина: больше слоёв — более сложные функции.
• Нелинейности: без них сеть остаётся линейной моделью, сколько слоёв ни ставь.
• Регуляризация — единственный пункт списка, который сложность уменьшает.

К списку стоит добавить две ручки, которые не меняют архитектуру, но меняют эффективную гибкость: величину весов (её ограничивает weight decay, урок 22) и время обучения (early stopping, урок 20). Большая сеть, остановленная рано, ведёт себя как более простая.

Из чего состоит ошибка на новых данных

Третий опыт в лаборатории показал странную вещь: гибкая модель на другой выборке — уже другая модель. Сделаем из этого наблюдения формулу. Мысленный эксперимент такой: одну и ту же модель обучают много раз, каждый раз на новой обучающей выборке \(D\) из того же источника.

Теперь зафиксируем одну точку \(x\) и спросим у каждой обученной модели её ответ в этой точке. Ответы разные, потому что выборки разные. У этого облака ответов есть центр и есть разброс — больше нам ничего не понадобится.

Bias — систематическая ошибка: насколько средняя модель промахивается мимо истины. Он велик, когда модели не хватает гибкости, и новыми данными не лечится.

Variance — чувствительность к выборке: насколько ответ прыгает, когда обучающие точки заменяют другими из того же источника. Она велика, когда модель подстраивается под шум.

Noise \(\sigma^2\) — разброс самих измерений вокруг \(f(x)\). От модели он не зависит, поэтому его называют irreducible error.

Bias — куда модель целится в среднем; variance — насколько дрожит её рука.

Три выстрела в одну точку

Посчитаем на числах. В точке \(x_0\) истинное значение \(f(x_0) = 2.0\), шум измерений \(\sigma^2 = 0.25\). Есть три модели разной гибкости. Каждую обучили на трёх выборках и записали её ответ в \(x_0\): жёсткая ответила 1.0, 1.4 и 1.2; средняя — 1.7, 2.2 и 1.8; гибкая — 1.0, 3.2 и 1.8.

Для средней модели, шаг за шагом:

Выигрывает средняя модель, хотя у неё нет рекорда ни по одному слагаемому. Последний столбец получен простым сложением, и это не приём для примера, а точное равенство.

Конспект даёт формулу без вывода. Вывод короткий, и в нём всего два приёма: «добавить и вычесть» и «среднее от отклонения равно нулю».

1. Новое измерение — это закон плюс шум. Чтобы не тащить аргумент, пишем \(f\), \(g_D\), \(\bar g\) вместо значений в точке \(x\). Ошибка модели на новой точке:

   \[ t - g_D = (f - g_D) + \epsilon \]

2. Возводим в квадрат и берём ожидание. Получаются три слагаемых:

   \[ \begin{aligned} \E\bigl[(t - g_D)^2\bigr] = {} & \E\bigl[(f - g_D)^2\bigr] \\ & + 2\,\E\bigl[\epsilon\,(f - g_D)\bigr] \\ & + \E\bigl[\epsilon^2\bigr] \end{aligned} \]

3. Шум нового измерения не зависит от обучающей выборки и в среднем равен нулю. Поэтому среднее произведения распадается на произведение средних и исчезает, а \(\E[\epsilon^2]\) — это дисперсия шума:

   \[ \E\bigl[\epsilon\,(f - g_D)\bigr] = \E[\epsilon]\cdot\E[f - g_D] = 0 \] \[ \E\bigl[\epsilon^2\bigr] = \sigma^2 \]

4. Осталось первое слагаемое. Добавим и вычтем средний ответ \(\bar g\):

   \[ f - g_D = (f - \bar g) + (\bar g - g_D) \]

   Первая скобка — число: от выборки она не зависит. Вторая — отклонение модели от собственного среднего.

5. Снова квадрат и ожидание по \(D\). Перекрёстный член исчезает, потому что \(\E_D[\bar g - g_D] = \bar g - \bar g = 0\) по определению \(\bar g\):

   \[ \begin{aligned} \E_D\bigl[(f - g_D)^2\bigr] = {} & (f - \bar g)^2 \\ & + \E_D\bigl[(g_D - \bar g)^2\bigr] \end{aligned} \]

6. Собираем всё вместе и узнаём определения:

   \[ \begin{gathered} \E\bigl[(t - g_D)^2\bigr] = \underbrace{(\bar g - f)^2}_{\text{Bias}^2} \\ {} + \underbrace{\E_D\bigl[(g_D - \bar g)^2\bigr]}_{\text{Var}} + \underbrace{\sigma^2}_{\text{noise}} \end{gathered} \]

   Ни одно слагаемое не отрицательно, и ни одно не превращается в другое: это три независимых источника ошибки.

Trade-off: что двигает оптимум

В таблице про три выстрела bias и variance двигались в противоположные стороны. Это не совпадение, а типичная картина, и у неё есть имя: bias–variance trade-off. Посмотри на него в той же задаче с полиномами.

Итог двух лабораторий помещается в таблицу. В конспекте это Table 1; здесь в ней заменено одно слово.

Три ручки помимо сложности

Третий и четвёртый опыты показали, что сложность — не единственное, от чего зависит overfitting. Вот полный список с направлениями.

Вторая строка — главная практическая новость: variance убывает примерно как \(1/N\). Поэтому одна и та же сеть на маленьком датасете переобучается, а на большом нет. Последняя строка — план следующих уроков: early stopping (урок 20), weight decay (урок 22) и dropout (урок 23) в умеренной дозе покупают большое снижение variance ценой небольшого bias. Перестараться тоже можно: слишком сильная регуляризация — четвёртая причина underfitting из списка в первом разделе.

У сети есть ещё одна ось сложности — время обучения: чем дольше идёт gradient descent, тем точнее подогнаны обучающие точки. Поэтому рис. 5 повторяется с эпохами по горизонтали. Такой график есть на стр. 126 конспекта, и на нём основан early stopping из урока 20.

Вернёмся к слону

Теперь слова фон Неймана читаются как утверждение о training error. Четыре параметра проходят через четыре точки. Пятнадцать — через пятнадцать: в первой лаборатории это степень 14. Сеть из урока 12 — через сколько угодно. Согласие с точками, под которые модель подгоняли, — не довод: при достаточном числе параметров оно гарантировано заранее.

Universal approximation theorem и бритва Оккама отвечают на разные вопросы. Теорема — про то, что сеть может представить. Бритва — про то, что сеть выучит из \(N\) шумных точек. Гибкость снижает bias, но платят за неё variance, и тем дороже, чем меньше данных и чем больше в них шума. Отсюда и приговор Ферми: достоинство теоремы становится недостатком ровно тогда, когда свободы у модели больше, чем могут удержать данные.

А довод — это ошибка на точках, которые в подгонке не участвовали. Весь остаток главы 3 — инструменты: как такую ошибку честно измерить (уроки 18–19) и как удержать variance, не вернув bias (уроки 20–23).

Слона, кстати, можно посмотреть: рисунок 2010 года и вся история собраны в статье Von Neumann's elephant.