Неопределенная среда

Случай известной детерминированной среды с заданной целевой функцией банален. По сути, вся область ИИ началась с рассмотрения этого случая, когда была высказана лабиринтная гипотеза мышления. И, естественно, исследователи очень быстро с общей постановки задачи перешли к вопросу о том, как ее решать на практике в условиях ограниченных вычислительных ресурсов. Вместе с тем заданность среды означает неавтономность и неуниверсальность соответствующих интеллектуальных программ. Так, удается создать программы, которые оказываются эффективнее человека в каждом из таких ограниченных миров, но это не позволяет компьютеру решать новые задачи самостоятельно. Вполне естественно желание сразу рассмотреть общий случай, включающий произвольную и неопределенную среду. Конечно, можно задаться вопросом, стоит ли браться за более сложную задачу, когда полное решение для более простой задачи детерминированной среды (при ограничении на ресурсы) отсутствует? Но в истории науки есть множество примеров, когда решение более простой, частной задачи не удавалось получить до тех пор, пока не была решена более общая задача. Здесь рассмотрение постановки задачи для более универсального интеллектуального агента, если и не приведет к своему полному решению, позволит лучше понять проблему ИИ в целом и облегчит решение чуть более частных задач.

Что означает отсутствие у нас полной информации о среде? Это означает, что мы не знаем в точности алгоритма среды q. Но что агенту о среде известно? Пусть существует некоторое множество алгоритмов, каждый из которых может оказаться истинным (это множество может быть алгоритмически полным). И пусть агенту дано распределение априорных вероятностей μ(q).

Введение такого распределения может показаться странным. Ведь рассматриваемые алгоритмические модели являются детерминированными и либо соответствуют среде, либо нет. Однако наименее противоречивой является не статистическая, а информационная интерпретация вероятности: вероятность событию, модели и т.д. приписывается постольку, поскольку у нас нет полной информации для их предсказания или выбора. Здесь же мы как раз и предполагаем неполную информацию о модели среды, и эта неполнота гибко описывается распределением вероятностей. Следует, однако, подчеркнуть, что распределение μ(q) нельзя считать «истинным»; корректнее его полагать наилучшим из возможных при имеющейся априорной информации. Хотя в некоторых условиях этому распределению вероятностей можно придать и вполне статистический смысл. К примеру, если «среда» – это противник при конкретной игре в шахматы, то априорные вероятности могут обозначать, например, частоту встречаемости противников, идеально играющих по принципу минимакса, профессионалов, новичков и т.д. В этом случае можно полагать, что есть некая генеральная совокупность противников-«сред», которая описывается «истинным» распределением μ(q), хотя некоторая доля условности остается и здесь.

Имея распределение вероятностей μ(q), несложно модифицировать постановку задачи для агента как максимизацию математического ожидания ожидаемого подкрепления:

formula_40

Опять же, это выражение не обладает оригинальностью и приведено здесь в соответствии, например, с [Hutter, 2005]. Оптимальная модель агента тогда будет определяться как

formula_41

Казалось бы, данное выражение введено корректно. Интересно, однако, то, что программу p* нельзя выбирать априорно в соответствии с ним и оставлять неизменной. Как было подчеркнуто выше, сейчас мы рассматриваем детерминированные среды, поэтому распределение μ(q) не может иметь смысла истинной стохастической модели среды. Вместо этого, μ(q) – априорно лучшая неопределенная модель детерминированной среды.

Разницу между ними можно пояснить на примере бинарной последовательности, которая в одном случае порождается неизвестным детерминированным алгоритмом (генератором псевдослучайных чисел, ГПСЧ), а в другом – истинно случайным процессом с вероятностями P(0)=P(1)=0.5. Случайный процесс описывается вполне определенной стохастической моделью, которая может быть истинной. Сколько бы мы нулей и единиц ни наблюдали, на модель это никак не влияет. Напротив, в случае неопределенной детерминистской модели наблюдение части бинарной последовательности будет снижать неопределенность: не любой ГПСЧ может породить именно ту последовательность, которую мы наблюдаем, и часть из них мы можем исключить из рассмотрения.

Но если у нас есть некоторые q, которые не согласуются с уже имеющейся историей, разве может для них выполняться неравенство μ(q)≠0? Очевидно, нет. Поэтому распределение μ(q) и математическое ожидание подкрепления при имеющейся истории взаимодействия агента со средой должно пересчитываться. Для неопределенных детерминированных моделей можно принять простой способ пересчета для момента k:

formula_42

где C_{k} – константа (для имеющейся истории в момент k), обеспечивающая нормировку μ_{k}(q). Поскольку модели среды детерминированные, они не изменяют плавно своей вероятности, скажем, по правилу Байеса, а просто отсеиваются. Накладывает ли использование детерминированных программ p и q какие-то ограничения на универсальность интеллектуального агента? Вопрос этот неоднозначный, поскольку само наличие истинной случайности в реальном мире дискуссионно. А при том, что наименее противоречивая формализация понятия вероятности достигается в рамках алгоритмической теории информации, в нулевом приближении можно считать, что детерминированных моделей достаточно. К этому вопросу, однако, мы вернемся позднее.

