Алгоритмическая вероятность

Алгоритмическая вероятность является основным элементом теории индуктивного вывода Соломонова — теории предсказания на основе наблюдений, изначально разработанной с целью применения в машинном обучении: по заданной последовательности символов определить, какой появится следующим. Теория Соломонова даёт оптимальный (в определённом смысле) ответ на эту задачу, хотя его невозможно реализовать на практике.

Четыре главные идеи, вдохновившие Соломонова при создании алгоритмической вероятности: бритва Оккама, принцип множества объяснений Эпикура (англ. Epicurus' principle of multiple explanations), современная теория вычислений (например, использование универсальной машины Тьюринга) и правило Байеса для предсказаний^[5].

Принципы бритвы Оккама и Эпикура представляют собой различные нематематические аппроксимации универсального априорного распределения.

• Бритва Оккама: «среди теорий, согласующихся с наблюдаемыми явлениями, следует выбирать самую простую»^[6].
• Принцип множества объяснений Эпикура: «если существует несколько теорий, согласующихся с наблюдениями, сохранять все такие теории»^[7].

В основе универсального априорного распределения лежит абстрактная вычислительная модель, такая как универсальная машина Тьюринга^[8]. В качестве такой модели может выступать любая абстрактная ЭВМ, если она тьюринг-полна, то есть любая вычислимая функция реализуема на ней в виде хотя бы одной программы.

Абстрактная машина используется для определения смысла выражения «простое объяснение». В формализме программы рассматриваются как объяснения или теории явлений, которые, будучи запущены на абстрактной ЭВМ, порождают наблюдаемые строки. Каждая программа получает вес, зависящий от её длины. Универсальное вероятностное распределение определяется как распределение по всем выходным строкам для случайного входа, при этом каждой конечной подстроке q сопоставляется сумма вероятностей программ, выводящих что-либо, начинающееся с q^[9]. Таким образом, простое объяснение — короткая программа; сложное объяснение — длинная программа. Программы меньшей длины (простые объяснения) встречаются с большей вероятностью; соответственно, строка наблюдений с высокой вероятностью — та, которую может сгенерировать короткая программа, или множество немного более длинных программ. Вероятность низка у тех наблюдаемых строк, которые требуют длинных программ.

Алгоритмическая вероятность тесно связана с сложностью Колмогорова. Колмогоров вводил понятие сложности с позиций теории информации и задач случайности, а Соломонов — с позиции индуктивного вывода. Универсальное априорное распределение, которое подставляется вместо каждого реального априорного в формулу Байеса, предложил Соломонов, а сложность Колмогорова стала побочным продуктом этого подхода. Это распределение даёт предсказание наиболее вероятного продолжения наблюдений и количественную оценку вероятности такого продолжения.

Полумера Соломонова универсальна в мощном смысле, однако время вычисления может быть бесконечным. Одна из стратегий решения этой проблемы — вариант поискового алгоритма Леонида Левина^[10], при котором время вычислений для программ ограничивается и более короткие программы получают больше времени. При увеличении времени работы постепенно строится последовательность приближений, сходящихся к универсальному распределению вероятностей. Другой способ — ограничение пространства поиска за счёт дополнительных обучающих последовательностей.

Соломонов доказал, что это распределение машинно-инвариантно с точностью до константы (теорема об инвариантности сложности Колмогорова)^[11].

Теорема Колмогорова об инвариантности утверждает, что сложность Колмогорова (или минимальная длина описания) данных инвариантна относительно выбора тьюринг-полного языка, моделирующего универсальную машину Тьюринга:

${\displaystyle \forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)}$

где ${\displaystyle K_{U}(x)=\min _{p}\{|p|:U(p)=x\}}$.

Минимальное описание p, такое что {{{1}}}, выступает естественным образом представления строки x относительно тьюринг-полного языка U. Более того, если x невозможно дополнительно сжать, p — нестягиваемая и потому невычислимая строка. Это соответствует представлению учёных о случайности и объясняет невычислимость сложности Колмогорова.

Любые данные имеют необходимое и достаточное представление в виде случайной строки.

Следующее приведено по ^[12]:

Из теории компиляторов известно, что для любых двух тьюринг-полных языков U₁ и U₂ существует компилятор Λ₁, реализованный на U₁, переводящий программы с языка U₂ в функционально эквивалентные программы на U₁.

Если p — кратчайшая программа, печатающая строку x, тогда:

${\displaystyle K_{U_{1}}(x)\leq |\Lambda _{1}|+|p|\leq K_{U_{2}}(x)+{\mathcal {O}}(1)}$

где , а по симметрии получаем обратное неравенство.

Любое однозначно декодируемое кодирование удовлетворяет неравенству Крафта-Макмиллана; благодаря префиксной сложности Колмогорова выводится универсальное распределение:

