Comprimento mínimo da descrição - Minimum description length

Comprimento mínimo de descrição (MDL) refere-se a várias formalizações da navalha de Occam com base em linguagens formais usadas para descrever dados parcimoniosamente . MDL é um conceito importante na teoria da informação e na teoria da aprendizagem computacional .

Em sua forma mais básica, MDL é um princípio de seleção de modelo : a descrição mais curta dos dados é o melhor modelo. Essas descrições são úteis para fornecer modelos científicos baseados em dados . Essa ideia pode ser estendida a outras formas de inferência indutiva e aprendizado, por exemplo, para estimativa e predição sequencial sem identificar explicitamente um único modelo dos dados.

Existem diferentes, embora inter-relacionados, usos do sintagma nominal definido " o princípio do comprimento mínimo da descrição " que variam no que se entende por descrição :

  • Na teoria da aprendizagem de Jorma Rissanen , um conceito central da teoria da informação, os modelos são hipóteses estatísticas e as descrições são definidas como códigos universais.
  • A primeira tentativa pragmática de Rissanen em 1978 de derivar automaticamente descrições curtas está relacionada ao Critério de Informação Bayesiano (BIC).
  • Dentro da Teoria da Informação Algorítmica , onde o comprimento da descrição de uma sequência de dados é o comprimento do menor programa que produz esse conjunto de dados. Nesse contexto, ele também é conhecido como princípio MDL 'idealizado' e está intimamente relacionado à teoria da inferência indutiva de Solomonoff , que é que o melhor modelo de um conjunto de dados é representado por seu arquivo autoextraível mais curto .

Visão geral

Selecionar a descrição do comprimento mínimo dos dados disponíveis como o melhor modelo observa o princípio identificado como navalha de Occam. Antes do advento da programação de computadores, gerar tais descrições era o trabalho intelectual dos teóricos científicos. Era muito menos formal do que na era do computador. Se dois cientistas tivessem uma discordância teórica, raramente poderiam aplicar formalmente a navalha de Occam para escolher entre suas teorias. Eles teriam conjuntos de dados diferentes e, possivelmente, linguagens descritivas diferentes. No entanto, a ciência avançada como a navalha de Occam foi um guia informal para decidir qual modelo era o melhor.

Com o advento das linguagens formais e da programação de computadores, a navalha de Occam foi definida matematicamente. Modelos de um determinado conjunto de observações, codificados como bits de dados, podem ser criados na forma de programas de computador que geram esses dados. A navalha de Occam poderia então selecionar formalmente o programa mais curto, medido em bits dessa informação algorítmica , como o melhor modelo.

Para evitar confusão, observe que não há nada no princípio MDL que implique que uma máquina produziu o programa que incorpora o modelo. Pode ser inteiramente produto de humanos. O princípio MDL se aplica independentemente de a descrição a ser executada em um computador ser produto de humanos, máquinas ou qualquer combinação destes. O princípio MDL requer apenas que a descrição mais curta, quando executada, produza o conjunto de dados original sem erros.

Códigos de duas partes

A distinção em programas de computador entre programas e dados literais se aplica a todas as descrições formais e às vezes é chamada de " duas partes " de uma descrição. No aprendizado MDL estatístico, essa descrição é freqüentemente chamada de código de duas partes .

MDL em Aprendizado de Máquina

O MDL se aplica ao aprendizado de máquina quando algoritmos (máquinas) geram descrições. O aprendizado ocorre quando um algoritmo gera uma descrição mais curta do mesmo conjunto de dados.

O comprimento mínimo teórico da descrição de um conjunto de dados, chamado de complexidade de Kolmogorov , não pode, entretanto, ser calculado. Ou seja, mesmo que por acaso um algoritmo gere o programa mais curto de todos os que geram o conjunto de dados, um provador automatizado de teoremas não pode provar que esse programa não existe. No entanto, dados dois programas que geram o conjunto de dados, o princípio MDL seleciona o mais curto dos dois como incorporando o melhor modelo.

