Мінімальна довжина повідомлення

Мініма́льна довжина́ повідо́млення (МДП, англ. minimum message length, MML) — формальне перевизначення Леза Оккама в теорії інформації: навіть якщо моделі не є рівними в точності допасованості до спостережених даних, та з них, що породжує найкоротше сукупне повідомлення, правдоподібніше є правильною (де повідомлення складається з вираження моделі, за яким слідує вираження даних, стисло закодованих із застосуванням цієї моделі). МДП було винайдено Крісом Воллесом, з першою появою в основоположній праці «An information measure for classification» Воллеса і Бултона 1968 року.

МДП передбачено не просто як теоретичну побудову, а як методику, яку може бути розгорнуто на практиці. Вона відрізняється від пов'язаного поняття колмогоровської складності тим, що не вимагає використання для моделювання даних мови, повної за Тюрінгом. Відношення між строгою МДП (СМДП, англ. Strict MML, SMML) та колмогоровською складностю окреслено в праці Воллеса та Доу 1999 року. Крім того, можна використовувати ряд математичних наближень «строгої» МДП — див., наприклад, глави 4 і 5 книги Воллеса (посмертно) 2005 року.

Визначення

«Математична теорія зв'язку» Шеннона (1949 року) стверджує, що в оптимальному коді довжина повідомлення (у двійковому кодуванні) події $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))$. Перша частина кодує саму модель. Друга частина містить інформацію (наприклад, значення параметрів або початкових умов тощо), яка при обробці моделлю дає на виході спостережені дані.

МДП природно й точно здійснює компроміс між складністю та допасованістю моделі. Складніша модель бере більше на визначення (довша перша частина), але ймовірно краще допасовується до даних (коротша друга частина). Таким чином, метрика МДП не обиратиме складнішої моделі, якщо ця модель не платитиме за себе.

Неперервнозначні параметри

Однією з причин, чому модель може бути довшою, є просто те, що різні її параметри вказано з вищою точністю, що відтак вимагає передавання більшої кількості цифр. Значна частина потужності МДП випливає з її обробки того, як точно вказувати параметри в моделі, а також різних наближень, як зробити це здійсненним на практиці. Це дозволяє їй з користю порівнювати, скажімо, модель із багатьма неточно вказаними параметрами з моделлю з меншою кількістю точніше вказаних параметрів.

Ключові властивості МДП

