Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Мініма льна довжина повідо млення МДП англ minimum message length MML формальне перевизначення Леза Оккама в теорії інфо

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

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

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

Визначення

«Математична теорія зв'язку» Шеннона (1949 року) стверджує, що в оптимальному коді довжина повідомлення (у двійковому кодуванні) події image, image, де image має ймовірність image, задається як image.

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

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

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

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

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

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

Див. також

Посилання

  • Wallace; Boulton (August 1968). . Computer Journal. 11 (2): 185—194. Архів оригіналу за 8 березня 2016. Процитовано 8 липня 2017. (англ.)
  • Посилання на всі відомі публікації Кріса Воллеса [ 14 червня 2006 у Wayback Machine.]. (англ.)
  • (May 2005). Statistical and Inductive Inference by Minimum Message Length. Information Science and Statistics. Springer-Verlag. ISBN .[недоступне посилання] — приклади сторінок [ 3 серпня 2020 у Wayback Machine.]. (англ.)
  • База даних публікацій Кріса Воллеса з пошуком [ 8 липня 2017 у Wayback Machine.]. (англ.)
  • Wallace, C.S.; Dowe, D.L. (1999). . 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). . 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). (PDF). Proc. 8th International Workshop on AI and Statistics. с. 253—260. Архів оригіналу (PDF) за 23 вересня 2015. Процитовано 8 липня 2017. (Показує, як добре працює Лезо Оккама, будучи інтерпретованим як МДП.) (англ.)
  • Allison, L. (Jan 2005). . J. Functional Programming. 15 (1): 15—32. Архів оригіналу за 17 листопада 2004. Процитовано 8 липня 2017. (МДП, рухома кома та код [ 8 липня 2017 у Wayback Machine.] Haskell).
  • Comley, J.W.; Dowe, D.L. (April 2005). . У Grunwald, P.; Pitt, M. A.; Myung, I. J. (ред.). Advances in Minimum Description Length: Theory and Applications. M.I.T. Press. с. 265—294. ISBN . Архів оригіналу за 19 червня 2006. Процитовано 8 липня 2017.
[Див. також Comley, Joshua W.; Dowe, D.L. (5-8 June 2003). . Proc. 2nd Hawaii International Conference on Statistics and Related Fields. Архів оригіналу за 4 серпня 2016. Процитовано 8 липня 2017., .pdf [ 10 лютого 2006 у Wayback Machine.]. (англ.) Праці Комлі та Доу 2003 та 2005 років є першими двома працями про баєсові мережі МДП із застосуванням як дискретно-, так і неперервнозначних параметрів.]


