Перегляд вихідного коду сторінки Мінімальна довжина опису

'''Принцип мінімальної довжини опису''' ('''МДО''', {{lang-en|minimum description length principle, MDL}}) — формалізація [[Лезо Оккама|леза Оккама]], в якій найкращою [[Гіпотеза|гіпотезою]] для заданого набору даних є та, яка веде до найкращого [[стиснення даних]]. МДО запропонував [[Йорма Ріссанен]] 1978 року.<ref>{{Cite journal | last1 = Rissanen | first1 = J. | title = Modeling by shortest data description | doi = 10.1016/0005-1098(78)90005-5 | journal = Automatica | volume = 14 | issue = 5 | pages = 465–658 | year = 1978 | pmid =  | pmc = }} {{ref-en}}</ref> Вона є важливим поняттям в [[Теорія інформації|теорії інформації]] та {{нп|Теорія обчислювального навчання|теорії обчислювального навчання||Computational learning theory}}.<ref name="mdl">{{cite web|url=http://www.mdl-research.org/ |title=Minimum Description Length |last= |first= |date= |publisher=[[Гельсінський університет|University of Helsinki]] |accessdate=2010-07-03 |deadurl=yes |archiveurl=https://web.archive.org/web/20100218134039/http://www.mdl-research.org/ |archivedate=18 лютого 2010 }} {{ref-en}}</ref><ref name="mit">
{{cite news
|url=http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11155
|title=the Minimum Description Length principle
|last=Grünwald
|first=P.
|date=June 2007
|publisher=[[MIT Press]]
|accessdate=2010-07-03
|archiveurl=https://web.archive.org/web/20100616234207/http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11155
|archivedate=2010-06-16
|deadurl=yes
}} {{ref-en}}
</ref><ref name="catalog">{{cite news
|url=http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478
|title=Advances in Minimum Description Length: Theory and Applications
|last=Grünwald
|first=P
|date=April 2005
|publisher=[[MIT Press]]
|accessdate=2010-07-03
|archive-date=19 червня 2006
|archive-url=https://web.archive.org/web/20060619060230/http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478
}} {{ref-en}}</ref>

== Огляд ==
Будь-який набір даних може бути представлено як стрічку [[символ]]ів зі скінченної (скажімо, [[Двійкова система числення|двійкової]]) [[Абетка|абетки]].

{{Quote|[Принцип МДО] ґрунтується на такій інтуїції: будь-яку закономірність в заданому наборі даних може бути використано для [[Стиснення даних|стиснення цих даних]], тобто для опису їх із застосуванням меншого числа символів, ніж потрібно для опису цих даних буквально.|Петер Грюнвальд|MDL Tutorial<ref name="peter">{{cite news
|url=http://homepages.cwi.nl/~pdg/ftp/mdlintro.pdf
|title=MDL Tutorial
|last=Grünwald
|first=Peter
|date=
|publisher=
|accessdate=2010-07-03
|archive-date=29 серпня 2017
|archive-url=https://web.archive.org/web/20170829234005/http://homepages.cwi.nl/~pdg/ftp/mdlintro.pdf
}} {{ref-en}}</ref>}}

Щоби обрати гіпотезу, яка схоплює найбільше закономірності в даних, науковці шукають таку гіпотезу, з якою можна досягти найкращого стиснення. Для цього фіксують [[код]] для стиснення даних, найчастіше за допомогою ([[Повнота за Тюрінгом|повної за Тюрінгом]]) [[комп'ютер]]ної [[Формальна мова|мови]]. Цією мовою пишуть [[Комп'ютерна програма|програму]] для виведення даних; таким чином, програма ефективно представляє ці дані. Довжину найкоротшої програми, яка виводить дані, називають [[Колмогоровська складність|колмогоровською складністю]] цих даних. Це є центральною ідеєю {{нп|Теорія індуктивного висновування Соломонова|ідеалізованої теорії індуктивного висновування||Solomonoff's theory of inductive inference}} {{нп|Рей Соломонов|Соломонова||Ray Solomonoff}}.

=== Висновування ===
Проте ця математична теорія не дає практичного шляху досягання висновування. Найважливішими причинами цього є наступні:

* Колмогоровська складність є [[Необчислюваність|необчислюваною]]: такого алгоритму, який для довільної послідовності даних на вході видавав би на виході програму, що виводить ці дані, не існує.
* Колмогоровська складність залежить від того, яку [[Комп'ютерна мова|комп'ютерну мову]] використовують. Вибір мови є вільним, але він впливає на цю складність з точністю до деякого сталого адитивного члену. З цієї причини сталі члени в теорії колмогоровської складності, як правило, не враховують. Проте на практиці, коли доступним є лише невеликий обсяг даних, такі сталі можуть мати дуже великий вплив на результати висновування: при роботі з обмеженими даними добрі результати гарантовано бути не може.

МДО намагається зараджувати цьому шляхом:

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

Замість «програм» в теорії МДО зазвичай говорять про кандидатури гіпотез, моделей або кодів. Набір дозволених кодів тоді називають класом моделей. (Деякі автори називають клас моделей моделлю.) Відтак обирають такий код, для якого сума опису коду та опису даних із застосуванням цього коду є мінімальною.

Однією з важливих властивостей методів МДО є те, що вони забезпечують природний захист від [[перенавчання]], оскільки вони втілюють компроміс між складністю гіпотези (класу моделей) та складністю даних за заданої гіпотези.<ref name="mit"/> Це показано в наступному прикладі.

== Приклад МДО ==
{{Multiple issues|розділ=так|
{{плутаний розділ|date=липень 2017}}
{{Refimprovesect|date=липень 2017}}
}}

Монету підкидають 1&nbsp;000 разів, і записують кількості аверсів та реверсів. Розгляньмо два класи моделей:

* Перший є кодом, який представляє результати через 0 для аверсів та 1 для реверсів. Цей код представляє гіпотезу того, що монета є справедливою. Довжина коду за цього кодування завжди дорівнює 1&nbsp;000 біт.
* Другий складається з усіх кодів, що є ефективними для монети з певним зсувом, представляючи гіпотезу того, що монета не є справедливою. Скажімо, ми спостерігаємо 510 аверсів та 490 реверсів. Тоді довжина коду відповідно до найкращого кодування в другій моделі є коротшою за 1&nbsp;000 біт.

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

== Позначення МДО ==
Центральною для теорії МДО є [[взаємно однозначна відповідність]] між [[Функція (математика)|функціями]] довжини коду та [[Розподіл ймовіності|розподілами ймовірності]]. (Це випливає з [[Нерівність Крафта — Макміллана|нерівності Крафта&nbsp;— Макміллана]].) Для будь-якого розподілу ймовірності <math>P</math> можливо побудувати такий код <math>C</math>, що довжина (в бітах) <math>C(x)</math> дорівнює <math>-\log_2 P(x)</math>; цей код мінімізує очікувану довжину коду. І навпаки, для заданого коду <math>C</math> можливо побудувати такий розподіл ймовірності <math>P</math>, що виконуватиметься те саме. (Проблеми з округленнями тут ігноровано.) Іншими словами, пошук ефективного коду зводиться до пошуку доброго розподілу ймовірності, й навпаки.

== Пов'язані поняття ==
МДО має тісний зв'язок з [[Теорія ймовірності|теорією ймовірності]] та [[Статистика|статистикою]] через зазначений вище взаємозв'язок між кодами та розподілами ймовірності. Це призвело до розгляду МДО деякими дослідниками як рівнозначного [[Баєсове висновування|баєсовому висновуванню]]: довжина коду моделі та даних разом в МДО відповідають [[Апріорна ймовірність|апріорній імовірності]] та [[Відособлена правдоподібність|відособленій правдподібності]] відповідно в баєсовій системі.<ref name="mackay">{{cite news
|url=http://www.inference.phy.cam.ac.uk/mackay/itila/
|title=Information Theory, Inference, and Learning Algorithms
|last=MacKay
|first=David
|year=2003
|publisher=[[Cambridge University Press]]
|accessdate=2010-07-03
|archive-date=6 лютого 2015
|archive-url=https://web.archive.org/web/20150206001819/http://www.inference.phy.cam.ac.uk/mackay/itila/
}} {{ref-en}}</ref>

В той час як баєсів механізм часто є корисним для побудови ефективних кодів МДО, система МДО також допомагає з іншими кодами, які не є баєсовими. Одним з прикладів є ''код унормованої максимальної правдоподібності'' ({{lang-en|normalized maximum likelihood code}}) Штаркова, що відіграє центральну роль у поточній теорії МДО, але не має еквіваленту в баєсовому висновуванні. Крім того, Ріссанен наголошує, що ми не повинні робити жодних припущень про ''істинний'' [[Імовірнісна модель|процес породжування даних]]: на практиці клас моделей зазвичай є спрощенням дійсності, і відтак не містить коду або розподілу ймовірності, що є істинним в будь-якому об'єктивному сенсі.<ref name="cwi">{{cite news
|url=http://www.mdl-research.net/jorma.rissanen/
|title=Homepage of Jorma Rissanen
|last=Rissanen
|first=Jorma
|date=
|publisher=
|accessdate=2010-07-03
|archive-date=10 грудня 2015
|archive-url=https://web.archive.org/web/20151210054325/http://www.mdl-research.net/jorma.rissanen/
}} {{ref-en}}</ref><ref name="springer">{{cite news
|url=http://www.springer.com/computer/foundations/book/978-0-387-36610-4
|title=Information and Complexity in Statistical Modeling
|last=Rissanen
|first=J.
|year=2007
|publisher=Springer
|accessdate=2010-07-03}} {{ref-en}}</ref> У крайньому згаданому посиланні Ріссанен спирається в математичному обґрунтуванні МДО на {{нп|Структурна функція Колмогорова|структурну функцію Колмогорова||Kolmogorov structure function}}.

Згідно філософії МДО, баєсові методи слід відхиляти, якщо вони ґрунтуються на небезпечних [[Апріорна ймовірність|апріорних]], що вели би до поганих результатів. Апріорним, що є прийнятними з точки зору МДО, також як правило віддають перевагу в так званому [[Об'єктивна баєсова ймовірність|об'єктивному баєсовому]] аналізі, проте мотивація там зазвичай відрізняється.<ref name="volker">{{cite news
|url=http://volker.nannen.com/pdf/short_introduction_to_model_selection.pdf
|title=A short introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length.
|last=Nannen
|first=Volker
|date=
|publisher=
|accessdate=2010-07-03
|archive-date=2 червня 2010
|archive-url=https://web.archive.org/web/20100602044851/http://volker.nannen.com/pdf/short_introduction_to_model_selection.pdf
}} {{ref-en}}</ref>

=== Інші системи ===
МДО не була першим підходом до навчання в [[Теорія інформації|теорії інформації]]; це 1968 року Воллес та Бултон започаткувати пов'язане поняття, назване [[Мінімальна довжина повідомлення|мінімальною довжиною повідомлення]] (МДП). Відмінність між МДО та МДП є джерелом постійної плутанини. З поверхневої точки зору, ці методи здаються переважно рівнозначними, але є деякі суттєві відмінності, особливо в інтерпретуванні:

* МДП є цілком суб'єктивним баєсовим підходом: він починається з ідеї, що хтось представляє свої переконання про процес породжування даних у вигляді апріорного розподілу. МДО уникає припущень про процес породжування даних.
* Обидва методи використовують двочастинні коди: перша частина завжди представляє інформацію, якої намагаються навчитися, таку як номер класу моделей ([[обирання моделі]]) або значення параметрів ([[оцінювання параметрів]]); друга частина є кодуванням даних за заданої інформації в першій частині. Відмінність між цими двома методами полягає в тім, що працях з МДО відстоюють необхідність переміщення небажаних параметрів до другої частини коду, де їх може бути представлено разом з даними шляхом застосування так званого {{нп|Одночастинний код|одночастинного коду||One-part code}}, що часто є ефективнішим за двочастинний. У первинному описі МДП всі параметри кодують в першій частині, тож вчаться всіх параметрів.
* В рамках МДП кожен параметр вказувано з рівно такою точністю, яка дає в результаті оптимальну загальну довжину повідомлення: попередній приклад міг виникнути, якщо якийсь параметр первинно розглядали як «можливо корисний» для моделі, але згодом було з'ясовано, що він не здатен допомогти в поясненні даних (такому параметрові буде призначено довжину коду, що відповідає (баєсовій) апріорній імовірності того, що параметр виявиться некорисним). В рамках МДО основну увагу приділяють порівнянню радше класів моделей, ніж моделей, і є природнішим підходити до такого ж питання шляхом порівняння класу моделей, що явно включає такий параметр, з іншим класом, який не включає його. Відмінність полягає в механізмі, що застосовують для досягнення одного й того ж висновку.

== Ключові люди ==

* [[Йорма Ріссанен]]

== Див. також ==

* {{нп|Алгоритмічна ймовірність|||Algorithmic probability}}
* [[Алгоритмічна теорія інформації]]
* [[Індуктивне висновування]]
* {{нп|Індуктивна ймовірність|||Inductive probability}}
* [[Мінімальна довжина повідомлення]]
* [[Лезо Оккама]]

== Примітки ==
{{Примітки}}

== Література ==
* [http://www.mdl-research.net/ Minimum Description Length on the Web] {{Webarchive|url=https://web.archive.org/web/20190109161704/http://www.mdl-research.net/jorma.rissanen/ |date=9 січня 2019 }} від Університету Гельсінкі. Містить матеріали для читання, демонстрації, події та посилання на дослідників МДО. {{ref-en}}
* [http://www.mdl-research.net/jorma.rissanen/ Homepage of Jorma Rissanen] {{Webarchive|url=https://web.archive.org/web/20151210054325/http://www.mdl-research.net/jorma.rissanen/ |date=10 грудня 2015 }}, містить конспекти лекцій та інші недавні матеріали з МДО. {{ref-en}}
* ''Advances in Minimum Description Length'', [[MIT Press]], {{ISBN|0-262-07262-9}}. {{ref-en}}

{{Статистика}}
<!-- {{Найменші квадрати та регресійний аналіз}} -->

{{DEFAULTSORT:Мінімальна довжина опису}}
[[Категорія:Алгоритмічна теорія інформації]]