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

Пусть ${\displaystyle U}$ — префиксная универсальная машина Тьюринга, то есть множество её корректных программ является префиксным кодом, и ни одна программа не является началом другой. Это свойство гарантирует, что машина может однозначно определить, где заканчивается одна программа и начинается другая, без необходимости использования специальных разделителей или знания длины программы заранее.

Для конечной двоичной строки ${\displaystyle x}$ алгоритмическая вероятность, также называемая универсальной априорной вероятностью или распределением Соломонова — Левина, определяется как сумма вероятностей всех программ, которые выводят строку, начинающуюся с ${\displaystyle x}$^[2]:

${\displaystyle m(x)=\sum _{p:U(p)=x*}2^{-|p|}}$,

где запись ${\displaystyle U(p)=x*}$ означает, что выход программы ${\displaystyle p}$ начинается с ${\displaystyle x}$, а ${\displaystyle |p|}$ — длина программы в битах. Вероятность ${\displaystyle 2^{-|p|}}$ соответствует вероятности того, что на вход универсальной машины будет подана именно программа ${\displaystyle p}$, если каждый её бит выбирается независимо и равновероятно (как при подбрасывании правильной монеты).

Если рассматривать только программы, выход которых в точности равен ${\displaystyle x}$, получают вариант ${\displaystyle m(x)=\sum _{p:U(p)=x}2^{-|p|}}$. Эта величина называется точечной алгоритмической вероятностью.

Поскольку множество префиксных программ удовлетворяет неравенству Крафта, сумма не превосходит единицы, поэтому ${\displaystyle m}$ является полумерой, то есть ${\displaystyle \sum _{x}m(x)\leq 1}$. Алгоритмическая вероятность не является вычислимой функцией, однако она нижнеполувычислима: существует вычислимая процедура, которая монотонно приближает её значение снизу по мере запуска всех возможных программ параллельно^[3].

Алгоритмическая вероятность обладает рядом замечательных свойств, делающих её универсальным инструментом в теории информации и машинном обучении:

• доминирование. Для любой нижнеполувычислимой полумеры ${\displaystyle P}$ существует константа ${\displaystyle c_{P}>0}$, зависящая только от ${\displaystyle P}$, такая что для всех ${\displaystyle x}$ выполняется ${\displaystyle m(x)\geq c_{P}\cdot P(x)}$. В этом смысле ${\displaystyle m}$ мажорирует с точностью до мультипликативной константы любую эффективно перечислимую вероятностную модель, что делает её оптимальным априорным распределением^[4];
• инвариантность. Смена базовой универсальной машины Тьюринга меняет значение ${\displaystyle m(x)}$ не более чем в константу раз, что напрямую следует из теоремы о существовании компилятора между любыми двумя универсальными машинами. Это означает, что алгоритмическая вероятность не зависит от конкретного выбора языка программирования или архитектуры компьютера с точностью до аддитивной константы в логарифмической шкале;
• связь с предсказанием. Условная вероятность ${\displaystyle m(x_{n+1}|x_{1}...x_{n})=m(x_{1}...x_{n+1})/m(x_{1}...x_{n})}$ может использоваться для предсказания продолжения последовательности. Если истинные данные порождены любой вычислимой мерой, то ошибка такого предсказания быстро убывает, и сумма ожидаемых квадратичных отклонений конечна. Это свойство делает алгоритмическую вероятность теоретически оптимальным методом предсказания;
• субаддитивность. Для конкатенации строк выполняется неравенство ${\displaystyle m(xy)\leq m(x)\cdot m(y)}$, что отражает тот факт, что программа, выводящая ${\displaystyle xy}$, может быть построена как композиция программ для ${\displaystyle x}$ и ${\displaystyle y}$.

Таким образом, этот формализм элегантно объединяет в себе понятия случайности, сжатия данных и индуктивного предсказания в рамках единой математической структуры.

