Descrição de comprimento mínimo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.[1] DCM foi introduzido em 1978 por Jorma Rissanen e é um conceito importante em teoria da informação e teoria da aprendizagem computacional..[2][3][4]

Resumo[editar | editar código-fonte]

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

 [O princípio da DCM] é baseado na seguinte ideia: qualquer regularidade em um conjunto de dados pode ser usado para compressão dos mesmos (sem perda de informação). Ex: Exibir o dado usando o menor conjunto de símbolos que é preciso para decrevê-lo 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[editar | editar código-fonte]

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 overfitting, porque eles implementam um tradeoff 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.

Exemplo de DCM[editar | editar código-fonte]

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 elementdo 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[editar | editar código-fonte]

É 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ódigotal que o comprimento (em bits) deis é igual a; esse código minimiza o comprimento de código esperado. Vice versa, um códigodado , pode-se construir uma distribuição de probabilidadetal 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[editar | editar código-fonte]

O DCM é fortemente ligado à teoria das probabilidades e estatística através da correspondência enter 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.[5]

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.[6][7] 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.[8]

Outros Sistemas[editar | editar código-fonte]

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 cahmado 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[editar | editar código-fonte]

  • Jorma Rissanen

Veja também[editar | editar código-fonte]

Referências

  1. Rissanen, J. (1978). «Modeling by shortest data description». Automatica. 14 (5): 465–658. doi:10.1016/0005-1098(78)90005-5 
  2. «Minimum Description Length». University of Helsinki. Consultado em 3 de julho de 2010 
  3. Grünwald, P. (junho de 2007). «the Minimum Description Length principle». MIT Press. Consultado em 3 de julho de 2010 
  4. Grünwald, P (abril de 2005). «Advances in Minimum Description Length: Theory and Applications». MIT Press. Consultado em 3 de julho de 2010 
  5. MacKay, David (2003). «Information Theory, Inference, and Learning Algorithms». Cambridge University Press. Consultado em 3 de julho de 2010 
  6. Rissanen, Jorma. «Homepage of Jorma Rissanen». Consultado em 3 de julho de 2010 
  7. Rissanen, J. (2007). «Information and Complexity in Statistical Modeling». Springer. Consultado em 3 de julho de 2010 
  8. Nannen, Volker. «A short introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length.» (PDF). Consultado em 3 de julho de 2010 

Leitura adicional[editar | editar código-fonte]