Простейшая модель с ограничением ресурсов

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

Р. Соломонов указал [Solomonoff, 1986], что большим шагом вперед по использованию алгоритмической вероятности при решении практических проблем является процедура поиска, предложенная Л.А. Левиным (учеником А.Н. Колмогорова) [Левин, 1973] и сейчас называемая LSearch, которая позволяет получать решение любой P или NP проблемы за время, пропорциональное оптимальному времени, умноженному на константный сомножитель.

Общая идея этой процедуры заключается в том, чтобы выделять на проверку каждой алгоритмической модели q время, пропорциональное ее априорной вероятности\xi(q)= 2^{-l(q)}. При фиксированных ресурсах можно заранее рассчитать, сколько тактов процессорного времени выделить на выполнение той или иной модели (алгоритма). Если же решение ищется до достижения какого-то удовлетворительного качества, то модели могут выполняться параллельно с приоритетами ξ(q) (или в случае последовательного исполнения на каждом такте с вероятностью ξ(q) выбирается модель q для продолжения вычислений).

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

Тонкий вопрос, однако, заключается в том, учитывать ли в предсказании результаты, сформированные алгоритмами, которые не успели остановиться. Случай предсказания особый: от предсказываемых естественных процессов мы вполне может ожидать безостановочности, которая, однако, связана не с постоянной модификацией «истории», а с формированием «будущего». При этом, скажем, алгоритм, который выводит бесконечную последовательность 010101… будет проще алгоритма, который выводит эту же последовательность, но некоторого фиксированного размера. В этом смысле требование от q вывода истории x<k и останавливаться (что делается в AIξ) может быть не вполне естественным. Данная тонкость на текущем уровне детальности моделей универсального интеллекта принципиальной роли не играет.

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

Очевидно, процедура LSearch при ограниченном времени успеет выполнить только более короткие и более быстрые алгоритмы. Несколько обобщая, можно ввести следующее распределение ξtl на множестве программ, ограниченных по длине и времени выполнения:

formula_73

Как и раньше, сами алгоритмические вероятности введем как

formula_74

Следует иметь в виду, что распределение, записанное в таком виде, не является нормированным. Нормировку выполнить несложно, но без этого также можно и обойтись. Также отметим, что интересующие нас условные вероятности легко ввести по аналогии с P_{ALP}(x'|x), что даст некий аналог формулы (42) в [Hutter, 2007].

Очевидно,

formula_75

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

Это распределение может напрямую использоваться для модификации моделей типа AIξ при поиске моделей среды. Совместное увеличение значений t и l может проводиться так же, как в LSearch, чтобы в момент T каждая программа q выполнилась на 2^{-l(q)}T шагов; в момент T успеют выполниться те программы, для которых  2^{-l(q)}T\gt t(q), то есть программы окажутся отсортированными по величине  2^{l(q)}t(q). При этом первая модель q, которая воспроизводит историю взаимодействия агента со средой и выполняет предсказание, будет обладать наименьшим значением  2^{l(q)}t(q), логарифм от которой можно назвать сложностью по Левину (такое определение сложности имеет глубокий смысл, который требует отдельного обсуждения).

После нахождения модели с минимальной сложностью перебор может не прекращаться до исчерпания вычислительных ресурсов, поскольку универсальное предсказание в моделях ИМИ подразумевает использование многих моделей, совместимых с историей. Однако и при использовании единственной лучшей модели время вычисления может оказаться O( 2^{L}T), где L и T – соответствующие характеристики минимальной модели. Как видно, такая схема вычислений (аналогичная LSearch) имеет замедляющий множитель 2^L, связанный с тем, что до обнаружения этой модели придется выполнить порядка 2^L программ и потратить на каждую из них до T тактов времени. Кроме того, для универсального агента необходимо выполнять предсказание для разных цепочек своих действий (здесь возникает соблазн разделить задачи предсказания и выбора действий, но, как мы покажем, наивное их разделение нарушает универсальность агента).

В любом случае мультипликативная замедляющая константа 2^L является гигантской. И, кроме того, в случае реального мира величина L (длина «истинной» модели среды) может быть неограниченной сверху. Как результат, сложность поиска минимальной детерминированной модели среды будет экспоненциально возрастать с увеличением длины истории. А в случае ограниченных ресурсов это сделает недостижимой сходимость поведения агента, основанного на распределении \xi ^{tl}, к поведению агента, использующего некое «правильное» априорное распределение μ (поскольку сходимость в случае ξ как раз и возникала при увеличении объема наблюдательных данных, когда этот объем начинает превосходить сложность источника данных).

М. Хаттером вводится модель AI\xi ^{tl} [Hutter, 2005]. Интересно, однако, то, что в ней не просто используется \xi ^{tl} вместо ξ, но и предлагается метод поиска, оптимальный по времени выполнения с точностью до аддитивной, а не мультипликативной константы. Основная идея этого метода заключается в том, чтобы перебирать не все, а только те алгоритмы, для которых доказано, что предсказываемые ими значения целевой функции не являются завышенными. При этом перебираются не модели среды, а программы самого агента, которые, правда, выводят не только действия, но и значения подкрепления (присутствующие в истории и ожидаемые). Доказательства генерируются в некоторой формальной системе отдельным алгоритмом, работающим параллельно с процедурами исполнения моделей.

Некоторое сомнение вызывает возможность строгого конструктивного доказательства требуемого свойства для программ рационального поведения без перебора прочих программ. В этом смысле выглядящая привлекательной замена мультипликативной замедляющей константы на аддитивную на практике может оказаться неэффективной. В любом случае, это дополнительное время, требуемое на поиск доказательств, является слишком большим, чтобы реальный ИИ мог действовать в соответствии с этим подходом. Поскольку в будущем мы не будем использовать саму модель AI\xi ^{tl}, здесь не приводятся детальные разъяснения на ее счет, за которыми лучше обратиться к первоисточнику.