• МДП можливо застосовувати для порівняння моделей різної структури. Наприклад, її найпершим застосуванням було знаходження сумішевих моделей з оптимальним числом класів. Додавання додаткових класів до сумішевої моделі завжди дозволятиме допасовувати дані з вищою точністю, але згідно МДП це мусить зважуватися з додатковими бітами, необхідними для кодування параметрів, що визначають ці класи.
• МДП є методом баєсового порівняння моделей. Вона дає кожній моделі бал.
• МДП є масштабо-інваріантною та статистично інваріантною. На відміну від багатьох баєсових методів обирання, МДП не хвилює, якщо ви перейдете від вимірювання довжини до об'єму, чи від декартових координат до полярних.
• МДП є статистично конзистентною. Для задач на кшталт задачі Неймана-Скотта (1948 року) чи факторного аналізу, де обсяг даних на параметр обмежено згори, МДП може оцінювати всі параметри зі статистичною конзистентністю.
• МДП враховує точність вимірювання. Вона використовує інформацію за Фішером (в наближенні Воллеса-Фрімена 1987 року, або інших гіпер-об'ємах в інших наближеннях), щоби оптимально дискретувати неперервні параметри. Тому апостеріорне завжди є ймовірністю, а не густиною ймовірності.
• МДП застосовують з 1968 року. Схеми кодування МДП було розроблено для декількох розподілів та для багатьох типів систем машинного навчання, включно зі некерованою класифікацією, деревами та графами рішень, послідовностями ДНК, баєсовими мережами, нейронними мережами (наразі лише одношаровими), стисненням зображень, сегментуванням зображень та функцій тощо.

Див. також

• Алгоритмічна ймовірність
• Алгоритмічна теорія інформації
• Виведення граматик
• Індуктивне висновування
• Індуктивна ймовірність
• Колмогоровська складність — абсолютна складність (в межах сталої, що залежить від конкретного вибору універсальної машини Тюрінга); МДП зазвичай є обчислюваним наближенням (для опрацювання див. статтю Воллеса та Доу 1999 року в спеціальному випуску, згаданому нижче)
• Мінімальна довжина опису — припустимо небаєсова альтернатива з можливо відмінним обґрунтуванням, яку було запропоновано 10 роками пізніше — для порівняння див., наприклад, розд. 10.2 у книзі Воллеса (посмертно) 2005 року, розд. 11.4.3, стор. 272 [Архівовано 27 вересня 2016 у Wayback Machine.]–273 [Архівовано 27 вересня 2016 у Wayback Machine.] в Комлі та Доу 2005 року, та спеціальний випуск Computer Journal про колмогоровську складність № 42 (4) 1999 року.
• Лезо Оккама

Посилання

• Wallace; Boulton (August 1968). An information measure for classification. Computer Journal. 11 (2): 185—194. Архів оригіналу за 8 березня 2016. Процитовано 8 липня 2017. (англ.)
• Посилання на всі відомі публікації Кріса Воллеса [Архівовано 14 червня 2006 у Wayback Machine.]. (англ.)
• Wallace, C.S. (May 2005). Statistical and Inductive Inference by Minimum Message Length. Information Science and Statistics. Springer-Verlag. ISBN 0-387-23795-X.^{[недоступне посилання]} — приклади сторінок [Архівовано 3 серпня 2020 у Wayback Machine.]. (англ.)
• База даних публікацій Кріса Воллеса з пошуком [Архівовано 8 липня 2017 у Wayback Machine.]. (англ.)
• Wallace, C.S.; Dowe, D.L. (1999). Minimum Message Length and Kolmogorov Complexity. Computer Journal. 42 (4): 270—283. Архів оригіналу за 4 липня 2010. Процитовано 8 липня 2017. (англ.)
• Special Issue on Kolmogorov Complexity. Computer Journal. 42 (4). 1999. (англ.)
• Dowe, D.L.; Wallace, C.S. (1997). Resolving the Neyman-Scott Problem by Minimum Message Length. 28th Symposium on the interface, Sydney, Australia. Computing Science and Statistics. Т. 28. с. 614—618. Архів оригіналу за 4 серпня 2016. Процитовано 8 липня 2017. (англ.)
• Історія МДП, остання промова Кріса Воллеса [Архівовано 8 липня 2017 у Wayback Machine.]. (англ.)
• Needham, S.; Dowe, D. (2001). Message Length as an Effective Ockham's Razor in Decision Tree Induction (PDF). Proc. 8th International Workshop on AI and Statistics. с. 253—260. Архів оригіналу (PDF) за 23 вересня 2015. Процитовано 8 липня 2017. (Показує, як добре працює Лезо Оккама, будучи інтерпретованим як МДП.) (англ.)
• Allison, L. (Jan 2005). Models for machine learning and data mining in functional programming. J. Functional Programming. 15 (1): 15—32. Архів оригіналу за 17 листопада 2004. Процитовано 8 липня 2017. (МДП, рухома кома та код [Архівовано 8 липня 2017 у Wayback Machine.] Haskell).
• Comley, J.W.; Dowe, D.L. (April 2005). Chapter 11: Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages. У Grunwald, P.; Pitt, M. A.; Myung, I. J. (ред.). Advances in Minimum Description Length: Theory and Applications. M.I.T. Press. с. 265—294. ISBN 0-262-07262-9. Архів оригіналу за 19 червня 2006. Процитовано 8 липня 2017.

[Див. також Comley, Joshua W.; Dowe, D.L. (5-8 June 2003). General Bayesian Networks and Asymmetric Languages. Proc. 2nd Hawaii International Conference on Statistics and Related Fields. Архів оригіналу за 4 серпня 2016. Процитовано 8 липня 2017., .pdf [Архівовано 10 лютого 2006 у Wayback Machine.]. (англ.) Праці Комлі та Доу 2003 та 2005 років є першими двома працями про баєсові мережі МДП із застосуванням як дискретно-, так і неперервнозначних параметрів.]

• Dowe, David L. (2010). MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness (PDF). Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics). Elsevier. с. 901—982. ISBN 978-0-444-51862-0. Архів оригіналу (PDF) за 14 квітня 2016. Процитовано 8 липня 2017. (англ.)
• Minimum Message Length (MML) [Архівовано 10 листопада 2016 у Wayback Machine.], введення Ллойда Еллісона до МДП, (MML alt.) [Архівовано 8 липня 2017 у Wayback Machine.]. (англ.)
• Minimum Message Length (MML), дослідники та посилання [Архівовано 9 лютого 2006 у Wayback Machine.]. (англ.)
• Ще один вебсайт досліджень МДП. Архів оригіналу за 12 квітня 2017. (англ.)
• Сторінка Snob [Архівовано 27 вересня 2016 у Wayback Machine.] для сумішевого моделювання з МДП. (англ.)
• mikko.ps: Короткі ввідні слайди від Мікко Койвісто з Гельсінкі (англ.)
• Метод інформаційного критерію Акаіке (ІКА, англ. Akaike information criterion, AIC) для обирання моделі, та порівняння [Архівовано 4 серпня 2016 у Wayback Machine.] з МДП: Dowe, D.L.; Gardner, S.; Oppy, G. (Dec 2007). Bayes not Bust! Why Simplicity is no Problem for Bayesians. Brit. J. Philos. Sci. 58: 709—754. Архів оригіналу за 16 грудня 2008. Процитовано 8 липня 2017. (англ.)