Минимальная длина сообщения

Минимальная длина сообщения ( MML ) — это байесовский метод теории информации для сравнения и выбора статистических моделей. ^[1] Он представляет собой формальное в теории информации переформулирование бритвы Оккама : даже когда модели равны по степени точности соответствия наблюдаемым данным, та модель, которая дает наиболее краткое объяснение с большей вероятностью будет правильной данных (когда объяснение состоит из формулировку модели с последующим без потерь кодированием данных с использованием заявленной модели). MML был изобретен Крисом Уоллесом , впервые появившимся в основополагающей статье «Информационная мера классификации». ^[2] ММЛ задуман не просто как теоретическая конструкция, а как метод, который можно применять на практике. ^[3] Он отличается от родственной концепции колмогоровской сложности тем, что не требует использования полного по Тьюрингу языка для моделирования данных. ^[4]

Определение

Шеннона В «Математической теории связи» (1948) говорится, что в оптимальном коде длина сообщения (в двоичном формате) о событии $E$ , $\operatorname {length} (E)$ , где $E$ имеет вероятность $P(E)$ , определяется $\operatorname {length} (E)=-\log _{2}(P(E))$ .

Теорема Байеса утверждает, что вероятность (переменной) гипотезы $H$ при наличии фиксированных доказательств $E$ пропорционально $P(E|H)P(H)$ , которая по определению условной вероятности равна $P(H\land E)$ . Нам нужна модель (гипотеза) с наибольшей такой апостериорной вероятностью . Предположим, мы кодируем сообщение, которое представляет (описывает) одновременно модель и данные. С $\operatorname {length} (H\land E)=-\log _{2}(P(H\land E))$ , наиболее вероятная модель будет иметь самое короткое такое сообщение. Сообщение разбивается на две части: $-\log _{2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E|H))$ . Первая часть кодирует саму модель. Вторая часть содержит информацию (например, значения параметров или начальные условия и т. д.), которая при обработке моделью выводит наблюдаемые данные.

MML естественным и точным образом меняет сложность модели на ее соответствие. Более сложная модель требует больше времени для формулирования (более длинная первая часть), но, вероятно, лучше соответствует данным (более короткая вторая часть). Таким образом, метрика MML не будет выбирать сложную модель, если она не окупит себя.

Непрерывные параметры

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

Ключевые особенности ММЛ

MML можно использовать для сравнения моделей различной структуры. Например, его самое раннее применение заключалось в поиске смешанных моделей с оптимальным количеством классов. Добавление дополнительных классов в смешанную модель всегда позволит подобрать данные с большей точностью, но согласно MML это необходимо сопоставлять с дополнительными битами, необходимыми для кодирования параметров, определяющих эти классы.
MML — это метод сравнения байесовских моделей . Это дает каждой модели балл.
MML масштабно-инвариантен и статистически инвариантен. В отличие от многих методов байесовского выбора, MML не заботится о том, переходите ли вы от измерения длины к объему или от декартовых координат к полярным координатам.
ММЛ статистически последователен. Для таких задач, как задача Неймана-Скотта (1948) или факторный анализ, где количество данных на параметр ограничено сверху, MML может оценить все параметры со статистической согласованностью .
MML обеспечивает точность измерений. Он использует информацию Фишера (в приближении Уоллеса-Фримена 1987 года или другие гиперобъемы в других приближениях ) для оптимальной дискретизации непрерывных параметров. Следовательно, апостериорное всегда является вероятностью, а не плотностью вероятности.
MML используется с 1968 года. Схемы кодирования MML были разработаны для нескольких дистрибутивов и многих видов машинного обучения, включая неконтролируемую классификацию, деревья и графики решений, последовательности ДНК, байесовские сети , нейронные сети (пока только однослойные), сжатие изображений, сегментация изображений и функций и т. д.

См. также

Алгоритмическая вероятность
Алгоритмическая теория информации
Грамматическая индукция
Индуктивный вывод
Индуктивная вероятность
Колмогоровская сложность – абсолютная сложность (в пределах константы, в зависимости от конкретного выбора универсальной машины Тьюринга ); MML обычно представляет собой вычислимое приближение (см. ^[4])
Минимальная длина описания – альтернатива с возможно другой (небайесовской) мотивацией, разработанная через 10 лет после MML.
Бритва Оккама

Ссылки

^ Уоллес, CS (Кристофер С.), -2004 г. (2005). Статистический и индуктивный вывод по минимальной длине сообщения . Нью-Йорк: Спрингер. ISBN 9780387237954 . OCLC 62889003 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )
^ Уоллес, CS; Бултон, DM (1 августа 1968 г.). «Информационная мера классификации» . Компьютерный журнал . 11 (2): 185–194. дои : 10.1093/comjnl/11.2.185 . ISSN 0010-4620 .
^ Эллисон, Ллойд. (2019). Кодирование по «бритве Оккама» . Спрингер. ISBN 978-3030094881 . OCLC 1083131091 .
^ Перейти обратно: ^а ^б Уоллес, CS; Доу, Д.Л. (1 января 1999 г.). «Минимальная длина сообщения и колмогоровская сложность» . Компьютерный журнал . 42 (4): 270–283. дои : 10.1093/comjnl/42.4.270 . ISSN 0010-4620 .

