Экзамен по кругу

Один пробник — одна лотерея

В прошлом уроке данные резали один раз: бо́льшая часть учит сеть (training set), меньшая проверяет (validation set). Это hold-out, один пробный экзамен перед настоящим. У одного разреза две слабости, и обе растут, когда данных мало.

Первая: результат зависит от того, какие именно примеры случайно попали в пробник. Другой разрез даст другое число. Это разброс оценки, её variance.

Вторая: примеры, отложенные на проверку, сеть не учат. Сеть, обученная на трёх четвертях данных, обычно немного хуже той, которую в конце обучат на всех. Значит, пробник в среднем показывает ошибку чуть больше настоящей. Это систематический сдвиг оценки, её bias, и он пессимистичный.

На слайде профессора про hold-out две фразы (лекция 3, слайд 6). Правило: "When lots of data are available use a Hold Out set and perform validation". Когда данных много, обе слабости малы; отсюда и условие. И облачко возле validation set: "Hold out error might be biased by the specific split!". Это первая слабость. Слово biased здесь бытовое: «перекошена тем, как лёг разрез». В какую сторону перекосит, заранее неизвестно, поэтому в точных терминах это variance, а не bias.

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

В каждом раунде делается одно и то же: обучить новую сеть на учебной части, посчитать её ошибку на отложенной части, записать число. В конце числа усредняют. На рисунке ниже настоящие числа: это те 12 примеров и та модель, с которыми ты будешь работать в виджете.

А вторая слабость? Сам по себе круг её не лечит: на рис. 1 и слева, и справа каждая сеть учится на 9 примерах из 12. Это проверяется симуляцией. Возьмём миллион таких наборов по 12 примеров; модель — прямая, как в виджете ниже. Итоговая прямая, обученная на всех 12, на новых данных ошибается в среднем на 1.19. И один hold-out, и круг из четырёх раундов в среднем показывают 1.28: пессимизм одинаковый. Зато от набора к набору hold-out гуляет со стандартным отклонением 1.11, а круг — 0.64.

Bias лечится следующим ходом. Раз проверят в итоге всё равно все примеры, отложенную часть можно сделать маленькой: не четыре части по три задачи, а двенадцать по одной. Тогда каждая сеть учится на 11 примерах из 12. Сколько частей брать, решает ручка \(K\) из раздела 3, а начнём с её крайнего положения.

В cross-validation каждый пример один раз проверяет и много раз учит, а оценка — среднее по раундам.

Leave-one-out: по одному за дверь

Доведём идею до предела: в конверте лежит одна задача. Представь группу из \(N\) студентов. Каждого по очереди просят выйти за дверь, остальные вместе готовятся, а потом вышедшему задают его вопрос. Проверят каждого, и каждый раз готовилась почти вся группа. Это Leave-One-Out Cross-Validation, сокращённо LOOCV: \(N\) раундов, в каждом сеть учится на \(N - 1\) примерах и проверяется на одном оставшемся.

На слайде 7 лекции 3 раунды нарисованы столбцами с номерами 1, 2, …, \(n\), …, \(N\). В каждом столбце одна тонкая полоска подписана validation sample, всё остальное — training set. От столбца к столбцу полоска поднимается на один пример.

Считаем руками

Возьмём самую маленькую сеть на свете: входов нет, есть только bias \(w_0\), и ответ всегда один, \(g(x \mid w) = w_0\). Если учить её по Sum of Squared Errors, лучший \(w_0\) равен среднему арифметическому targets. Данные: три примера с \(t = 1,\ 2,\ 6\).

Раунд 1: прячем \(t = 1\). Среднее оставшихся \((2 + 6)/2 = 4\), ошибка на спрятанном \((1 - 4)^2 = 9\). Раунд 2: прячем 2, прогноз 3.5, ошибка 2.25. Раунд 3: прячем 6, прогноз 1.5, ошибка 20.25.

Справа на рисунке то же самое без пряток: учим на всех трёх, \(w_0 = 3\), ошибки 4, 1 и 9, в среднем 4.67. Модель та же, данные те же, а числа отличаются в 2.25 раза. Число 4.67 отвечает на вопрос «насколько хорошо сеть помнит то, что учила». Число 10.5 отвечает на вопрос «что будет на новом примере».

