Algumas histórias do desenvolvimento de puzlink.js

Eu escrevi uma nova ferramenta puzzlehunt chamada puzlink.js, que hospedei em meu site. Pensei em fazer um post parecido com o meu post de cromulência onde falo sobre toda a experimentação e implementação, e prometo isso e outras coisas. Mas eu era preguiçoso, então não o fiz. Em vez disso, aqui estão algumas histórias de desenvolvimento.

Salve-me da minha biblioteca padrão. Peguei essa frase em Write code that is easy to delete e adorei desde então. Coisas que escrevi e gostaria de não ter escrito: DefaultMap, Bitset, range, product, windows, accumulate, memoize. O maior e mais usado utilitário deve ser LogNumque reimplementa a matemática no semi-anel logarítmico. Passei uma boa parte das últimas duas semanas apenas escrevendo coisas e depois extraindo utilitários que incorporei bastante.

O teste qui-quadrado. Quando eu estava no ensino médio, estudar estatística consistia em aprender todos esses testes diferentes e quando aplicar cada um deles. Foi então que aprendi pela primeira vez sobre o teste do qui-quadrado, onde você faz uma série elaborada de procedimentos para adivinhar algum tipo de número e compará-lo com outro número. Eu não entendia quais eram os números na época. Nunca mais pensei no teste do qui-quadrado até ler o código-fonte do puzlink, onde ele é usado para detectar distribuições incomuns de letras. Então eu tive que reaprender o que era.

O teste do qui-quadrado fez muito mais sentido quando li sobre matemática. Digamos que, na distribuição de letras em inglês, a letra E tenha frequência relativa $p$. Observamos então $n$ letras, extraídas iid desta distribuição. O número de vezes que E aparece é uma variável aleatória, digamos $X\sim B(n, p)$

Frequentista durante a semana. Olha, a estatística bayesiana é legal e tudo, mas acho que só sou bayesiana nos finais de semana. Por que calcular três probabilidades quando se pode resolver o problema? Em vez de ter que pensar sobre a probabilidade, antes, e marginal, só preciso calcular o marginal. E muitas vezes, calcular o marginal é complicado por si só.

Suponha que eu tenha $n$ palavras, de comprimentos $\ell_1, \ldots, \ell_n$

Relacionamento semântico do lado do cliente. Eu queria implementar links no formato “contém uma palavra de (categoria)”. Você pode codificar várias categorias, mas não pode codificar todos deles, então seria bom ter uma solução geral. E eu queria poder fazer isso inteiramente do lado do cliente, com um tamanho total de dados inferior a 1 MB.

Pensei em usar incorporações de palavras, mas encaixar as coisas em 1 MB parecia difícil. Se você tiver vetores padrão de 300 dimensões de carros flutuantes de 32 bits, serão cerca de 850 palavras distintas. Você pode usar hash ou quantizar para talvez obter até 20 mil palavras, mas temos pelo menos 50 mil palavras nas quais estamos potencialmente interessados. Além disso, uma vez que você tenha vetores semelhantes, como você descreve o relacionamento deles? Acabei usando o WordNet, que tinha dados de ontologias. Isso nos dá verificações de palavras da mesma categoria e com menos de 500 kB.

Poset de cones sob contenção. Uma ideia importante que roubei do Collective.jl foi a de característicasque são propriedades binárias que uma palavra pode ter, como “tem pelo menos duas consoantes seguidas”. Muitos dos recursos que generalizei em métricas: neste caso, a métrica é “número máximo de consoantes seguidas”, que podemos transformar em traços exigindo “pelo menos duas” da métrica, ou “exatamente três”, e assim por diante. O uso de métricas nos permite reutilizar a computação e remover relatórios de recursos redundantes: se soubermos que cada palavra tem exatamente três consoantes seguidas, não precisamos relatar que cada palavra tem pelo menos duas consoantes seguidas.

Tentei então generalizar ainda mais, tornando as métricas multidimensionais. Uma métrica bidimensional é algo como “tem (número) bigramas, cada um repetindo (número) vezes”. Converter isso em um recurso consiste em especificar uma região do espaço em que estamos interessados, e nossas regiões eram cones afins gerados por um subconjunto da base padrão. Sendo o nerd que sou, fiquei animado para usar algumas das palavras matemáticas que aprendi na faculdade na “vida real”. Tipo, comecei a pensar em eliminar cones redundantes considerando o poset sob contenção, pegando o subconjunto induzido por um subconjunto das palavras de entrada e mantendo apenas os extremos. Isso funcionou! Mas nenhuma das métricas que acabei usando era multidimensional, então me livrei de todo aquele código.