${\displaystyle P(x)=\sum _{U(p)=x}P(U(p)=x)=\sum _{U(p)=x}2^{-K_{U}(p)}\leq 1}$

причём тот факт, что U может моделировать универсальную машину Тьюринга с префиксным (префикс-свободным) кодом, гарантирует: для двух различных описаний p и p', p не является подстрокой p', и наоборот.

В вычислимой Вселенной, при заданном феномене с кодировкой x \in \{0,1\}^*, сгенерированной физическим процессом, вероятность такого явления однозначно определена и равна сумме вероятностей отдельных и независимых причин. Признак префиксности обеспечивает причинную независимость.

Это непосредственное следствие неравенства Крафта—Макмиллана.

Оно утверждает, что для набора строк {{{1}}}, существует префиксный код с кодовыми словами {{{1}}}, где для всех i длина слова равна k_i, тогда и только тогда, когда

${\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}$

где s — размер алфавита S.

Без ограничения общности можно упорядочить k_i так, что

${\displaystyle k_{1}\leq k_{2}\leq ...\leq k_{n}}$

Префиксный код существует тогда и только тогда, когда на каждом шаге j есть хотя бы одно кодовое слово, не содержащее ни одно из предыдущих j-1 как префикс. В силу наличия кодового слова \sigma_i на предыдущем шаге i<j, запрещены s^{k_j-k_i} кодовых слов, имеющих \sigma_i в качестве префикса. Следовательно, в общем случае префиксный код существует тогда и только тогда, когда

${\displaystyle \forall j\geq 2,s^{k_{j}}>\sum _{i=1}^{j-1}s^{k_{j}-k_{i}}}$

Разделив обе части на s^{k_j}, получаем

${\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}$

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

Рэй Соломонов изобрёл концепцию алгоритмической вероятности вместе с соответствующей теоремой об инвариантности около 1960 года^[13], опубликовав по этой теме доклад: «A Preliminary Report on a General Theory of Inductive Inference»^[2]. Он подробнее развил свои идеи в 1964 году в работах «A Formal Theory of Inductive Inference», части I^[14] и II^[15].

Последовательные решения на основе алгоритмической вероятности — теоретическая концепция, предложенная Маркусом Хуттером (англ. Marcus Hutter) для объединения алгоритмической вероятности с теорией принятия решений. Эта система служит основой для построения универсальных интеллектуальных агентов, способных к оптимальному поведению в любой вычислимой среде. Она базируется на теории индукции Соломонова и включает элементы обучения с подкреплением, оптимизации и последовательного (пошагового) выбора^[16].

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

Модель AIXI — центральная часть теории Хуттера. Она описывает универсального искусственного агента, максимизирующего ожидаемое вознаграждение в неизвестной среде. AIXI предполагает, что среда описывается вычислимым вероятностным распределением и использует прошлые наблюдения для индуктивного вывода максимально вероятной модели среды, опираясь на алгоритмическую вероятность. Математически агент перебирает все возможные последовательности действий и наблюдений в будущем, вычисляет их алгоритмические вероятности и ожидаемые полезности, выбирая такую последовательность действий, что максимизирует суммарную награду. Такой подход сводит задачу последовательного выбора к оптимизации. Однако в общем виде модель AIXI невычислима и не может быть непосредственно реализована на практике.

AIXI универсально оптимальна в том смысле, что не хуже любого другого агента во всех вычислимых средах. Благодаря этому модель служит теоретическим «эталоном интеллекта». Но базирование на алгоритмической вероятности делает AIXI вычислительно чрезмерно сложной, требуя экспоненциальных затрат для перебора всех вариантов. Для устранения этого недостатка Хуттер предложил приближённые варианты с ограничением времени, такие как AIXItl, что позволяет снизить вычислительную нагрузку, сохраняя многие теоретические достоинства исходной модели. Эти приближения обеспечивают компромисс между вычислимостью и теоретической оптимальностью.

Фреймворк AIXI имеет важные последствия для искусственного интеллекта и смежных областей. Он задаёт строгий формальный критерий интеллекта и теоретическую основу для решения задач предсказания, обучения с подкреплением и оптимизации. Тем не менее, у подхода есть ограничения: модель предполагает вычислимость среды (тем самым исключая хаотические и невычислимые системы) и предъявляет чрезмерные вычислительные требования, что затрудняет реализацию в реальных задачах.

Теория Хуттера затрагивает философские вопросы природы интеллекта и вычислений. Опора на алгоритмическую вероятность связывает интеллект с вычислимостью и предсказуемостью, что может исключить из рассмотрения некоторые природные или хаотические явления. Несмотря на это, модель AIXI указывает верхние границы возможного поведения интеллектуальных систем и служит этапом на пути к практическому искусственному интеллекту.

• Рэй Соломонов
• Андрей Колмогоров
• Леонид Левин