Колмогоровская сложность

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

Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

Выражает возможность фрактального описания.

К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

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

Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.

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

Определение

Чтобы определить колмогоровскую сложность, мы должны сначала задать язык описания строк. Такой язык описания может быть основан на любом языке программирования, таком как Lisp, Pascal или Java. Если $P$ — программа, выходом которой является строка $x$, то $P$ — описание $x$. Длиной описания является длина $P$ как строки. В ходе определения длины $P$ должны быть вычислены дли́ны подпрограмм, использующихся в $P$. Длина любой целой константы $n$, которая появляется в $P$ — это количество битов, требующихся для представления $n$, равное (грубо) $\log _{2}n$.

Мы можем альтернативно выбрать кодировку для машины Тьюринга, где кодировка — функция, устанавливающая в соответствие каждой машине Тьюринга $M$ битовую строку $\langle M\rangle$. Если $M$ — машина Тьюринга, которая на вход $w$ даёт на выходе строку $x$, то объединённая строка $\langle M\rangle w$ есть описание для $x$. Это теоретический подход, который является более подходящим для построения детальных формальных доказательств и предпочтителен в исследовательской литературе. Двоичное лямбда-исчисление может дать наиболее простое определение сложности. В этой статье мы используем неформальный подход.

Любая строка $s$ имеет как минимум одно описание, то есть программу

  function GenerateFixedString()
    return s

Если описание $s$, $d(s)$ минимальной длины, то есть использует наименьшее количество символов, то оно называется минимальным описанием $s$, а длина $d(s)$, то есть количество символов в этом описании, — колмогоровской сложностью $s$, $K(s)$. Символьно:

$K(s)=|d(s)|.$

Рассмотрим, как выбор языка описания влияет на значение $K$, и покажем, что эффект от смены языка описания является ограниченным.

Теорема. Если $K_{1}$ и $K_{2}$ — функции сложности, относящиеся к языкам описания $L_{1}$ и $L_{2}$, то существует константа $c$ (зависящая только от языков $L_{1}$ и $L_{2}$), такая, что

$\forall s|K_{1}(s)-K_{2}(s)|\leqslant c.$

Доказательство. Обратно, достаточно доказать, что существует некоторая константа $c$, такая, что для всех битовых строк $s$

$K_{1}(s)\leqslant K_{2}(s)+c.$

Положим, что существует программа на языке $L_{1}$, которая работает как интерпретатор для $L_{2}$:

  function InterpretLanguage(string p)

где $p$ — программа на языке $L_{2}$. Интерпретатор характеризуется следующим свойством:

Возвращаемым значением в результате работы InterpretLanguage на входных данных $p$ будет результат работы $p$.

Таким образом, если $P$ является программой на языке $L_{2}$, которая является минимальным описанием $s$, то InterpretLanguage($P$) возвращает строку $s$. Длина этого описания $s$ есть сумма:

1. Длины программы InterpretLanguage, которая может быть принята за константу $c$.
2. Длины $P$, определяемой $K_{2}(s)$.

Это доказывает искомую верхнюю оценку.

См. также: теорема инвариантности

История и контекст

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

Идея теории колмогоровской сложности основана на ключевой теореме, впервые открытой Рэем Соломоноффом (англ. Ray Solomonoff), опубликовавшим её в 1960 году, описав в работе «A Preliminary Report on a General Theory of Inductive Inference» как часть своего изобретения алгоритмической вероятности. Он дал более полное описание в своих публикациях «A Formal Theory of Inductive Inference», часть 1 и 2 в журнале «Information and Control», сделанных в 1964 году.

Позже А. Н. Колмогоров независимо опубликовал эту теорему в журнале «Проблемы передачи информации», Грегори Хайтин также представил эту теорему в журнале «J. ACM». Работа Хайтина была отправлена в октябре 1966 года, исправлена в декабре 1968 года и цитирует обе работы Соломоноффа и Колмогорова.

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

Когда Колмогоров узнал о работе Соломоноффа, он признал его приоритет. Несколько лет работа Соломоноффа была более известна в СССР, чем на Западе. Однако, общепринято в научном сообществе ассоциировать этот тип сложности с Колмогоровым, который говорил о случайности последовательностей, в то время как алгоритмическая вероятность стала связываться с Соломоноффым, который фокусировался на прогнозировании, используя своё открытие распределения универсальной априорной вероятности.

Существуют некоторые другие варианты колмогоровской сложности или алгоритмической информации. Один из наиболее широко используемых основан на самоограниченных программах и в основном связывается с Л. А. Левиным (1974). Аксиоматический подход к колмогоровской сложности, основанный на аксиомах Блума (1967), был введен М. Бургиным (1982).

Некоторые полагают, что название «колмогоровская сложность» — это пример эффекта Матфея.

Основные следствия

В последующих рассуждениях под $K(s)$ будем подразумевать сложность строки $s$.

Несложно заметить, что минимальное описание строки не может быть больше, чем сама строка: приведённая выше программа GenerateFixedString, чей выход $s$, больше $s$ на фиксированную величину.

