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

Формальная информационная теория перефразирования бритвы Оккама

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

Определение

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

Теорема Байеса утверждает, что вероятность (переменной) гипотезы при фиксированных доказательствах пропорциональна , что, по определению условной вероятности , равно . Мы хотим модель (гипотезу) с самой высокой такой апостериорной вероятностью . Предположим, мы кодируем сообщение, которое представляет (описывает) как модель, так и данные совместно. Поскольку , наиболее вероятная модель будет иметь самое короткое такое сообщение. Сообщение разбивается на две части: . Первая часть кодирует саму модель. Вторая часть содержит информацию (например, значения параметров или начальных условий и т. д.), которая при обработке моделью выводит наблюдаемые данные. ${\displaystyle H}$ ${\displaystyle E}$ ${\displaystyle P(E|H)P(H)}$ ${\displaystyle P(H\land 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 учитывает точность измерения. Он использует информацию Фишера (в приближении Уоллеса-Фримена 1987 года или другие гиперобъемы в других приближениях) для оптимальной дискретизации непрерывных параметров. Поэтому апостериорная вероятность всегда является вероятностью, а не плотностью вероятности.
• MML используется с 1968 года. Схемы кодирования MML были разработаны для нескольких распределений и многих видов машинного обучения, включая неконтролируемую классификацию, деревья решений и графы, последовательности ДНК, байесовские сети , нейронные сети (пока только однослойные), сжатие изображений, сегментацию изображений и функций и т. д.

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

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

Ссылки

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

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

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

• Уоллес; Бултон (август 1968). «Информационная мера для классификации». Computer Journal . 11 (2): 185–194. doi : 10.1093/comjnl/11.2.185 .

Книги:

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

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

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

• Dowe, David L. (2010). "MML, гибридные байесовские сетевые графические модели, статистическая согласованность, инвариантность и уникальность" (PDF) . Справочник по философии науки (Том 7: Справочник по философии статистики) . Elsevier. стр. 901–982. ISBN 978-0-444-51862-0.
• Минимальная длина сообщения (MML), введение MML в Лос-Анджелесе (MML alt.).
• Минимальная длина сообщения (MML), исследователи и ссылки.
• "Еще один сайт исследований MML". Архивировано из оригинала 12 апреля 2017 г.
• Страница Snob для моделирования смесей MML .
• MITECS: Крис Уоллес написал запись на MML для MITECS. (Требуется учетная запись)
• mikko.ps: Короткие вводные слайды Микко Койвисто в Хельсинки
• Метод выбора модели на основе информационного критерия Акаике ( AIC ) и сравнение с MML: Dowe, DL; Gardner, S.; Oppy, G. (декабрь 2007 г.). «Bayes not Bust! Why Simplicity is no Problem for Bayesians». Br. J. Philos. Sci . 58 (4): 709–754. doi :10.1093/bjps/axm033.