Аппроксимация колмогоровской сложности

22

Я изучил кое-что о сложности Колмогорова , прочитал некоторые статьи и книги Витани и Ли и использовал концепцию нормализованного расстояния сжатия для проверки стилометрии авторов (определите, как каждый автор пишет некоторые текстовые и групповые документы по их сходству).

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

Помимо языков сжатия данных и языков программирования (на которых вы бы написали какой-нибудь компрессор), что еще можно использовать для аппроксимации колмогоровской сложности? Есть ли другие подходы, которые можно использовать?

woliveirajr
источник
Я не уверен, что понимаю ваш вопрос: определение KC включает машины Тьюринга, из которых программы образуют примеры (относительно некоторого перевода). Что значит аппроксимировать колмогоровскую сложность «без языков программирования»?
Коди
1
Сожмите строку, используя любое программное обеспечение для сжатия, например, GZip. Размер выходных данных является верхней границей KC строки.
М. Алагган
@cody: точно, я использовал компрессоры данных в своих исследованиях (zip, bzip, ppmd), чтобы приблизить KC. Компрессор данных - это не программы. Итак, я ищу предложения о том, что можно использовать в KC, кроме языков (= написать программу на C / prolog / что угодно) и компрессоров данных (= использовать zip, gzip, ppmc, ppmd ...) :)
woliveirajr
1
Мне кажется, мне просто кажется, что определение программы сжатия данных точно: программа, которая аппроксимирует KC строки программой («uncompressor») и другой строкой (сжатая строка).
Коди

Ответы:

9

Я предполагаю , что один возможный ответ на ваш вопрос заключается в следующем: Возьмите псевдослучайных чисел генератор . Попробуйте выбрать генератор, который имеет несколько мощных атак против него: атака генератора случайных чисел для G - это (для наших целей) алгоритм A, который при заданной строке s определяет начальное число A ( s ) , такое что G ( A ( s ) ) = s . Затем приблизьте KC s :GGAs A(s)G(A(s))=ss

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Где это длина программы, которая вычисляет G ( s ) (часто довольно короткая, как для линейных генераторов).|G|G(s)

Обратите внимание, что на практике атаки генератора случайных чисел выполняются не так, как описано: они могут дать сбой или привести к неполным результатам. В этом случае вы можете адаптировать алгоритм так, чтобы он возвращал когда результат атаки неудовлетворительный. То же самое относится и к алгоритмам сжатия.|s|

Предостережение в этом подходе в отличие от алгоритмов сжатия заключается в том, что алгоритмы сжатия в целом гораздо больше подходят для вычисления KC, поскольку они приспособлены для работы с любой строкой, тогда как атака может работать, только если оказывается в образе G ( очень маловероятно ).sG

Коди
источник
7

p(x)logp(x)

Вот почему сложность Колмогорова так интересна не потому, что это лучший алгоритм сжатия (который все равно заботится о сжатии), а потому, что это лучший алгоритм обучения . Сжатие и обучение - это одно и то же: поиск шаблонов в ваших данных. Статистическая структура, построенная на этой идее, называется «Минимальная длина описания», и она была непосредственно вдохновлена ​​колмогоровской сложностью.

Смотрите также этот вопрос в разделе StackExchange.

Питер
источник
5

грамматическое кодирование является менее часто используемой версией алгоритма сжатия и может рассматриваться как «грубая» оценка колмогоровской сложности. Грамматическое кодирование не так часто используется в качестве алгоритма сжатия, как другие более распространенные подходы, возможно, в основном потому, что оно не сильно улучшает сжатие, например, из Lempel-Ziv в текстовых корпусах, но оно может хорошо работать с другими видами данных. идея состоит в том, чтобы «сжать» строку, используя правила грамматики. вывод грамматики может привести к созданию DAG (по сравнению с менее сложным деревом), поэтому возможна существенная сложность представления.

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

K(x)

K(x)

Существуют также другие методы алгоритма сжатия, кроме подходов типа «кодирование длины серий» Лемпеля-Зива, например, векторная алгебра и SVD могут использоваться в качестве алгоритма сжатия. также преобразования Фурье часто используются для сжатия изображений, например, в стандарте JPG.

ВЗН
источник
1
K(x)
Хорошая идея, однако, алгоритмы с потерями обычно имеют настраиваемый параметр, который определяет «потери» и теоретически может достичь без потерь с достаточным количеством «членов» или, так сказать, «частот», и это также зависит от входных выборок, так что значение параметра без потерь будет зависеть об их «относительном порядке по сравнению со случайностью»,
видимом
1
@cody and vzn: Спасибо за ответ, вы дали мне несколько хороших идей для моего доктора философии о сжатии без потерь x с потерями :)
woliveirajr
JPEG использует DCT, а не DFT.
Зло