Минимальная длина описания - Minimum description length

Минимальная длина описания (MDL) относится к различным формализациям бритва Оккама на основе формальные языки раньше скупо описывать данные. В своей основной форме MDL - это выбор модели принцип: кратчайшее описание данных как лучшая модель. Эти описания предназначены для предоставления ориентированных на данные научные модели. Эта идея может быть распространена на другие формы индуктивного вывода и обучения, помимо выбора модели - ее также можно использовать для оценки и последовательного прогнозирования, например, без явного определения единой модели для данных. MDL - важное понятие в теория информации и теория вычислительного обучения. Важно отметить, что определенная существительная фраза "в минимальная длина описания принцип"используется по крайней мере для трех совершенно разных воплощений этой идеи, которые, хотя и взаимосвязаны, различаются по тому, что подразумевается под словом" описание ". В основном он используется для Йорма Риссанен Российская теория обучения, в которой модели представляют собой статистические гипотезы, а описания определяются как универсальные коды, является центральной концепцией теории информации (см. ниже). Во-вторых, он все еще часто используется для обозначения Риссанен 1978 год^[1] самая первая прагматическая попытка автоматического получения кратких описаний, связанных с Байесовский информационный критерий (BIC). В-третьих, его часто используют в Алгоритмическая теория информации, где длина описания последовательности данных - это длина наименьшей программы, которая выводит этот набор данных. В этом контексте он также известен как «идеализированный» принцип MDL и тесно связан с Теория индуктивного вывода Соломонова, заключающаяся в том, что лучшая модель набора данных - это его кратчайший самораспаковывающийся архив.

Обзор

Выбор минимальной длины описания доступных данных, поскольку лучшая модель учитывает принцип идентифицированный как бритва Оккама. До появления компьютерного программирования создание таких описаний было интеллектуальным трудом научных теоретиков. Это было гораздо менее формально, чем в компьютерный век. Если у двух ученых возникнут теоретические разногласия, они редко смогут формально применяют бритву Оккама, чтобы выбирать между своими теориями. У них будут разные наборы данных и, возможно, разные языки описания. Тем не менее, наука, продвинутая вперед по мере того, как бритва Оккама, была неофициальным руководством в принятии решения, какая модель лучше всего.

С появлением формальных языков и компьютерного программирования бритва Оккама получила математическое определение. Модели данного набора наблюдений, закодированные в виде битов данных, могут быть созданы в форме компьютерных программ, которые выводят эти данные. Тогда бритва Оккама могла формально выберите самую короткую программу, измеренную в битах этого алгоритмическая информация, как лучшая модель.

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

Двухчастные коды

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

MDL в машинном обучении

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

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

На практике при нахождении модели машинного обучения, которая наилучшим образом соответствует данным в соответствии с принципом MDL, выбирается модель, которая минимизирует длину двухчастного кода (программы). Например, в контролируемом случае изучения списка наиболее подходящих правил (вероятностная форма список решений ) из набора данных^[2], выбирается список правил, который минимизирует код, состоящий из двух частей: 1) код, который однозначно определяет список правил с учетом всех возможных списков правил, которые могут быть сгенерированы из этого набора данных, т. е. с учетом количества переменных и их возможные комбинации; и 2) код, который возвращает набор данных с учетом конкретного списка правил, как определено в первом коде. Первый код специально создан, чтобы избежать переобучения за счет штрафов за более сложные списки правил, которые, естественно, были бы более склонны к переобучению. Обратите внимание, что использование кода, состоящего из двух частей, необходимо, когда нужно различать разные модели, например, в случае поиска модели и ее параметров, которые наилучшим образом соответствуют данным. Это контрастирует с задачей простого желания знать размер модели (например, количество правил в списке правил), необходимый для наилучшей производительности.

Недавние работы по алгоритмическому обучению MDL

