Descrição de comprimento mínimo

O Princípio da descrição de comprimento mínimo (DCM) é uma formalização da Navalha de Occam na qual a melhor hipótese para um dado conjunto de dados é a que leva a máxima compressão dos mesmos. DCM foi introduzido em 1978 por Jorma Rissanen e é um conceito importante em teoria da informação e teoria da aprendizagem computacional.

Resumo

Qualquer conjunto de dados pode ser representado por uma cadeia de símbolos de um alfabeto (inclusive o binário) finito.

"O princípio DCM é baseado no seguinte pensamento: qualquer regularidade em um certo conjunto de dados pode ser utilizado para compressão de dados, i.e. para descrevê-lo usando menos símbolos que o necessário para descrever os dados literalmente." (Grünwald, 1998)

Para selecionar a hipótese que captura a maior regularidade nos dados, os cientistas procuram o código com o qual a melhor compressão pode ser conseguida. Para tanto, o código para comprimir os dados, geralmente é escrito em uma linguagem(Turing-complete) de programação. Um programa que tem como saída estes dados(antes da compressão) é escrito na linguagem escolhida; assim, o programa efetivamente representa os dados. O comprimento do programa mais curto que tem como saída estes dados é chamado de Complexidade de Kolmogorov dos dados. Esta é a ideia central da teoria da inferência indutiva de Ray Solomonoff.

Inferência

Entretanto, essa teoria matemática não propicia uma maneira prática de conseguir uma inferência. As razões mais importantes para isso são:

•  A Complexidade de Kolmogorov não é computável: não existe algoritmo que, quando uma sequencia de dados arbitrária é dada como entrada, retorna como saída o menor programa que produz aqueles dados.  
• A Complexidade de Kolmogorov depende de qual linguagem de programação é utilizada. Isto é uma escolha arbitrária, mas influencia a complexidade em um termo constante a ser acrescentado. Por esta razão, termos constantes costumam ser desconsiderados na teoria complexidade de Kolmogorov. Na prática, no entanto, onde frequentemente apenas uma quantidade pequena de dados está disponível, de modo que, constantes podem ter uma grande influência nos resultados da Inferência: não há garantia de bons resultados quando se está trabalhando com poucos dados. 

A DCM tenta minimizar estes problemas das seguintes maneiras:

•  Restringindo o conjunto de códigos permitidos de modo que torne possível (computável) encontrar o tamanho de código mais curto para o dado, relativo aos comprimentos de código permitidos e 
• Escolhendo um código que é razoavelmente eficiente, quaisquer que sejam os dados disponíveis. Este ponto é um tanto nebuloso e há muita pesquisa em andamento nesta área. 

Em vez de "programas", na teoria DCM geralmente se fala de hipóteses candidatas, modelos ou códigos. O conjunto de códigos permitidos é então chamado de classe de modelos. (Alguns autores se referem a classes de modelos como modelos.) O código é então escolhido de maneira que a soma da descrição do código e a descrição dos dados que usa o código é minima. 

Uma das propriedades mais importantes dos métodos DCM é que eles oferecem uma proteção natural contra o over-fitting, porque eles implementam um trade-off entre a complexidade da hipótese (classes de modelos) e a complexidade dos dados oferecidos pela hipótese. O exemplo mostrado a seguir ilustra essa propriedade.

Visão geral

DCM é uma teoria de inferência indutiva e estatística que começa com a seguinte ideia: toda aprendizagem estatística é sobre achar regularidades em dados, e a melhor hipótese para descrever as regularidades em dados é também aquela que consegue comprimir ao máximo os mesmos. Assim como outros métodos estatísticos, ela pode ser usada para aprender os parâmetros de um modelo utilizando algum dado. Entretanto, normalmente métodos estatísticos padrões assumem que a forma geral de um modelo é fixa. O maior diferencial do DCM é que ele também pode ser utilizado para selecionar a forma geral de um modelo e seus parâmetros. A quantidade de interesse (ás vezes somente o modelo, ás vezes somente parâmetros, ás vezes ambos ao mesmo tempo) é chamado de hipótese. A ideia básica é então de considerar o (sem perda de dados) código de duas etapas que codifica dados $D$ com comprimento ${L(D)}$ por primeiramente codificar a hipótese $H$ no conjunto de hipóteses consideradas ${\cal {H}}$ e então codificar $D$ "com a ajuda de" $H$; no contexto mais simples, isso significa apenas "codificando os desvios dos dados das previsões feitas por $H$":

