Опасность упрощения ИМИ на примере элементарной среды

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

Рассмотрим очень простую среду, которая на каждое действие агента y выдает подкрепление r с неизменной, но не известной заранее вероятностью P(r | y). При этом и действия, и величины подкреплений будут принадлежать конечным множествам. Данная среда стохастична, и алгоритмическая сложность истории взаимодействия с такой средой будет пропорциональна длине самой истории. Однако в связи с известностью и элементарностью регулярной части модели среды, полное ее восстановление достаточно просто.

Рассматриваемые модели сред представляют собой двумерные массивы P(r | y). Все модели будут совместимы с историей, за исключением тех, у которых P(r | y)=0 для таких пар (y, r), которые в данной истории встречаются; а с учетом того, что вероятности являются вещественными, таких моделей будет множество меры ноль. Массив P(r | y) является лишь регулярной частью модели, которая должна быть дополнена данными, необходимыми для генерации истории по распределению P(r | y). Каждый элемент истории (y, r) кодируется словом c длиной -log_{{2}}P(r|y) бит (здесь мы не будем обращать внимания на то, что длина кодового слова может составлять дробное число бит). Закодированная таким образом история в совокупности с описанием распределения P(r | y) и является полной моделью среды, согласованной с ее историей: q=P(r | y),{c_{\lt k}}. Длина такой модели будет равна сумме длины описания P(r | y) и длины закодированной истории. Эта модель алгоритмична и детерминирована в следующем смысле: ее можно представить как самораспаковывающийся архив – программу, внутри которой прописаны массивы c_{\lt k} и P(r | y), по которым происходит «распаковка» истории. Длина самой программы распаковки также должна была бы учитываться; но поскольку алгоритм распаковки один и тот же для всего множества рассматриваемых моделей, мы ее опускаем. Также мы положим длины описаний распределений P(r | y) равными, хотя это дополнительное упрощение. Тогда длина полной модели будет равна:

formula_76

Весьма примечательно, что сложность модели определяется по истории, хотя в AIξ просто перебираются модели, имеющие «безусловную» длину. Откуда берется такой эффект? Его причина достаточна прозрачна. Действуя в точности по схеме AIξ, мы должны были бы перебирать для каждого распределения P(r | y) все возможные цепочки кодов истории c_{\lt k}, среди которых лишь одна оказалась бы согласованной с имеющейся реальной историей. Здесь же мы в явном виде без перебора восстанавливаем оставшуюся (случайную) часть модели по ее началу (регулярной части). То есть мы сразу выделяем из всего множества моделей подмножество таких моделей, которые согласованы с историей. Из-за этого, правда, исчезает возможность перебора моделей в порядке возрастания их длины. Такая ситуация достаточно характерна при использовании стохастических моделей, что мы более детально обсудим позднее.

В рассматриваемом элементарном случае легко в явном виде построить и модель минимальной длины, для чего нужно P(r | y) оценить как частоту подкрепления r при условии выполнения действия y.

Структура AIξ в форме (2.1.9) (или (2.1.5) с учетом того, что здесь мы используем суженное пространство моделей) указывает, что мы должны перебирать все возможные модели среды, то есть в данном случае все возможные распределения P(r | y), и для каждой из них перебирать все возможные цепочки действий. Понятно, что для рассматриваемого класса элементарных сред эту схему можно сильно упростить. Однако здесь мы хотим показать, что даже для такого банального случая есть опасность выполнить неправильное упрощение. Вполне может показаться интуитивно очевидным, что при имеющемся распределении P(r | y), полученном по частотной оценке, легко выбрать оптимальное действие, как действие с максимальным математическим ожиданием подкрепления. Однако это неверно. Ведь, с другой стороны, также может показаться очевидным, что постоянное совершение действий с высокой оценкой ожидаемого непосредственного подкрепления будет препятствовать совершению действий, которые еще не были опробованы или которые при первом своем применении привели к плохому результату, что не исключает возможности того, что такие действия обладают очень высоким истинным значением среднего подкрепления. В теории обучения с подкреплением это хорошо известная дилемма исследования/использования (exploration/exploitation). Но в AIξ такая дилемма не возникала. Либо она там решается сама собой (то есть действия, приводящие к высокому подкреплению или к получению новой информации, выбираются оптимальным образом), либо в AIξ что-то упущено.

Попробуем разобрать этот вопрос чуть детальнее. Если у нас есть некоторая история y_{\lt k},r_{\lt k}, то вероятность соответствующей ей модели с распределением P(r | y) будет

