Эффективно вычислимые варианты колмогоровской сложности

Сложность префикса Колмогорова (т. Е. $K(x)$ - это размер минимальной программы с самоограничением, которая выводит ) имеет несколько приятных особенностей:$x$

1. Это соответствует интуиции предоставления строк с шаблонами или структурой меньшей сложности, чем без строк.
2. Это позволяет определить условную сложность , или даже лучше для некоторого оракула .K ( x | O ) $K(x|y)$$K(x|O)$$O$
3. Он является субаддитивным .$K(x,y) \leq K(x) + K(y)$

Однако у него есть ужасный недостаток: возвращение учетом неразрешимо.$K(x)$$x$

Я задавался вопросом, существует ли вариант колмогоровской сложности использующий ограниченную модель вычислений (либо используя более слабые языки, чем TM, либо используя ограниченный TM с ресурсами), который сохраняет функции (1) и (2) (feature ( 3) является бонусом, но не обязательным), будучи эффективно вычисляемым?$K'(x)$

Мотивация для этого вопроса заключается в использовании в имитационных исследованиях различных игрушечных моделей эволюции. Таким образом, ответ, который использовался как «грубое приближение» для сложности Колмогорова в числовой работе прежде, является предпочтительным. Однако цель не состоит в том, чтобы идти полностью экспериментально, поэтому предпочтителен относительно простой / чистый язык описания / модель вычисления для , так что можно было бы доказать некоторые разумные теоремы о том, насколько сильно отличается от и на какие струны.K ′$K'$$K'$$K$

Относятся вопросы

Колмогоровская сложность со слабыми языками описания

Есть ли разумное понятие алгоритма аппроксимации для неразрешимой задачи?

Gzip. У Cilibrasi и Vitanyi есть действительно хорошая статья, в которой они используют gzip как приближение сложности Колмогорова для кластеризации. Кластеризация с помощью сжатия

Я больше думал о своем вопросе и пришел к возможному решению. У него есть два ограничения, оно определено только для строк длиной (хотя я буду обсуждать это подробнее), и в нем не говорится об универсальных машинах Тьюринга, вместо этого следует предыдущий вопрос и использование альтернативной модели вычислений.$n = 2^m$

По сути, мы можем интерпретировать строку с помощью | х | = 2 м как функция f x : { 0 , 1 } m → { 0 , 1 } . Тогда нашей мерой сложности K ′ ( x ) является размер (число ребер) уникальной приведенной упорядоченной диаграммы двоичных решений (ROBDD; со стандартным упорядоченным порядком), представляющей f x . Это удовлетворяет условию [1]. Кроме того, поскольку ROBDD могут быть вычислены во времени полинома в 2 $x$$|x| = 2^m$$f_x: \{0,1\}^m \rightarrow \{0,1\}$$K'(x)$$f_x$$2^m$У нас есть эффективная мера.

Чтобы удовлетворить условию [2], мы должны изменить стандартные BDD, разрешив специальный тип на узле. Обычно узлы обозначены индексами , мы включим специальный узел оракула. Для K ( x | y ) где | у | = 2 м, мы разрешим специальные узлы в BDD следующим образом:$i \in \{1,...,m\}$$K(x|y)$$|y| = 2^m$

Если мы запускаем BDD на входе ( | a | = m ), то нормальный узел, помеченный i, просто отправляет нас вниз по краю, обозначенному a i . Вместо этого узел оракула отправит нас на ребро, помеченное как f y ( a ) . Таким образом, K ′ ( x | x ) = 2 и с большой вероятностью K ′ ( x | y ) ≈ K ( x ) для y, выбранного случайным образом.$a$$|a| = m$$i$$a_i$$f_y(a)$$K'(x|x) = 2$$K'(x|y) \approx K(x)$$y$

[Примечание: не ясно, можно ли по-прежнему эффективно вычислять условную сложность :(]

Удобно, у нас также есть субаддитивность, поскольку мы строим OBDD для нас может быть запрос для первого бита, и на 0 перейдите к ROBDD для x и на 1 к ROBDD для y . Таким образом, мы имеем K ′ ( x . Y ) ≤ K ′ ( x ) + K ′ ( y ) .$x.y$$0$$x$$1$$y$$K'(x.y) \leq K'(x) + K'(y)$

При потенциальной стоимости субаддитивности мы могли бы определить для любой длины x , просто взяв куски степени два и сложив их сложности. Например, для | х | = 2 м и | у | = 2 l при m > l мы можем определить K ′ ( x . Y ) = K ′ ( x ) + K ′ ( y ) .$K'(x)$$x$$|x| = 2^m$$|y| = 2^l$$m > l$$K'(x.y) = K'(x) + K'(y)$

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

Я не эксперт, но если вам нужна практическая мера сложности для строк, вы можете взглянуть на меру T-сложности Титченера .

Смотрите сайт Титченера для быстрого ознакомления; его документы можно скачать в формате PDF .

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

Я также нашел несколько статей о практических реализациях (см., Например, « Алгоритм быстрого T-разложения »)

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

• Если у вас есть какое-либо вычисляемое распределение вероятностей, которое назначает вашу вероятность данных то, согласно неравенству Крафта, у вас есть компрессор, который сжимает ваши данные в - log p ( x ) битах.$p(x)$$- \log p(x)$
• Если у вас есть какой-нибудь вычислимый компрессор C, который сжимает ваши данные в битов, то у вас есть K ( x ) ≤ n + s C , где s C зависит от вашего компрессора, но не от x (это в основном количество битов, которое вам нужно опишите C на вашей универсальной машине Тьюринга).$n$$K(x) \leq n + s_C$$s_C$$x$

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

$K(x)$

$K(x)$$K$

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

Для технических деталей см. Эту статью . Отказ от ответственности: я один из авторов.

$K(x)$$K(x)$

Вы ищете ограниченный ресурс колмогоровской сложности. Вы можете начать с этой статьи и разветвляться.