Na prática, ao encontrar um modelo de aprendizado de máquina que melhor se ajusta aos dados de acordo com o princípio MDL, seleciona-se o modelo que minimiza o comprimento de um código (programa) de duas partes. Por exemplo, no caso supervisionado de aprendizagem da lista de regras de melhor ajuste (a forma probabilística de uma lista de decisão ) de um conjunto de dados, escolhe-se a lista de regras que minimiza o código de duas partes composto por: 1) o código que define exclusivamente uma lista de regras com todas as listas de regras possíveis que podem ser geradas a partir desse conjunto de dados, ou seja, levando em consideração o número de variáveis ​​e suas combinações possíveis; e 2) o código que retorna o conjunto de dados dada a lista de regras específica conforme definido no primeiro código. O primeiro código é feito especificamente para evitar overfitting por meio da penalização de listas de regras mais complexas que seriam naturalmente mais propensas a overfitting. Observe que usar um código de duas partes é essencial quando se precisa distinguir os diferentes modelos, como no caso de encontrar o modelo e seus parâmetros que melhor se ajustam aos dados. Isso contrasta com a tarefa de apenas querer saber o tamanho do modelo (por exemplo, o número de regras em uma lista de regras) necessário para o melhor desempenho.

Trabalho recente em Algorithmic MDL Learning

A aprendizagem recente de MDL por máquina de modelos de dados algorítmicos, em oposição aos estatísticos, tem recebido atenção crescente com o aumento da disponibilidade de dados, recursos de computação e avanços teóricos. As abordagens são informadas pelo crescente campo da inteligência artificial geral . Pouco antes de sua morte, Marvin Minsky se manifestou fortemente a favor dessa linha de pesquisa, dizendo:

"Parece-me que a descoberta mais importante desde Gödel foi a descoberta por Chaitin, Solomonoff e Kolmogorov do conceito chamado Probabilidade Algorítmica, que é uma nova teoria fundamental de como fazer previsões com base em uma coleção de experiências e esta é uma bela teoria, todo mundo deveria aprender, mas tem um problema, ou seja, você não pode realmente calcular o que essa teoria prevê porque é muito difícil, requer uma quantidade infinita de trabalho. No entanto, deve ser possível fazer aproximações práticas para o Chaitin , Kolmogorov, Solomonoff teoria que faria previsões melhores do que qualquer coisa que temos hoje. Todos deveriam aprender tudo sobre isso e passar o resto de suas vidas trabalhando nisso. "
Painel de discussão sobre os limites do entendimento
World Science Festival, NYC, 14 de dezembro de 2014


Aprendizagem MDL Estatística

Qualquer conjunto de dados pode ser representado por uma sequência de símbolos de um alfabeto finito (digamos, binário ) .

[O Princípio MDL] é baseado no seguinte insight: qualquer regularidade em um determinado conjunto de dados pode ser usada para compactar os dados , ou seja, para descrevê-los usando menos símbolos do que o necessário para descrever os dados literalmente. (Grünwald, 1998)

Com base nisso, em 1978, Jorma Rissanen publicou um algoritmo de aprendizagem MDL usando a noção estatística de informação em vez de informação algorítmica. Começa com esta ideia: todo aprendizado estatístico consiste em encontrar regularidades nos dados, e a melhor hipótese para descrever as regularidades nos dados é também aquela que é capaz de comprimir estatisticamente mais os dados. Como outros métodos estatísticos, ele pode ser usado para aprender os parâmetros de um modelo usando alguns dados. Normalmente, porém, os métodos estatísticos padrão assumem que a forma geral de um modelo é fixa. O principal ponto forte do MDL é que ele também pode ser usado para selecionar a forma geral de um modelo e seus parâmetros. A quantidade de interesse (às vezes apenas um modelo, às vezes apenas parâmetros, às vezes ambos ao mesmo tempo) é chamada de hipótese. A ideia básica é então considerar o código de dois estágios (sem perdas) que codifica dados com comprimento , primeiro codificando uma hipótese no conjunto de hipóteses consideradas e, em seguida, codificando "com a ajuda de" ; no contexto mais simples, isso significa apenas "codificar os desvios dos dados das previsões feitas por :

