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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

К примеру, рассмотрим две строки длиной 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 короче, чем n0. Так программа 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}).

Рассмотрим программу, реализующую эффективное перечисление всех формальных доказательств в \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. Существует число n0, такое что U + log2(n0) + C < n0, где C - дополнительная длина программы

  function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n0)

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

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

Минимальная длина сообщения[править | править вики-текст]

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

Колмогоровская случайность[править | править вики-текст]

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

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

Связь с энтропией[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  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}.
  11. http://www.loria.fr/~hoyrup/random_ergodic.pdf
  12. http://arxiv.org/pdf/cs.CC/0404039

Литература[править | править вики-текст]