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

Принцип минимальной длины описания (англ. minimum description length, MDL) — это формализация бритвы Оккама, в которой лучшая гипотеза (модель и её параметры) для данного набора данных это та, которая ведёт к лучшему сжиманию данных. Принцип MDL предложил Йорма Риссанен в 1978 году. Принцип является важной концепцией в теории информации и теории вычислительного обучения.

Обзор

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

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

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

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

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

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

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

MDL в сравнении с теорией логического вывода Соломонова

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

Вывод

Однако эта математическая теория не даёт практического метода получения вывода. Наиболее важные причины этого:

• Колмогоровская сложность не вычислима — нет алгоритма, который по произвольной последовательности данных выдаёт кратчайшую программу, воспроизводящую данные.
• Колмогоровская сложность зависит от того, какой компьютерный язык используется. Выбор языка произволен, но он влияет на сложность на некоторую дополнительную константу. По этой причине константа в теории колмогоровской сложности отбрасывается. На практике, однако, доступно лишь небольшое количество данных, так что константы могут иметь очень большое влияние на результаты вывода — хорошие результаты при работе с ограниченным набором данных не гарантируется.

MDL пытается бороться с этой проблемой посредством:

• Ограничения набора разрешённых кодов так, что становится возможным (вычислительно) найти наименьшую длину кода для данных согласно разрешённым кодам.
• Выбора кодов, которые обоснованно эффективны независимо от данных. Идея «обоснованной эффективности» отражается в идее «универсального кода».

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

Пример MDL

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

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

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

MDL обозначение

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

Связанные концепции

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

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

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

Другие системы

MDL не был первым подходом информационно-теоретического обучения. Ещё в 1968 году Уоллес и Болтон ввели связанную концепцию, названную сообщением минимальной длины (англ. minimum message length, MML). Разница между MDL и MML является источником постоянной путаницы. Внешне методы выглядят большей частью эквивалентными, но есть некоторые существенные отличия, особенно в интерпретации:

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

См. также

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

Литература для дальнейшего чтения

• 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.