В предыдущем параграфе рассматривались равномерные оценки разницы истинного и эмпирического рисков. Если в рассматриваемом классе моделей есть «плохие», то равномерные оценки становятся слишком пессимистичными. Часто нельзя гарантировать, что что наш алгоритм обучения их никогда не выбирает, поэтому класс моделей для равномерной оценки не получится сузить до класса только «хороших» моделей. Но можно надеяться, что плохие выучиваются не слишком часто. Например, известно, что градиентный спуск обычно сходится к хорошим моделям (об этом мы ещё поговорим в параграфе про implicit bias). В этом параграфе мы разберём элегантный способ учесть «предпочтения» алгоритма обучения в оценке разницы рисков.
Вспомним равномерную оценку для конечного :
где – мощность класса . Эта оценка формально верна и для бесконечного , но смысл её теряется. Давайте попробуем исправить это.
Пусть не более, чем счётно. Для каждого возьмём своё . Если взять таким, чтобы было конечным, то приходим к осмысленной оценке:
Рассмотрим теперь некоторое вероятностное распределение на . В качестве возьмём
где . Из этого уравнения получаем следующее выражение для :
В итоге, для любого получаем оценку:
Или, что то же самое, с вероятностью по для любого :
Заметим, что если конечно, а – равномерное распределение, то оценка выше совпадает с равномерной оценкой. Если же наш алгоритм обучения предпочитает выбирать модели, для которых велико, то оценка улучшается по сравнению с равномерной. Таким образом, распределение «кодирует» наши представления о предпочтениях алгоритма. Будем называть «априорным распределением».
Как обобщить оценку выше на несчётные классы моделей? В первую очередь, предположим, что наш алгоритм обучения стохастичен, а значит, на выходе даёт не одну модель, а распределение:
Будем называть это распределение «апостериорным». Такое рассуждение осмысленно, например, для стохастического градиентного спуска: очевидно, что результат его работы на невыпуклой функции потерь недетерминирован (он может сходиться в разные локальные минимумы).
Заметим, что главное отличие апостериорного распределения от априорного в том, что первое зависит от данных, а второе – нет. Важно понимать при этом, что, несмотря на названия, эти два распределения не связаны между собой никаким вариантом формулой Байеса. Сходство с байесовским подходом скорее внешнее. Поэтому слова «априорное» и «апостериорное» имеет смысл писать в кавычках, но для экономии места мы их будем в дальнейшем опускать.
Оценки разности рисков, о которых речь пойдёт ниже, называются PAC-байесовскими (PAC-bayesian, где PAC – probably approximately correct).
Сформулируем одну из классических оценок из этого класса:
Теорема Макаллестера. Пусть – множество моделей и – распределение на . Тогда для любого с вероятностью по имеем:
где и .
Видим, что оценка тем лучше, чем ближе апостериорное распределение к априорному. Здесь работает следующая интуиция. Если для большинства обучающих наборов данных апостериорное распределение близко к априорному, то оно почти не зависит от данных, а значит, истинный риск и риск на обучающей выборке должны быть близки с высокой вероятностью. Если же апостериорное зависит от данных сильно, то, скорее всего, модель сильно переобучается, а значит, оценка не может быть хорошей; в нашем случае она велика из-за большой KL-дивергенции.
Для доказательства теоремы нам понадобятся две леммы:
Лемма 1. Для любого распределения на и для любого с вероятностью по имеем:
где .
Лемма 2 (лемма Донскера-Вередана, Donsker-Varadhan). Пусть и – вероятностные распределения на множестве . Тогда для любого
Доказательство теоремы
Применим лемму 2 к , и :
Тогда по лемме 1 с вероятностью по имеем:
Доказательство, таким образом, легко завершается:
Доказательство леммы 2
Мы рассмотрим лишь простой случай, когда и у , и у есть плотности, и они нигде не обращаются в ноль.
Доказательство леммы 1
Нам понадобится
Неравенство Маркова. Пусть – неотрицательная случайная величина. Тогда для любого $ a > 0$ имеем
В качестве и из неравенства Маркова возьмём
Тогда
Значит, нам достаточно доказать, что
Мы докажем даже более сильное соотношение:
Заметим, что из неравенства Хёффдинга будет следовать
Для простоты предположим, что распределение имеет плотность для любого ; обозначим её . В этом случае мы можем ограничить матожидания по напрямую:
В общем случае, мы не можем предполагать наличие плотности у . Доказательство в этом случае можно найти в оригинальной работе D. A. McAllester Some pac-bayesian theorems, а также в конспекте лекций автора этого параграфа.
Теорема Макаллестера – не единственная из возможных пак-байесовских оценок. Например, несколько улучшенную версию той же оценки можно найти в работе Bounds for averaging classifiers. Другие оценки подобного типа можно найти в монографии PAC-Bayesian supervised classification: the thermodynamics of statistical learning.
Применение пак-байесовских оценок к детерминированным алгоритмам обучения
Выше были рассмотрены две PAC-байесовские оценки: одна для не более, чем счётного множества моделей, другая – для произвольного. За возможность использования несчётных классов моделей мы заплатили тем, что алгоритм обучения должен быть недетерминированным (для детерминированных алгоритмов KL-дивергенция в Теореме Макаллестера может вырождаться в бесконечность; например, это так, если априорное распределение гауссово). Чаще всего класс моделей всё-таки несчетён: например, если это класс всех сетей фиксированной архитектуры, то он индексируется весами, которых несчётное множество. При этом, хотя используемый алгоритм обучения и в самом деле недетерминирован (стохастический градиентный спуск зависит от случайного выбора батчей и от инициализации весов) и теорема Макаллестера выполняется, финальное распределение моделей очень сложно охарактеризовать, и из-за этого непонятно, как считать KL-дивергенцию.
Предположим, что алгоритм обучения всё-таки детерминирован; этого можно добиться, зафиксировав сид генератора случайных чисел при обучении. Как получить осмысленную PAC-байесовскую оценку для детерминированного алгоритма на несчётном множестве моделей?
Мы рассмотрим два способа.
Первый способ – добавить известный шум в финальную модель, выданную детерминированным алгоритмом. Так, для нейронных сетей, результатом работы алгоритма обучения является набор весов. Если добавить в этот набор гауссовский шум, а также в качестве априорного распределения взять гауссовское, то KL-дивергенцию в теореме Макаллестера можно будет посчитать аналитически.
Дисперсию шума в апостериорном распределении тоже можно обучить с помощью градиентного спуска одновременно с весами, тем самым минимизируя правую часть оценки из вышеупомянутой теоремы. Если в найденную модель удастся добавить шум так, чтобы KL-дивергенция значительно уменьшилась, но при этом риск на обучающей выборке не сильно вырос, то оценка на истинный риск получится хорошей.
Это рассуждение связывает PAC-байесовские оценки и гипотезу о том, что «плоские» («широкие») минимумы хорошо обобщают. В самом деле, если минимум «плоский», то в модель из него можно добавить много шума, не испортив качество на обучении. Оценки, основанные на этом принципе, можно найти в работах Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data и A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks.
Второй способ состоит в том, чтобы взять дискретное кодирование и применить дискретную PAC-байесовскую оценку к закодированной модели вместо оригинальной. Обозначим закодированную модель через . Следуя работе Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach, возьмём априорное распределение с массой, убывающей с ростом длины кода:
Здесь $\vert f_c\vert $ – длина кода модели , – некоторое вероятностное распределение на , а – нормализующая константа. Тогда KL-дивергенция примет следующий вид:
Для того, чтобы KL-дивергенция выше была как можно меньше, необходимо, чтобы наш алгоритм обучения на реалистичных данных сходился в модели с маленькой длиной кода. Для этого будем применять наше кодирование не к оригинальной модели, а к сжатой с помощью некоторого алгоритма сжатия. Здесь мы предполагаем, что модели, к которым сходится наш алгоритм обучения, можно сжать с малыми потерями до моделей с малой длиной кода. Другими словами, мы опираемся на предположение, что обученные модели в некоторым смысле «простые».
Если модель параметризована весами , типичный алгоритм сжатия выдаст набор , где
- – позиции ненулевых весов;
- – «словарь» весов;
- , – квантизованные значения весов.
Выход алгоритма будет выглядеть как , если , иначе .
Тогда наивное 32-битное кодирование даст следующую длину:
В работе Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach описанный выше способ применяется к модели MobileNet (свёрточной сети, сконструированной специально для мобильных устройств), обученной на наборе данных ImageNet, и получают верхнюю оценку на истинный риск, равную (риск случайного угадывания – ). Хотя такой результат и выглядит очень скромным, но это первая осмысленная оценка обобщающей способности реально используемой нейронной сети на реалистичном наборе данных.