Теорема. Существует константа $c$, такая, что

$\forall s\,K(s)\leqslant |s|+c.$

Невычислимость колмогоровской сложности

Первое следствие^[чего?] заключается в том, что нет эффективного способа вычисления $K$.

Теорема. $K$ — невычислимая функция.

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

  function KolmogorovComplexity(string s)

которая принимает на входе $s$ и возвращает $K(s)$. Теперь рассмотрим программу

  function GenerateComplexString(int n)
     for i = 1 to infinity:
        for each string s of length exactly i
           if KolmogorovComplexity(s) >= n
              return s
              quit

Эта программа вызывает подпрограмму KolmogorovComplexity. Программа пробует каждую строку, начиная с кратчайшей, пока не найдет строку со сложностью как минимум $n$, которую возвращает. Следовательно, получив любое положительно целое число $n$, она производит строку с колмогоровской сложностью не меньше $n$. Эта программа имеет собственную фиксированную длину $U$. Входом программы GenerateComplexString является целое $n$ и размер $n$ измеряется количеством битов, необходимым для его представления, которое есть $\log _{2}n$. Далее рассмотрим следующую программу:

  function GenerateParadoxicalString()
      return GenerateComplexString(n0)

Эта программа вызывает GenerateComplexString как подпрограмму и также имеет свободный параметр $n_{0}$. Эта программа выводит строку $s$, чья сложность составляет как минимум $n_{0}$. При благоприятном выборе параметра $n_{0}$ мы придём к противоречию. Чтобы выбрать это значение, заметим, что $s$ описывается программой GenerateParadoxicalString, чья длина не больше, чем

$U+\log _{2}n_{0}+C,$

где константа $C$ добавлена из-за программы GenerateParadoxicalString. Так как $n$ растёт быстрее, чем $\log _{2}n$, существует значение $n_{0}$, такое, что

$U+\log _{2}n_{0}+C<n_{0}.$

Но это противоречит определению о том, что имеется сложность как минимум $n_{0}$. То есть, по определению ($s$), допускается, что строка $s$, возвращаемая программой GenerateParadoxicalString, может быть создана программой длиной $n_{0}$ или больше, но GenerateParadoxicalString короче, чем $n_{0}$. Так программа KolmogorovComplexity на самом деле не может вычислить сложность случайной строки.

Это доказательство от противного, где противоречие похоже на парадокс Берри: «Пусть $n$ — наименьшее положительно целое, которое не может быть названо меньше чем двадцатью английскими словами». Также возможно показать невычислимость $K$ путём сведения невычислимости к задаче остановки $H$, так как $K$ и $H$ тьюринг-эквивалентны.

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

Цепное правило для колмогоровской сложности

Основная статья: Цепное правило для колмогоровской сложности

Цепное правило для колмогоровской сложности утверждает, что

$K(X,Y)=K(X)+K(Y\mid X)+O{\big (}\log K(X,Y){\big )}.$

Оно утверждает, что кратчайшая программа, воспроизводящая $X$ и $Y$ не больше чем на $\log K(X,Y)$ превосходит по размеру программу, воспроизводящую $X$, и программу, воспроизводящую $Y$ при данном $X$. С использованием этого выражения можно определить аналог взаимной информации для колмогоровской сложности.

Сжатие

Вычислять верхнюю границу для $K(s)$ несложно: нужно просто сжать строку $s$ каким-либо методом, реализовать соответствующий декомпрессор на выбранном языке, соединить декомпрессор со сжатой строкой и измерить длину полученной строки.

Строка $s$ сжимается на $c$, если имеет описание, длина которого не превосходит $|s|-c$. Это равнозначно утверждению $K(s)\leqslant |s|-c$. Если это не выполняется, то $s$ не сжимается на $c$. Строка, не сжимаемая на 1, называется просто несжимаемой; по принципу Дирихле, несжимаемые строки должны существовать, так как есть $2^{n}$ битовых строк длиной $n$, но только $2^{n}-1$ строк длиной меньше $n$.

По той же причине большинство строк сложны в том смысле, что они не могут быть значительно сжаты: $K(s)$ не намного меньше $|s|$, длины $s$ в битах. Чтобы уточнить, зафиксируем значение $n$. Существует $2^{n}$ битовых строк длиной $n$. Равномерное распределение вероятностей на пространстве этих битовых строк определяется точно равным весовому коэффициенту $2^{-n}$ для каждой строки длиной $n$.

Теорема. Вероятность того, что строка не сжимается на $c$ равна как минимум $1-2^{-c+1}+2^{-n}$ с равномерным распределением вероятностей на пространстве битовых строк длиной $n$.

Для доказательства этой теоремы заметим, что количество описаний длин не превосходит $n-c$, полученное из геометрической прогрессии:

$1+2+2^{2}+\ldots +2^{n-c}=2^{n-c+1}-1.$

Остаётся как минимум

$2^{n}-2^{n-c+1}+1$

битовых строк, несжимаемых на $c$. Для определения вероятности разделим на $2^{n}$.

Теорема Хайтина о неполноте