Отдельной формулы для LOOCV на слайдах нет. Это частный случай формулы со слайда 9, до которой дойдём в разделе 3: при \(K = N\) каждый fold состоит из одного примера, и \(\hat e_i\) — ошибка такого fold. Буква \(i\) для спрятанного примера взята из конспекта; на слайде 7 раунды нумерует \(n\).

Откуда взялось ровно 2.25? Для сети из одного bias это можно вывести, и вывод показывает, как именно training error обманывает.

1. Сеть \(g(x \mid w) = w_0\), обученная на всех \(N\) примерах. Производная суммы квадратов по \(w_0\) обращается в ноль, когда \(w_0\) равен среднему targets:

   \[ w_0 = \bar t = \frac{1}{N}\sum_{n=1}^{N} t_n \]

2. Без \(i\)-го примера среднее считается по остальным \(N - 1\): из полной суммы \(N\bar t\) убираем \(t_i\).

   \[ w_0^{(i)} = \frac{N\bar t - t_i}{N - 1} \]

3. Насколько сеть промахнулась по спрятанному примеру. Приводим к общему знаменателю:

   \[ t_i - w_0^{(i)} = \frac{N}{N-1}\,(t_i - \bar t) \]

   Промах в раунде равен промаху «на своих», растянутому в \(N/(N-1)\) раз.

4. Возводим в квадрат и усредняем по всем \(i\). Справа появляется обычная средняя ошибка на training set:

   \[ \hat E_{\text{LOOCV}} = \Big(\frac{N}{N-1}\Big)^{2} E_{\text{train}} \]

5. Проверка: при \(N = 3\) множитель равен \((3/2)^2 = 2.25\), и \(2.25 \cdot 4.67 = 10.5\). При \(N = 10\) множитель 1.23, при \(N = 100\) уже 1.02.

   У этой крошечной сети обман быстро исчезает с ростом \(N\). У гибкой сети с тысячами весов он держится намного дольше.

Три свойства LOOCV

Почти нет bias. Каждая из \(N\) сетей училась на \(N - 1\) примере из \(N\), то есть почти на всех данных. Поэтому LOOCV оценивает ошибку почти той самой сети, которую ты в конце обучишь на всех данных. Остаётся едва заметный пессимизм: \(N - 1\) всё-таки меньше \(N\).

На слайде профессора слова almost нет. Облачко над схемой говорит: "Unbiased but unfeasible with lots of data" (лекция 3, слайд 7). Точный смысл этого unbiased такой. В среднем по всем возможным наборам данных оценка LOOCV в точности равна средней ошибке сети, обученной на \(N - 1\) примерах: для такой сети она несмещённая без оговорок. А в работу пойдёт сеть, обученная на всех \(N\) примерах, и она в среднем чуть лучше. Отсюда «почти». На экзамене пиши слово слайда и тут же причину: unbiased, because each model is trained on \(N - 1\) of the \(N\) samples.

Очень дорого. Одна оценка стоит \(N\) обучений. А оценивать обычно нужно не одну конфигурацию. Это вторая половина того же облачка: "unfeasible with lots of data".

Высокая variance. Каждое \(\hat e_i\) стоит на одном-единственном примере, поэтому оно очень шумное. Усреднение помогает меньше, чем кажется: любые два training set совпадают в \(N - 2\) примерах, сети получаются почти одинаковыми, и их ошибки сильно связаны между собой. Среднее связанных чисел гасит шум хуже, чем среднее независимых.

Итог: LOOCV берут, когда примеров мало (сотни и меньше), а модель учится быстро. На слайде 7 то же правило записано строкой "When having few data available use Leave-One-Out Cross-Validation (LOOCV)". Для глубоких сетей это почти всегда теоретическая точка отсчёта, а не рабочий инструмент.

K-fold: ручка между «дёшево» и «точно»

LOOCV — крайний случай общей схемы. В K-fold cross-validation весь training dataset делят на \(K\) непересекающихся частей (folds) примерно по \(N/K\) примеров. В раунде \(k\) сеть учится на \(K - 1\) частях и проверяется на \(k\)-й. Потом \(K\) ошибок усредняют.

