Вычислимость
Колмогоровская сложность и случайность
Что значит «случайный»? Почему zip не может сжать mp3? Почему работает регуляризация в нейросетях? Все эти вопросы имеют один ответ - колмогоровская сложность, самая глубокая мера информации.
- Алгоритмы сжатия (zip, gzip) - практические аппроксиматоры K
- Регуляризация в ML - MDL принцип на практике
- Криптографически стойкие PRNG: несжимаемые (но не случайные!)
- Тест Мартина-Лёфа: формальное определение случайности
Колмогоровская сложность: информация в программе
**Колмогоровская сложность** K(x) строки x - длина кратчайшей программы на фиксированном универсальном языке (например, Python), которая выводит x. Это формальная мера информационного содержания строки.
**Почему K неисчислима?** Если бы алгоритм A вычислял K(x), можно было бы построить программу, порождающую строку с K > её длины - противоречие (Paradox Конструктивности). Это та же идея, что и диагонализация Кантора.
Почему колмогоровская сложность неисчислима?
Несжимаемость и случайность Мартина-Лёфа
**Случайность Мартина-Лёфа:** Строка x называется (алгоритмически) случайной, если K(x) ≥ |x| - O(1). Случайные строки несжимаемы - нет закономерности для эксплуатации.
**Несжимаемость ≠ случайность в практике:** PRNG выдают несжимаемые последовательности, но они детерминированы (K = O(1)). Истинная случайность требует физических источников (тепловой шум, квантовые эффекты).
Строка из первых 10000 цифр π: какова её колмогоровская сложность (приблизительно)?
MDL: минимальная длина описания в ML
**MDL (Minimum Description Length)** - принцип в машинном обучении, основанный на K-сложности: лучшая модель - та, которая кратчайшим образом описывает данные. Это формализация бритвы Оккама.
**Solomonoff induction:** Соломонов обобщил MDL до принципа универсального обучения: распределение вероятностей, взвешенное по K-сложности, является оптимальным Байесовским предиктором. Это математическое основание для AGI - теоретически оптимальное обучение.
MDL и K-сложность - это теоретические понятия. В ML побеждает та модель, у которой меньше loss на test set, никакая «длина описания» здесь не нужна.
MDL формализует бритву Оккама и эквивалентен Bayesian model selection с uniform prior. Регуляризация (L1, L2, dropout), early stopping, минимальный размер архитектуры - всё это эвристики MDL: штрафуем сложность модели в пользу обобщения. K-сложность невычислима, но её аппроксимации (description length, MDL, BIC) уже работают.
Test loss выглядит исчерпывающей метрикой, поэтому теория «длины описания» кажется лишней. На деле выбор архитектуры, гиперпараметров и регуляризации - это и есть выбор кратчайшего описания при заданном loss. Без MDL-интуиции overparameterized модели проигрывают на чужих данных, потому что описывают шум, а не сигнал. Solomonoff induction - формальный предел этой логики.
Как регуляризация (L2/Ridge) связана с принципом MDL?
Ключевые идеи
- K(x) = длина кратчайшей программы, порождающей x
- K(x) неисчислима - сводится к Halting Problem
- Алгоритмически случайная строка = несжимаемая (K(x) ≈ |x|)
- Большинство строк несжимаемы (простой счётный аргумент)
- MDL: лучшая модель минимизирует |модель| + |данные|модель|
Связанные темы
Колмогоровская сложность объединяет теорию информации и вычислимость.
- Неразрешимость — K неисчислима по той же причине, что Halting Problem
- Lambda-исчисление — Универсальная машина для определения K
Вопросы для размышления
- Если K(x) неисчислима, как алгоритмы сжатия работают на практике? В чём ограничение?
- Почему нельзя доказать что конкретная строка (например, SHA256(0)) алгоритмически случайна?
- Как принцип MDL объясняет почему нейросети с dropout лучше обобщаются?
Связанные уроки
- comp-09 — Неразрешимость halting problem - часть доказательства несжимаемости
- comp-14 — Lambda-исчисление задаёт понятие программы для колмогоровской сложности
- comp-16 — Дескриптивная сложность - следующий взгляд на информационные пределы
- crypto-05-information-theory — Энтропия Шеннона и колмогоровская сложность - два языка для измерения информации
- fl-01-intro