formula_77

с точностью до нормирующей константы. Однако даже такая полная модель не описывает предсказания. Нас же интересуют r_{k:m}, а они могут быть любыми особенно с учетом произвольности выбора y_{k:m}. Значит, они также должны быть включены в модель (здесь видно, что использование детерминированных моделей для сред с возрастающей сложностью является несколько искусственным). Из-за этого для каждой цепочки будущих действий удобнее рассматривать все возможные отклики среды и по ним уже строить согласованные с ними модели. Для этого случая используем формулу (2.1.5):

formula_78

Здесь разные q’ определяются разными P(r | y) – конечным множеством вещественных переменных, и разными r_{k:m} – конечным множеством дискретных переменных. Суммирование по q’ распадается на интегрирование по всем переменным P(r | y) и суммирование по всем возможным r_{k:m}:

formula_79

При этом q'_{r}(y_{\leq t})=r_{t}. А чему равна вероятность модели \mu_{k}(q')? Поскольку модель включает в себя коды для всей цепочки r_{1:m} (так как если бы она их не включала, это была бы уже другая модель), кажется естественным считать, что

formula_80

Для простоты будем считать, что у нас есть всего два действия с индексами 1 и 2, а подкрепление может принимать значения только 0 и 1. Тогда регулярная компонента модели задается значениями вероятностей, которые мы обозначим как P01, P11, P02, P22, где первый индекс отвечает за значение r, а второй – за номер действия. При этом P01 = 1 – P11 и P02 = 1 – P22, то есть интеграл будет двойным. Далее можно заметить, что вероятность модели не зависит от порядка действий и подкреплений, поэтому можно различать модели не по r_{1:m}, а только по числу раз, когда некоторое действие сопровождалось определенным подкреплением. Пусть n_{01},n_{11},n_{02},n_{12} – количество соответствующих пар (подкрепление | действие) в истории, а N01, N11, N02, N12 – в будущем; при этом значения N1=N01+N11 и N2=N02+N12 определяются при переборе действий, а при переборе моделей имеются только две свободные переменные, например N01 и N02. Тогда

formula_81

и

formula_82

Множители  C_{N_{1}}^{N_{01}}, C_{N_{2}}^{N_{02}} появляются в связи с тем, что суммирование по r_{k:m} нельзя просто заменить суммированием по N01 и N02, поскольку одной модели, задаваемой через N01 и N02, будет соответствовать разное число моделей, задаваемых через r_{k:m}. Это число и выражается через количество сочетаний. Эти сомножители можно было опустить, что дало бы тоже корректную формулу, но соответствующую немного другому распределению μ(q’), задающему достаточно интересное индуктивное смещение, которое, однако, могло бы вызвать лишние вопросы. Теперь можно поменять порядок интегрирования и суммирования и в явном виде вычислить интегралы вида:

formula_83

Теперь мы можем окончательно получить:

formula_84

Максимизируемое выражение вычисляется в явном виде. Остается только перебрать N1 и N2 при том, что N1+N2=m–k, то есть перебор линеен по глубине предсказания. Еще раз отметим, что для получения математического ожидания подкреплений вероятности надо нормировать.

Посмотрим, какое ожидание подкрепления получится при разных историях и при разных N1, N2. При n_{01}=n_{11}=n_{02}=n_{12}=0 получаем средний ожидаемый выигрыш 0.5 вне зависимости от того, сколько каких действий предполагается выполнить в будущем. Это кажется естественным, но некоторые сомнения могут закрасться уже здесь: хотя у нас нет априорного предпочтения какой-то среде, кажется, что возможность выбора лучших действий должна как-то смещать ожидаемое подкрепление в сторону большего суммарного подкрепления. Далее, при n_{01}=n_{11}\neq 0 и n_{02}=n_{12}=0 (одно из действий дало равное число подкреплений 0 и 1, другое не опробовано) имеем ту же картину, то есть действия оказываются равнозначными. С одной стороны, кажется, что здесь также нет предпочтения в выборе какого-то действия, поскольку текущие частоты подкреплений для них одинаковы. С другой стороны, кажется, что опробование нового (n_{02}=n_{12}=0) действия должно иметь больший потенциал: если действие окажется «плохим», то его можно будет дальше не повторять, и проигрыш будет незначительным; если же оно окажется «хорошим», то его можно будет повторять много раз, получая от этого выигрыш.