${L(D)}=\min _{H\in {\cal {H}}}\ (\ L(H)+L(D|H)\ )\$

O $H$ que atinge esse mínimo é então visto como a melhor explicação dos dados $D$. Como um exemplo simples, imagine um problema de regressão: os dados $D$ podem consistir em uma sequência de pontos $D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$, o conjunto ${\cal {H}}$ podem ser o conjunto de todos os polinômios de $X$ a $Y$. Para descrever um polinomial $H$ de grau (suponhamos) $k$, seria preciso primeiro discretizar os parâmetros com alguma precisão; seria necessário descrever essa precisão (um número natural); em seguida, seria necessário descrever o grau $k$ (outro número natural), e na etapa final, seria necessário descrever $k+1$ parâmetros; o comprimento total seria $L(H)$. Então se descreveria os pontos em $D$ usando algum código fixo para os valores de x e, em seguida, usando um código fixo para os $n$ desvios $y_{i}-H(x_{i})$.

Na prática, muitas vezes (mas nem sempre) usa-se um modelo probabilístico. Por exemplo, se associa cada polinômio $H$ com a distribuição condicional correspondente que expressa que, dados $X$, $Y$ é normalmente distribuído com média $H(X)$ e alguma variação $\sigma ^{2}$ que pode tanto ser corrigida ou adicionada como um parâmetro livre. Então o conjunto de hipóteses ${\cal {H}}$ reduz à suposição de um modelo linear, $Y=H(X)+\epsilon$ , com $H$ um polinomial.

Além disso, muitas vezes não se tem interesse diretamente por valores de parâmetros específicos, mas apenas, por exemplo, o grau do polinômio. Nesse caso, define-se ${\cal {H}}$ como sendo ${\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}$ onde cada ${\cal {H}}_{j}$ representa a hipótese de que os dados são melhor descritos como um polinômio de j-ésimo grau. Então se codifica os dados $D$ dada a hipótese ${\cal {H}}_{j}$ usando um código de uma parte projetado para que, sempre que alguma hipótese $H\in {\cal {H}}_{j}$ ajusta-se bem aos dados, o comprimento do código $L(D|H)$ é pequeno. O design de tais códigos é chamado universal coding. Existem vários tipos de códigos universais que se pode usar, geralmente fornecendo comprimentos semelhantes para longas sequências de dados, mas diferentes para as curtas. Os 'melhores' (no sentido de que possuem uma propriedade de otimização minimax) são os que possuem probabilidade máxima normalizada (NML) ou códigos de Shtarkov. Uma classe de códigos bastante útil são os "códigos de probabilidade marginal Bayesianos". Para famílias exponenciais de distribuições, quando o método de Jeffreys é usado e o espaço do parâmetro é adequadamente restrito, estes coincidem assintoticamente com os códigos NML; isso coloca a teoria DCM em contato próximo com a seleção objetiva do modelo de Bayes, em que às vezes também se adota o método de Jeffreys, embora por razões diferentes.

Exemplo de DCM

Uma moeda é jogada 1.000 vezes e número de caras e coroas é registrado. Considere duas classes de modelos:

•  A primeira é o código que representa um resultado com 0 para caras e 1 para coroas. Este código representa a hipótese de que a moeda é justa. O comprimento relacionado a este código é sempre de exatamente 1.000 bits. 
•  A segunda consiste em todos os códigos que são eficientes para uma moeda com uma tendência específica, representando a hipótese de que a moeda não é justa. Digamos que nós observamos 510 caras e 490 coroas. Então o comprimento de código associado ao melhor código associado ao segundo modelo de classes é menor do que 1.000 bits.  

Por essa razão um método estatístico ingênuo poderia escolher o segundo modelo como o melhor para uma explanação dos dados. Entretanto, uma abordagem DCM construiria um código único baseado nas hipóteses em vez de usar apenas o melhor. Para fazer isso, é mais simples usar um código de duas partes no qual cada elemento do do modelo de classes com o melhor desempenho é especificado. A partir daí dado é especificado usando este código. Muitos bits são necessários para especificar qual código deve ser usado; então o comprimento total baseado no segundo modelo de classes poderia ser maior do que 1,000 bits. Portanto a conclusão quando seguimos uma abordagem DCM é que inevitavelmente não há evidência que sustente a hipótese da moeda tendenciosa, mesmo que o melhor elemento do segundo modelo de dados forneça um melhor formato para os dados.