Центральным результатом теории является теорема о кодировании, доказанная Л. А. Левиным и независимо Г. Хайтиным^[5]. Она устанавливает жёсткую связь между алгоритмической вероятностью и префиксной колмогоровской сложностью ${\displaystyle K(x)}$, определяемой как длина кратчайшей программы, выводящей ${\displaystyle x}$:

${\displaystyle m(x)=\Theta (2^{-K(x)})}$,

что эквивалентно записи ${\displaystyle -\log _{2}m(x)=K(x)+O(1)}$. Иными словами, наиболее весомый вклад в ${\displaystyle m(x)}$ даёт кратчайшая программа для ${\displaystyle x}$, а вклады более длинных программ экспоненциально убывают. Эта связь придаёт строгий математический смысл принципу простоты: объект тем вероятнее, чем короче его минимальное описание.

Алгоритмическая вероятность обобщает классическое понятие энтропии Шеннона из теории информации. Если для дискретного источника с распределением вероятностей ${\displaystyle P}$ энтропия определяется как ${\displaystyle H(P)=-\sum _{x}P(x)\log _{2}P(x)}$, то алгоритмическая энтропия строки ${\displaystyle x}$ определяется как ${\displaystyle -\log _{2}m(x)}$.

Ключевое различие заключается в том, что энтропия Шеннона характеризует среднюю неопределённость источника в целом, тогда как алгоритмическая вероятность задаёт конкретную вероятность каждому отдельному объекту, не требуя знания распределения. Более того, для любого вычислимого распределения ${\displaystyle P}$ выполняется неравенство ${\displaystyle -\log _{2}m(x)\leq -\log _{2}P(x)+O(1)}$, что означает, что алгоритмическая сложность (информация) не превосходит шенноновской информации (самоинформации) с точностью до константы.

Это соотношение показывает, что алгоритмическая вероятность является универсальным расширением классической теории информации на случай, когда распределение вероятностей неизвестно или невычислимо.

Важным понятием, тесно связанным с алгоритмической вероятностью, является число Омега Чейтина ${\displaystyle \Omega }$, определяемое как вероятность того, что универсальная машина Тьюринга остановится на случайной программе^[6]:

${\displaystyle \Omega =\sum _{p:U(p){\text{ останавливается}}}2^{-|p|}}$.

Число ${\displaystyle \Omega }$ является алгоритмически случайным, то есть его биты не могут быть сжаты или предсказаны никакой программой короче самой последовательности. Более того, знание первых ${\displaystyle n}$ бит числа ${\displaystyle \Omega }$ позволяет решить проблему остановки для всех программ длины не более ${\displaystyle n}$, что делает ${\displaystyle \Omega }$ максимально невычислимой величиной в определённом смысле.

Число Омега демонстрирует фундаментальную связь между алгоритмической вероятностью, случайностью и пределами вычислимости. Оно показывает, что существуют математические факты, которые истинны, но не могут быть доказаны в рамках любой формальной аксиоматической системы достаточной мощности, что является вариантом теоремы Гёделя о неполноте.

Алгоритмическая вероятность принципиально невычислима: не существует алгоритма, который мог бы точно вычислить ${\displaystyle m(x)}$ для произвольной строки ${\displaystyle x}$ за конечное время. Это следует из проблемы остановки, поскольку для вычисления ${\displaystyle m(x)}$ необходимо знать, какие программы остановятся и выведут строку, начинающуюся с ${\displaystyle x}$.

Однако ${\displaystyle m(x)}$ является нижнеполувычислимой, что означает существование алгоритма, который монотонно приближает её значение снизу. Такой алгоритм может параллельно запускать все возможные программы и по мере их остановки добавлять их вклад ${\displaystyle 2^{-|p|}}$ к текущей оценке ${\displaystyle m(x)}$.

На практике для аппроксимации алгоритмической вероятности используются различные эвристики:

