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

Материал из MachineLearning.

Текущая версия

Статья написана с использованием LLM GPT-4 Turbo и проверена участником Amir Baidanov 02:39, 19 июля 2026 (MSD)

Принцип минимальной длины описания (Minimum Description Length, MDL) — фундаментальный принцип статистического вывода и теории информации, предлагающий выбирать модель, которая обеспечивает наиболее компактное описание данных. В основе принципа лежит идея: лучшая модель — та, которая позволяет максимально сжать данные, то есть требует наименьшего суммарного количества бит для кодирования как самой модели, так и ошибок её предсказаний. MDL тесно связан с байесовским выводом, регуляризацией и колмогоровской сложностью.

Интуитивная картина

Представьте, что вы хотите передать кому-то массив чисел. Вы можете передать числа как есть, но это займёт много места. Альтернатива — найти закономерность (модель), описать её коротко, а затем передать только отклонения от этой закономерности. Если закономерность выбрана удачно, общий объём передаваемой информации окажется меньше, чем при простой передаче исходных данных. MDL предлагает выбирать именно ту модель, которая минимизирует суммарную длину описания.

Рассмотрим простой пример. Пусть даны точки на плоскости, и мы хотим подобрать полиномиальную модель. Модель нулевого порядка (константа) описывается коротко, но ошибки велики, и для их кодирования потребуется много бит. Модель высокого порядка (например, полином 9-й степени) даёт малые ошибки, но сама модель требует длинного описания (много коэффициентов). MDL помогает найти золотую середину — модель, для которой сумма длин описания модели и ошибок минимальна.

Историческая справка

Принцип минимальной длины описания имеет глубокие корни в теории информации и алгоритмической теории информации. Рэй Соломонов в 1960 году предложил идею универсального предсказания на основе минимальной длины описания ^[1]. Примерно в то же время Андрей Колмогоров разработал понятие колмогоровской сложности — минимальной длины программы, которая выводит данную строку ^[1]. Грегори Чайтин независимо развил аналогичные идеи ^[1].

В современном виде MDL был сформулирован Юрмо Риссаненом в 1978 году ^[1]. Риссанен предложил практическую схему двухчастного кодирования, которая стала основой для широкого применения MDL в статистике и машинном обучении. В последующие десятилетия принцип развивался в работах Баррона, Килвинена, Грюнвальда и других исследователей ^[1].

Математическая постановка

Пусть дана обучающая выборка . Мы рассматриваем семейство моделей с параметрами . Принцип MDL предлагает выбрать модель , минимизирующую общую длину описания:

,

где:

• — длина описания модели (например, количество бит для кодирования параметров );
• — длина описания данных при использовании модели (обычно связана с логарифмом правдоподобия).

В простейшем случае для моделей с непрерывными параметрами используется приближение:

,

где — число параметров модели, — объём выборки. Это приближение лежит в основе связи MDL с байесовским информационным критерием (BIC).

Для дискретных моделей или моделей с конечным числом параметров длина описания модели может быть вычислена как число бит, необходимое для кодирования параметров с оптимальной точностью.

Связь с байесовским выводом

MDL тесно связан с байесовским подходом. Если задать априорное распределение для параметров модели, то оптимальная длина описания модели соответствует плюс константа, а длина описания данных при модели соответствует . Тогда минимизация общей длины эквивалентна максимизации апостериорной вероятности:

.

Однако MDL не требует задания априорного распределения в явном виде: вместо этого он использует универсальные коды или нормализованную максимальную вероятность, что делает его более объективным в некоторых ситуациях.

Связь с регуляризацией и критериями выбора моделей

MDL тесно связан с другими критериями выбора моделей:

• Информационный критерий Акаике (AIC): . AIC минимизирует расходимость Кульбака — Лейблера между истинным распределением и моделью, но не является асимптотически консистентным (при может выбирать избыточно сложные модели).
• Байесовский информационный критерий (BIC): . BIC является приближением к MDL для больших выборок и асимптотически консистентен.
• Регуляризация: MDL можно интерпретировать как форму регуляризации, где штраф за сложность модели пропорционален . Например, L0-регуляризация минимизирует число ненулевых параметров, что соответствует простейшей форме .

Колмогоровская сложность и её ограничения

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

Современный MDL обходит эту проблему, используя:

• ограниченные классы моделей (например, полиномы, деревья решений, смеси распределений);
• приближённые методы кодирования (например, коды Хаффмана, арифметическое кодирование);
• асимптотические приближения, такие как нормализованная максимальная вероятность.

Практические применения

Выбор порядка полиномиальной регрессии

Рассмотрим задачу подбора полиномиальной модели вида

.

Для каждого порядка мы оцениваем параметры методом наименьших квадратов и вычисляем длину описания:

.

Для кодирования коэффициентов требуется примерно бит (с учётом точности), а для кодирования ошибок — , где — дисперсия остатков. Выбирается порядок , минимизирующий сумму.