Notação DCM

É crucial para a teoria DCM a correspondência um para um entre o comprimento de código de funções e a distribuição de probabilidade. ( A partir da desigualdade de Kraft-McMillan.) Para qualquer distribuição de probabilidade, é possível construir um código tal que o comprimento (em bits) deis é igual a; esse código minimiza o comprimento de código esperado. Vice versa, um código dado, pode-se construir uma distribuição de probabilidade tal que ela mesma equivale ao código. (Problemas circunscritos estão sendo ignorados aqui.) Em outras palavras, procurar por um código eficiente se reduz a procurar por uma boa distribuição de probabilidade e vice versa.

Conceitos relacionados

O DCM é fortemente ligado à teoria das probabilidades e estatística através da correspondência entre códigos e distribuições de probabilidade mencionados acima. Esse fato levou os pesquisadores a enxergar DCM como equivalente à inferência Bayesiana: comprimento de código de modelo e dados juntos em MDL correspondem à probabilidade a priori e probabilidade marginal, respectivamente, no framework Bayesiano.

Enquanto máquinas Bayesianas são frequentemente úteis na construção de códigos de DCM eficientes, o framework MDL também acomoda outros códigos que não são Bayesianos. Um exemplo é a verosimilhança máxima normalizada de Shtarkov, que desempenha um papel central na atual teoria DCM, mas não tem equivalente na inferência Bayesiana. Além disso, Rissanen salienta que não devemos fazer suposições sobre o verdadeiro processo gerador dos dados: na prática, uma classe de modelo é normalmente uma simplificação da realidade e, portanto, não contém qualquer código ou distribuição de probabilidade que é verdade em qualquer sentido objetivo. Na última referência mencionada Rissanen embasa a matemática de DCM em função de estrutura de Kolmogorov. 

De acordo com a filosofia de DCM, métodos Bayesianos devem ser desconsiderados se eles são baseados em premissas inseguras que levariam a resultados ruins. As premissas que são aceitáveis do ponto de vista de um DCM também tendem a ser favorecidas na chamada análise bayesiana objetiva. Lá, no entanto, a motivação geralmente é diferente.

Outros Sistemas

A DCM não foi a primeira abordagem em teoria da informação para aprendizagem de máquina; Em 1968 Wallace e Boulton foram pioneiros em um conceito chamado de Mensagem de Comprimento Mínimo (MCM). A diferença ente DCM e MCM provoca confusão. Superficialmente, os métodos parecem na maior parte equivalentes, mas há algumas diferenças significativas, especialmente na interpretação:

• MCM é uma abordagem completamente Bayasiana subjetiva: ela começa com a ideia de que um representa a crença do outro sobre o processo de geração de dados na forma de uma distribuição prévia. DCM evita assumir premissas no processo de geração de dados.
• Ambos métodos fazem uso do código de duas partes: a primeira parte sempre representa a informação que está tentando aprender, bem com o índice de uma classe de modelos(seleção de modelo), ou valores de parâmetros (estimativa de parâmetros); a segunda parte é uma decodificação dos dados informados na primeira parte. A diferença ente os métodos é que, na literatura DCM, se recomenda que parâmetros indesejados sejam movidos para a segunda parte do código, onde eles podem ser representados com os dados chamados de código de uma parte, que frequentemente é mais eficiente do que um código de duas partes. Na descrição original do MCM, todos os parâmetros são codificados na primeira parte, portanto todos os parâmetros são aprendidos. 

Pessoas chave

• Jorma Rissanen

Veja também

• Algorithmic probability
• Algorithmic information theory
• Inductive inference
• Inductive probability
• Minimum message length
• Occam's razor

Leitura adicional

• Minimum Description Length on the Web, by the University of Helsinki. Features readings, demonstrations, events and links to MDL researchers.
• Homepage of Jorma Rissanen, containing lecture notes and other recent material on MDL.
• Advances in Minimum Description Length, MIT Press, ISBN 0-262-07262-9.