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

не указывает всего лишь на рог антилопы? Или, может быть, это название конкретной разновидности антилоп, представитель которой и пробегал мимо. Хуже того, это может означать, что некая конкретная антилопа пробежала мимо в конкретный день недели! Возможно огромное число ситуаций, на которые мог ссылаться представитель племени, используя это слово, поэтому мы должны сделать вывод о том, что выучить язык невозможно, сколько бы времени мы ни провели в племени.

Есть шутка о планете, населенной людьми, которые верят в антииндукцию: если в прошлом солнце вставало над землей каждый день, то сегодня нам следует ожидать, что оно не взойдет. В результате все эти люди голодают и живут в бедности. Некто посещает эту планету и говорит им: «Послушайте, почему вы до сих пор пользуетесь этой философией антииндукции? Вы живете в ужасной бедности!»

«Ну, никогда раньше это не срабатывало…»

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

Мне кажется, ключевой момент, который должен приниматься во внимание при любом подходе, будь то байесизм, теория вычислительного обучения или еще что-то, состоит в том, что мы никогда не рассматриваем все логически представимые гипотезы на равных основаниях. Если у вас имеется 500 воронов, каждый из которых либо бел, либо черен, то в принципе существует 2500 гипотез, которые вам следует рассмотреть. Если вороны могут быть не только черными и белыми, но и зелеными, гипотез будет еще больше. Однако в реальности мы никогда не рассматриваем все эти гипотезы как равно возможные. Мы всегда ограничиваем свое внимание некоторым небольшим подмножеством гипотез — их можно назвать «достаточно простыми» гипотезами, — если только данные не вынуждают обратиться к более сложным гипотезам. Иными словами, мы всегда неявно используем так называемую «бритву Оккама» (хотя совершенно неясно, это ли имел в виду сам Оккам).

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

Но это все пустые разговоры. Можем ли мы на самом деле понять, как взаимосвязаны число рассматриваемых гипотез и степень уверенности, с которой мы предсказываем будущее? Один из способов сделать это сформулировал Лесли Валиант в 1984 г.[123] Его подход называется PAC-обучение, где PAC означает «probably approximately correct» («вероятно почти корректное»). Мы не собираемся предсказывать все, что происходит в будущем, не собираемся даже предсказывать с определенностью большую часть, но с высокой вероятностью мы попытаемся предсказать большую часть верно.

Возможно, это звучит как чистая философия, но часть этих рассуждений можно напрямую связать с экспериментами. К примеру, эту теорию использовали в экспериментах с такими вещами, как нейронные сети и машинное обучение. Когда-то в процессе написания статьи о PAC-обучении я захотел выяснить, как эта теория реально используется, и заглянул на «Академию Google». На момент публикации этой книги статья Валианта была процитирована 4000 раз. На основании этого можно заключить, что следует ожидать дальнейших публикаций на эту тему.

Как же работает PAC-обучение? Возьмем множество S, которое может быть конечным или бесконечным, и назовем его пространством примеров. К примеру, пусть мы — это младенец, который пытается освоить язык и получающий несколько примеров предложений, грамматически верных или неверных. Из этого нам нужно вывести правило, по которому можно определить, является ли новое предложение грамматически верным или нет. В этом случае наше пространство примеров — это множество возможных предложений.

Концепция — это булева функция f: S → {0, 1}, отображающая каждый элемент пространства примеров либо на 0, либо на 1. Позже мы можем отбросить допущение о том, что концепции представляют собой булевы функции, но для простоты мы пока будем считать их таковыми. В нашем примере концепция — это язык, который мы пытаемся изучить; получив предложение, концепция сообщает нам, верно ли оно грамматически. Далее, мы можем получить класс концепций и обозначить его C. Здесь C можно считать множеством языков, которые наш младенец, приходя в мир, считает в принципе возможными еще до получения каких-либо данных о реальном используемом языке.

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

Какова же цель всего этого? Мы получаем m образцов xi, извлеченных независимо из распределения D, и для каждого xi мы получаем f(xi), то есть нам сообщают, верен ли грамматически каждый из наших образцов. Пользуясь этими данными, мы хотим создать язык-гипотезу h, такой, что

где ~ означает, что x берется из распределения D. То есть мы хотим, чтобы наша гипотеза h расходилась с концепцией f не более чем в доле ε примеров x, извлеченных из распределения D. Можем ли мы уверенно надеяться на такой результат? Нет? Ну почему же нет?

Вам может не повезти с получаемыми образцами; так, можно извлекать из распределения один и тот же образец снова и снова. Если единственное предложение, которое вам доведется слышать младенцем, будет: «Какой умный малыш!», то у вас не выработается никакой базы, на основании которой вы сможете определить, является ли также предложением фраза: «Мы считаем эти истины самоочевидными». В общем-то, следует считать, что возможных предложений существует экспоненциально много, но младенец слышит из них лишь полиномиальное количество.

Итак, мы говорим, что должны лишь выдать только ε-хорошую гипотезу с вероятностью 1 — δ по