Дата публікації:
Minima lna dovzhina povido mlennya MDP angl minimum message length MML formalne pereviznachennya Leza Okkama v teoriyi informaciyi navit yaksho modeli ne ye rivnimi v tochnosti dopasovanosti do sposterezhenih danih ta z nih sho porodzhuye najkorotshe sukupne povidomlennya pravdopodibnishe ye pravilnoyu de povidomlennya skladayetsya z virazhennya modeli za yakim sliduye virazhennya danih stislo zakodovanih iz zastosuvannyam ciyeyi modeli MDP bulo vinajdeno en z pershoyu poyavoyu v osnovopolozhnij praci An information measure for classification Vollesa i Bultona 1968 roku MDP peredbacheno ne prosto yak teoretichnu pobudovu a yak metodiku yaku mozhe buti rozgornuto na praktici Vona vidriznyayetsya vid pov yazanogo ponyattya kolmogorovskoyi skladnosti tim sho ne vimagaye vikoristannya dlya modelyuvannya danih movi povnoyi za Tyuringom Vidnoshennya mizh strogoyu MDP SMDP angl Strict MML SMML ta kolmogorovskoyu skladnostyu okresleno v praci Vollesa ta Dou 1999 roku Krim togo mozhna vikoristovuvati ryad matematichnih nablizhen strogoyi MDP div napriklad glavi 4 i 5 knigi Vollesa posmertno 2005 roku Viznachennya Matematichna teoriya zv yazku Shennona 1949 roku stverdzhuye sho v optimalnomu kodi dovzhina povidomlennya u dvijkovomu koduvanni podiyi E displaystyle E length E displaystyle operatorname length E de E displaystyle E maye jmovirnist P E displaystyle P E zadayetsya yak length E log2 P E displaystyle operatorname length E log 2 P E Teorema Bayesa stverdzhuye sho jmovirnist zminnoyi gipotezi H displaystyle H za zadanogo nezminnogo svidchennya E displaystyle E ye proporcijnoyu do P E H P H displaystyle P E H P H sho za viznachennyam umovnoyi jmovirnosti dorivnyuye P H E displaystyle P H land E Mi hochemo gipotezi modeli z najvishoyu takoyu aposteriornoyu jmovirnistyu Pripustimo sho mi koduyemo povidomlennya sho predstavlyaye opisuye yak model tak i dani razom Oskilki length H E log2 P H E displaystyle operatorname length H land E log 2 P H land E najimovirnisha model matime najkorotshe take povidomlennya Ce povidomlennya skladayetsya z dvoh chastin log2 P H E log2 P H log2 P E H displaystyle log 2 P H land E log 2 P H log 2 P E H Persha chastina koduye samu model Druga chastina mistit informaciyu napriklad znachennya parametriv abo pochatkovih umov tosho yaka pri obrobci modellyu daye na vihodi sposterezheni dani MDP prirodno j tochno zdijsnyuye kompromis mizh skladnistyu ta dopasovanistyu modeli Skladnisha model bere bilshe na viznachennya dovsha persha chastina ale jmovirno krashe dopasovuyetsya do danih korotsha druga chastina Takim chinom metrika MDP ne obiratime skladnishoyi modeli yaksho cya model ne platitime za sebe Neperervnoznachni parametriOdniyeyu z prichin chomu model mozhe buti dovshoyu ye prosto te sho rizni yiyi parametri vkazano z vishoyu tochnistyu sho vidtak vimagaye peredavannya bilshoyi kilkosti cifr Znachna chastina potuzhnosti MDP viplivaye z yiyi obrobki togo yak tochno vkazuvati parametri v modeli a takozh riznih nablizhen yak zrobiti ce zdijsnennim na praktici Ce dozvolyaye yij z koristyu porivnyuvati skazhimo model iz bagatma netochno vkazanimi parametrami z modellyu z menshoyu kilkistyu tochnishe vkazanih parametriv Klyuchovi vlastivosti MDPMDP mozhlivo zastosovuvati dlya porivnyannya modelej riznoyi strukturi Napriklad yiyi najpershim zastosuvannyam bulo znahodzhennya en z optimalnim chislom klasiv Dodavannya dodatkovih klasiv do sumishevoyi modeli zavzhdi dozvolyatime dopasovuvati dani z vishoyu tochnistyu ale zgidno MDP ce musit zvazhuvatisya z dodatkovimi bitami neobhidnimi dlya koduvannya parametriv sho viznachayut ci klasi MDP ye metodom bayesovogo porivnyannya modelej Vona daye kozhnij modeli bal MDP ye masshtabo invariantnoyu ta statistichno invariantnoyu Na vidminu vid bagatoh bayesovih metodiv obirannya MDP ne hvilyuye yaksho vi perejdete vid vimiryuvannya dovzhini do ob yemu chi vid dekartovih koordinat do polyarnih MDP ye statistichno konzistentnoyu Dlya zadach na kshtalt zadachi Nejmana Skotta 1948 roku chi faktornogo analizu de obsyag danih na parametr obmezheno zgori MDP mozhe ocinyuvati vsi parametri zi statistichnoyu konzistentnistyu MDP vrahovuye tochnist vimiryuvannya Vona vikoristovuye informaciyu za Fisherom v nablizhenni Vollesa Frimena 1987 roku abo inshih giper ob yemah v inshih nablizhennyah shobi optimalno diskretuvati neperervni parametri Tomu aposteriorne zavzhdi ye jmovirnistyu a ne gustinoyu jmovirnosti MDP zastosovuyut z 1968 roku Shemi koduvannya MDP bulo rozrobleno dlya dekilkoh rozpodiliv ta dlya bagatoh tipiv sistem mashinnogo navchannya vklyuchno zi nekerovanoyu klasifikaciyeyu derevami ta grafami rishen poslidovnostyami DNK bayesovimi merezhami nejronnimi merezhami narazi lishe odnosharovimi stisnennyam zobrazhen segmentuvannyam zobrazhen ta funkcij tosho Div takozh en Algoritmichna teoriya informaciyi en Induktivne visnovuvannya en Kolmogorovska skladnist absolyutna skladnist v mezhah staloyi sho zalezhit vid konkretnogo viboru universalnoyi mashini Tyuringa MDP zazvichaj ye obchislyuvanim nablizhennyam dlya opracyuvannya div stattyu Vollesa ta Dou 1999 roku v specialnomu vipusku zgadanomu nizhche Minimalna dovzhina opisu pripustimo nebayesova alternativa z mozhlivo vidminnim obgruntuvannyam yaku bulo zaproponovano 10 rokami piznishe dlya porivnyannya div napriklad rozd 10 2 u knizi Vollesa posmertno 2005 roku rozd 11 4 3 stor 272 27 veresnya 2016 u Wayback Machine 273 27 veresnya 2016 u Wayback Machine v Komli ta Dou 2005 roku ta specialnij vipusk Computer Journal pro kolmogorovsku skladnist 42 4 1999 roku Lezo OkkamaPosilannyaWallace Boulton August 1968 Computer Journal 11 2 185 194 Arhiv originalu za 8 bereznya 2016 Procitovano 8 lipnya 2017 angl Posilannya na vsi vidomi publikaciyi Krisa Vollesa 14 chervnya 2006 u Wayback Machine angl May 2005 Statistical and Inductive Inference by Minimum Message Length Information Science and Statistics Springer Verlag ISBN 0 387 23795 X nedostupne posilannya prikladi storinok 3 serpnya 2020 u Wayback Machine angl Baza danih publikacij Krisa Vollesa z poshukom 8 lipnya 2017 u Wayback Machine angl Wallace C S Dowe D L 1999 Computer Journal 42 4 270 283 Arhiv originalu za 4 lipnya 2010 Procitovano 8 lipnya 2017 angl Special Issue on Kolmogorov Complexity Computer Journal 42 4 1999 angl Dowe D L Wallace C S 1997 28th Symposium on the interface Sydney Australia Computing Science and Statistics T 28 s 614 618 Arhiv originalu za 4 serpnya 2016 Procitovano 8 lipnya 2017 angl Istoriya MDP ostannya promova Krisa Vollesa 8 lipnya 2017 u Wayback Machine angl Needham S Dowe D 2001 PDF Proc 8th International Workshop on AI and Statistics s 253 260 Arhiv originalu PDF za 23 veresnya 2015 Procitovano 8 lipnya 2017 Pokazuye yak dobre pracyuye Lezo Okkama buduchi interpretovanim yak MDP angl Allison L Jan 2005 J Functional Programming 15 1 15 32 Arhiv originalu za 17 listopada 2004 Procitovano 8 lipnya 2017 MDP ruhoma koma ta kod 8 lipnya 2017 u Wayback Machine Haskell Comley J W Dowe D L April 2005 U Grunwald P Pitt M A Myung I J red Advances in Minimum Description Length Theory and Applications M I T Press s 265 294 ISBN 0 262 07262 9 Arhiv originalu za 19 chervnya 2006 Procitovano 8 lipnya 2017 Div takozh Comley Joshua W Dowe D L 5 8 June 2003 Proc 2nd Hawaii International Conference on Statistics and Related Fields Arhiv originalu za 4 serpnya 2016 Procitovano 8 lipnya 2017 pdf 10 lyutogo 2006 u Wayback Machine angl Praci Komli ta Dou 2003 ta 2005 rokiv ye pershimi dvoma pracyami pro bayesovi merezhi MDP iz zastosuvannyam yak diskretno tak i neperervnoznachnih parametriv Dowe David L 2010 PDF Handbook of Philosophy of Science Volume 7 Handbook of Philosophy of Statistics Elsevier s 901 982 ISBN 978 0 444 51862 0 Arhiv originalu PDF za 14 kvitnya 2016 Procitovano 8 lipnya 2017 angl Minimum Message Length MML 10 listopada 2016 u Wayback Machine vvedennya Llojda Ellisona do MDP MML alt 8 lipnya 2017 u Wayback Machine angl Minimum Message Length MML doslidniki ta posilannya 9 lyutogo 2006 u Wayback Machine angl Arhiv originalu za 12 kvitnya 2017 angl Storinka Snob 27 veresnya 2016 u Wayback Machine dlya en z MDP angl Korotki vvidni slajdi vid Mikko Kojvisto z Gelsinki angl Metod informacijnogo kriteriyu Akaike IKA angl Akaike information criterion AIC dlya obirannya modeli ta porivnyannya 4 serpnya 2016 u Wayback Machine z MDP Dowe D L Gardner S Oppy G Dec 2007 Brit J Philos Sci 58 709 754 Arhiv originalu za 16 grudnya 2008 Procitovano 8 lipnya 2017 angl, Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Топ