Sobre Navalha de Occam e Mininum Description Length (MDL)

Quem assistiu o filme Contato, certamente deve se lembrar da cena na qual a protagonista Eleanor Arroway interpretada por Jodi Foster é inquirida sobre a viagem que ela afirma ter feito utilizando o tal equipamento alienígena construído com recursos terrestres. Durante o interrogatório, Michael Kitz personagem vivido por James Woods pergunta a Eleanor se ela conhecia a Navalha de Occam. Já sem muitos argumentos a heroína se cala e a hipótese que ela não tenha feito a tal viagem é escolhida pelos inquiridores. Mas afinal, o que é essa tal navalha?

William Ockham foi um cara que viveu no século XIV e a ele é atribuído o tal princípio com a peculiar denominação “Navalha de Occam”. Também chamada de “Lei da parcimônia” a Navalha de Occam diz que se você tiver duas ou mais explicações para um determinado fenômeno é melhor você escolher a mais simples, contanto que ela explique o fenômeno tão bem quanto as outras. Era isso que Michael Kitz queria dizer ao perguntar a Eleanor se ela conhecia esse princípio. A pergunta podia ser feito da seguinte forma: tenho duas histórias aqui, uma simples e outra toda complicada e até um pouco absurda. Ambas explicam o que ocorreu satisfatóriamente. O que você, como cientista, escolheria Sra. Arroway?

Vamos a um segundo exemplo. Imagine a seguinte situação: você tem n pontos e quer descobrir qual polinômio se ajusta melhor a esses dados. Bom, sabemos que sempre existe um polinômio de grau igual a (n-1) que se ajustará perfeitamente aos n pontos. Mas, essa é a melhor escolha? A resposta é: depende. Veja a figura abaixo. Vemos claramente que um polinômio com grau 3 já oferece um bom ajuste aos dados. Usar um polinômio de grau maior do que 3 é trabalho demais pra pouca melhora no ajuste. Isso é chamado de Overfitting.

Mininum Description Length (MDL) é um método de inferência indutiva que implementa a mesma filosofia presente na Navalha de Occam. Esse método fornece soluções genéricas para o chamado Problema de Seleção de Modelo. Que é o caso dos pontos mencionado anteriormente. Uso uma reta ou uma parábola para descrever meus dados? E o legal mesmo é o insight por trás desse método. Para ele, aprender é encontrar regularidade nos dados. Bom até aí tudo bem. Mas ora, dados regulares têm um coeficiente de compressão alto, certo? Então quanto mais conseguirmos comprimir os dados mais aprenderemos sobre eles! Falando mais formalmente, se tivermos um conjunto de hipóteses H sobre um conjunto de dados D, então o que estamos procurando são hipóteses (uma ou mais) em H que forneçam a maior compressão de D.

Essa é a idéia geral do assunto e apesar de ser uma teoria bem legal é também um bocado cabeluda. Para aqueles que quiserem saber mais, há um material muito bom sobre MDL em Peter Grünwald.

Inteligência Artificial, Teoria da Informação 1 Comentário

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)