A concretização deste mínimo é então visto como a melhor explicação dos dados . Como um exemplo simples, pegue um problema de regressão: os dados podem consistir em uma sequência de pontos , o conjunto pode ser o conjunto de todos os polinômios de a . Para descrever um polinômio de grau (digamos) , seria necessário primeiro discretizar os parâmetros com alguma precisão; seria necessário então descrever essa precisão (um número natural); a seguir, seria preciso descrever o grau (outro número natural) e, na etapa final, descrever os parâmetros; o comprimento total seria . Em seguida, descreveríamos os pontos de usar algum código fixo para os valores x e, em seguida, usar um código para os desvios .

Na prática, muitas vezes (mas nem sempre) usa-se um modelo probabilístico . Por exemplo, associamos cada polinômio com a distribuição condicional correspondente expressando aquele dado , é normalmente distribuído com média e alguma variância que pode ser fixada ou adicionada como um parâmetro livre. Então, o conjunto de hipóteses se reduz à suposição de um modelo linear,, com um polinômio.

Além disso, muitas vezes não se está diretamente interessado em valores de parâmetros específicos, mas apenas, por exemplo, o grau do polinômio. Nesse caso, define- se estar onde cada um representa a hipótese de que os dados são mais bem descritos como um polinômio de j-ésimo grau. Em seguida, codifica-se os dados de uma hipótese usando um código de uma parte projetado de modo que, sempre que alguma hipótese se ajusta bem aos dados, o comprimento de código é curto. O design de tais códigos é chamado de codificação universal . Existem vários tipos de códigos universais que podem ser usados, muitas vezes fornecendo comprimentos semelhantes para sequências de dados longas, mas diferindo para sequências curtas. O 'melhor' (no sentido de que tem uma propriedade de otimalidade minimax) são os códigos de máxima verossimilhança normalizada (NML) ou Shtarkov . Uma classe de códigos bastante útil são os códigos de verossimilhança marginal Bayesianos. Para famílias exponenciais de distribuições, quando Jeffreys prior é usado e o espaço de parâmetros é adequadamente restrito, eles coincidem assintoticamente com os códigos NML; isso coloca a teoria MDL em contato próximo com a seleção objetiva do modelo de Bayes, em que às vezes também se adota a anterior de Jeffreys, embora por razões diferentes. A abordagem MDL para seleção de modelo "fornece um critério de seleção formalmente idêntico ao da abordagem BIC " para um grande número de amostras.

Exemplo de Aprendizagem MDL Estatística

Uma moeda é lançada 1000 vezes e o número de cara e coroa é registrado. Considere duas classes de modelo:

  • O primeiro é um código que representa resultados com 0 para cara ou 1 para coroa. Este código representa a hipótese de que a moeda é justa. O comprimento do código de acordo com este código é sempre exatamente 1000 bits.
  • O segundo consiste em todos os códigos que são eficientes para uma moeda com algum viés específico, representando a hipótese de que a moeda não é justa. Digamos que observamos 510 caras e 490 caudas. Então, o comprimento do código de acordo com o melhor código na segunda classe de modelo é menor que 1000 bits.

Por esta razão, um método estatístico ingênuo pode escolher o segundo modelo como uma explicação melhor para os dados. No entanto, uma abordagem MDL construiria um único código com base na hipótese, em vez de apenas usar o melhor. Este código pode ser o código de máxima verossimilhança normalizado ou um código Bayesiano. Se esse código for usado, o comprimento de código total com base na segunda classe de modelo seria maior do que 1000 bits. Portanto, a conclusão ao seguir uma abordagem MDL é inevitavelmente que não há evidências suficientes para apoiar a hipótese da moeda enviesada, embora o melhor elemento da segunda classe do modelo forneça melhor ajuste aos dados.

Notação MDL Estatística

Central para a teoria MDL é a correspondência um-para-um entre funções de comprimento de código e distribuições de probabilidade (isso segue da desigualdade Kraft-McMillan ). Para qualquer distribuição de probabilidade , é possível construir um código de modo que o comprimento (em bits) de seja igual a ; este código minimiza o comprimento de código esperado. Inversamente, dado um código , pode-se construir uma distribuição de probabilidade de forma que a mesma seja válida. (Os problemas de arredondamento são ignorados aqui.) Em outras palavras, pesquisar um código eficiente é equivalente a pesquisar uma boa distribuição de probabilidade.