Недавнее машинное MDL-обучение алгоритмических, в отличие от статистических, моделей данных привлекает все большее внимание с увеличением доступности данных, вычислительных ресурсов и теоретических достижений.^[3]^[4] Подходы сообщаются растущим полем общий искусственный интеллект. Незадолго до смерти Марвин Мински решительно поддержал это направление исследований, заявив:^[5]

«Мне кажется, что самым важным открытием со времен Гёделя было открытие Чайтиным, Соломоновым и Колмогоровым концепции под названием« Алгоритмическая вероятность », которая представляет собой фундаментальную новую теорию того, как делать прогнозы на основе совокупности опытов, и это прекрасная теория. каждый должен изучить его, но у него есть одна проблема, а именно: вы не можете вычислить то, что предсказывает эта теория, потому что это слишком сложно, требует бесконечного объема работы. Однако должна быть возможность сделать практические приближения к Chaitin , Колмогоров, теория Соломонова, которая дает более точные прогнозы, чем все, что у нас есть сегодня. Каждый должен узнать все об этом и провести остаток своей жизни, работая над этим ».

Панельная дискуссия «Пределы понимания»

Всемирный фестиваль науки, Нью-Йорк, 14 декабря 2014 г.

Статистическое обучение MDL

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

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

Основываясь на этом, в 1978 году Йорма Риссанен опубликовал алгоритм обучения MDL с использованием статистическое понятие информации а не алгоритмической информации. Он начинается с этой идеи: все статистическое обучение направлено на поиск закономерностей в данных, и лучшая гипотеза для описания закономерностей в данных также является той, которая способна статистически сжимайте данные максимально. Как и другие статистические методы, его можно использовать для изучения параметров модели с использованием некоторых данных. Однако обычно стандартные статистические методы предполагают, что общая форма модели фиксирована. Основная сила MDL в том, что с его помощью можно также выбрать общий вид модели и ее параметры. Интересующая величина (иногда просто модель, иногда просто параметры, иногда и то, и другое одновременно) называется гипотезой. Основная идея состоит в том, чтобы рассмотреть (без потерь) двухступенчатый код который кодирует данные ${ displaystyle D}$ с длиной ${ Displaystyle {L (D)}}$ сначала кодируя гипотезу ${ displaystyle H}$ в совокупности рассмотренных гипотез ${ displaystyle { cal {H}}}$ а затем кодирование ${ displaystyle D}$ "с помощью" ${ displaystyle H}$ ; в простейшем контексте это просто означает «кодирование отклонений данных от прогнозов, сделанных ${ displaystyle H}$ :

{ Displaystyle {L (D)} = мин _ {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)}$ короткий. Дизайн таких кодов называется универсальное кодирование. Существуют различные типы универсальных кодов, которые можно использовать, часто дающие одинаковые длины для длинных последовательностей данных, но различающиеся для коротких. «Лучшими» (в том смысле, что он обладает свойством минимаксной оптимальности) являются нормализованная максимальная вероятность (NML) или Штарков коды. Довольно полезный класс кодов - это Байесовские коды предельного правдоподобия. Для экспоненциальных семейств распределений, когда используется апор Jeffreys и пространство параметров соответствующим образом ограничено, они асимптотически совпадают с кодами NML; это приводит теорию MDL в тесный контакт с объективным выбором модели Байеса, в котором также иногда принимают априорное положение Джеффриса, хотя и по другим причинам. Подход MDL к выбору модели »дает критерий выбора, формально идентичный критерию BIC подход"^[7] для большого количества образцов.

Пример статистического изучения MDL

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

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

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

Статистическая запись MDL

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

Ограничения статистического изучения MDL

Язык описания статистических MDL не является универсальным в вычислительном отношении. Поэтому он даже в принципе не может изучить модели рекурсивных природных процессов.

Связанные понятия

