Введение
Принцип выбора модели Минимальная длина описания (MDL) — это принцип выбора модели, согласно которому лучшей является модель, обеспечивающая самое короткое описание данных. Методы MDL обучаются с точки зрения сжатия данных и иногда описываются как математическое применение бритвы Оккама. Принцип MDL может быть расширен на другие формы индуктивного вывода и обучения, например, на оценку и последовательное предсказание, без явной идентификации единственной модели для данных. MDL берет свои корни преимущественно в теории информации и был далее развит в рамках общих областей статистики, теоретической информатики и машинного обучения, а также более узко — в теории вычислительного обучения. Исторически сложилось несколько различных, но взаимосвязанных интерпретаций существительной фразы "принцип минимальной длины описания", различающихся в понимании того, что подразумевается под "описанием": в теории обучения Джормы Риссанена, являющейся центральной концепцией теории информации, модели рассматриваются как статистические гипотезы, а описания определяются как универсальные коды. Первая попытка Риссанена в 1978 году автоматически получать краткие описания связана с Байесовским информационным критерием (BIC). В алгоритмической теории информации длина описания последовательности данных определяется длиной наименьшей программы, выдающей этот набор данных. В этом контексте он также известен как "идеализированный" принцип MDL и тесно связан с теорией индуктивного вывода Соломоноффа, согласно которой лучшая модель набора данных представлена его кратчайшим самораспаковывающимся архивом.
Minimum Description Length (MDL) is a model selection principle where the shortest description of the data is the best model. MDL methods learn through a data compression perspective and are sometimes described as mathematical applications of Occam's razor. The MDL principle can be extended to other forms of inductive inference and learning, for example to estimation and sequential prediction, without explicitly identifying a single model of the data. MDL has its origins mostly in information theory and has been further developed within the general fields of statistics, theoretical computer science and machine learning, and more narrowly computational learning theory. Historically, there are different, yet interrelated, usages of the definite noun phrase "the minimum description length principle" that vary in what is meant by description:
Within Jorma Rissanen's theory of learning, a central concept of information theory, models are statistical hypotheses and descriptions are defined as universal codes. Rissanen's 1978 pragmatic first attempt to automatically derive short descriptions, relates to the Bayesian Information Criterion (BIC). Within Algorithmic Information Theory, where the description length of a data sequence is the length of the smallest program that outputs that data set. In this context, it is also known as 'idealized' MDL principle and it is closely related to Solomonoff's theory of inductive inference, which is that the best model of a data set is represented by its shortest self extracting archive.
Обзор
Выбор описания минимальной длины для доступных данных в качестве наилучшей модели соответствует принципу, известному как бритва Оккама. До появления компьютерного программирования создание таких описаний было интеллектуальным трудом научных теоретиков. Это было гораздо менее формализовано, чем в компьютерную эпоху. Если у двух ученых возникало теоретическое разногласие, они редко могли формально применить бритву Оккама для выбора между своими теориями. У них были бы разные наборы данных и, возможно, разные описательные языки. Тем не менее, наука развивалась, поскольку бритва Оккама служила неформальным ориентиром в определении наилучшей модели. С появлением формальных языков и компьютерного программирования бритва Оккама получила математическое определение. Модели заданного набора наблюдений, закодированные в битах данных, можно создавать в виде компьютерных программ, выдающих эти данные. Тогда бритва Оккама могла формально выбрать самую короткую программу, измеренную в битах этой алгоритмической информации, в качестве наилучшей модели. Чтобы избежать недоразумений, следует отметить, что в принципе MDL (минимальной длины описания) ничего не подразумевает, что программу, воплощающую модель, создала машина. Она может быть полностью результатом человеческой деятельности. Принцип MDL применим независимо от того, является ли описание, предназначенное для выполнения на компьютере, результатом работы человека, машины или их комбинации. Принцип MDL требует лишь того, чтобы кратчайшее описание при выполнении воспроизводило исходный набор данных без ошибок.
Коды из двух частей
Различие в компьютерных программах между программами и непосредственными данными применимо ко всем формальным описаниям и иногда называется "двумя частями" описания. В статистическом обучении MDL такое описание часто называют двухкомпонентным кодом.
MDL в машинном обучении
MDL применяется в машинном обучении, когда алгоритмы (машины) генерируют описания. Обучение происходит, когда алгоритм генерирует более короткое описание того же набора данных. Теоретическая минимальная длина описания набора данных, называемая сложностью Колмогорова, однако, не может быть вычислена. То есть, даже если случайно алгоритм сгенерирует самую короткую программу, выдающую этот набор данных, автоматический теорем-доказатель не сможет доказать, что более короткой программы не существует. Тем не менее, при наличии двух программ, выдающих один и тот же набор данных, принцип MDL выбирает более короткую из них, считая, что она представляет собой лучшую модель.
Последние работы по алгоритмическому обучению MDL
Недавние исследования машинного обучения на основе принципа минимальной длины описания (MDL) алгоритмических, в отличие от статистических, моделей данных привлекают все больше внимания в связи с ростом доступности данных, вычислительных мощностей и теоретическим прогрессом. Эти подходы опираются на стремительно развивающуюся область искусственного общего интеллекта. Незадолго до смерти Марвин Мински решительно поддержал это направление исследований, заявив:
Статистическое обучение MDL
Любой набор данных может быть представлен цепочкой символов из конечного (скажем, бинарного) алфавита. [Принцип МДЛ] основан на следующем понимании: любая закономерность в заданном наборе данных может быть использована для сжатия данных, то есть для их описания с использованием меньшего количества символов, чем требуется для буквального описания данных. (Grünwald, 2004) На основе этого, в 1978 году Йорма Риссанен опубликовал алгоритм обучения МДЛ, использующий статистическое понятие информации, а не алгоритмическую. За прошедшие 40 лет это развилось в богатую теорию статистических и машинных процедур обучения, связанную с байесовским выбором и усреднением моделей, методами регуляризации, такими как Lasso и Ridge, и так далее. Grünwald и Roos (2020) дают введение, охватывающее все современные разработки. Риссанен исходил из идеи, что все статистическое обучение заключается в поиске закономерностей в данных, и лучшая гипотеза для описания этих закономерностей – это та, которая способна статистически наиболее эффективно сжать данные. Как и другие статистические методы, его можно использовать для обучения параметров модели на основе имеющихся данных. Однако, как правило, стандартные статистические методы предполагают, что общая форма модели фиксирована. Главное преимущество МДЛ заключается в том, что его можно использовать и для выбора общей формы модели, и для обучения ее параметров. Объект интереса (иногда только модель, иногда только параметры, а иногда и то, и другое одновременно) называется гипотезой. Основная идея состоит в рассмотрении (без потерь) двухэтапного кода, который кодирует данные длиной, сначала кодируя гипотезу из рассматриваемого набора гипотез, а затем кодируя "с помощью" ; в простейшем случае это означает "кодирование отклонений данных от предсказаний, сделанных ". Достижение этого минимума рассматривается как наилучшее объяснение данных. В качестве простого примера рассмотрим задачу регрессии: данные могут состоять из последовательности точек , набор может быть множеством всех многочленов от до . Чтобы описать многочлен степени (скажем), сначала необходимо дискретизировать параметры с определенной точностью; затем нужно описать эту точность (натуральное число); далее – описать степень (еще одно натуральное число), и, наконец, описать параметров; общая длина составит . Затем точки описываются с использованием фиксированного кода для значений x и кода для отклонений. На практике часто (но не всегда) используется вероятностная модель. Например, каждому многочлену сопоставляется соответствующее условное распределение, выражающее, что при заданном величина распределена нормально со средним и некоторой дисперсией , которая может быть фиксированной или добавлена в качестве свободного параметра. Тогда набор гипотез сводится к предположению о линейной модели , с многочленом. Кроме того, часто интересуют не конкретные значения параметров, а, например, степень многочлена. В этом случае представляет собой множество гипотез, где каждая означает, что данные лучше всего описываются многочленом j-й степени. Затем данные кодируются при заданной гипотезе с помощью однокомпонентного кода, разработанного таким образом, чтобы, когда какая-либо гипотеза хорошо соответствует данным, длина кода была короткой. Разработка таких кодов называется универсальным кодированием. Существуют различные типы универсальных кодов, которые можно использовать, часто дающие схожие длины для длинных последовательностей данных, но различающиеся для коротких. "Лучшие" (в смысле наличия свойства минимаксной оптимальности) – это коды нормализованного максимального правдоподобия (NML) или коды Штаркова. Довольно полезным классом кодов являются коды байесовского маргинального правдоподобия. Для экспоненциальных семейств распределений, при использовании априорного распределения Джеффриса и соответствующем ограничении пространства параметров, они асимптотически совпадают с кодами NML; это сближает теорию МДЛ с объективным байесовским выбором модели, в котором также иногда используется априорное распределение Джеффриса, хотя и по другим причинам. Подход МДЛ к выбору модели "дает критерий отбора, формально идентичный подходу BIC" для большого количества выборок.
Based on this, in 1978, Jorma Rissanen published an MDL learning algorithm using the statistical notion of information rather than algorithmic information. Over the past 40 years this has developed into a rich theory of statistical and machine learning procedures with connections to Bayesian model selection and averaging, penalization methods such as Lasso and Ridge, and so on Grünwald and Roos (2020) give an introduction including all modern developments. Rissanen started out with this idea: all statistical learning is about finding regularities in data, and the best hypothesis to describe the regularities in data is also the one that is able to statistically compress the data most. Like other statistical methods, it can be used for learning the parameters of a model using some data. Usually though, standard statistical methods assume that the general form of a model is fixed. MDL's main strength is that it can also be used for selecting the general form of a model and its parameters. The quantity of interest (sometimes just a model, sometimes just parameters, sometimes both at the same time) is called a hypothesis. The basic idea is then to consider the (lossless) two stage code that encodes data with length by first encoding a hypothesis in the set of considered hypotheses and then coding "with the help of" ; in the simplest context this just means "encoding the deviations of the data from the predictions made by :
The achieving this minimum is then viewed as the best explanation of data As a simple example, take a regression problem: the data could consist of a sequence of points , the set could be the set of all polynomials from to To describe a polynomial of degree (say) , one would first have to discretize the parameters to some precision; one would then have to describe this precision (a natural number); next, one would have to describe the degree (another natural number), and in the final step, one would have to describe parameters; the total length would be One would then describe the points in using some fixed code for the x values and then using a code for the deviations
In practice, one often (but not always) uses a probabilistic model. For example, one associates each polynomial with the corresponding conditional distribution expressing that given , is normally distributed with mean and some variance which could either be fixed or added as a free parameter. Then the set of hypotheses reduces to the assumption of a linear model, , with a polynomial. Furthermore, one is often not directly interested in specific parameters values, but just, for example, the degree of the polynomial. In that case, one sets to be where each represents the hypothesis that the data is best described as a j th degree polynomial. One then codes data given hypothesis using a one part code designed such that, whenever some hypothesis fits the data well, the codelength is short. The design of such codes is called universal coding. There are various types of universal codes one could use, often giving similar lengths for long data sequences but differing for short ones. The 'best' (in the sense that it has a minimax optimality property) are the normalized maximum likelihood (NML) or Shtarkov codes. A quite useful class of codes are the Bayesian marginal likelihood codes. For exponential families of distributions, when Jeffreys prior is used and the parameter space is suitably restricted, these asymptotically coincide with the NML codes; this brings MDL theory in close contact with objective Bayes model selection, in which one also sometimes adopts Jeffreys' prior, albeit for different reasons. The MDL approach to model selection "gives a selection criterion formally identical to the BIC approach" for large number of samples.
Пример статистического обучения
Монету подбрасывают 1000 раз, и количество выпавших орлов и решек фиксируется. Рассмотрим два класса моделей: первый – это код, представляющий исходы нулем для орла и единицей для решки. Этот код отражает гипотезу о честной монете. Длина кода, использующего этот код, всегда составляет ровно 1000 бит. Второй класс состоит из всех кодов, эффективных для монеты с определенной степенью смещения, представляя гипотезу о нечестной монете. Предположим, мы наблюдаем 510 орлов и 490 решек. Тогда длина кода, соответствующего наилучшему коду во втором классе моделей, будет меньше 1000 бит. По этой причине наивный статистический метод может выбрать вторую модель в качестве лучшего объяснения данных. Однако подход MDL (Minimum Description Length) построит единый код на основе гипотезы, а не просто выберет лучший из доступных. Этот код может быть кодом максимального правдоподобия с нормализацией или байесовским кодом. Если использовать такой код, то общая длина кода, основанная на втором классе моделей, превысит 1000 бит. Следовательно, при применении подхода MDL неизбежно приходят к выводу, что недостаточно доказательств в пользу гипотезы о смещенной монете, даже несмотря на то, что наилучший элемент второго класса моделей обеспечивает лучшее соответствие данным.
The first is a code that represents outcomes with a 0 for heads or a 1 for tails. This code represents the hypothesis that the coin is fair. The code length according to this code is always exactly 1000 bits. The second consists of all codes that are efficient for a coin with some specific bias, representing the hypothesis that the coin is not fair. Say that we observe 510 heads and 490 tails. Then the code length according to the best code in the second model class is shorter than 1000 bits. For this reason, a naive statistical method might choose the second model as a better explanation for the data. However, an MDL approach would construct a single code based on the hypothesis, instead of just using the best one. This code could be the normalized maximum likelihood code or a Bayesian code. If such a code is used, then the total codelength based on the second model class would be larger than 1000 bits. Therefore, the conclusion when following an MDL approach is inevitably that there is not enough evidence to support the hypothesis of the biased coin, even though the best element of the second model class provides better fit to the data.
Статистическая нотация МДС
Центральным в теории MDL является взаимно однозначное соответствие между функциями длины кода и распределениями вероятностей (это следует из неравенства Крафта — Макмиллана). Для любого распределения вероятностей можно построить код, такой что длина (в битах) кода равна ; этот код минимизирует ожидаемую длину кода. И наоборот, заданному коду можно сопоставить распределение вероятностей, для которого выполняется то же самое условие. (Вопросы округления здесь не рассматриваются.) Иными словами, поиск эффективного кода эквивалентен поиску хорошего распределения вероятностей.
Ограничения статистического обучения
Язык описания статистического MDL не является вычислительно универсальным. Следовательно, он не способен, даже в принципе, обучаться моделям рекурсивных природных процессов.
Связанные понятия
Статистическое обучение MDL очень тесно связано с теорией вероятности и статистикой благодаря соответствию между кодами и распределениями вероятностей, упомянутому выше. Это привело некоторых исследователей к рассмотрению MDL как эквивалента байесовскому выводу: длина кода модели и данных вместе в MDL соответствует, соответственно, априорной вероятности и предельной вероятности в байесовском подходе. Хотя байесовский аппарат часто полезен при построении эффективных кодов MDL, структура MDL также допускает другие коды, не являющиеся байесовскими. Примером служит нормализованный код максимального правдоподобия Штаркова, который играет центральную роль в современной теории MDL, но не имеет аналога в байесовском выводе. Более того, Риссанен подчеркивает, что не следует делать никаких предположений об истинном процессе генерации данных: на практике класс моделей обычно является упрощением реальности и, следовательно, не содержит кода или распределения вероятностей, которые были бы истинными в каком-либо объективном смысле. В указанной работе Риссанен основывает математическое обоснование MDL на структуре Колмогорова. Согласно философии MDL, байесовские методы следует отвергать, если они основаны на ненадежных априорных распределениях, приводящих к плохим результатам. Априорные распределения, приемлемые с точки зрения MDL, также часто предпочтительны в так называемом объективном байесовском анализе, однако мотивация там обычно иная.
Другие системы
Риссанен не был первым, кто применил информационно-теоретический подход к обучению; еще в 1968 году Уоллес и Бультон предложили связанную концепцию, известную как минимальная длина сообщения (MML). Разница между MDL и MML – источник постоянной путаницы. На первый взгляд, методы кажутся в основном эквивалентными, но существуют некоторые существенные различия, особенно в интерпретации: MML – это полностью субъективный байесовский подход: он исходит из идеи, что представления о процессе генерации данных выражаются в форме априорного распределения. MDL избегает предположений о процессе генерации данных. Оба метода используют двухкомпонентные коды: первая компонента всегда представляет информацию, которую необходимо узнать, например, индекс класса модели (выбор модели) или значения параметров (оценка параметров); вторая компонента – это кодирование данных, учитывающее информацию из первой компоненты. Различие между методами заключается в том, что в литературе по MDL рекомендуется перемещать нежелательные параметры во вторую компоненту кода, где они могут быть представлены вместе с данными, используя так называемый однокомпонентный код, который часто более эффективен, чем двухкомпонентный код. В оригинальном описании MML все параметры кодируются в первой компоненте, следовательно, все параметры изучаются. В рамках MML точность определения каждого параметра соответствует оптимальной общей длине сообщения: предыдущий пример может возникнуть, если какой-то параметр изначально считался "потенциально полезным" для модели, но впоследствии оказалось, что он не способствует объяснению данных (такому параметру будет присвоена длина кода, соответствующая априорной (байесовской) вероятности того, что параметр окажется бесполезным). В рамках MDL больше внимания уделяется сравнению классов моделей, чем отдельным моделям, и более естественно подходить к тому же вопросу, сравнивая класс моделей, явно включающих такой параметр, с другим классом, который его не включает. Разница заключается в механизмах, используемых для достижения одного и того же вывода.
MML is a fully subjective Bayesian approach: it starts from the idea that one represents one's beliefs about the data generating process in the form of a prior distribution. MDL avoids assumptions about the data generating process. Both methods make use of two part codes: the first part always represents the information that one is trying to learn, such as the index of a model class (model selection) or parameter values (parameter estimation); the second part is an encoding of the data given the information in the first part. The difference between the methods is that, in the MDL literature, it is advocated that unwanted parameters should be moved to the second part of the code, where they can be represented with the data by using a so called one part code, which is often more efficient than a two part code. In the original description of MML, all parameters are encoded in the first part, so all parameters are learned. Within the MML framework, each parameter is stated to exactly the precision which results in the optimal overall message length: the preceding example might arise if some parameter was originally considered "possibly useful" to a model but was subsequently found to be unable to help to explain the data (such a parameter will be assigned a code length corresponding to the (Bayesian) prior probability that the parameter would be found to be unhelpful). In the MDL framework, the focus is more on comparing model classes than models, and it is more natural to approach the same question by comparing the class of models that explicitly include such a parameter against some other class that doesn't. The difference lies in the machinery applied to reach the same conclusion.