Теперь несложно уточнить математическое ожидание подкрепления с учетом имеющейся истории и оптимальную стратегию на момент k:

formula_43

Здесь стоит особо оговорить смысл того, что в случае неопределенной среды не существует такого оптимального алгоритма p*, который при детерминированной среде мог быть построен по формуле (2.1.2) при k=1. Это достаточно простой, но принципиальный для понимания момент: кажется, что в случае неопределенной среды даже при данном распределении μ(q) нельзя (априорно) построить оптимальный алгоритм интеллекта, поскольку в зависимости от текущей истории он будет разным, то есть алгоритм  p_{1}^{*} , определяемый по уравнению (2.1.4), будет неоптимальным при k >1. В то же время, сам выбор оптимальной программы, например в соответствии с уравнением (2.1.4), на каждом такте выглядит вполне алгоритмическим, то есть этот выбор осуществляется таким алгоритмом  p_{1}^{*} , который остается оптимальным при k >1. Может показаться, что здесь есть некое противоречие. Однако его на самом деле нет. Просто алгоритмов, которые для текущего момента истории и данного распределения μ(q) дают максимальное значение математического ожидания будущего подкрепления, существует много. Какой именно из них возвращается по argmax в (2.1.4) не оговаривается. И этот алгоритм вполне может оказаться неоптимальным при поступлении новых данных. Однако среди всех оптимальных алгоритмов существуют и универсальные алгоритмы, в частности, выполняющие поиск других оптимальных алгоритмов по (2.1.4).

Естественно, существует универсальный алгоритм выбора оптимального действия, который перебирает не алгоритмы порождения действий, а непосредственно цепочки действий:

formula_44

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

В этой связи может показаться ненужным искать программы на каждом шаге в соответствии с (2.1.4), если у нас уже есть универсальная оптимальная программа в форме (2.1.5). Однако оптимальность последней будет нарушена, как только величина целевой функции станет зависеть от скорости работы алгоритма выбора действий, и построение универсального оптимального алгоритма вручную окажется проблематичным, и такой алгоритм окажется необходимым строить в процессе самооптимизации, для описания которой придется вернуться к поиску алгоритмов, что мы будем обсуждать позднее.

Уравнения (2.1.4) и (2.1.5) эквивалентны аналогичным уравнениям в [Hutter, 2005]. Здесь мы их приводим без уточнения, хотя полагаем их не вполне верными. Дело в том, что по (2.1.4) так же нельзя выбирать оптимальную программу  p_{k}^{*} , как нельзя было априорно выбирать неизменную  p_{1}^{*} . Данные уравнения не учитывают процесс изменения распределения μ(q) по мере накопления информации. В зависимости от выбора действия распределение μ(q) может оставаться неизменным или сужаться. Исследовательское поведение как раз и подразумевает выбор действий, нацеленных на получение информации, максимально снижающей неопределенность. Следует ожидать, что исследовательское поведение не будет свойственно агенту, действующему в соответствии с (2.1.4) и (2.1.5). Но здесь мы пока продолжим изложение по [Hutter, 2005], а к этому вопросу вернемся позднее.

Подчеркнем еще один аспект. Программа выбора оптимального действия является классическим алгоритмом, который запускается на определенных входных данных и формирует ответ. Однако действия интеллектуального агента в целом не являются классическим алгоритмом в том смысле, что система управления работает непрерывно и запускает алгоритм выбора действия на каждом такте с новыми данными. То есть данная система не работает с некоторой входной лентой, содержащей фиксированные исходные данные, по которым формируется некий конечный ответ. Напротив, система интерактивно взаимодействует со средой, функционирующей неформализованным образом и в процессе выполнения меняющей входные данные системы управления. В этом смысле данная система является не алгоритмом в строгом смысле этого слова, а алгоритмическим процессом (который также можно назвать «адаптивным алгоритмом»). Несмотря на очевидность данного обстоятельства, оно часто упускается из виду, в результате чего, в частности, к алгоритмическому интеллектуальному агенту некорректным образом применяется теорема Гёделя о неполноте формальных систем (в то же время, к агенту как открытой системе, взаимодействующей с неформальным миром, теорема Гёделя просто неприменима). Помимо этого интерактивность (адаптивность) этой системы может принять более сложную и не столь очевидную форму при развитии модели интеллектуального агента, поэтому данное формальное отличие от классического понятия алгоритма следует не упускать из вида.

В уравнении (2.1.5) по сравнению с (2.1.3) добавляется суммирование по всем заданным моделям сред, что делает задачу выбора оптимального действия вычислительно еще более тяжелой, но это является необходимым для универсальности агента. На данном этапе рассмотрения принципиальнее то, что априорное распределение для реального мира является недоступным.