Внешние ссылки

Оригинальная публикация:

Уоллес; Бултон (август 1968 г.). «Информационная мера классификации» . Компьютерный журнал . 11 (2): 185–194. дои : 10.1093/comjnl/11.2.185 .

Книги:

Уоллес, CS (май 2005 г.). Статистический и индуктивный вывод по минимальной длине сообщения . Информатика и статистика. Спрингер-Верлаг. дои : 10.1007/0-387-27656-4 . ISBN 978-0-387-23795-4 .
Эллисон, Л. (2018). Кодирование по «бритве Оккама» . Спрингер. дои : 10.1007/978-3-319-76433-7 . ISBN 978-3319764320 . S2CID 19136282 . , о реализации MML и исходном коде .

Ссылки по теме:

Ссылки на все Криса Уоллеса . известные публикации
База данных публикаций Криса Уоллеса с возможностью поиска .
Уоллес, CS; Доу, Д.Л. (1999). «Минимальная длина сообщения и колмогоровская сложность». Компьютерный журнал . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . дои : 10.1093/comjnl/42.4.270 .
«Спецвыпуск о колмогоровской сложности» . Компьютерный журнал . 42 (4). 1999. ^{[ мертвая ссылка ]}
Доу, Д.Л.; Уоллес, CS (1997). Решение проблемы Неймана-Скотта по минимальной длине сообщения . 28-й симпозиум по интерфейсу, Сидней, Австралия. Информатика и статистика . Том. 28. стр. 614–618.
История ММЛ, последнее выступление CSW .
Нидэм, С.; Доу, Д. (2001). Длина сообщения как эффективная бритва Оккама при индукции дерева решений (PDF) . Учеб. 8-й международный семинар по искусственному интеллекту и статистике . стр. 253–260. (Показывает, как хорошо работает бритва Оккама , если ее интерпретировать как MML.)
Эллисон, Л. (январь 2005 г.). «Модели машинного обучения и интеллектуального анализа данных в функциональном программировании» . Журнал функционального программирования . 15 (1): 15–32. дои : 10.1017/S0956796804005301 . S2CID 5218889 . MML, FP и Haskell ( код ).
Комли, JW; Доу, Д.Л. (апрель 2005 г.). «Глава 11: Минимальная длина сообщения, MDL и обобщенные байесовские сети с асимметричными языками» . В Грюнвальде П.; Питт, Массачусетс; Мьюнг, Эй Джей (ред.). Достижения в минимальной длине описания: теория и приложения . МТИ Пресс. стр. 265–294. ISBN 978-0-262-07262-5 .
Комли, Джошуа В.; Доу, Д.Л. (5–8 июня 2003 г.). Общие байесовские сети и асимметричные языки . Учеб. 2-я Гавайская международная конференция по статистике и смежным областям. , .pdf . Comley & Dowe ( 2003 , 2005 ) — первые две статьи о байесовских сетях MML, в которых используются как дискретные, так и непрерывные параметры.

Доу, Дэвид Л. (2010). «MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» (PDF) . Справочник по философии науки (Том 7: Справочник по философии статистики) . Эльзевир. стр. 901–982. ISBN 978-0-444-51862-0 .
Минимальная длина сообщения (MML) , введение в MML в Лос-Анджелесе (альтернативный вариант MML) .
Минимальная длина сообщения (MML), исследователи и ссылки .
«Еще один веб-сайт исследований MML» . Архивировано из оригинала 12 апреля 2017 года.
Страница Snob для моделирования смесей MML .
MITECS : Крис Уоллес написал статью о MML для MITECS. (Требуется учетная запись)
mikko.ps : Короткие вводные слайды Микко Койвисто в Хельсинки
по информационному критерию Акаике ( AIC Метод выбора модели ) и сравнение с MML: Доу, Д.Л.; Гарднер, С.; Оппи, Г. (декабрь 2007 г.). «Байесианство не крах! Почему простота не является проблемой для байесовцев». Бр. Дж. Филос. Наука . 58 (4): 709–754. дои : 10.1093/bjps/axm033 .

[1] Уоллес, CS (Кристофер С.), -2004 г. (2005). Статистический и индуктивный вывод по минимальной длине сообщения . Нью-Йорк: Спрингер. ISBN 9780387237954 . OCLC 62889003 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[2] Уоллес, CS; Бултон, DM (1 августа 1968 г.). «Информационная мера классификации» . Компьютерный журнал . 11 (2): 185–194. дои : 10.1093/comjnl/11.2.185 . ISSN 0010-4620 .

[3] Эллисон, Ллойд. (2019). Кодирование по «бритве Оккама» . Спрингер. ISBN 978-3030094881 . OCLC 1083131091 .

[:0-4] Перейти обратно: ^а ^б Уоллес, CS; Доу, Д.Л. (1 января 1999 г.). «Минимальная длина сообщения и колмогоровская сложность» . Компьютерный журнал . 42 (4): 270–283. дои : 10.1093/comjnl/42.4.270 . ISSN 0010-4620 .

[1]

[2]

[3]

[4]