На слайде 8 лекции 3 это нарисовано для \(K = 5\). Training dataset разрезан на пять кусков с номерами от 1 до 5. В столбце \(k\) кусок \(k\) подписан validation set, остальные четыре — training set. Слайд 9 добавляет к этой картинке две формулы.

На самом слайде первая формула записана короче:

Индекс \(n_k\) значит «пример из fold \(k\)»: это то же, что \(n \in N_k\). А веса там записаны просто \(w\), без пометки, и их легко принять за одни и те же во всех раундах. Это не так: в раунде \(k\) берут веса той сети, которая fold \(k\) не видела. Поэтому в уроке написано \(\vb{w}^{(k)}\). Вторая сумма на слайде подписана просто \(k\) снизу и \(K\) сверху.

Пример на числах: \(N = 100\), \(K = 5\). В каждом fold 20 примеров, то есть \(|N_k| = 20\), и каждая сеть учится на 80. Ошибки раундов 0.21, 0.18, 0.25, 0.20 и 0.16 дают оценку \(1.00 / 5 = 0.20\).

Как выбрать K

Чем меньше \(K\), тем меньше данных достаётся каждой сети и тем пессимистичнее оценка. Чем больше \(K\), тем ближе training set к полному набору, но тем больше обучений и тем сильнее шумит оценка. В конспекте это выделено маркером, и эту фразу стоит уметь написать по-английски: "Small K (e.g., 2 or 3) leads to higher bias but lower variance, while large K (e.g., LOOCV) leads to lower bias but higher variance and computational cost."

На слайде 8 лекции 3 об этом одна строка: "K-fold Cross-Validation is a good trade-off (sometime better than LOOCV)". Слово sometime напечатано там именно так, без s на конце. Trade-off здесь — между двумя крайностями с тех же слайдов: hold-out стоит одно обучение, но зависит от разреза, а LOOCV — unbiased, но стоит \(N\) обучений. Скобку слайд не расшифровывает. Обычное объяснение — два выигрыша сразу: \(K\) обучений вместо \(N\) и оценка, которая шумит меньше, чем среднее \(N\) сильно связанных слагаемых. Слово sometime честное: так выходит не всегда, оговорка в разделе 2.

Самый частый выбор — \(K = 5\); \(K = 10\) берут, когда данных меньше и жалко отдавать пятую часть; \(K = 2\) или 3 — когда данных очень много и считать дорого.

Что остаётся после cross-validation

Раунды пройдены. У тебя \(K\) обученных сетей и одно число. Слайд 9 лекции 3 на этом месте спрашивает: "What do I do with all these models?". Какую из сетей нести дальше? Ни одну.

Cross-validation оценивает не сеть, а рецепт: архитектуру, hyperparameters и способ обучения. Число \(\hat E\) говорит, какую ошибку даёт этот рецепт на новых данных. Сами \(K\) сетей — строительные леса: каждая видела только часть данных.

Порядок действий такой. Прогнать K-fold для каждой конфигурации. Выбрать ту, у которой \(\hat E\) меньше. Обучить её заново на всех \(N\) примерах: больше данных — лучше сеть. Число \(\hat E\) для этой сети слегка пессимистично, потому что в раундах данных было меньше. Но если конфигураций было несколько, сам выбор сдвигает число победителя в обратную сторону, вниз. Об этом следующий раздел.

Это и есть ответ на вопрос слайда 9, и оба его шага записаны на слайдах той же лекции. Выбор: на слайде 10 возле разреза на training set и validation set стоит облачко "… more common here for model selection (hyperparameter tuning)", то есть чаще всего K-fold крутят именно ради выбора. Обучение заново: рецепт выбора на слайде 16 кончается строкой "Put back all data together and minimize". Есть и второй законный ответ, которого на слайдах нет: не выбрасывать \(K\) сетей, а усреднять их ответы как ensemble. Только число \(\hat E\) тогда описывает одну такую сеть, а не их ансамбль.

