Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Теорема. Чтобы удовлетворить требованию о том, что результирующая гипотеза h согласуется с 1 — ε будущих данных из тех, что будут случайно отобраны из D, с вероятностью 1 — δ по выбору примеров, достаточно найти такую произвольную гипотезу h, которая согласуется с

образцами, отобранными независимым образом из D.

Ключевой момент в отношении этой оценки заключается в том, что она логарифмически связана с числом возможных гипотез |C|. Даже если гипотез экспоненциально много, эта оценка все равно полиномиальна. Но почему мы требуем, чтобы распределение D, на котором будет тестироваться обучающий алгоритм, совпадало с распределением, из которого извлекаются пробные примеры?

Потому что если ваше пространство образцов представляет собой ограниченное подмножество пространства примеров, то вас обманули.

Это подобно требованию о том, что в тестовом опросе не должно быть ничего, что не изучалось бы на уроках. Если предложения, которые вы слышите от людей, соответствуют только английскому языку, а вы хотите гипотезу, которая соответствовала бы французским предложениям, то это вряд ли возможно. Все-таки нужно допускать, что будущее напоминает прошлое.

Стоит вам сделать такое допущение, и теорема Валианта скажет, что для конечного числа гипотез и с разумным числом образцов обучение возможно. И более никаких допущений не нужно.

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

Существует способ делать это, но теория вычислительного обучения говорит нам, что этот способ не единственный. Не обязательно начинать с каких бы то ни было допущений о распределении вероятностей по гипотезам. Можно даже сделать наихудшее допущение об этой гипотезе (мы, компьютерщики, обожаем это делать, поскольку все мы пессимисты!), а затем просто сказать, что вы бы хотели получить хоть какую-то гипотезу из класса концепций при любом распределении с высокой вероятностью по выбору образцов. Иными словами, вы можете обменять байесовское распределение вероятностей для гипотез на распределение вероятностей для примеров.

Во многих случаях это и правда предпочтительнее: вы не имеете понятия о том, что представляет собой верная гипотеза, — в этом и заключается проблема, — так почему вам нужно априорно принимать какое-то конкретное предварительное распределение? Мы не обязаны знать начальное распределение по гипотезам, чтобы применять теорию вычислительного обучения. Нам нужно только допустить, что некое распределение имеется.

Доказывается теорема Валианта совсем несложно. Назовем заданную гипотезу h плохой, если они расходится с f более чем на доле ε данных. Тогда для любой конкретной плохой гипотезы h, поскольку x1, …, xm независимы, мы имеем

Pr[h(x1) =f(x1), …,h(xm) =f(xm)] < (1 — ε)m.

Это ограничивает вероятность того, что данная плохая гипотеза дала верные предсказания по образцам. Тогда чему равна вероятность того, что существует плохая гипотеза h ∈ C, которая согласуется со всеми данными выборки? Мы можем воспользоваться границей объединения:

Pr[существует плохая h, которая согласуется с f для всех образцов] < |C| (1 — ε)m.

Мы можем приравнять эту вероятность к δ и решить уравнение относительно m. Получаем:

Что и требовалось доказать.

Это дает нам границу числа образцов, необходимых для конечного множества гипотез, но как насчет бесконечных классов концепций? К примеру, что если мы пытаемся узнать прямоугольник на плоскости? Тогда наше пространство примеров — это множество всех заполненных прямоугольников. Предположим, нам даны m точек, и для каждой указано, принадлежит она или нет «секретному прямоугольнику».

Итак, сколько у нас возможных прямоугольников? Существует 2ℵ₀ возможных вариантов, так что мы не можем применить предыдущую теорему! Тем не менее если даны 20–30 случайных точек в прямоугольнике и 20–30 случайных точек вне прямоугольника, но рядом с ним, интуитивно кажется, что мы имеем довольно здравое представление о том, где именно находится прямоугольник. Можем ли мы предложить более общую теорему об обучении, применимую, когда класс концепций бесконечен? Да, но для начала нам понадобится концепция под названием дробление.

Для некоторого класса концепций C мы говорим, что подмножество пространства примеров {s1, s2, …, sk} раздроблено C, если для всех 2k возможных классификаций s1, s2, …, sk существует некоторая функция f ∈ C, которая согласуется с этой классификацией. Тогда определим VC-размер класса C, обозначаемый VCdim (C), как размер наибольшего подмножества, раздробленного C.

Что представляет собой VC-размер класса концепций прямоугольников? Нам нужно наибольшее множество точек, таких, что для любого возможного распределения их на те, которые принадлежат прямоугольнику и которые не принадлежат, существует некоторый прямоугольник, который содержит только те точки, которые нам нужны, причем все. Нижеследующая диаграмма иллюстрирует, как добиться этого с четырьмя точками. С другой стороны, не существует способа сделать это с пятью точками (доказательство этого пусть будет упражнением для вас!).

Одно из следствий следующей теоремы гласит, что PAC-обучение возможно с конечным числом образцов в том и только том случае, если VC-размер класса концепций конечен.

Теорема (Блумер, Эренфойхт, Хаусслер и Вармут, 1989)[124]. Чтобы получить гипотезу h, способную объяснить долю 1 — ε будущих данных, извлеченных из распределения D, с вероятностью 1 — δ, достаточно построить любую h из C, которая согласуется с

образцов, извлеченных независимо из D. Более того, это точная оценка (с учетом зависимости от ε).

Эту теорему доказать труднее, чем предыдущую, на это потребовалась бы отдельная глава, так что мы опустим доказательство. Интуитивно, однако, за доказательством стоит просто бритва Оккама. Если VC-размер конечен, то после рассмотрения количества образцов, превышающего VC-размер, энтропия уже рассмотренных данных достигнет лишь приблизительно VC-размера. Вы делаете m наблюдений, после чего возможное количество вещей, которые вы уже видели, будет меньше 2m; в противном случае было бы VCdim (C) ≥ m. Следовательно, для описания этих m наблюдений требуется меньше чем m бит. Это означает, что можно предложить теорию, которая объясняет прошлые данные и содержит при этом меньше параметров, чем сами данные.

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