Пожалуйста, установите плагин Math Anywhere для Chrome, чтобы увидеть отображаемые уравнения. Или лучше просто перейдите на версию на моем сайте: https://jg-blog.surge.sh/blog/no-free-lunch

Это часть серии, но ее можно читать отдельно.

Теория, которая все объясняет, но ничего не объясняет — Карл Поппер¹

Теорема об отсутствии бесплатного обеда была впервые доказана Дэвидом Вулпертом и Уильямом Макреди в 1997 году. Проще говоря, теорема об отсутствии бесплатного обеда утверждает, что ни один алгоритм обучения не может успешно обобщаться для всех наборов данных. Подразумевается, что крайне важно выбрать правильный алгоритм обучения для вашего набора данных.

Обобщение означает создание прогнозов на основе прошлых точек данных о точках данных, которые вы раньше не видели. Легко видеть, что невозможно обобщать, не делая предположений о данных. Если я скажу вам, что f(0) = -1,2, f(1), = -2, f(2) = -1, f(2,2) = -2, f(3) = 0, сможете ли вы математически доказать, что значения f(2.5) или f(4) равны? Очевидно, что вы не сможете этого сделать, если не сделаете какое-то предположение о функции f. Одним из наиболее часто применяемых предположений в машинном обучении является предположение о гладкости: аналогичные входные данные имеют аналогичные выходные данные. Полезная интерпретация гладкости состоит в том, что производная функции имеет тенденцию быть малой. Применяя предположение о гладкости к f, мы можем сделать вывод, что f(2.5) должно быть где-то между f(2.2) (которое, как мы наблюдали, равно -2) и f(3) (которое, как мы наблюдали, равно 0). Итак, мы ожидаем, что f(2.5) будет около -1. В машинном обучении мы называем эти допущения обобщением индуктивных предубеждений алгоритма обучения.

Если набор возможных входных данных является дискретным и ограниченным, так что существует конечное число n возможных входных значений, то нам нужно только знать значение f для этих n значений и сохранить его в таблице поиска. Это называется запоминанием данных, и в этом случае не требуется никакого обобщения. Таким образом мы можем легко решить многие проблемы, но это не работает для непрерывных значений или когда n неоправданно велико. Поскольку машинное обучение происходит на компьютерах, все предположительно непрерывные значения будут числами с плавающей запятой. Эти числа с плавающей запятой чаще всего являются 32-битными, поэтому обычно существует конечное число возможных значений n=2³². Однако 2³² кажется неоправданно большим для таблицы поиска. Для такой таблицы поиска потребуются миллиарды точек данных. Поэтому часто приходится обобщать.

Предположение о гладкости хорошо соответствует физике. В то время как многие вещи (возможно, все вещи) дискретны на самом низком уровне, классическая физика, описывающая мир макроуровня, к которому мы все привыкли, имеет в основном гладкие уравнения. Более того, Эйнштейн показал, что скорости ограничены скоростью света. Это означает, что при малом $\epsilon › 0$ мы можем показать, что для всех объектов вдоль любой оси $x$ $|x(t + \epsilon) — x(t)| ‹ c * \epsilon$, где $c$ — скорость света. Эквивалентно, $|x’(t)| ‹ с$. На практике большинство скоростей, с которыми мы имеем дело, намного меньше скорости света. Таким образом, положение является гладким по времени.

Одним из самых простых и наиболее общих алгоритмов вывода, использующих предположение о гладкости, является квантование + интерполяционная таблица. Он может аппроксимировать любую гладкую функцию с произвольно высокой точностью при наличии достаточного количества данных. Это универсальный аппроксиматор гладких функций. Квантование дискретизирует входные данные, умножая входные числа на некоторую шкалу $s$ и затем округляя до ближайшего целого числа. Если все наши входные данные находятся в некотором ограниченном диапазоне от $a$ до $b$, то общее количество возможных значений для квантованных входных данных равно $s(b-a)$. Затем таблица поиска, применяемая к квантованным данным, должна хранить только $s(b-a)$ возможных значений. Таким образом, мы можем сэкономить память за счет точности, уменьшив масштаб $s$. Между тем, больший масштаб приводит к более точным прогнозам, но требует большей таблицы поиска. При наличии достаточного количества обучающих данных и достаточно большой интерполяционной таблицы любая гладкая функция может быть смоделирована с любой необходимой точностью.

Для иллюстрации мы моделируем функцию f(x) = x * sin(x). Суть в том, чтобы делать прогнозы в точках, которые мы еще не видели, поэтому я беру выборку из 500 точек в качестве обучающих данных, на которых обучается наш алгоритм обучения. Код для создания этого графика находится под графиком.

Определение: теорема о бесплатном обеде не существует

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

Компромисс смещения и дисперсии

