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

Любой набор данных может быть представлен как строка символов из конечного (скажем, двоичного) алфавита.

[Принцип MDL] основан на следующем осознании: любая закономерность в заданном наборе данных может быть использована для сжатия данных, то есть описания данных с использованием меньшего набора символов, чем нужно для описания данных буквально. (Грюнвальд, 1998)[5]

MDL является теорией логического и статистического вывода, который начинается с идеи: всё статистическое обучение относится к обнаружению закономерностей в данных, а лучшая гипотеза описания закономерностей в данных, это та, которая позволяет сжать данные наиболее сильно. Подобно другим статистическим методам, принцип может быть использован для обучения параметров модели, используя некоторые данные. Хотя, обычно, стандартные статистические методы предполагают, что общий вид модели фиксирован. Основная сила принципа MDL заключается в том, что он может быть использован для выбора общего вида модели и её параметров. Количественная характеристика (иногда только модели, иногда только параметров, иногда и модели, и параметров) называется гипотезой. Базовой идеей является рассмотрение двухступенчатого кода (без потерь), который кодирует данные ${\displaystyle D}$ путём сначала кодирования гипотезы ${\displaystyle H}$ в множестве рассматриваемых гипотез ${\displaystyle {\cal {H}}}$, а затем кодирования ${\displaystyle D}$ «с помощью» ${\displaystyle H}$. В простейшем контексте это просто означает «кодировку отклонения данных от предсказания, полученного посредством» ${\displaystyle H}$:

${\displaystyle {L(D)}=\min _{H\in {\cal {H}}}\ (\ L(H)+L(D|H)\ )\ }$

