Минимальная длина сообщения - Minimum message length
Минимальная длина сообщения (MML) - это байесовский теоретико-информационный метод сравнения и выбора статистических моделей. Он представляет собой формальное переформулирование теории информации бритвы Оккама : даже когда модели равны по своей мере соответствия наблюдаемым данным, модель, генерирующая наиболее краткое объяснение данных, с большей вероятностью будет правильной (где объяснение состоит из заявление модели с последующим кодированием данных без потерь с использованием указанной модели). MML был изобретен Крисом Уоллесом , впервые появившимся в основополагающей статье «Информационная мера для классификации». MML задуман не только как теоретическая конструкция, но и как метод, который можно применить на практике. Он отличается от родственной концепции сложности Колмогорова тем, что не требует использования полного по Тьюрингу языка для моделирования данных.
Определение
Shannon «s Математическая теория связи (1948) утверждает , что в оптимальном коде, длина сообщения (в двоичной системе ) о событии , где была вероятность , задается .
Теорема Байеса утверждает, что вероятность гипотезы (переменной) при наличии фиксированных свидетельств пропорциональна , которая, по определению условной вероятности , равна . Нам нужна модель (гипотеза) с наивысшей такой апостериорной вероятностью . Предположим, мы кодируем сообщение, которое представляет (описывает) как модель, так и данные вместе. Так как наиболее вероятная модель будет иметь самое короткое такое сообщение. Сообщение разбивается на две части: . Первая часть кодирует саму модель. Вторая часть содержит информацию (например, значения параметров или начальные условия и т. Д.), Которая при обработке моделью выводит наблюдаемые данные.
MML естественно и точно меняет сложность модели на степень соответствия. Формирование более сложной модели занимает больше времени (более длинная первая часть), но, вероятно, лучше соответствует данным (более короткая вторая часть). Таким образом, показатель MML не выберет сложную модель, если эта модель не окупится.
Непрерывные параметры
Одна из причин, по которой модель может быть длиннее, может быть просто потому, что ее различные параметры указаны с большей точностью, что требует передачи большего количества цифр. Большая часть возможностей MML заключается в том, что он умеет точно указывать параметры в модели, а также в различных приближениях, которые делают это возможным на практике. Это позволяет с пользой сравнить, скажем, модель с множеством неточно заданных параметров с моделью с меньшим количеством параметров, сформулированных более точно.
Ключевые особенности MML
- MML можно использовать для сравнения моделей разной структуры. Например, его самое раннее применение было в поиске моделей смеси с оптимальным количеством классов. Добавление дополнительных классов в смешанную модель всегда позволяет подгонять данные с большей точностью, но согласно MML это должно быть сопоставлено с дополнительными битами, необходимыми для кодирования параметров, определяющих эти классы.
- MML - это метод сравнения байесовских моделей . Это дает каждой модели оценку.
- MML является масштабно-инвариантным и статистически инвариантным. В отличие от многих байесовских методов выбора, MML не заботится о том, переходите ли вы от измерения длины к объему или от декартовых координат к полярным координатам.
- MML статистически согласован. Для таких задач, как проблема Неймана-Скотта (1948) или факторный анализ, где количество данных для каждого параметра ограничено выше, MML может оценить все параметры со статистической согласованностью .
- MML учитывает точность измерения. Он использует информацию Фишера (в приближении Уоллеса-Фримена 1987 года или другие гиперобъемы в других приближениях ) для оптимальной дискретизации непрерывных параметров. Следовательно, апостериорная всегда является вероятностью, а не плотностью вероятности.
- MML используется с 1968 года. Схемы кодирования MML были разработаны для нескольких распределений и для многих типов машинного обучения, включая неконтролируемую классификацию, деревья решений и графы, последовательности ДНК, байесовские сети , нейронные сети (пока только однослойные), сжатие изображений, сегментация изображений и функций и т. д.
Смотрите также
- Алгоритмическая вероятность
- Алгоритмическая теория информации
- Введение в грамматику
- Индуктивный вывод
- Индуктивная вероятность
- Колмогоровская сложность - абсолютная сложность (в пределах постоянной, в зависимости от конкретного выбора универсальной машины Тьюринга ); MML обычно является вычислимым приближением (см.)
- Минимальная длина описания - альтернатива, возможно, с другой (небайесовской) мотивацией, разработанная через 10 лет после MML.
- бритва Оккама
Рекомендации
Внешние ссылки
Оригинальная публикация:
- Уоллес; Бултон (август 1968 г.). «Информационная мера для классификации» . Компьютерный журнал . 11 (2): 185–194. DOI : 10.1093 / comjnl / 11.2.185 .
Книги:
- Уоллес, CS (май 2005 г.). Статистический и индуктивный вывод по минимальной длине сообщения . Информатика и статистика. Springer-Verlag. ISBN 978-0-387-23795-4 . CS1 maint: обескураженный параметр ( ссылка )
- Эллисон, Л. (2018). Кодирование бритвы Оккама . Springer. DOI : 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 . DOI : 10.1093 / comjnl / 42.4.270 .
- «Спецвыпуск о колмогоровской сложности» . Компьютерный журнал . 42 (4). 1999 г.
- Dowe, DL; Уоллес, CS (1997). Решение проблемы Неймана-Скотта с помощью минимальной длины сообщения . 28-й симпозиум по интерфейсу, Сидней, Австралия. Вычислительная техника и статистика . 28 . С. 614–618.
- История MML, последний доклад CSW .
- Needham, S .; Доу, Д. (2001). Длина сообщения как эффективная бритва Оккама в индукции дерева решений (PDF) . Proc. 8-й Международный семинар по ИИ и статистике . С. 253–260. (Показывает, как хорошо работает бритва Оккама при интерпретации как MML.)
- Эллисон, Л. (январь 2005 г.). «Модели для машинного обучения и интеллектуального анализа данных в функциональном программировании». Журнал функционального программирования . 15 (1): 15–32. DOI : 10.1017 / S0956796804005301 . S2CID 5218889 . ( Код MML, FP и Haskell ).
- Комли, JW; Доу, Д.Л. (апрель 2005 г.). «Глава 11: Минимальная длина сообщения, MDL и обобщенные байесовские сети с асимметричными языками» . In Grunwald, P .; Питт, Массачусетс; Myung, IJ (ред.). Достижения в минимальной длине описания: теория и приложения . MIT Press. С. 265–294. ISBN 978-0-262-07262-5 .
- Комли, Джошуа В .; Доу, Д.Л. (5–8 июня 2003 г.). Общие байесовские сети и асимметричные языки . Proc. 2-я Гавайская международная конференция по статистике и смежным областям. , .pdf . Comley & Dowe ( 2003 , 2005 ) - первые две статьи по байесовским сетям MML, использующим как дискретные, так и непрерывные параметры.
- Доу, Дэвид Л. (2010). «MML, гибридные байесовские сетевые графические модели, статистическая согласованность, инвариантность и уникальность» (PDF) . Справочник по философии науки (Том 7: Справочник по философии статистики) . Эльзевир. С. 901–982. ISBN 978-0-444-51862-0 .
- Минимальная длина сообщения (MML) , введение LA MML (альтернативный вариант MML) .
- Минимальная длина сообщения (MML), исследователи и ссылки .
- «Еще один сайт исследования MML» . Архивировано из оригинала 12 апреля 2017 года.
- Страница сноба для моделирования смеси MML .
- MITECS : Крис Уоллес написал статью о MML для MITECS. (Требуется учетная запись)
- mikko.ps : короткие вводные слайды Микко Койвисто в Хельсинки
- Метод информационного критерия Акаике ( AIC ) выбора модели и сравнение с MML: Dowe, DL; Gardner, S .; Оппи, Г. (декабрь 2007 г.). «Байес - это не бюст! Почему простота не проблема для байесовцев». Br. J. Philos. Sci . 58 (4): 709–754. DOI : 10.1093 / bjps / axm033 .