Как мы уже видели во введении, мы не можем напрямую оптимизировать истинный риск модели
так как нам недоступно полное распределение данных . Поэтому вместо задачи минимизации истинного риска, мы будем минимизировать эмпирический риск
на доступном нам наборе данных .
Классическая теория предлагает оценивать разность эмпирического и истинного равномерно, что даёт
Такая оценка не зависит от алгоритма обучения; она зависит лишь от класса моделей , в котором происходит поиск. Так, в случае нейронных сетей в качестве класса можно взять класс всех нейронных сетей фиксированной архитектуры, отличающихся только весами.
Если класс настолько велик, что для большинства наборов данных размера содержит модель , у которой эмпирический риск мал, а истинный велик, то оценка выше теряет смысл. Работа Understanding deep learning requires rethinking generalization показала, что именно это и происходит в нейронных сетях, применяемых на практике, на реальных наборах данных. А именно, пусть – алгоритм, применяемый для обучения сети, например, градиентный спуск. Предположим, что с высокой вероятностью , если только размер выборки не слишком велик. Пусть – наша выборка, а – датасет, в котором примеры берутся из выборки, а разметка случайна. По предположению, модель , обученная на объединённом датасете, имеет нулевой риск на «настоящем» датасете , если только не слишком велик. С другой стороны, если , то – истинный риск такой модели близок к риску случайного угадывания.
Тем не менее, если в качестве взять не все модели, реализуемые данной архитектурой нейронной сети, а лишь реализуемые данным алгоритмом обучения на наборах данных из распределения с высокой вероятностью, то можно надеятся, что равномерная оценка окажется осмысленной.
Мы говорим «с высокой вероятностью» для того, чтобы исключить «нереалистичные» наборы данных, обучение на которых ведёт к плохим результатам, а также ничтожно-редкие случаи реализации шума в алгоритме обучения, при котором последний сходится в «плохие» решения. Подробнее о том, какие модели реализуются градиентным спуском, мы обсудим в параграфе про implicit bias.
Оценка супремума
Попробуем оценить супремум разницы рисков. Будем считать, что выборка выбирается случайным (и равновероятным) образом из распределения данных . Некоторые из выборок могут быть катастрофически плохими, поэтому мы будем рассматривать оценки, которые верны не обязательно всегда, а просто с достаточно большой вероятностью.
Предположим сначала, что класс моделей конечен. Тогда
Заметим, что . Поэтому при фиксированном разницу рисков можно оценить с помощью неравенства Хёффдинга.
Неравенство Хёффдинга (Hoeffding's inequality). Пусть – независимые одинаково распределённые случайные величины со значениями в . Тогда для всех имеют место неравенства
Как следствие неравенства Хёффдинга, получаем, что для любого и для любой .
Заметим, что тогда для любой ,
Несмотря на то, что эта оценка является оценкой на обобщающую способность, она не имеет смысла, так как модель в ней задана априори и не зависит от . Другими словами, она верна для необученных моделей .
Возвращаясь к нашей оценке, получаем:
где – мощность класса . Следовательно,
В случае бесконечного используем следующее обобщение неравенства Хёффдинга:
Неравенство МакДайармида (McDiarmid's inequality). Пусть – независимые одинаково распределённые случайные величины, – скалярная функция с аргументами, такая что
для некоторых . Тогда для любого имеет место неравенство
Применяя теорему к , получаем:
из чего следует:
где – эмпирический риск на выборке . В следующем подразделе мы постараемся оценить жёлтое слагаемое.
Симметризация и сложность Радемахера
Оценим сверху матожидание супремума:
Этот шаг называется «симметризация»: теперь выражение выше зависит от двух равнозначных обучающих выборок и . Ниже для краткости будем обозначать и .
Как оценить сверху супремум разности рисков? Наивная оценка, супремум суммы, слишком слаба: в самом деле, при фиксированном наборе данных вполне вероятно может существовать модель, имеющая большой риск на нём (достаточно взять модель, обученную на тех же данных, но с «неправильными» метками), поэтому матожидание супремума эмпирического риска может быть велико.
Для обхода этой сложности заметим, что выражение выше симметрично относительно перестановки местами двух выборок:
Более того, так как элементы обеих выборок выбираются независимо, значение выражения не меняется и при перестановке местами отдельно -ых элементов двух выборок. А именно, для любого набора
Будем выбирать независимо и равновероятно из . Такие случайные величины называются переменными Радемахера.
Поскольку оценки выше были верны для любых сигм, они верны и в среднем по переменным Радемахера, выбранным независимо от выборки:
После введения переменных Радемахера оценка супремума разницы рисков через сумму супремумов становится не такой плохой. В самом деле, рассмотрим бинарную классификацию с помощью линейной модели. Если данные хорошо разделяются плоскостью, то будет большим, так как в качестве можно взять линейную модель с противоположно ориентированной разделяющей плоскостью для . В то же время для того, чтобы было большим, необходимо, чтобы существовала модель, отвечающая правильно на тех примерах, где , и неправильно, где ; для линейной модели это невозможно при большинстве конфигураций сигм.
Величина
называется сложностью Радемахера класса функций (для распределения на и длины выборок ). Она велика, если в классе содержатся функции, принимающие большие значения с заданными знаками на любом наборе данных фиксированного размера. Другими словами, сложность Радемахера измеряет, насколько выходы функций из класса могут коррелировать со случайным шумом.
Для нас актуальна сложность Радемахера классов вида , то есть композиций моделей из класса и функции риска . Если – класс линейных моделей в пространстве размерности меньшей, чем , то сложность Радемахера невелика. В то же время если – множество всех возможных решающих деревьев, то, если только наборы данных непротиворечивы, она равна единице. В самом деле, решающее дерево способно запомнить всю обучающую выборку, то есть добиться единичной корреляции с любым случайным шумом.
Вернёмся к оценке разницы рисков:
Оценка для «0/1-риска»
Сложность Радемахера зависит от функции риска. Рассмотрим задачу бинарной классификации с классами и . Возьмём в качестве функции риска индикатор ошибки бинарной классификации, или «0/1-риск»:
Название «0/1-риск» обусловлено тем, что риск принимает значения и .
Заметим следующее:
где – класс эквивалентности функций из , в котором две функции считаются эквивалентными тогда и только тогда, когда их образы на выборке имеют одинаковые знаки. Другими словами, среди всех функций, принимающих одни и те же знаки на , мы выберем по одной и сформируем из них множество . Заметим, что это множество конечно: .
Нам понадобится следующая
Лемма. Пусть – случайная величина со значениями в и нулевым средним. Тогда для любых $ s > 0$ имеет место неравенство
С её помощью получаем:
Эта оценка верна для любого . Минимизируем её по . Легко видеть, что оптимальное равняется ; подставляя его, получаем:
Определим функцию роста класса как
Эта функция показывает, сколько различных разметок класс функций может породить на наборе данных, в зависимости от размера этого набора. Очевидно, что и монотонно не убывает.
Например, для линейной модели на -мерном пространстве признаков при (любое подмножество точек в общем положении в -мерном пространстве всегда можно отделить гиперплоскостью), но строго меньше этого числа при (например, если точки – углы квадрата на плоскости, его диагонали нельзя разделить прямой).
Когда , будем говорить, что « разделяет ».
Определим размерность Вапника-Червоненкиса (или VC-размерность) как максимальное , при котором семейство разделяет любой датасет :
Таким образом, VC-размерность линейной модели равна .
Следующая лемма даёт связь между размерностью Вапника-Червоненкиса и функцией роста:
Лемма (Sauer–Shelah, см. подробнее здесь)
Изучим асимптотическое поведение сложности Радемахера при . Обозначим . Для имеем , а для :
Подставляя это выражение в (1), получаем окончательную оценку на сложность Радемахера:
Соответствующая оценка на истинный риск тогда примёт вид:
Для того, чтобы эта оценка была осмыслена, необходимо гарантировать . Для линейных моделей, при условии (данных намного больше, чем признаков), оценки действительно получаются осмысленными.
К сожалению, для нейронных сетей это подчас неверно. В работе Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks показано, что если обозначает класс моделей, реализуемых полносвязной сетью ширины с параметрами, то . Таким образом, наша оценка на сложность Радемахера становится бесполезной в реалистичных сценариях, когда число весов сети много больше числа примеров в обучающей выборке .
Если априори известно, что результат обучения лежит в некотором классе , то в оценке сложности Радемахера можно использовать именно этот класс, а не полный класс моделей . Очевидно, что сложность , лежащего в , не больше сложности . Так, в работе Spectrally-normalized margin bounds for neural networks получены оценки для сложности полносвязной сети с липшицевыми функциями активации при условии, что нормы весов ограничены; см. также полный конспект лекций. В этом случае под будем понимать класс сетей с весами нормы не больше . Обозначим соответствующую оценку через :
К сожалению, нет гарантий, что градиентный спуск всегда сходится в решение с нормой меньше какого-то числа. Чтобы обойти это ограничение, используют следующую технику. Возьмём последовательность ограничений , такую что
Также возьмём последовательность , монотонно убывающую к нулю и суммирующуюся в . Тогда для любого
А значит,
Из этого следует, что
где – минимальное , при котором .
Такая техника используется, например, в работах Spectrally-normalized margin bounds for neural networks и A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks.
Фундаментальная проблема равномерных оценок
Пример модели (розовая кривая), имеющей малый истинный риск, но большой эмпирический на заданном наборе данных (кружочки). Данные одного класса лежат на желтом круге, другого – на голубом; оптимальная разделяющая поверхность обозначена пунктиром. Имея набор из кружочков, мы строим противоположный набор, обозначенный крестиками; заметим, что он мог прийти из того же распределения. Если алгоритм обучения старается отодвинуть границу классов как можно дальше от примеров, то результатом обучения на наборе крестиков может стать розовая кривая. Пример взят из работы Uniform convergence may be unable to explain generalization in deep learning.
Напомним, что построение равномерных оценок проходило в несколько шагов:
- Оценка супремумом
- Применение неравенства макДайармида:
- Оценка матожидания супремума (жёлтое слагаемое выше) с помощью симметризации с дальнейшим выходом на сложность Радемахера:
На каждом шаге предыдущая величина оценивается сверху, и потенциально каждое из этих неравенств может оказаться слишком слабым и привести к бессмысленной оценке. Давайте это проиллюстрируем.
Выше мы уже отмечали, что если класс содержит модель, для которой мал, а велик, то равномерная оценка становится бессмысленной. По этой причине, имеет смысл выбирать класс как можно более маленьким. Самым лучшим из возможных классов мог бы быть класс моделей, к которым сходится наш алгоритм обучения с высокой вероятностью.
Рассмотрим случай, близкий к идеальному: тот, в котором существует , для которого при любых имеем . Иными словами, предположим, что все модели класса хорошо обобщают. В этом случае оценка выше близка к идеальной:
Но что будет, если мы начнём честно воспроизводить процесс построения равномерных оценок? После второго шага мы получаем оценку вида
которая не сильно хуже предыдущей, но в которой всё равно появилось лишнее слагаемое.
Но допустим, что мы хотим честно проделать третий шаг процедуры получения равномерных оценок. Для этого нам необходимо было оценить матожидание супремума, которое после симметризации получает вот такую верхнюю оценку:
Таким образом, малость истинного риска не гарантирует малость эмпирического риска на любом наборе данных. Так, авторы статьи Uniform convergence may be unable to explain generalization in deep learning предъявили пример, в котором для любого существует модель , такая что , но при этом и малы. Иллюстрация такой ситуации приведена в начале параграфа. Тогда велик, и оценки теряют смысл.
К счастью, даже эта фундаментальная проблема не ставит крест на равномерных оценках. Так, работы Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting и Stability and Deviation Optimal Risk Bounds with Convergence Rate рассматривают равномерную оценку в классе интерполирующих моделей, то есть, имеющих нулевой эмпирический риск:
Для таких моделей контрпример выше не работает.