Каково будет ожидаемое подкрепление при n_{01}=n_{02},n_{11}=n_{12}, но n_{01}\neq n_{11} (то есть, если судить по истории, действия равнозначны, но частота подкреплений 0 и 1 разная)? Расчеты показывают, что математическое ожидание подкрепления не зависит от соотношения будущих действий N1 и N2, хотя оно при этом отличается от соотношения n_{11}/(n_{01}+n_{11}). В частности, при n_{01}=2,n_{11}=1 математическое ожидание подкрепления в расчете на одно действие оказывается 0.4, а не 1/3. Однако при увеличении длины истории различие это уменьшается. Так, при n_{01}=8,n_{11}=4 матожидание уже 0.357, а при n_{01}=16,n_{11}=8 оно составляет 0.346. На самом деле, это достаточно естественно: ведь, скажем, история с n_{01}=1,n_{11}=0 могла быть порождена с некоторой вероятностью почти любым распределением, а вовсе не только распределением с P01=1, поэтому чистая частотная оценка является смещенной.

В остальном различий нет: если мы возьмем какие-то значения n_{01},n_{11},n_{02},n_{12}, то при N2=0, N1=m–k ожидаемое подкрепление будет определяться той же оценкой P01 по n_{01},n_{11}, а при N1=0, N2=m–k – оценкой P02 по n_{02},n_{12}. К примеру, при n_{01}=2,n_{11}=1,n_{02}=8,n_{12}=4 получим ожидание 0.4 при N2=0 и 0.357 при N1=0, которые плавно переходят друг в друга при других соотношениях N1 и N2. При этом стоит отметить, что при n_{01}=1,n_{11}=2 соответствующая оценка получается также не 2/3, а 0.6, то есть в этом случае она оказывается «заниженной». Иными словами, отличие ожидаемого подкрепления от простой частотной оценки всецело обусловлено смещением оценок вероятностей, а вовсе не общим увеличением подкрепления за счет учета новой информации в процессе последовательного выбора действий.

Можно подумать, что так и должно быть (то есть данные оценки корректны, и никакая стратегия выбора действий не может дать лучшего результата в силу стохастичности среды), либо же, что в самой AIξ что-то не учтено. Однако простое рассмотрение выбора первого действия показывает следующее. Пусть, к примеру, n_{01}=5,n_{11}=5,n_{02}=0,n_{12}=0 и m–k=10. У агента есть возможность выбрать одно из двух действий, и для каждого из них он с равной вероятностью получит один из двух исходов. Но будут ли при этом действия равноценными? Посмотрим, какое ожидание подкрепления будет в каждом случае:

если выбрано первое действие:

formula_85

если выбрано второе действие:

formula_86

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

Усредняя, получаем, что выбор первого действия дает ожидание подкрепления (с учетом подкрепления от выбираемого действия), равное 0.515, а второго – 0.575. Не только выбор второго (не совершавшегося ранее) действия приводит к большему значению ожидаемого подкрепления (то есть действия, направленные на приобретение новой информации, «сами собой» увеличивают ожидаемое подкрепление, что не требует каких-то специальных механизмов), но даже выбор первого действия дает ожидание, превышающее 0.5. И это именно то, чего следовало ожидать! Ведь математическое ожидание максимума из двух случайных величин, равномерно распределенных в диапазоне [0, 1], больше, чем 0.5. И именно этот эффект мы сейчас наблюдаем при рассмотрении выбора текущего лучшего действия.

Так почему же мы получали равные 0.5 значения ожидаемого подкрепления при выборе разных соотношений N1 и N2? Поскольку расчет максимального ожидаемого подкрепления не отличается по своей сути от максимизации подкрепления при выборе текущего действия (max вместо argmax), причина должна быть в том, что было упущено нечто важное. Здесь некорректный переход достаточно очевиден, поскольку он должен нарушать учет получаемой информации при максимизации последующего выбора. В частности, порядок действий здесь должен иметь значение: несмотря на то, что у нашей среды полностью отсутствует память, и в наперед выбранной совокупности действий порядок действий действительно не имеет значения, но при последовательном выборе действий их порядок играет решающее значение для обеспечения индуктивного поведения, то есть поведения, направленного на получение информации.

