Em Finalmente, uma definição de programação que eu realmente consigo entender Fiquei maravilhado com um comentário particularmente estranho e maravilhoso deixado neste blog. Alguns comentaristas se perguntaram se esse comentário foi gerado por meio de Cadeias de Markov. Pensei nisso, mas tive dificuldade em imaginar uma entrada de corpus de texto que pudesse produzir um resultado tão profundamente estranho.
Portanto o que são essas cadeias de Markov? de que estamos falando?
Um exemplo de cadeias de Markov em ação é Garkov, onde a longa duração Garfield tira de desenho animado encontra cadeias de Markov. Apresento a seguir, para sua leve diversão, duas tiras representativas que encontrei no site Hall da fama de Garkov:
Mas o Garfield é um alvo fácil:
- Garfield menos Garfield. O que está escrito na lata. Surpreendentemente catártico.
- Gato de lasanha. Recriações de ação ao vivo quase indescritivelmente estranhas das tiras do Garfield. Se o senhor clicar em apenas um link nesta postagem, que seja neste. Sanidade opcional.
- Variações do Garfield. Versões de Garfield desenhadas à mão no estilo “comix” underground, geralmente em guardanapos de papel.
- Barfield. Tiras de Garfield sutilmente modificadas para incluir funções corporais divertidas.
- Segunda-feira permanente. Comentários literários sobre tiras selecionadas.
- Arbuckle. Tiras fielmente redesenhadas por “artistas” aleatórios da internet, com uma reviravolta dramática: Jon não pode realmente ouvir Garfield, porque ele é, afinal de contas, um gato.
- Randomizador do Garfield. Infelizmente extinto – combinava painéis aleatórios para formar “novas” tiras do Garfield.
Então, vamos prosseguir para a parte “kov” de Garkov. A melhor descrição das cadeias de Markov que já li está em capítulo 15 do Pérolas de programação:
Um gerador pode criar um texto mais interessante fazendo com que cada letra seja uma função aleatória de sua antecessora. Portanto, poderíamos ler um texto de amostra e contar quantas vezes cada letra segue um A, quantas vezes elas seguem um B e assim por diante para cada letra do alfabeto. Quando escrevemos o texto aleatório, produzimos a próxima letra como uma função aleatória da letra atual. O texto Order-1 foi criado exatamente por esse esquema:
t I amy, vin. id wht omanly heay atuss n macon aresethe hired boutwhe t, tl, ad torurest t plur I with hengamind tarer-plarody thishand.
Podemos estender essa ideia para sequências mais longas de letras. O texto de ordem 2 foi criado gerando cada letra como uma função das duas letras que a precedem (um par de letras é geralmente chamado de digrama). O digrama TH, por exemplo, é frequentemente seguido em inglês pelas vogais A, E, I, O, U e Y, menos frequentemente por R e W, e raramente por outras letras.
Ther I the heingoind of-pleat, blur it dwere wing waske hat trooss. O senhor não pode ficar sentado”. “O senhor poderia”, eu disse, “que o vídeo não estava lá.
O texto de ordem 3 é construído escolhendo-se a próxima letra em função das três letras anteriores (um trigrama).
Eu os tenho o viu o amanhã. E o senhor pensa que, antes de viajar, o senhor foi um dos que mais se destacaram,
Quando chegamos ao texto da ordem 4, a maioria das palavras é em inglês, e o senhor talvez não se surpreenda ao saber que ele foi gerado a partir de uma história de Sherlock Holmes ( “The Adventure of Abbey Grange” (A aventura de Abbey Grange)).
O senhor ouviu”. “Exatamente, ele está muito feliz com o problema, e por Hopkins! Isso é uma das dificuldades que o senhor tem. O senhor se apressou?” “Sangue noite que.
Portanto, o texto nas tiras de Garkov é gerado exatamente dessa forma, mas usando palavras em vez de letras. O corpus de entrada é, como o senhor poderia esperar, o texto de muitas tiras antigas do Garfield.
O que me surpreende nas cadeias de Markov é a inacreditável simples são. Uma cadeia de Markov não tem memória dos estados anteriores: o próximo estado (palavra, no nosso caso) é escolhido com base em um lançamento aleatório de dados e uma pesquisa em uma tabela dos estados que tendem a seguir historicamente o estado atual no corpus de entrada. Com um corpus de entrada adequado, eles funcionam quase que estranhamente bem, uma prova do amplo poder da inferência estatística rudimentar. O Garfield está no mercado desde 1978 e ainda está em andamento… bem, em andamento, portanto, não há falta de material para trabalhar.
Agora vamos tentar nós mesmos. Eu alimentei o texto dos últimos doze Ensaios de Paul Graham para esse gerador de Markov on-line, usando dois agrupamentos de palavras – o que Bentley chama de “Order-2”. Aqui está o resultado que obtive:
No entanto, o senhor pode sentir a necessidade de aproveitar o aumento do preço baixo. Os senhores não estão todos jogando um jogo de soma zero. Não há um número fixo de startups; nós financiamos startups que financiamos para trabalhar em questões de importância passageira. Mas estou desconfortavelmente ciente de que isso faz parte de qualquer ilusão sobre o problema de comer demais ao parar de comer. Eu não podia simplesmente evitar que a Internet se tornasse, porque a empresa é a nova tendência de se preocupar obsessivamente com o que significava para alguém, geralmente uma pessoa de fora, que deliberadamente provocava brigas em uma startup em vez de simplesmente iniciá-la. O senhor sabe como a Lista A é selecionada. E até isso dá mais trabalho.
Mas as cadeias de Markov não são úteis apenas para gerar automaticamente paródias de ensaios de Paul Graham. Elas também são bastante práticas. O senhor pode até dizer que as cadeias de Markov são uma grande parte do que alimenta a Internet atual. O mais notável, pelo menos para mim, é que as cadeias de Markov são a base da A fórmula do PageRank de um trilhão de dólares do Google:
O [PageRank] usa um modelo de um surfista aleatório que fica entediado após vários cliques e muda para uma página aleatória. O valor do PageRank de uma página reflete a chance de o usuário aleatório chegar a essa página clicando em um link. [PageRank] pode ser entendido como uma cadeia de Markov em que os estados são páginas e as transições são todas igualmente prováveis e são os links entre as páginas.
Como resultado da teoria de Markov, é possível demonstrar que o PageRank de uma página é a probabilidade de estar nessa página depois de muitos cliques. Isso é igual a t-1 em que t é a expectativa do número de cliques (ou saltos aleatórios) necessários para ir da página até ela mesma.
A propósito, se o senhor não leu o artigo original de 1998 sobre o PageRank, intitulado O ranking de citações do PageRank: Bringing Order to the Web (pdf), o senhor realmente deveria. É impressionante como, dez anos depois, muitas das previsões desse artigo se concretizaram. Ele está repleto de coisas interessantes; a lista dos 15 principais sites do PageRank por volta de 1996 na Tabela 1 é um lembrete revelador do quanto avançamos. Além disso, há referências a sites pornográficos também!
Os modelos markovianos – especificamente, os modelos Markov ocultos – também são relacionados ao nosso velho amigo, a filtragem bayesiana de spam. Eles são ainda melhores! O exemplo mais notável é o Discriminador CRM114, conforme descrito neste excelente apresentação (pdf).
Se o senhor brincar com o Sintetizador de texto Markov, o senhor descobrirá rapidamente que os métodos Markov são tão bons quanto o corpus de entrada. Se o senhor digitar um monte de palavras iguais, ou palavras sem sentido aleatórias, é isso que receberá de volta.
Mas é difícil imaginar um corpus de entrada mais ideal para as técnicas markovianas do que a vastidão inimaginável da Web e do e-mail, não é mesmo?