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

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

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

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

К примеру, рассмотрим две строки длиной 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»^[1] как часть своего изобретения алгоритмической вероятности. Он дал более полное описание в своих публикациях «A Formal Theory of Inductive Inference», часть 1 и 2 в журнале «Information and Control».^[2][3], сделанных в 1964 году.

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

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

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

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

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

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

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

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

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

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

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

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

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

Другими словами, не существует программы, которая бы принимала на вход строку $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$₀. Так программа KolmogorovComplexity на самом деле не может вычислить сложность случайной строки.

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

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

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

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

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

$K(X,\;Y)=K(X)+K(Y\mid X)+O(\log K(X,\;Y)).$

Оно утверждает, что кратчайшая программа, воспроизводящая $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$^[10].

По той же причине, большинство строк сложны в том смысле, что они не могут значительно сжаты: $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}$).

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

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

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

Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый Колмогоровской случайности. Вы можете помочь проекту, написав этот раздел.

Примечания

1. ↑ Solomonoff, Ray (February 4, 1960). «A Preliminary Report on a General Theory of Inductive Inference» (PDF). Report V-131 (Zator Co.). revision, Nov., 1960.
2. ↑ Solomonoff, Ray (March 1964). «A Formal Theory of Inductive Inference Part I». Information and Control 7 (1): 1—–22. DOI:10.1016/S0019-9958(64)90223-2.
3. ↑ Solomonoff, Ray (June 1964). «A Formal Theory of Inductive Inference Part II». Information and Control 7 (2): 224–254. DOI:10.1016/S0019-9958(64)90131-7.
4. ↑ Колмогоров, А. Н. (1965). «Три подхода к определению понятия «количество информации»». Проблемы передачи информации 1 (1): 3–11.
5. ↑ (1969) «On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers» (PDF). Journal of the ACM 16: 407. DOI:10.1145/321526.321530.
6. ↑ (1968) «Logical basis for information theory and probability theory». IEEE Transactions on Information Theory 14 (5): 662–664. DOI:10.1109/TIT.1968.1054210.
7. ↑ Li Ming An Introduction to Kolmogorov Complexity and Its Applications. — 2nd. — Springer. — ISBN 0387948686
8. ↑ В оригинале: «Let $\scriptstyle{n}$ be the smallest positive integer that cannot be defined in fewer than twenty English words»
9. ↑ Piter Bro Miltersen. Course notes for Data Compression - 2. Kolmogorov complexity.
10. ↑ Так как существует $\scriptstyle{n_L=2^L}$ строк длиной $\scriptstyle{L}$, то количество строк длиной $\scriptstyle{L=0,\;\ldots,\;(n-1)}$ — $\scriptstyle{n_0+n_1+\ldots+n_{n-1}=2^0+2^1+\ldots+2^{n-1}}$, что является конечной геометрической прогрессией с суммой равной $\scriptstyle{2^0+2^1+\ldots+2^{n-1}=2^0\times(1-2^n)/(1-2)=2^n-1}$.

Литература

• Верещагин Н. К. Курс колмогоровской сложности.