Таким образом, нельзя было отождествлять \mu_{k}(q') и \mu_{m}(q'), хотя это не слишком прозрачно при рассмотрении детерминированных моделей, поскольку программы, содержание закодированную историю и закодированное предсказание будущего формально являются разными. Это приводит к некорректному разделению задач предсказания и выбора оптимальных действий, из-за чего в последствии и возникает возможность замены перебора по r_{k:m} перебором по  N1 и N2. На самом деле, и в AIξ, заданной в форме уравнения (20) из [Hutter, 2007], не производится учета гипотетического изменения распределения μ или ξ при получении новой информации. Более аккуратное воплощение модели AIξ в указанной форме также показывает, что она не реализует индуктивного поведения. В равной мере нельзя использовать ни \mu_{m}(q'), ни \mu_{k}(q'), а нужно для каждого варианта прогнозируемой истории на момент t использовать собственное уточненное распределение \mu_{t}(q').

Для получения правильного эффекта индуктивного поведения удобнее использовать рекурсивную форму AIξ (точнее, AIμ), в которой шаги максимизации при выборе одного действия и суммирования по разным возможным откликам среды в явном виде чередуются. У Хаттера [Hutter, 2007] формула (22) имеет вид, аналогичный следующему уравнению:

formula_87

где вероятности P могут вычисляться через универсальное распределение ξ или какое-то конкретное распределение μ в зависимости от постановки задачи.

Стоит отметить, что разные формы AIξ в [Hutter, 2007], а, именно, (20) и (22), вряд ли могут быть эквиваленты. Последняя форма предпочтительнее, поскольку она учитывает возможные разные отклики среды в зависимости от совершаемых действий, но она также не содержит в явном виде учета уточнения распределения вероятностей. Мы предлагаем следующую форму, которая представляется наиболее корректной:

formula_88

где P_{t}=P(x_{t}|x_{\lt t},y_{1:t}). Стоит отметить, что это должны быть нормированные распределения; игнорирование нормировки (как это делается в AIξ из-за использования только P_{k}) недопустимо в силу того, что нормировка оказывается разной в зависимости от рассматриваемого варианта будущего взаимодействия агента и среды.

С учетом нормировки P_{t} можно все r_{t} и P_{t} собрать внутри последней суммы и переписать формулу (2.2.3) в виде

formula_89

который наиболее близок к AIξ в упомянутой форме (22). Если бы все P_{t} зависели от всех последующих действий, то из свойств условной вероятности выполнялось бы соотношение P_{k}...P_{m}=P(x_{k:m}|x_{\lt k},y_{\leq m}) , и уравнение (2.2.4) было бы в точности эквивалентно уравнению (22) из [Hutter, 2007]. Но важная тонкость заключается в том, что P_{t}=P(x_{t}|x_{\lt t},y_{1:t}) зависит только от совершенных к моменту t действий, а не всех действий до момента m (то есть действия выбираются не априорно, а после получения новой информации), поэтому P_{k}...P_{m}=P(x_{k:m}|x_{\lt k},y_{\leq m}) , и (2.2.3) обладает свойствами, отсутствующими в AIξ.

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

Можно задаться вопросом, не получится ли, наоборот, что агент всегда будет пытаться опробовать незнакомые действия? Такое поведение тоже выглядело бы нерациональным (не случайно у людей есть такие пословицы, как «от добра добра не ищут» или «лучше синица в руках, чем журавль в небе»). Для «бессмертного» агента, возможно, так и будет: если «плохое» действие всегда имеет только локальный эффект, а «хорошее» действие можно эксплуатировать неограниченно, то проверка нового будет всегда оправданной. Однако уже в случае простых Марковских сред вполне могут существовать действия, приводящие к «безвыходным положениям» (совокупности состояний среды, имеющих вероятные переходы только друг между другом, но не другими состояниями) с низким значением целевой функции. Стремление избежать таких ситуаций в условиях априорной неопределенности должно ограничивать «любопытство». Как именно агент будет себя вести в конкретных ситуациях, существенно зависит от целевой функции. Но можно надеяться, что в рамках некоторой заданной целевой функции ИМИ-агент будет оптимально разрешать дилемму исследования/использования.

Как видно, упрощение ИМИ может приводить к существенно отрицательным последствиям. Это, однако, не означает, что такое упрощение в принципе невозможно. В частности, в нашем примере индуктивное поведение могло быть достигнуто и при использовании одной модели, но представление которой было бы расширено понятием неопределенности. Так, по истории n_{01},n_{11},n_{02},n_{12} можно было бы восстанавливать одну частотную модель, но дополненную информацией о неопределенности, которая тем выше, чем меньше соответствующие значения n_{01}+n_{11},n_{02}+n_{12}. Совершение каждого действия приводит к модификации этой модели как в плане P(r | y), так и в плане неопределенностей. Для данного случая несложно разработать частный способ учета неопределенности модели, который заменил бы интегрирование по всем моделям. Однако в общем случае для алгоритмически полного пространства моделей данная задача нетривиальна, и мы к ней вернемся позднее.

Выводы

Модели ИМИ достаточно легко сделать вычислимыми и в определенной степени учитывающими ресурсные ограничения. Однако в лучшем случае они оказываются оптимальными по времени выполнения с точностью до мультипликативной замедляющей константы, пропорциональной  2^{-L}, где L – длина «истинной» модели среды. Помимо того, что значение L может быть большим даже для отдельных частных задач, для стохастической среды оно вообще не ограничено, в связи с чем требуется модификация моделей ИМИ. Мультипликативный замедляющий фактор может быть превращен в аддитивный, который, однако, помимо того, что является еще более значительным, также действует в каждый момент времени.

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

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

Литература

(Goertzel, 2010) Goertzel B. Toward a Formal Characterization of Real-World General Intelligence // In: E.Baum, M.Hutter, E.Kitzelmann (Eds), Advances in Intelligent Systems Research. 2010. Vol. 10 (Proc. 3rd Conf. on Artificial General Intelligence, AGI 2010, Lugano, Switzerland, March 5-8, 2010.). P. 19–24.

(Hall, 2008) Hall S. VARIAC: an Autogenous Cognitive Architecture // In: Frontiers in Artificial Intelligence and Applications (Proc. 1st AGI Conference). 2008. V. 171. P. 176–187.

(Hibbard, 2009) Hibbard B. Bias and No Free Lunch in Formal Measures of Intelligence // Journal of Artificial General Intelligence. 2009. V. 1. P. 54–61.

(Hutter, 2005) Hutter M. Universal Artificial Intelligence. Sequential Decisions Based on Algorithmic Probability / Springer. 2005. 278 p.

(Hutter, 2007) Hutter M. Universal Algorithmic Intelligence: A Mathematical Top→Down Approach // in Artificial General Intelligence. Cognitive Technologies, B. Goertzel and C. Pennachin (Eds.). Springer. 2007. P. 227–290.

(Looks, 2009) Looks M., Goertzel B. Program Representation for General Intelligence // B. Goertzel, P. Hitzler, M. Hutter (Eds), Advances in Intelligent Systems Research. V. 8 (Proc. 2nd Conf. on Artificial General Intelligence, AGI 2009, Arlington, Virginia, USA, March 6-9, 2009). P. 114–119.

(Pankov, 2008) Pankov S. A Computational Approximation to the AIXI Model // Frontiers in Artificial Intelligence and Applications (Proc. 1st AGI Conference). 2008. V. 171. P. 256–267.

(Schmidhuber, 2007a) Schmidhuber J. The New AI: General & Sound & Relevant for Physics // in Artificial General Intelligence. Cognitive Technologies, B. Goertzel and C. Pennachin (Eds.). Springer. 2007. P. 175–198.

(Schmidhuber, 2007b) Schmidhuber J. Gödel Machines: Fully Self-Referential Optimal Universal Self-improvers // In: Artificial General Intelligence. Cognitive Technologies, B. Goertzel and C. Pennachin (Eds.). Springer. 2007. P. 199–226.

(Solomonoff, 1986) Solomonoff R. The Application of Algorithmic Probability to Problems in Artificial Intelligence // In: L.N. Kanal and J.F. Lemmer (Eds.). Uncertainty in Artificial Intelligence: Elsevier Science Publishers. 1986. P. 473–491.

(Solomonoff, 2003) Solomonoff R. Progress in Incremental Machine Learning // Technical Report IDSIA-16-03, IDSIA. 2003.

(Solomonoff, 2010) Solomonoff R. Algorithmic Probability, Heuristic Programming and AGI // In: E.Baum, M.Hutter, E.Kitzelmann (Eds), Advances in Intelligent Systems Research. 2010. V. 10 (Proc. 3rd Conf. on Artificial General Intelligence, Lugano, Switzerland, March 5-8, 2010). P. 151–

(Wang, 2007) Wang P. The Logic of Intelligence. In: Artificial General Intelligence // In: Cognitive Technologies, B. Goertzel and C. Pennachin (Eds.). Springer, 2007. P. 31–62.

(Левин, 1973) Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9. № 3. С. 115–116.