Две меры предосторожности, без которых число \(\hat E\) врёт.

Перемешай перед разбиением. Если примеры лежат по порядку (сначала один класс, потом другой, или по времени), соседние folds будут из разных миров. Для классификации лучше ещё и stratified разбиение: в каждом fold те же доли классов, что во всём наборе. На слайде 4 лекции 3 это отдельная строка: "In classification preserve class distribution, i.e., stratified sampling!".

Preprocessing считай внутри каждого раунда. z-стандартизация из Applied Statistics — хороший пример: среднее и стандартное отклонение берут только по \(K - 1\) учебным folds и применяют к отложенному. Если посчитать их один раз по всем данным, validation fold уже повлиял на обучение. Это утечка из урока 18, только спрятанная внутри цикла.

Лучший из десяти одинаковых

Вернёмся к загадке. В ней одно и то же число сделало две разные работы.

Вот десять оценок из загадки на одном конкретном наборе данных. У всех десяти конфигураций настоящая ошибка 0.20.

Каждая точка по отдельности честная: в среднем она равна 0.20 и колеблется вокруг со стандартным отклонением \(\sqrt{0.2 \cdot 0.8 / 150} \approx 0.033\). Среднее десяти точек 0.201. Но мы берём не случайную точку и не среднее, а минимальную. А минимум из нескольких шумных чисел в среднем лежит ниже каждого из них.

1. Оценка каждой конфигурации \(\theta\) — её настоящая ошибка плюс шум с нулевым средним. Значит, каждая оценка несмещённая:

   \[ \hat E_\theta = E_\theta + \varepsilon_\theta, \quad \E[\hat E_\theta] = E_\theta \]