Limitações do Aprendizado MDL Estatístico

A linguagem de descrição do MDL estatístico não é computacionalmente universal. Portanto, ele não pode, mesmo em princípio, aprender modelos de processos naturais recursivos.

Conceitos relacionados

O aprendizado estatístico de MDL está fortemente conectado à teoria da probabilidade e à estatística por meio da correspondência entre os códigos e as distribuições de probabilidade mencionadas acima. Isso levou alguns pesquisadores a ver o MDL como equivalente à inferência bayesiana : o comprimento do código do modelo e os dados juntos no MDL correspondem, respectivamente, à probabilidade anterior e à verossimilhança marginal na estrutura bayesiana.

Embora a maquinaria bayesiana seja frequentemente útil na construção de códigos MDL eficientes, a estrutura MDL também acomoda outros códigos que não são bayesianos. Um exemplo é o código de máxima verossimilhança normalizado de Shtarkov , que desempenha um papel central na teoria MDL atual, mas não tem equivalente na inferência bayesiana. Além disso, Rissanen enfatiza que não devemos fazer suposições sobre o verdadeiro processo de geração de dados : na prática, uma classe de modelo é tipicamente uma simplificação da realidade e, portanto, não contém nenhum código ou distribuição de probabilidade verdadeira em qualquer sentido objetivo. Na última referência mencionada, Rissanen baseia o fundamento matemático do MDL na função de estrutura de Kolmogorov .

De acordo com a filosofia MDL, os métodos bayesianos devem ser descartados se forem baseados em antecedentes inseguros que levariam a resultados ruins. As priors que são aceitáveis ​​de um ponto de vista MDL também tendem a ser favorecidas na chamada análise Bayesiana objetiva ; lá, entretanto, a motivação geralmente é diferente.

Outros sistemas

A abordagem de Rissanen não foi a primeira abordagem teórica da informação para o aprendizado; já em 1968, Wallace e Boulton foram os pioneiros em um conceito relacionado chamado comprimento mínimo de mensagem (MML). A diferença entre MDL e MML é uma fonte de confusão contínua. Superficialmente, os métodos parecem em sua maioria equivalentes, mas existem algumas diferenças significativas, especialmente na interpretação:

  • O MML é uma abordagem bayesiana totalmente subjetiva: começa com a ideia de que se representa as próprias crenças sobre o processo de geração de dados na forma de uma distribuição prévia. O MDL evita suposições sobre o processo de geração de dados.
  • Ambos os métodos fazem uso de códigos de duas partes : a primeira parte sempre representa a informação que se está tentando aprender, como o índice de uma classe de modelo ( seleção de modelo ) ou valores de parâmetro ( estimativa de parâmetro ); a segunda parte é uma codificação dos dados fornecidos as informações na primeira parte. A diferença entre os métodos é que, na literatura MDL, é preconizado que os parâmetros indesejados devem ser movidos para a segunda parte do código, onde podem ser representados com os dados usando um chamado código de uma parte , que geralmente é mais eficiente do que um código de duas partes . Na descrição original do MML, todos os parâmetros são codificados na primeira parte, portanto, todos os parâmetros são aprendidos.
  • Dentro da estrutura MML, cada parâmetro é declarado exatamente com essa precisão, o que resulta no comprimento geral ideal da mensagem: o exemplo anterior pode surgir se algum parâmetro foi originalmente considerado "possivelmente útil" para um modelo, mas posteriormente foi considerado incapaz de ajudar para explicar os dados (tal parâmetro será atribuído a um comprimento de código correspondente à probabilidade anterior (bayesiana) de que o parâmetro seria considerado inútil). Na estrutura MDL, o foco está mais na comparação de classes de modelo do que de modelos, e é mais natural abordar a mesma questão comparando a classe de modelos que inclui explicitamente esse parâmetro com alguma outra classe que não inclui. A diferença está na maquinaria aplicada para chegar à mesma conclusão.

Veja também

Referências

Leitura adicional