На практике это означает, что при увеличении ошибка уменьшается, но штраф за сложность растёт. MDL находит баланс, часто выбирая модели меньшей сложности, чем, например, минимизация среднеквадратичной ошибки.

Выбор числа кластеров

В задаче кластеризации MDL можно использовать для выбора числа кластеров . Общая длина описания складывается из:

• описания центров кластеров (параметров модели);
• описания принадлежности каждого объекта к кластеру;
• описания отклонений объектов от центров.

Минимизация этой суммы позволяет выбрать оптимальное , избегая как слишком простых моделей (один кластер), так и слишком сложных (каждый объект — отдельный кластер).

Обучение деревьев решений

MDL используется для построения деревьев решений: при разделении узла вычисляется, насколько уменьшается длина описания данных после разделения. Разделение производится только в том случае, если выигрыш в кодировании данных превышает затраты на кодирование самого разделения (условие, правила разбиения). Это позволяет строить деревья, которые хорошо обобщают и не переобучаются ^[1].

Выбор числа компонент в смеси распределений

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

Современные направления

Нормализованная максимальная вероятность (NML)

Нормализованная максимальная вероятность (Normalized Maximum Likelihood) — это современный подход в рамках MDL, позволяющий строить универсальные коды для параметрических семейств без явного задания априорного распределения. Длина описания по NML:

,

где второй член — нормализующая константа, зависящая от семейства моделей. NML даёт минимаксно оптимальные коды и широко используется в современной теории MDL ^[1].

MDL для нейронных сетей

Применение MDL к нейронным сетям сталкивается с вычислительными сложностями из-за большого числа параметров. Однако разрабатываются приближённые методы:

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

Байесовский вывод и MDL

Современные исследования активно исследуют связь MDL с вариационным байесовским выводом и свободной энергией. MDL можно рассматривать как форму регуляризации с информационно-теоретическим обоснованием, что делает его привлекательным для теоретического анализа алгоритмов обучения.

Преимущества и недостатки

Преимущества

• Единая информационно-теоретическая основа для выбора моделей;
• Не требует задания априорного распределения в явном виде;
• Естественная защита от переобучения;
• Теоретическое обоснование через теорию информации и статистическое обучение;
• Применимость к широкому классу моделей (классификация, регрессия, кластеризация).

Недостатки

• Вычислительная сложность при переборе моделей;
• Трудность точного вычисления длины описания для сложных моделей;
• Зависимость от способа кодирования данных и параметров;
• Для многих задач MDL сводится к другим критериям (например, BIC), и практическая разница может быть незначительной;
• Сложность применения к нейросетям с миллионами параметров.

Ошибки интерпретации

MDL — это просто BIC

Хотя для больших выборок MDL и BIC асимптотически эквивалентны для некоторых классов моделей, в общем случае MDL является более общим принципом. BIC — лишь одно из приближений к MDL, основанное на асимптотическом разложении Лапласа. Для малых выборок или сложных моделей различия становятся существенными.

MDL всегда даёт простые модели

MDL минимизирует общую длину описания, что часто соответствует выбору простых моделей, но не всегда. Если данные действительно сложны, MDL выберет сложную модель, если это даёт выигрыш в общей длине описания. Таким образом, MDL не «любит» простые модели, а ищет оптимальный баланс.

Колмогоровская сложность практически применима

Колмогоровская сложность невычислима, и попытки использовать её напрямую для выбора моделей обречены на неудачу. MDL использует вычислимые приближения, основанные на конкретных классах моделей и схемах кодирования.

Краткий вывод

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

См. также

• Теория информации
• Колмогоровская сложность
• Байесовский вывод
• Информационный критерий Акаике
• Байесовский информационный критерий
• Регуляризация
• Выбор модели

Примечания

Литература

1. Solomonoff R. J. (1964). A formal theory of inductive inference. Information and Control, 7(1): 1–22.
2. Kolmogorov A. N. (1965). Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1): 1–7.
3. Chaitin G. J. (1966). On the length of programs for computing finite binary sequences. Journal of the ACM, 13(4): 547–569.
4. Rissanen J. (1978). Modeling by shortest data description. Automatica, 14(5): 465–471.
5. Rissanen J. (1986). Stochastic complexity and modeling. The Annals of Statistics, 14(3): 1080–1100.
6. Rissanen J. (1996). Fisher information and stochastic complexity. IEEE Transactions on Information Theory, 42(1): 40–47.
7. Grünwald P. D. (2007). The Minimum Description Length Principle. MIT Press.
8. Barron A., Rissanen J., Yu B. (1998). The minimum description length principle in coding and modeling. IEEE Transactions on Information Theory, 44(6): 2743–2760.
9. Hansen M. H., Yu B. (2001). Model selection and the principle of minimum description length. Journal of the American Statistical Association, 96(454): 746–774.
10. Quinlan J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.

Ссылки

• A Tutorial Introduction to the Minimum Description Length Principle (Grünwald P. D.)
• MDL Research — исследовательский сайт, посвящённый принципу MDL.
• Jorma Rissanen — страница основателя MDL.