Контекст. Ошибка обобщения относится к вероятности ошибочных прогнозов в будущих данных после обучения некоторого алгоритма на некоторых данных. Это основная величина, интересующая машинное обучение (Синонимы: производительность == ошибка обобщения == истинная ошибка). Распределение данных относится к распределению вероятностей экземпляров данных (например, изображение + метка). Обычно мы предполагаем, что каждая новая выборка независима и одинаково распределена.
Инженер машинного обучения: я хочу знать, какова будет производительность моего алгоритма. Но я не знаю, что такое распределение данных..
Вольперт (NoFreeLunch): извините, боюсь, я не могу этого сделать. Независимо от того, какой у вас алгоритм, всегда существует такое распределение, что ваш алгоритм работает как минимум так же плохо, как случайное угадывание! Поэтому мы не можем быть уверены, что ваш алгоритм сработает!
Инженер машинного обучения: :/ — Хорошо! Но что, если я получу какие-то данные, тогда у меня будет некоторое представление о том, что такое распределение, верно?
ПАК (независимо) [застенчивым голосом]: Эээ, да, тебе просто нужно…
Меньший венчурный капитал: Да!!, тогда вы можете получить некоторое представление о производительности вашего алгоритма, взглянув на ошибку обучения после обучения на данных. Мы можем оценить истинную ошибку по ошибке обучения, если вы дадите нам только размер VC вашего алгоритма.
ML: Хм, но это только верхняя граница. Мой алгоритм мог бы работать намного лучше, верно?
Большой венчурный капитал. Но невозможно гарантировать, что он будет работать намного лучше. Это потому, что я могу доказать, что для любого алгоритма существует такое распределение данных, что истинная ошибка не намного меньше, чем предсказывает верхняя граница. Итак, опять же, если вы ничего не предполагаете/не знаете о распределении данных, это лучшее, что мы можем сделать!
ML: Хорошо… но для некоторых распределений данных истинная ошибка может быть намного ниже верхней границы, даже если существует какое-то очень плохое распределение, если его нет. Возможно, по данным я мог бы также оценить, нахожусь ли я в каком-то хорошем или плохом распределении.
Малые и большие венчурные капиталисты: Хммм
Радемахер [появляется позади Малого ВК]: Верно! Вы можете оценить ожидаемую сложность Радемахера из обучающих данных, и это может дать более точные оценки истинной ошибки для случаев, когда вы получаете распределение данных не в худшем случае (для VC)!
Большой венчурный капитал: :S
ML: О, отлично! Но подождите... Ваша оценка ничего не предполагает об алгоритме, кроме его класса гипотез. Вы уверены, что это намного лучше, чем VC? Можете ли вы гарантировать, что мой алгоритм, опять же, не будет работать намного лучше? Например, я имею в виду, что у меня есть эти новые вещи, называемые глубокими нейронными сетями, и у них, похоже, ОГРОМНЫЙ класс гипотез, и я просто не уверен, что ваша оценка сможет объяснить, когда они работают хорошо (потому что они действительно часто !)
Радемахер: Да, но, эээ.. (где больше Радемахера, когда он нужен..)
Байес: Что ж, для заданного распределения данных я могу точно определить нижнюю границу истинной ошибки любого алгоритма! Это просто называется байесовским риском. И да, это может быть намного ниже, чем вам говорит Радемахер.
ML: Но я не хочу ничего предполагать о распределении данных. Я просто знаю о своем алгоритме и данных, которые я получаю. Разве я не могу сказать что-то вроде «для моего конкретного алгоритма, для любого распределения данных, учитывая данные, моя истинная ошибка жестко ограничена между этими двумя значениями»?
Байесовский: возможно, вы сможете оценить байесовский риск по данным. Но если ваш алгоритм не будет следовать моему правилу, я не уверен, что произойдет. Я слишком стар для этого…
[Чувствительная, вероятно, вмешалась бы сейчас, но она опоздала на вечеринку]
PAC-Bayes Junior: Моя верхняя граница, зависящая от данных, верна для любого распределения данных, и она может быть точнее/лучше, чем у Радемахера. Он предполагает, что ваш алгоритм похож на байесовский, но не является фактическим байесовским предиктором, потому что, конечно, вам не нужно знать, каково истинное распределение данных.
PAC-Bayes: Это мой сын! Кстати, если вы хотите что-то, что справедливо для более общих алгоритмов, просто скажите мне, но вам нужно определиться с априором, а также уметь вычислять относительные энтропии.
PAC-Bayes Junior: Спасибо, папа! Подожди, разве я не родился раньше тебя!?
ML: Кхм, звучит здорово! Но как выбрать приору? Кроме того, ваши границы жесткие? Можете ли вы показать мне, что вы не можете добиться большего успеха, не делая никаких предположений о распределении данных?
PAC-Bayes: Что ж, для данного априорного алгоритма лучшим алгоритмом (для моей границы) является соответствующий ему байесовский предиктор, и в этом случае вы можете просто использовать границу Джуниора. Для других алгоритмов вам, вероятно, нужен априор, который согласуется с алгоритмом, иначе я могу представить, что что-то работает не слишком хорошо. Но я сейчас не уверен, какой априор лучше для общего алгоритма. Хороший вопрос!
PAC-Bayes Junior: Да! А по поводу другого вопроса.. Пока не уверен! Было бы здорово найти мою версию с более низкой оценкой! (Большой ПАК-Байес, где ты?). Кроме того, честное предупреждение, моя оценка по-прежнему зависит от выбора априора. И я ничего не могу сказать об этом выборе, кроме того, что он должен зависеть от ваших убеждений о распределении данных. Старый Байес должен быть знаком с этим
Байесовский: не заставляйте меня начинать
ML: Круто! Итак, в общем, подытожим. Если у меня есть какое-то априорное убеждение, я должен использовать его как априорное. Затем я должен использовать соответствующий байесовский предсказатель, а затем использовать связанный PAC-Байес, чтобы проверить, были ли мои убеждения правильными или нет, и дать соответствующую оценку будущей/истинной ошибки моего алгоритма (низкая ошибка, если мои убеждения были правильными, и высокая если не). Вы пока не можете гарантировать мне, что нет лучшей оценки, чем вы, но ладно, по крайней мере, вы честны :)
*SRM (система минимизации структурных рисков) только что присоединился к серверу*
Продолжение следует…
