Принцип минимальной длины описания (MDL)

Почему нейросеть с миллиардом параметров иногда хуже генерализирует, чем с миллионом? Почему L2-регуляризация работает? MDL даёт единый принцип: лучшая модель - та, которая лучше всего сжимает данные с учётом своей собственной сложности.

• **Pruning и квантование LLM**: LoRA, GPTQ, INT4 - сжатие весов с минимальной потерей качества, практическая MDL
• **Дерево решений**: MDL-критерий остановки ветвления (Fayyad-Irani) - стандарт в системах вроде C4.5, scikit-learn
• **BIC в статистике**: выбор числа компонент GMM, степени полинома, структуры байесовской сети

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

• Shannon Entropy: the Math of Uncertainty
• Kolmogorov Complexity

Принцип MDL: модель как сжатие

Зачем нужно регуляризовывать ML-модели? Интуитивно - чтобы не переобучиться. Но почему? **MDL** (Minimum Description Length, Rissanen 1978) даёт глубокий ответ: хорошая модель должна **сжимать данные**. Лучшая модель - та, что задаётся кратко и хорошо предсказывает данные.

MDL - это практическая аппроксимация колмогоровской сложности K(данные). Если K неисчислима, MDL предлагает конкретные вычислимые критерии выбора модели. Это мост между теоретическим идеалом и практическим машинным обучением.

MDL и байесовский вывод глубоко связаны. Если модели M присвоить априорную вероятность P(M) ∝ 2^(-L(M)), то MAP-оценка (максимум апостериорной вероятности) эквивалентна MDL. Длина кода = -log P: L(M) = -log₂ P(M). Выбор кода = выбор априора. Это позволяет интерпретировать любой байесовский метод как MDL и наоборот.

Двухчастные коды и стохастическая сложность

Ранний MDL Рисанена использовал **двухчастные коды**: отдельно кодируем модель и данные при модели. Но есть проблема: как выбрать «длину» для непрерывных параметров? Риссанен решил это через **стохастическую сложность** - более продвинутую версию MDL.

**NML (Normalized Maximum Likelihood)** - идеальный вариант MDL. Код, при котором «стохастическая сложность» минимальна, задаётся через нормализованную функцию правдоподобия. Он инвариантен к параметризации и оптимален в минимаксном смысле - худший случай для самого «трудного» распределения.

MDL и регуляризация в ML

Регуляризация L1 и L2 кажутся техническим трюком. Но через призму MDL они получают глубокое обоснование: это ничто иное, как **байесовский априор** на параметры, эквивалентный штрафу за длину описания модели.

**Minimum Description Length of Neural Networks** (Hinton & van Camp, 1993) предложили измерять «длину» весов нейросети. Это привело к weight sharing, pruning и квантованию весов. Современные методы сжатия моделей (LoRA, QLoRA, INT4-квантование) - практические реализации MDL-принципа: нужно найти кратчайшее описание модели, сохраняющее качество.

MDL на практике: деревья, кластеры, признаки

MDL особенно мощен там, где сложность модели нельзя выразить простым числом параметров - например, для деревьев решений, кластеризации или отбора признаков. Здесь MDL предоставляет единый принцип без дополнительных предположений.

**MDL для отбора признаков**: включение признака оправдано, если уменьшение L(данные|M) (лучше предсказание) превышает увеличение L(M) (сложнее модель). Это автоматически учитывает мощность признака и корреляции. В отличие от p-value и correlation threshold, MDL учитывает стоимость ошибки первого рода.

**Perplexity** языковой модели - это 2^H, где H - кросс-энтропия на тестовой выборке. Минимальная perplexity соответствует максимальному сжатию текста моделью - это MDL в действии! GPT-4 достигает perplexity ~5-8 на английском тексте, что близко к теоретическому пределу Шеннона (~1.3 бит/символ). Чем меньше perplexity - тем «компактнее» модель описывает язык.

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

• **MDL**: хорошая модель минимизирует L(M) + L(данные|M) - баланс сложности и качества подгонки
• **Связь с BIC**: двухчастный MDL ≈ BIC; NML - точный MDL через нормализованное правдоподобие
• **Регуляризация = MDL**: L2 ≡ гауссовский код параметров; L1 ≡ разреженный (Laplace) код
• **Практика**: pruning, выбор k для кластеров, глубины дерева - всё решается единым принципом

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

MDL - практический мост между теорией информации и машинным обучением:

• Колмогоровская сложность — MDL - вычислимое приближение к неисчислимой K(x)
• IT в статистике: достаточные статистики — Достаточная статистика = минимальное описание данных без потерь - MDL в статистике
• IT в Machine Learning — MDL объясняет регуляризацию, pruning и выбор архитектур нейросетей

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

• Perplexity языковой модели GPT-4 ≈ 6. Что это означает с точки зрения MDL? Насколько хорошо модель «сжимает» английский язык?
• L2-регуляризация и L1-регуляризация соответствуют гауссовскому и лапласовскому априорам. Какой априор выбрать для задачи, где большинство признаков нерелевантны?
• MDL использует длину кода как меру качества. Но длина кода зависит от выбора языка кодирования. Как это влияет на практическую применимость MDL?

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

• stat-03-mle
• ml-08-regularization