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

Строка «01010101...» длиной 1000 символов = 20 байт программы. Случайная строка той же длины = 1000 байт. Колмогоровская сложность формализует: насколько «интересна» строка? Это лежит в основе MDL (выбор моделей в ML), NCD (кластеризация геномов) и теоретического обоснования принципа Оккама.

• MDL в scikit-learn: BIC-критерий для выбора числа кластеров в GMM - практическая аппроксимация MDL
• NCD (Normalized Compression Distance): кластеризация геномов, определение авторства текстов, классификация музыки
• L1/L2 регуляризация нейросетей: интерпретация как минимизация длины описания весов модели

Предварительные знания

• Shannon Entropy: the Math of Uncertainty
• Lossless Coding: Huffman, LZ

Строки, программы и минимальное описание

Строка «01010101...» длиной 1000 символов: программа «напечатай 01 пятьсот раз» - около 20 байт. Случайная строка «1011001110100101...» той же длины: нет короткой программы, нужно перечислять побитово - около 1000 байт. Колмогоровская сложность K(x) = длина кратчайшей программы, которая выводит x на универсальной машине Тьюринга. Это индивидуальная мера информации строки - без вероятностей.

Числовые примеры: строка из 10^6 нулей - K ≈ 20 бит (log2(10^6) ≈ 20). Первые 10^6 цифр числа pi - K ≈ 50-100 бит (алгоритм BBP). Случайная 10^6-битная строка - K ≈ 10^6 бит. Разница в 50000x - это и есть разница между «сжимаемыми» и «несжимаемыми» строками.

Чем лучше реальный архиватор (zstd, brotli, lzma), тем точнее верхняя оценка K(x). Нижнюю оценку дать невозможно в общем случае - это следует из неисчислимости K.

Несжимаемость и алгоритмическая случайность

Строка x называется c-несжимаемой, если K(x) >= |x| - c. Большинство строк несжимаемы: из 2^n строк длины n не более 2^{n-c} + 1 строк имеют K(x) < n - c. Программ длины < n-c просто меньше, чем строк: нельзя всех «охватить». Именно это объясняет, почему нет архиватора, сжимающего все файлы.

K(x) неисчислима: нет алгоритма, точно вычисляющего K(x) для произвольной строки. Причина - сводимость к проблеме остановки: если бы K была вычислима, можно было найти кратчайшую останавливающуюся программу для любого x, что решало бы проблему остановки. Можно только аппроксимировать K сверху: запустить все программы длиной < k и найти кратчайшую, дающую x.

NCD применяется в биоинформатике (кластеризация геномов), криминалистике (определение авторства текстов), классификации музыки - везде, где нужна мера «алгоритмической похожести» без предположений о природе данных.

K(x) и H(X): индивидуальное vs. статистическое

Энтропия Шеннона H(X) - свойство распределения (источника). Колмогоровская сложность K(x) - свойство конкретной строки. Связь: если x_1, ..., x_n - случайная выборка из распределения p, то K(x_1...x_n)/n -> H(X) при n -> inf с вероятностью 1 (теорема Звонкина-Левина). В среднем они совпадают, но для конкретной строки могут кардинально различаться.

MDL, OCR и AIXI: практика алгоритмической теории

MDL (Minimum Description Length): выбирать модель, которая минимизирует сумму «длина модели + длина данных при модели». Это практическое приближение к минимизации K. В scikit-learn BIC-критерий для выбора числа компонент в GMM - это частный случай MDL. В нейросетях L1/L2 регуляризация - приближение к минимизации длины описания весов.

AIXI (Marcus Hutter, 2000): теоретически оптимальный универсальный агент ИИ. Выбирает действия, максимизируя ожидаемую награду, взвешивая все вычислимые модели мира с весами 2^(-K(модель)). Неисчислим, но задаёт теоретическую точку сравнения. AIXItl - исчислимая версия с ограничениями на длину программы и время.

Принцип Оккама через Колмогорова: P(теория | данные) ∝ 2^{-K(теория)} * P(данные | теория). Теории с меньшей K имеют больший априорный вес. Это байесовское обоснование бритвы Оккама: более короткие объяснения не просто «элегантнее», они имеют строго большую априорную вероятность.

Ключевые идеи

• K(x) = длина кратчайшей программы для вывода x - индивидуальная мера сложности строки
• Несжимаемость: большинство строк длины n имеют K(x) ≈ n - случайность = несжимаемость
• Неисчислимость: K(x) нельзя вычислить точно, только аппроксимировать через реальные архиваторы
• Связь с Шенноном: E[K(x)] ≈ H(X); H - среднее, K - индивидуальное
• MDL: min(K(модель) + K(данные | модель)) - практическая версия принципа Оккама
• NCD = (K(xy) - min(K(x), K(y))) / max(K(x), K(y)) - мера алгоритмической похожести

Связанные темы

Колмогоровская сложность связывает теорию и практику:

• Принцип MDL — MDL - практическое приближение к K(x) для выбора моделей
• Энтропия Шеннона — H(X) = E[K(x)] в среднем по типичным строкам
• Кодирование без потерь — Хаффман и LZ - практические алгоритмы, приближающие K(x) сверху

Вопросы для размышления

• K(x) неисчислима. Как NCD через zlib/gzip практически реализует идею колмогоровского расстояния? Какие ограничения у этого подхода?
• Если случайная строка несжимаема (K ≈ n), значит ли это, что псевдослучайные числа из PRNG тоже несжимаемы? Что происходит при сжатии вывода Mersenne Twister?
• MDL vs Байесовский выбор модели через BIC - в чём принципиальная разница? Когда MDL даёт другой ответ, чем BIC?

Связанные уроки

• alg-01-big-o