Нам известно, что во множестве всех возможных строк большинство строк являются сложными в том смысле, что не могут быть описаны в любом достаточно сжатом виде. Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. Точная формализация представлена далее. Для начала зафиксируем частную аксиоматическую систему $\mathbf {s}$ для натуральных чисел. Аксиоматическая система должна быть достаточно мощной, чтобы точному суждению $\mathbf {A}$ о сложности строки можно было поставить в соответствие формулу $\mathbf {F} _{\mathbf {A} }$ в аксиоматической системе $s$. Это соответствие должно обладать следующим свойством: если $\mathbf {F} _{\mathbf {A} }$ выводится из аксиом $\mathbf {s}$, то соответствующее суждение $\mathbf {A}$ истинно.

Теорема. Существует такая константа $L$ (которая зависит только от частной аксиоматической системы и выбранного языка описания), что ни для одной строки утверждение

$K(s)\geqslant L$

не может быть доказано в рамках $\mathbf {s}$.

Тем не менее, как легко понять, утверждение $K(s)\geqslant L$ будет истинным для бесконечного множества строк, а точнее, для всех строк, за исключением конечного их числа.

Доказательство теоремы основано на самореферентной конструкции, использованной в парадоксе Берри. Доказательство от противного. Если теорема не верна, то

Предположение (X): Для любого целого числа $n$ существует строка $s$, для которой в $\mathbf {s}$ существует вывод формулы «$K(s)\geqslant n$» (для которой мы предположили, что она может быть формализована в $\mathbf {s}$).

Рассмотрим программу, реализующую эффективное перечисление всех формальных доказательств в $\mathbf {s}$

  function NthProof(int n)

принимающую на вход n и выдающую некоторое доказательство. Некоторые из них доказывают формулу вида «$K(s)\geqslant n$», где s и n — константы в языке $\mathbf {s}$. Существует программа, проверяющая, доказывает ли n-е доказательство формулу «$K(s)\geqslant L$»:

  function NthProofProvesComplexityFormula(int n)

Обратно, строка s и число L могут быть вычислены программами

  function StringNthProof(int n)

  function ComplexityLowerBoundNthProof(int n)

Рассмотрим теперь следующую программу:

  function GenerateProvablyComplexString(int n)
     for i = 1 to infinity:
        if  NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
           return StringNthProof(i)

Принимая на вход n, эта программа проверяет каждое доказательство, пока не находит некоторую строку s и доказательство формулы K(s) ≥ L для некоторого L ≥ n. Эта программа останавливается по Предположению (X). Пусть эта программа имеет длину U. Существует число n₀, такое что U + log₂ n₀ + C < n₀, где C — дополнительная длина программы

  function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n0)

Заметим, что число n₀ также закодировано в этой программе, на что требуется log₂(n₀) информации. Программа GenerateProvablyParadoxicalString выдает строку s, для которой существует L, такое что K(s) ≥ L может быть выведено в $\mathbf {s}$, причём L ≥ n₀. В частности для неё верно K(s) ≥ n₀. Однако s может быть описана программой длины U + log₂ n₀ + C, значит её сложность меньше n₀. Полученное противоречие доказывает ложность Предположения (X).

Подобные же идеи используются для доказательства свойств константы Хайтина.

Минимальная длина сообщения

Принцип минимальной длины сообщения в статистическом и индуктивном выводе и машинном обучении был разработан Уоллесом (англ. C. S. Wallace) и Болтоном (англ. D. M. Boulton) в 1968 году. Принцип МДС является байесовским (включает априорные вероятности) и информационно-теоретическим. Он обладает желаемыми свойствами статистической инвариантности (вывод трансформируется с репараметризацией), статистической связности (даже для очень трудной задачи принцип сойдётся к нижележащей модели) и эффективности (модель, основанная на принципе МДС, сойдётся к любой достоверной нижележащей модели так быстро, как это возможно). Уоллес и Доу (англ. D. L. Dowe) показали формальную связь между принципом МДС и алгоритмической теорией информации (или колмогоровской сложностью).

Колмогоровская случайность

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

Это определение можно расширить на бесконечные последовательности символов конечного алфавита. Определение можно изложить тремя эквивалентными способами. Первый способ использует эффективный аналог теории меры; другой использует эффективный мартингал. Третий способ определения таков: бесконечная последовательность случайна, если колмогоровская сложность её начального сегмента растет достаточно быстро — существует константа c, такая что сложность любого начального сегмента длины n не меньше n − c. Оказывается, что это определение, в отличие от определения случайности конечной строки, не зависит от выбора универсальной машины.

Связь с энтропией

Согласно теореме Брудно, энтропия динамической системы и алгоритмическая сложность траекторий в ней связаны соотношением $K(x;T)=h(T)$ для почти всех $x$.

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

Литература

• Верещагин Н. К. Курс колмогоровской сложности.
• Верещагин Н. К., Шень В. А. Колмогоровская сложность и алгоритмическая случайность. — МЦНМО, 2013.
• Вьюгин В. В. Колмогоровская сложность и алгоритмическая случайность.