Минимальная длина сообщения - Minimum message length

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

Определение

Шеннон с Математическая теория коммуникации (1948) утверждает, что в оптимальном коде длина сообщения (в двоичном формате) события ${ displaystyle E}$, ${ displaystyle operatorname {length} (E)}$, куда ${ displaystyle E}$ имеет вероятность ${ Displaystyle P (E)}$, дан кем-то ${ Displaystyle OperatorName {длина} (E) = - log _ {2} (P (E))}$.

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

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

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

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

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

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

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

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

Рекомендации

внешняя ссылка

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

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

Книги:

• Уоллес, К. (Май 2005 г.). Статистический и индуктивный вывод по минимальной длине сообщения. Информатика и статистика. Springer-Verlag. ISBN  978-0-387-23795-4.
• Эллисон, Л. (2018). Кодирование бритвы Оккама. Springer. Дои:10.1007/978-3-319-76433-7. ISBN  978-3319764320., по внедрению MML, и исходный код.

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

• Ссылки на все Крис Уоллес известные публикации.
• А доступная для поиска база данных публикаций Криса Уоллеса.
• Wallace, C.S .; Доу, Д.Л. (1999). «Минимальная длина сообщения и колмогоровская сложность». Компьютерный журнал. 42 (4): 270–283. CiteSeerX  10.1.1.17.321. Дои:10.1093 / comjnl / 42.4.270.CS1 maint: ref = harv (связь)
• «Спецвыпуск о колмогоровской сложности». Компьютерный журнал. 42 (4). 1999.
• Dowe, D.L .; Уоллес, К.С. (1997). Решение проблемы Неймана-Скотта с помощью минимальной длины сообщения. 28-й симпозиум по интерфейсу, Сидней, Австралия. Вычислительная техника и статистика. 28. С. 614–618.CS1 maint: ref = harv (связь)
• История MML, последний доклад CSW.
• Needham, S .; Доу, Д. (2001). Длина сообщения как эффективная бритва Оккама в индукции дерева решений (PDF). Proc. 8-й Международный семинар по ИИ и статистике. С. 253–260.CS1 maint: ref = harv (связь) (Покажи покажи бритва Оккама отлично работает при интерпретации как MML.)
• Эллисон, Л. (январь 2005 г.). «Модели для машинного обучения и интеллектуального анализа данных в функциональном программировании». Журнал функционального программирования. 15 (1): 15–32. Дои:10.1017 / S0956796804005301.CS1 maint: ref = harv (связь) (MML, FP и Haskell код ).
• Comley, J.W .; Доу, Д.Л. (Апрель 2005 г.). «Глава 11: Минимальная длина сообщения, MDL и обобщенные байесовские сети с асимметричными языками». In Grunwald, P .; Pitt, M. A .; Мён, И. Дж. (Ред.). Достижения в области минимальной длины описания: теория и приложения. M.I.T. Нажмите. С. 265–294. ISBN  978-0-262-07262-5.CS1 maint: ref = harv (связь)
• Комли, Джошуа В .; Доу, Д.Л. (5–8 июня 2003 г.). Общие байесовские сети и асимметричные языки. Proc. 2-я Гавайская международная конференция по статистике и смежным областям.CS1 maint: ref = harv (связь), .pdf. Комли и Доу (2003, 2005 ) - первые две работы по байесовским сетям MML, использующим как дискретные, так и непрерывные параметры.

• Доу, Дэвид Л. (2010). «MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» (PDF). Справочник по философии науки (Том 7: Справочник по философии статистики). Эльзевир. С. 901–982. ISBN  978-0-444-51862-0.CS1 maint: ref = harv (связь)
• Минимальная длина сообщения (MML), Введение в MML Лос-Анджелеса, (MML alt.).
• Минимальная длина сообщения (MML), исследователи и ссылки.
• «Еще один сайт исследования MML». Архивировано из оригинал 12 апреля 2017 г.
• Страница сноба для MML моделирование смеси.
• MITECS: Крис Уоллес написал запись о MML для MITECS. (Требуется учетная запись)
• mikko.ps: Короткие вводные слайды Микко Койвисто в Хельсинки
• Информационный критерий Акаике (AIC ) метод выбор модели, а сравнение с MML: Dowe, D.L .; Gardner, S .; Оппи, Г. (декабрь 2007 г.). «Байес - это не бюст! Почему простота не проблема для байесовцев». Br. J. Philos. Наука. 58 (4): 709–754. Дои:10.1093 / bjps / axm033. Архивировано из оригинал на 2008-12-16.CS1 maint: ref = harv (связь)