Гипотеза ${\displaystyle H}$, на которой достигается минимум тогда рассматривается как лучшее объяснение данных ${\displaystyle D}$. В качестве простого примера рассмотрим задачу регрессии: данные ${\displaystyle D}$ пусть состоят из последовательности точек ${\displaystyle D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$, множество ${\displaystyle {\cal {H}}}$ пусть будет множеством всех многочленов из ${\displaystyle X}$ в ${\displaystyle Y}$. Чтобы описать многочлен ${\displaystyle H}$ степени (скажем) ${\displaystyle k}$, следует сначала дискретизировать параметры до некоторой точности, затем нужно описать эту точность (натуральное число). Затем следовало бы описать степень ${\displaystyle k}$ (ещё одно натуральное число) и, наконец, следовало бы описать ${\displaystyle k+1}$ параметров. Полная длина будет ${\displaystyle L(H)}$. Затем описываем точки в ${\displaystyle D}$, используя некоторый фиксированный код для x-значений, а затем используя код для ${\displaystyle n}$ отклонений ${\displaystyle y_{i}-H(x_{i})}$.

На практике, часто (но не всегда) используют статистическую модель. Например, ассоциируют каждый многочлен ${\displaystyle H}$ с соответствующим условным распределением, тем самым указывая, что данные ${\displaystyle X}$, ${\displaystyle Y}$ нормально распределены со средним ${\displaystyle H(X)}$ и некоторым отклонением ${\displaystyle \sigma ^{2}}$, которые могут быть либо фиксированы, либо добавлены как параметры. Тогда набор гипотез ${\displaystyle {\cal {H}}}$ сокращается до линейной модели ${\displaystyle Y=H(X)+\epsilon }$ с ${\displaystyle H}$ в виде многочлена.

Более того, часто конкретные значения параметров напрямую не очень интересны, а интересны только, например, степень многочлена. В этом случае полагают множество ${\displaystyle {\cal {H}}}$ равным ${\displaystyle {\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}}$, где каждый элемент ${\displaystyle {\cal {H}}_{j}}$ представляет гипотезу, что данные лучшим образом описываются многочленом степени j. Тогда кодируют данные ${\displaystyle D}$ данной гипотезы ${\displaystyle {\cal {H}}_{j}}$ с помощью одночастевого кода, разработанного так, что когда некоторая гипотеза ${\displaystyle H\in {\cal {H}}_{j}}$ хорошо соответствует данным, код ${\displaystyle L(D|H)}$ короткий. Разработка таких кодов называется универсальным кодированием. Существуют различные типы универсальных кодов, которые можно использовать, часто дающие близкие длины для длинных последовательностей данных, но отличающиеся для коротких последовательностей. 'Лучшими' кодами (в смысле, что они имеют свойство минимаксной оптимальности) являются нормированные коды максимального правдоподобия (англ. normalized maximum likelihood codes, NML) или коды Штарькова. Очень полезный класс кодов — коды байесовского маргинального правдоподобия. Для семейства экспоненциальных распределений, когда используется априорное распределение Джеффриca и пространство параметров подходящим образом ограничено, они асимптотически совпадают с кодами NML. Это придвигает теорию MDL вплотную к объективному байесовскому выбору модели, к которой также иногда применяется априорное распределение Джеффриca, хотя по другим причинам.

Монета бросается 1000 раз и число выпадения орла или решки записывается. Рассмотрим два класса моделей:

• Первая является кодом, в который записывается 0 для орла и 1 для решки. Этот код представляет гипотезу, что монета симметрична (то есть выпадение орла и решки должно быть одинаково вероятно). Длина кода, согласно этому кодированию всегда, равна в точности 1000 битам.
• Вторая состоит из всех кодов, которые эффективны для несимметричной монеты, и представляют гипотезу, что монета не симметрична. Скажем, мы наблюдаем 510 выпадений орла и 490 выпадений решки. Тогда длина кода, соответствующая наилучшему кодированию, во втором классе моделей меньше 1000 бит.

По этой причине наивный статистический метод может выбрать вторую модель как лучшее объяснение данных. Однако подход MDL строил бы один код, основанный на гипотезе вместо использования лучшего кода. Этот код мог бы быть нормированным кодом максимального правдоподобия или байесовским кодом. Если такой код используется, полная длина кода, основанного на втором классе моделей, была бы больше 1000 бит. Поэтому заключение, которое следует неминуемо из подхода MDL, будет, что нет достаточных оснований для гипотезы о несимметричной монете, даже если лучший элемент второго класса моделей даёт лучшее соответствие данным.

Центральным понятиям для MDL теории является один-к-одному соответствие между длиной кода функций и распределениями вероятностей (это следует из неравенства Крафта — Макмиллана). Для любого распределения вероятности ${\displaystyle P}$ можно построить код ${\displaystyle C}$, такой, что длина (в битах) ${\displaystyle C(x)}$ равна ${\displaystyle -\log _{2}P(x)}$. Этот код минимизирует ожидаемую длину кода. И наоборот, если дан код ${\displaystyle C}$, можно построить распределение вероятности ${\displaystyle P}$, такое, что выполняется выше указанное утверждение. (Проблемы округления здесь игнорируются.) Другими словами, поиск эффективного кода эквивалентен поиску хорошего распределения вероятности.

Принцип MDL сильно связан с теорией вероятностей и статистикой через соответствие кодов и распределение вероятностей, упомянутое выше. Это привело некоторых исследователей к выводу, что принцип MDL эквивалентен байесовскому выводу — длина кода модели и данные в MDL соответствуют априорной вероятности и маргинальному правдоподобию в байесовской схеме[6].

В то время как байесовские алгоритмы часто полезны для построения эффективных MDL кодов, принцип MDL вмещает также другие коды, не являющиеся бaйесовскими. Примером служит нормированный код максимального правдоподобия Штарькова, который играет центральную роль в текущей теории MDL, но не имеет эквивалента в байесовском выводе. Более того, Риссанен подчёркивает, что нам не следует делать каких-либо предположений о верности процесса получения данных — на практике, класс моделей обычно является упрощением реальности, а потому не содержит каких-либо кодов или распределений вероятности, верных в объективном смысле[7][8]. В последней ссылке Риссанен подводит математическое обоснование принципа MDL к структурной функции Колмогорова.

Согласно философии MDL следует избегать байесовских методов, если они основываются на ненадёжной априорной вероятности, что может привести к плохим результатам. Априорные условия, приемлемые с точки зрения MDL, также предпочтительнее так называемого байесовкого объективного анализа. Здесь, однако, причины обычно другие[9].

• Алгоритмическая вероятность
• Алгоритмическая теория информации
• Индуктивное умозаключение
• Индуктивная вероятность
• Колмогоровская сложность
• Сообщение минимальной длины
• Бритва Оккама

• Minimum Description Length on the Web, by the University of Helsinki. Features readings, demonstrations, events and links to MDL researchers.
• Homepage of Jorma Rissanen, containing lecture notes and other recent material on MDL.
• Advances in Minimum Description Length, MIT Press, ISBN 0-262-07262-9.