2. Минимум не больше любого из чисел. Возьмём любую конфигурацию \(\theta'\):

   \[ \min_\theta \hat E_\theta \;\le\; \hat E_{\theta'} \]

3. Усредняем обе части по всем возможным наборам данных. Справа получается настоящая ошибка \(\theta'\):

   \[ \E\big[\min_\theta \hat E_\theta\big] \;\le\; E_{\theta'} \]

4. Это верно для каждой \(\theta'\), в том числе для действительно лучшей:

   \[ \E\big[\min_\theta \hat E_\theta\big] \;\le\; \min_\theta E_\theta \]

   Среднее от минимума не больше минимума от средних. Равенство получается, только если на любом наборе данных побеждает один и тот же, действительно лучший кандидат: например, шума нет или кандидат один.

5. Насколько ниже? Если кандидаты одинаково хороши, а шум у каждого свой (независимый и примерно нормальный), минимум из десяти в среднем лежит на 1.54 стандартного отклонения ниже, из ста — на 2.51:

   \[ 0.20 - 1.54 \cdot 0.033 \approx 0.15 \]

   Точный счёт по биномиальному распределению даёт 15.1%, число из загадки.

Выбирать лучшего по validation — тоже обучение: число, по которому выбирали, больше не годится как оценка.

Это тот же механизм, что в уроке 18 делал training error оптимистичной: там веса подгоняли под training set, здесь выбор конфигурации подгоняют под validation folds. Эффект называют winner's curse, проклятие победителя. И он не исчезает, когда кандидаты на самом деле разные: победитель, скорее всего, действительно хорош, но его число всё равно сдвинуто вниз. Выбор может быть верным, а число при этом неверным.

Размер сдвига в загадке — почти худший случай. Там каждая архитектура ошибается на своих примерах. В жизни сети спотыкаются на одних и тех же трудных примерах, их оценки поднимаются и опускаются вместе, и минимум уходит от остальных не так далеко. Сдвиг получается меньше, но направление у него всегда одно: вниз.

Nested cross-validation: экзамен, который не участвовал в выборе

Лекарство то же, что в прошлом уроке: test set, то есть данные, которые не участвовали ни в одном решении. Но при малом \(N\) один test set — снова лотерея. Значит, его тоже надо пустить по кругу. Получается круг в круге.

Слайды доходят ровно до этой мысли. На слайде 10 лекции 3 повторена схема терминов из прошлого урока (слайд 5, "Clearing the terms …"): training dataset режут на training data и test data, а training data — на training set и validation set.

Новое на слайде 10 — три облачка. У первого разреза, где откладывают test data (на схеме это уровень "Pre-production"): "We can apply K-fold Cross-Validation also at this level for model assessment …". У второго, где откладывают validation set (на схеме — "Model Development"): "… more common here for model selection (hyperparameter tuning)". И третье, про цену: "Beware the number of models you get and how much it cost to train!".

То есть по слайду K-fold можно поставить на любой из двух разрезов. Поставить на оба сразу — это и есть nested cross-validation: внешний круг крутит первый разрез, внутренний — второй. Но ни этого названия, ни схемы из двух циклов, ни формул ниже на слайдах нет: всё это из конспекта (стр. 145–149). Считай остаток раздела материалом сверх слайдов. Он показывает, что получается, когда оба облачка работают вместе, и сколько это стоит.

1. Outer loop, assessment. Раздели данные на \(K\) outer folds. В раунде \(k\) один fold запирается как test, остальные \(K - 1\) образуют outer training set. В словах слайда 10 это test data и training data.
2. Inner loop, selection. Внутри outer training set сделай обычный \(M\)-fold для каждой конфигурации \(\theta\) из набора \(\Theta\): он по очереди назначает куски на роли training set и validation set. Выбери \(\theta^*_k\) с наименьшей средней ошибкой.
3. Проверка. Обучи \(\theta^*_k\) заново на всём outer training set и один раз проверь на запертом fold. Получится \(\hat e_k\).
4. Среднее. После \(K\) раундов усредни \(\hat e_k\).

Главная фраза раздела в конспекте (стр. 148): "the inner loop chooses the best hyperparameters, while the outer loop evaluates the whole selection procedure on unseen data". Outer loop оценивает не конфигурацию, а всю процедуру выбора целиком.

Сколько это стоит и что на выходе

Третье облачко слайда 10 предупреждает: "Beware the number of models you get and how much it cost to train!". Считаем обучения. В каждом из \(K\) outer раундов inner loop обучает \(M\) сетей на каждую из \(|\Theta|\) конфигураций, плюс одно обучение победителя на всём outer training set.

Для \(K = 5\), \(M = 3\) и 10 конфигураций это \(5 \cdot 31 = 155\). Для \(K = 10\), \(M = 5\) уже 510. Именно эти две пары называет конспект (стр. 149): \(K = 5\), \(M = 3\) как типичный выбор, \(K = 10\), \(M = 5\) для более точной оценки и для малых наборов данных. Размеры блоков при \(N = 150\), \(K = 5\), \(M = 3\): outer test 30, outer training 120, inner validation 40, inner training 80.

Чего nested CV не даёт: ни модели, ни «лучших hyperparameters». Победители \(\theta^*_k\) в разных outer раундах могут быть разными, это видно в виджете. На выходе одно число: ожидаемая ошибка процедуры «выбрать через inner CV, потом обучить». Итоговую модель получают отдельно: один раз запустить выбор на всех данных, обучить победителя на всех данных, а число \(\hat E_{\text{nested}}\) приложить как честную оценку.

И одна оговорка к заголовку конспекта «There is no more optimism»: nested CV убирает оптимизм от выбора. Остаётся обычный лёгкий пессимизм K-fold, потому что outer training set меньше полного набора.

Загадка решена

15.1% в отчёте — это минимум из десяти честных чисел. Каждое в среднем равно 20%, но минимум из десяти в среднем на полтора стандартных отклонения ниже. Fold, который в выборе не участвовал, возвращает 20%. В примере из документации scikit-learn то же проделано на настоящих данных, 150 цветках Iris: за 30 повторов non-nested score был систематически выше nested, в среднем на 0.007581. Score там — это accuracy, так что «выше» значит «оптимистичнее». Сдвиг меньше одного процентного пункта, намного скромнее, чем в загадке, но в ту же сторону.

В глубоком обучении чаще всего остаётся hold-out с отдельным test set: одно обучение стоит слишком дорого, чтобы повторять его десятки раз. Но логика та же самая: число, по которому что-то выбирали, в отчёт не идёт.