Мінімальна довжина опису

Принцип мінімальної довжини опису (МДО, англ. minimum description length principle, MDL) — формалізація леза Оккама, в якій найкращою гіпотезою для заданого набору даних є та, яка веде до найкращого стиснення даних. МДО запропонував Йорма Ріссанен 1978 року.^[1] Вона є важливим поняттям в теорії інформації та теорії обчислювального навчання^[en].^[2]^[3]^[4]

Огляд

Будь-який набір даних може бути представлено як стрічку символів зі скінченної (скажімо, двійкової) абетки.

[Принцип МДО] ґрунтується на такій інтуїції: будь-яку закономірність в заданому наборі даних може бути використано для стиснення цих даних, тобто для опису їх із застосуванням меншого числа символів, ніж потрібно для опису цих даних буквально.
— Петер Грюнвальд, MDL Tutorial^[5]

Щоби обрати гіпотезу, яка схоплює найбільше закономірності в даних, науковці шукають таку гіпотезу, з якою можна досягти найкращого стиснення. Для цього фіксують код для стиснення даних, найчастіше за допомогою (повної за Тюрінгом) комп'ютерної мови. Цією мовою пишуть програму для виведення даних; таким чином, програма ефективно представляє ці дані. Довжину найкоротшої програми, яка виводить дані, називають колмогоровською складністю цих даних. Це є центральною ідеєю ідеалізованої теорії індуктивного висновування^[en] Соломонова^[en].

Висновування

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

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

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

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

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

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

Приклад МДО

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

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

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

Позначення МДО

Центральною для теорії МДО є взаємно однозначна відповідність між функціями довжини коду та розподілами ймовірності. (Це випливає з нерівності Крафта — Макміллана.) Для будь-якого розподілу ймовірності $P$ можливо побудувати такий код $C$ , що довжина (в бітах) $C(x)$ дорівнює $-\log _{2}P(x)$ ; цей код мінімізує очікувану довжину коду. І навпаки, для заданого коду $C$ можливо побудувати такий розподіл ймовірності $P$ , що виконуватиметься те саме. (Проблеми з округленнями тут ігноровано.) Іншими словами, пошук ефективного коду зводиться до пошуку доброго розподілу ймовірності, й навпаки.

Пов'язані поняття

МДО має тісний зв'язок з теорією ймовірності та статистикою через зазначений вище взаємозв'язок між кодами та розподілами ймовірності. Це призвело до розгляду МДО деякими дослідниками як рівнозначного баєсовому висновуванню: довжина коду моделі та даних разом в МДО відповідають апріорній імовірності та відособленій правдподібності відповідно в баєсовій системі.^[6]

В той час як баєсів механізм часто є корисним для побудови ефективних кодів МДО, система МДО також допомагає з іншими кодами, які не є баєсовими. Одним з прикладів є код унормованої максимальної правдоподібності (англ. normalized maximum likelihood code) Штаркова, що відіграє центральну роль у поточній теорії МДО, але не має еквіваленту в баєсовому висновуванні. Крім того, Ріссанен наголошує, що ми не повинні робити жодних припущень про істинний процес породжування даних: на практиці клас моделей зазвичай є спрощенням дійсності, і відтак не містить коду або розподілу ймовірності, що є істинним в будь-якому об'єктивному сенсі.^[7]^[8] У крайньому згаданому посиланні Ріссанен спирається в математичному обґрунтуванні МДО на структурну функцію Колмогорова^[en].

Згідно філософії МДО, баєсові методи слід відхиляти, якщо вони ґрунтуються на небезпечних апріорних, що вели би до поганих результатів. Апріорним, що є прийнятними з точки зору МДО, також як правило віддають перевагу в так званому об'єктивному баєсовому аналізі, проте мотивація там зазвичай відрізняється.^[9]

Інші системи

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

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

Ключові люди

Йорма Ріссанен

Див. також

Примітки

↑ Rissanen, J. (1978). Modeling by shortest data description. Automatica. 14 (5): 465—658. doi:10.1016/0005-1098(78)90005-5. (англ.)
↑ Minimum Description Length. University of Helsinki. Архів оригіналу за 18 лютого 2010. Процитовано 3 липня 2010. (англ.)
↑ ^а ^б Grünwald, P. (June 2007). the Minimum Description Length principle. MIT Press. Архів оригіналу за 16 червня 2010. Процитовано 3 липня 2010. (англ.)
↑ Grünwald, P (April 2005). Advances in Minimum Description Length: Theory and Applications. MIT Press. Архів оригіналу за 19 червня 2006. Процитовано 3 липня 2010. (англ.)
↑ Grünwald, Peter. MDL Tutorial (PDF). Архів оригіналу (PDF) за 29 серпня 2017. Процитовано 3 липня 2010. (англ.)
↑ MacKay, David (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Архів оригіналу за 6 лютого 2015. Процитовано 3 липня 2010. (англ.)
↑ Rissanen, Jorma. Homepage of Jorma Rissanen. Архів оригіналу за 10 грудня 2015. Процитовано 3 липня 2010. (англ.)
↑ Rissanen, J. (2007). Information and Complexity in Statistical Modeling. Springer. Процитовано 3 липня 2010. (англ.)
↑ Nannen, Volker. A short introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (PDF). Архів оригіналу (PDF) за 2 червня 2010. Процитовано 3 липня 2010. (англ.)

Література

Minimum Description Length on the Web [Архівовано 9 січня 2019 у Wayback Machine.] від Університету Гельсінкі. Містить матеріали для читання, демонстрації, події та посилання на дослідників МДО. (англ.)
Homepage of Jorma Rissanen [Архівовано 10 грудня 2015 у Wayback Machine.], містить конспекти лекцій та інші недавні матеріали з МДО. (англ.)
Advances in Minimum Description Length, MIT Press, ISBN 0-262-07262-9. (англ.)

[1] Rissanen, J. (1978). Modeling by shortest data description. Automatica. 14 (5): 465—658. doi:10.1016/0005-1098(78)90005-5. (англ.)

[mdl-2] Minimum Description Length. University of Helsinki. Архів оригіналу за 18 лютого 2010. Процитовано 3 липня 2010. (англ.)

[mit-3] а ^б Grünwald, P. (June 2007). the Minimum Description Length principle. MIT Press. Архів оригіналу за 16 червня 2010. Процитовано 3 липня 2010. (англ.)

[catalog-4] Grünwald, P (April 2005). Advances in Minimum Description Length: Theory and Applications. MIT Press. Архів оригіналу за 19 червня 2006. Процитовано 3 липня 2010. (англ.)

[peter-5] Grünwald, Peter. MDL Tutorial (PDF). Архів оригіналу (PDF) за 29 серпня 2017. Процитовано 3 липня 2010. (англ.)

[mackay-6] MacKay, David (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Архів оригіналу за 6 лютого 2015. Процитовано 3 липня 2010. (англ.)

[cwi-7] Rissanen, Jorma. Homepage of Jorma Rissanen. Архів оригіналу за 10 грудня 2015. Процитовано 3 липня 2010. (англ.)

[springer-8] Rissanen, J. (2007). Information and Complexity in Statistical Modeling. Springer. Процитовано 3 липня 2010. (англ.)

[volker-9] Nannen, Volker. A short introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (PDF). Архів оригіналу (PDF) за 2 червня 2010. Процитовано 3 липня 2010. (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]