Статистическое изучение MDL очень сильно связано с теория вероятности и статистика через соответствие между кодами и распределениями вероятностей, упомянутыми выше. Это заставило некоторых исследователей рассматривать MDL как эквивалент Байесовский вывод: длина кода модели и данных вместе в MDL соответствуют соответственно априорная вероятность и предельная вероятность в байесовской структуре.^[8]

Хотя байесовский механизм часто бывает полезен при построении эффективных кодов MDL, структура MDL также поддерживает другие коды, которые не являются байесовскими. Примером может служить Штарков. нормализованный код максимального правдоподобия, который играет центральную роль в современной теории MDL, но не имеет эквивалента в байесовском выводе. Кроме того, Риссанен подчеркивает, что мы не должны делать никаких предположений относительно истинный процесс генерации данных: на практике класс модели обычно является упрощением реальности и, следовательно, не содержит никакого кода или распределения вероятностей, которые являются истинными в любом объективном смысле.^[9]^[10] В последней упомянутой ссылке Риссанен основывает математическую основу MDL на Структурная функция Колмогорова.

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

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

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

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

Смотрите также

дальнейшее чтение

Минимальная длина описания в Интернете, Университетом Хельсинки. Содержит чтения, демонстрации, мероприятия и ссылки на исследователей MDL.
Домашняя страница Йормы Риссанен, содержащий конспекты лекций и другие недавние материалы по MDL.
Улучшение минимальной длины описания, MIT Press, ISBN 0-262-07262-9.

[1] Риссанен, Дж. (Сентябрь 1978 г.). «Моделирование по кратчайшему описанию данных». Automatica. 14 (5): 465–471. Дои:10.1016/0005-1098(78)90005-5.

[2] Proença, Hugo; ван Леувен, Маттейс (май 2019 г.). «Интерпретируемая мультиклассовая классификация по спискам правил на основе MDL». arXiv:1905.00328. Дои:10.1016 / j.ins.2019.10.050. Цитировать журнал требует | журнал = (помощь)

[3] Зенил, Гектор; Киани, Нарсис А .; Zea, Allan A .; Тегнер, Джеспер (январь 2019 г.). «Причинная деконволюция алгоритмическими генеративными моделями». Природа Машинный интеллект. 1 (1): 58–66. Дои:10.1038 / с42256-018-0005-0. HDL:10754/630919.

[4] «Модернизация машинного обучения: ИИ, думающий как ученый». Природа Машинный интеллект: 1. 28 января 2019. Дои:10.1038 / с42256-019-0026-3.

[5] ttps://www.youtube.com/watch?v=DfY-DRsE86s&feature=youtu.be&t=5402

[peter-6] Грюнвальд, Питер (июнь 2004 г.). «Учебное введение в принцип минимальной длины описания». arXiv:математика / 0406077. Bibcode:2004математика ...... 6077G. Цитировать журнал требует | журнал = (помощь)

[7] Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2009). «Оценка и выбор модели». Элементы статистического обучения. Серии Спрингера в статистике. С. 219–259. Дои:10.1007/978-0-387-84858-7_7. ISBN 978-0-387-84857-0.

[mackay-8] MacKay, Дэвид Дж. К .; Кей, Дэвид Дж. К. Мак (2003). Теория информации, логические выводы и алгоритмы обучения. Издательство Кембриджского университета. ISBN 978-0-521-64298-9.^{[страница нужна ]}

[cwi-9] Риссанен, Йорма. "Домашняя страница Йормы Риссанен". Архивировано из оригинал на 2015-12-10. Получено 2010-07-03.^{[самостоятельно опубликованный источник? ]}

[springer-10] Риссанен, Дж. (2007). Информация и сложность статистического моделирования. Springer. Получено 2010-07-03.^{[страница нужна ]}

[volker-11] Наннен, Волкер (май 2010 г.). "Краткое введение в выбор модели, колмогоровскую сложность и минимальную длину описания (MDL)". arXiv:1005.2364. Bibcode:2010arXiv1005.2364N. Цитировать журнал требует | журнал = (помощь)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]