• методы сжатия данных. Универсальные алгоритмы сжатия, такие как LZ77, LZMA и PPM, могут использоваться для оценки колмогоровской сложности, а через неё — и алгоритмической вероятности. Идея заключается в том, что длина сжатого файла приближает длину кратчайшей программы, генерирующей его содержимое;
• поиск Левина. Этот метод использует универсальный поиск с распределением времени пропорционально ${\displaystyle 2^{-|p|}}$, что позволяет эффективно находить кратчайшие программы для заданных строк;
• байесовские методы. На практике алгоритмическую вероятность часто аппроксимируют смесью конкретных параметрических моделей, взвешенных по их априорной вероятности, что реализует идею индукции Соломонова в ограниченной форме.

Эти аппроксимации находят применение в задачах машинного обучения, сжатия данных и распознавания образов.

Распределение ${\displaystyle m}$ часто называют универсальным априорным распределением, поскольку оно может использоваться в качестве априорного распределения в формуле Байеса без задания конкретной модели предметной области. Если истинная порождающая мера ${\displaystyle \mu }$ является вычислимой, то байесовская смесь по ${\displaystyle m}$ будет быстро сходиться к ${\displaystyle \mu }$ в смысле ожидаемой квадратичной ошибки предсказания.

Формально, для любой вычислимой меры ${\displaystyle \mu }$ суммарная ожидаемая ошибка предсказания по ${\displaystyle m}$ ограничена колмогоровской сложностью самой ${\displaystyle \mu }$ с точностью до константы^[7]:

${\displaystyle \sum _{n=1}^{\infty }\sum _{x_{1}...x_{n}}\mu (x_{1}...x_{n})(m(x_{n+1}|x_{1}...x_{n})-\mu (x_{n+1}|x_{1}...x_{n}))^{2}\leq K(\mu )+O(1)}$.

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

Важным уточнением является различие между ${\displaystyle m(x)}$ и априорной вероятностью ${\displaystyle M(x)=\sum _{p:U(p)=x*}2^{-|p|}}$, где суммирование идёт по программам, выход которых начинается с ${\displaystyle x}$. Именно ${\displaystyle M}$ обладает свойством универсальности для предсказания и называется универсальной полумерой Соломонова. Она удовлетворяет неравенству ${\displaystyle M(xy)\leq M(x)}$ и может быть нормализована для получения полноценного распределения вероятностей.

На основе алгоритмической вероятности Рэй Соломонов построил теорию универсального индуктивного вывода. Пусть наблюдается последовательность данных ${\displaystyle x_{1},x_{2},...,x_{n}}$. Предсказание следующего символа ${\displaystyle x_{n+1}}$ даётся условным распределением ${\displaystyle M(x_{n+1}|x_{1}...x_{n})}$.

Этот метод рассматривает все вычислимые гипотезы, совместимые с данными, и взвешивает их пропорционально ${\displaystyle 2^{-K({\text{гипотезы}})}}$. Тем самым реализуются сразу два философских принципа: принцип Оккама, отдающий предпочтение более простым гипотезам, и принцип множественности объяснений Эпикура, требующий сохранять все гипотезы, совместимые с наблюдениями.

Индукция Соломонова является несмещённой в том смысле, что она не исключает априори ни одной вычислимой закономерности. Маркус Хуттер показал, что на её основе можно построить оптимальный в теоретическом смысле агент — модель AIXI, которая максимизирует ожидаемое вознаграждение в любой вычислимой среде, используя ${\displaystyle M}$ в качестве априорного распределения^[8].

Хотя ${\displaystyle M}$ невычислима, её можно аппроксимировать снизу с любой заданной точностью при наличии достаточных вычислительных ресурсов, что делает теорию важным теоретическим идеалом, к которому стремятся практические алгоритмы сжатия и предсказания.

Алгоритмическая вероятность (определяемая через универсальную априорную вероятность Соломонова — Левинова) служит теоретическим фундаментом для ряда направлений информатики и искусственного интеллекта, связывая теорию информации А. Н. Колмогорова, теорию вероятностей и теорию вычислимости в единую концептуальную рамку^[9]. В машинном обучении эта связь реализуется через принципы индуктивного вывода, которые формализуют идею бритвы Оккама в строгом математическом виде: среди всех гипотез, согласованных с наблюдаемыми данными, следует предпочитать наиболее простые.