Qual a melhor palavra no Termo? Data science ao resgate
Provavelmente você ja ouviu falar do Termo (ou sua versão em inglês, o Wordle), se não, permita-me fazer um breve resumo:
Cada dia uma mesma palavra é desbloqueada para todos que estão jogando. Seu objetivo é acertar que palavra é essa em até 7 tentativas, e quanto mais rápido você acertar maior seu status social. Ao chutar uma palavra o jogo te diz para cada letra se: a letra está na palavra e está no lugar certo (cor verde), a letra está na palavra mas está no lugar errado (cor amarela) ou a letra não está na palavra secreta (preto).
Com tamanho fenomeno, começaram a aparecer teorias interessantes de qual seria a melhor palavra para se começar o jogo. Seguindo o vídeo super educativo do 3Blue1Brown decidi fazer minha tentativa de achar a melhor palavra para o português.
Primeira Intuição
A abordagem mais intuitiva é provavelmente pegar palavras que contenham letras com alta frequência na nossa língua, como a e i, e chutar uma dessas.
Vamos fazer um exemplo em python e ver o que acontece!
Primeiro encontrei uma lista da frequência de cada letra no nosso alfabeto. Em seguida, uma lista de (quase) todas as palavras da nossa língua do IME-USP. Com um snippet filtramos só as palavras com 5 letras para usar nas nossas análises.
Hora do Jupyter
Vamos carregar nossos dados em data frames e criar uma função para calcular um "score" para cada palavra a partir da frequência de cada letra contida nela.
As palavras vão precisar de algum tratamento: primeiro tirar o \n do final, em seguida deixar todas as letras minúsculas, e finalmente tirar acentos
Bem melhor. Agora vamos pensar em como criar um score para cada palavra. Uma sugestão bem simples seria calcular a média das frequências.
Agora basta calcular para todas as palavras e ver quais tem o maior score, vamo?
Explicando: usando list comprehension calculamos o score de cada palavra com a nossa função, em seguida passamos tanto a lista de palavras como a lista de scores para o pandas criar um data frame para nos, ordenamos esse dataframe por score e voilá temos as palavras com maior score.
Mas Espera…
Tem algo errado com o nosso score. Ele sacou que palavras com a são boas porque a é uma letra bem frequente no português, mas exagerou! Os obcecados pelo jogo perceberam que esses chutes todos seriam muito ruins, ao repetir uma letra na palavra eu deixo de ter informação sobre outras letras.
A palavra informação traz consigo a resposta final de qual é a melhor palavra, vamos pensar então o que seria a melhor palavra e como informação é o que precisamos para resolver.
Uma palavra muito boa deve, na media dos jogos, riscar muitas alternativas, fazendo nós ficarmos com um espaço de possibilidade menor e assim ter mais chance de ganhar o jogo rápido e ser reconhecido por nossos amigos e familiares. Chutar uma palavra como xeque provavelmente seria uma péssima ideia, poucas palavras tem x, o e repetido não nos traz informação e q também não é tão comum assim. Já banco parece muito melhor, separa as palavras que têm a, b, n, c e o de todas as outras, cortando bastante nosso espaço de possibilidades.
Para formalizar essa ideia precisamos da ideia de entropia.
Entropia
entropia é definida como sendo uma forma de medir o grau médio de incerteza a respeito de fontes de informação, o que consequentemente permite a quantificação da informação presente que flui no sistema. Em termos simples, o conceito de entropia se associa à ideia de que, quanto mais incerto é o resultado de um experimento aleatório, maior é a informação que se obtém ao observar a sua ocorrência.
Essa definição já nos ajuda bastante a entender o que é entropia. Mas talvez um exemplo seja mais intuitivo.
Vamos supor que estamos em uma estação meteorológica e queremos avisar como está o clima hoje. Se o tempo esta sempre ensolarado, eu avisar para um amigo que aqui está sol é pouco informativo, causa pouca surpresa, certo? Porem se muito raramente chove, eu dizer que está chovendo traz mais surpresa.
Se p é a probabilidade de algo acontecer (a chance de chover em um dia na nossa estação), podríamos definir a surpresa de algo como 1/p. Porem isso tem um problema, se eu tenho um evento que acontece sempre, como fazer sol no deserto, p seria 1, então a nossa surpresa seria 1/1 =1, o que é esquisito, seria melhor se a surpresa de algo que acontece sempre fosse zero. Uma maneira de lidar com isso é definir a surpresa como log(1/p), assim quando p=1, log(1/1) = log(1) = 0. Muito melhor.
Agora, queremos decidir quão interessante é ouvir a previsão do clima desse local, queremos saber quão surpresos nós vamos ficar em média ouvindo essas previsões. Se encontrássemos um lugar com surpresa média alta seria incrível! Poderíamos ficar ouvindo o clima todo dia que seria sempre uma reviravolta digna de maratona na Netflix.
Para calcular essa surpresa média nossa abordagem pode ser a seguinte, vamos calcular a média da surpresa ponderadas pela frequência com que elas ocorrem. Se em um lugar faz sol 70% do tempo e chuva 30% do tempo, 70% do tempo nossa surpresa vai ser log(1/0.7) = 0.51 e 30% do tempo seria log(1/0.3)=1.73 (estou usando log na base 2, como mandam os antigos deuses da teoria da informação). Assim podemos calcular nossa surpresa media como sendo 0.7*0.51 + 0.3*1.73 = 0.876. Isso é a entropia, a surpresa media de uma variável. Show!
Formalizando essa ideia, se nossa probabilidade de um evento é p, então a surpresa é log2(1/p), e finalmente, a entropia, ou surpresa media é a soma de p*log2(1/p) para cada alternativa possivel. Essa fórmula é geralmente escrita da seguinte maneira:
Chique, vamos voltar para o Termo e aplicar essa ideia de entropia.
Entropia das Palavras
Nós podemos definir a entropia de uma palavra olhando para cada possível padrão de cores que aparece em cima dela.
No nosso corpo de palavras nós temos 6026 palavras, vamos supor que começamos com a palavra canoa e recebemos um padrão verde, verde, preto, amarelo e preto. Em seguida pegamos todas as palavras que satisfazem essa regra, como por exemplo calvo e cacho (vide a foto de exemplo) e calculamos a proporção que essas palavras representam do total. Vamos supor que no nosso exemplo aqui sobraram 189 palavras, isso significa que nosso p seria 189/6026 = 0.031. A nossa surpresa ao ver esse padrão seria log2(0.031) = 5.01, bem surpreendente.
Então ja podemos calcular a entropia de cada palavra. O plano é o seguinte: escolhemos uma palavra, depois criamos todos os padrões de cores possíveis, para cada padrão, filtramos as palavras que satisfazem ele e calculamos a proporção destas sobre todas as do nosso corpo de texto, finalmente calculamos a surpresa ponderada de cada um (p*log(1/p)) e somamos todas para ter a entropia da palavra. Ufa, passou a teoria, bora pro codigo.
Primeiro uma função para ver se dado um padrão e uma palavra de referência (aquela que queremos calcular a entropia), uma palavra é uma alternativa
Agora uma função para dado uma palavra de referência, e um padrão de cores, acha todas as alternativas possíveis
E finalmente nossa função para calcular a entropia de uma palavra, vamos precisar da palavra, de uma lista com todos os padrões possíveis e uma lista com todas as palavras
Para gerar todos os padrões possíveis, podemos usar a função product do pacote padrão itertools
Bora botar pra rodar isso ai, força que essa demora
Pega o resultado e coloca num data frame para visualizar mais fácil e salvar se quiser
Ta resolvido, seria é a melhor palavra, não repete letras, tem letras bem frequentes e melhor: é a com maior entropia. Ser nerd é bom demais.
Conclusão
Entropia é um conceito muito útil criado por um pessoal fera da teoria da informação, ela pode ser usada em muitas áreas diferentes, você consegue pensar em algum caso que seria util no seu dia a dia?
E agora que descobrimos a melhor palavra para começar, alguma ideia de como chutar a segunda? e a terceira, quarta?
Valeu! Qualquer coisa me chama: ggyshay@gmail.com