Более интуитивно понятным названием для наших целей могло бы быть компромисс между специфичностью и общностью, а не компромисс между смещением и дисперсией. Смещенная сторона компромисса соответствует алгоритмам обучения с более сильными индуктивными смещениями. Недостаток алгоритмов обучения с сильными индуктивными погрешностями заключается в том, что они обобщают только в том случае, если индуктивные погрешности верны для данных, к которым вы их применяете. Индуктивные предубеждения — это предположения алгоритма обучения, и если ваши предположения неверны, то и последующие выводы будут неверными. Алгоритмы обучения на стороне дисперсии компромисса между смещением и дисперсией требуют для обучения большого количества данных, но являются более общими в том смысле, что они могут хорошо обобщать более широкий спектр наборов данных при наличии достаточного количества данных. Таблица поиска — это самый крайний случай алгоритма обучения на стороне дисперсии компромисса. Он не имеет индуктивных смещений и работает со всем, но требует выборки данных для каждого возможного входа. Сочетание справочной таблицы с квантованием приближает ее к стороне компромисса, связанной со смещением. Использование более крупного масштаба для квантования приводит к еще большему смещению компромисса. Также см. подробные определения смещения и дисперсии из классической статистики, но эти определения не нужны для остальной части этой книги.

Теорема Байеса помогает нам точнее понять этот компромисс. Вероятность некоторой гипотезы (гипотеза представляет наши индуктивные предубеждения) $H$ при некоторых данных $D$ равна

экв. 1: $P(H|D) = \frac{P(D|H)P(H)}{P(D)}$

Байесовцы называют $P(D|H)$ доказательством гипотезы, потому что теорема Байеса показывает, что вероятность гипотезы при данных данных пропорциональна $P(D|H)$. Мы не можем полностью вычислить $P(H|D)$, потому что не знаем, что такое P(H) или P(D). На самом деле полное вычисление $P(H|D)$ не нарушило бы никакой теоремы о бесплатном обеде. Однако мы знаем, что сумма $P(D’|H)$ по всем возможным наборам данных $D’$ будет равна 1: $\sum_{D’} P(D’|H) =1$ . Следовательно, $P(D|H) =1-\sum_{D'\neq D} P(D'|H)$, где $\sum_{D'\neq D}$ представляет собой сумму по всем возможным наборам данных, кроме $Д$. Таким образом, чтобы доказательства были высокими, вероятность наборов данных, отличных от $D$, должна быть низкой. Следовательно, ни одна гипотеза не может хорошо соответствовать данному набору данных, а также хорошо соответствовать всем другим наборам данных.

Посмотрите несколько наглядных примеров компромисса смещения и дисперсии в видео ниже.

Понимание математической основы компромисса смещения и дисперсии рекомендуется, но не имеет решающего значения для этой серии. Я бы начал с разложения ошибки на смещение-дисперсию.

Примечание 1. Мы становимся более уверенными в том, что $H$ верно, когда собираем больше данных, если $H$ хорошо соответствует этим данным.

Если D представляет собой матрицу из $n$ независимо выбранных точек, то мы можем разложить уравнение. 1 как,

$P(H|D) = P(H)\prod_i^n \frac{P(D^i|H)}{P(D^i)} = P(H) \cdot M^n$

где $M$ — среднее геометрическое отношений $P(D^i|H)/P(D^i)$ для каждого $i$. Если $P(D|H) › P(D)$, то среднее геометрическое $M$ должно быть больше 1. Это происходит, когда доказательства относительно высоки. В этом случае $P(H|D)$ будет экспоненциально возрастать с ростом $n$, если предположить, что среднее геометрическое $M$ остается постоянным при увеличении $n$. Увеличение $n$ означает сбор большего количества данных, а оставшееся постоянным значение $M$ означает, что гипотеза $H$ обобщается на вновь собранные данные. В результате мы становимся более уверенными в том, что $H$ верно, поскольку мы собираем больше данных и видим, что они по-прежнему точны на новых данных.

Определение. упорядочить:

Как глагольная форма компромисса смещения и дисперсии. Регуляризация — это модификация алгоритма обучения, чтобы приблизить его к пределу смещения компромисса между смещением и дисперсией. Например, квантизация — это регуляризация таблицы поиска.

Повторите наш эксперимент с меньшим количеством обучающих данных

Квантование делит набор возможных входных данных на ячейки, а меньший масштаб квантования означает меньшие ячейки. Недостатком является то, что меньший масштаб квантования требует большей таблицы поиска и большего количества данных. Если нет данных для одного из квантованных значений, предиктор не знает, что делать. В этой реализации он просто произвольно возвращает -10. Итак, на графике справа, где масштаб квантования равен 50, вы видите много значений -10, потому что в таблице поиска не было соответствующего значения. Подробнее об этой проблеме будет позже в посте о проклятии размерности. График посередине со шкалой квантования 2 выглядит лучше, чем тот, что справа. Если мы повторим тот же эксперимент с 50 точками данных, а не с 500, то тот, что справа, пропускает почти все:

Обратите внимание, что предиктор хуже подходит для областей, где производная велика, потому что предположение о гладкости (что означает, что производная должна быть малой) здесь «менее верно».

Теорема о бесплатном обеде поднимает интересные вопросы о философии науки, к которым я отвечу далее в «Как возможна наука?».

Надеюсь, вы нашли это полезным. Любые отзывы или предложения по этому поводу будут оценены! 🙏

¹Хотя большинство источников, которые я проверил, приписывают эту цитату Попперу, очевидно, существует некоторый спор о ее происхождении. Кроме того, сама эта цитата исходит из Грегори Бонда. Поиск этой цитаты в Google Scholar дает много результатов. Он часто используется для обобщения аргументов Поппера в пользу фальсифицируемости.