Бритва Оккама и принцип минимальной длины описания

Простота гипотезы — это один из наиболее часто применяемых критериев в индуктивном выводе (см., например [1, гл. 12]). Однако сама по себе простота гипотезы не может являться критерием при выборе модели, поскольку самая простая гипотеза — это просто отсутствие какой-либо регулярной модели, выявляющей внутренние закономерности в данных. Так, на любой наблюдаемый факт мы можем сказать: «Такова божья воля». Другими словами, простейшая гипотеза гласит, что данные абсолютно случайны, что, естественно, допускает и произвольную экстраполяцию, а значит, никак не может помочь в прогнозировании.

С другой стороны, точность, с которой модель описывает данные, тоже не является подходящим самостоятельным критерием. И действительно, существуют так называемые гипотезы ad hoc, которые просто повторяют имеющиеся данные, производят описание данных без их объяснения. Подобные гипотезы ad hoc также не могут помочь в прогнозировании. При этом они абсолютно точно описывают данные, но обладают значительной по сравнению с простейшей гипотезой сложностью.

В связи с этим принято считать, что лучшая гипотеза, дающая наибольшую точность предсказания, — это компромисс между простотой гипотезы и тем, насколько хорошо она удовлетворяет данным наблюдений [5, с. 715]. В философии науки такое положение часто связывается с принципом бритвы Оккама [2, с. 10]. Этот принцип гласит: «То, что можно объяснить посредством меньшего, не следует выражать посредством большего» (Frustra fit per plura quod potest fieri per pauciora), или «Без необходимости не следует утверждать многое» (Pl urali tas non est ponenda sine necessitate). Чаще приводится другая формулировка: «Сущностей не следует умножать без необходимости» (En tia non sun t m ul ti plicanda sine necessi ta te), но она, по- видимому, в произведениях Уильяма Оккама не встречается.

Как уже было замечено, в байесовских методах простота гипотезы используется для задания априорных вероятностей гипотез, и такие методы также называют формализацией бритвы Оккама [5, с. 715; 6, п. 1.1]. Однако более
интересным вариантом формализации понятия простоты, с нашей точки зрения, оказываются подходы, основанные на теории информации. Здесь сложность (как противоположность простоты) получает конкретное измерение числом бит. Для корректного вычисления количества информации оказывается необходимым привлекать алгоритмическую теорию информации.

В машинном обучении (и в вычислительном индуктивном выводе вообще) такой подход был воплощен в нескольких концепциях. Среди этих концепций присутствуют такие как алгоритмическая вероятность (АЛВ; Algorithmic
Probabllity, ALP), разработанная Р. Соломоновым в 1964 г. [7]; принцип минимальной длины сообщения (МДС; Minimum Message Length, MML), предложенный К. Уалласом и Д. Болтаном в 1968 г. [8] (более поздние разработки по МДС можно найти, например, в работах [9, 10]), принцип минимальной длины описания (МДО; Minimum Description Length, MDL), описанный в 1978 г. Ж. Риссаненом [11] и несколько пересмотренный им позднее [12]; концепция идеальной МДО (Ideal MDL), предложенная М. Ли и П. Витани в 1989 г. [13] (см. также [14]), и принцип аппроксимации сложности (ПАС; Complexity Approximation Principle, САР), введенный в работе [15]. Чуть ли не каждый из этих методов разными авторами связывается с формализацией бритвы Оккама [16, 17, 18, с. 10]

Хотя эти принципы несколько отличаются в деталях, основная идея у них одна, и ее можно сформулировать следующим образом (см., например, [19]). Среди множества моделей следует выбрать ту, которая позволяет минимизировать сумму: 1) длины описания модели (в битах); 2) длины данных, описанных посредством этой модели (в битах).

Общее правило, сформулированное таким образом, мы будем называть принципом минимальной длины описания (МДО). В случаях, когда речь будет идти о формальной теории Риссанена, название которой и было выбрано для обозначения общего принципа, это будет оговариваться особо, чтобы не вызывать терминологической путаницы.

Длина описания модели определяет ее сложность, а длина описания данных с использованием модели — то, насколько хорошо модель удовлетворяет данным. Таким образом, компромисс между простотой и точностью модели
приобретает объективный численный характер.

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