A Lista, a Tese e Por Que Ela Começa em Compressão

Item da lista de Ilya: neste artigo, nenhum diretamente. Este é o artigo de abertura da série: apresenta as trinta referências, corrige três atribuições erradas que circulam com a lista, e enuncia a tese que amarra os 52 artigos seguintes.

Índice da Série: A Lista de Ilya

• 1. A Lista, a Tese e Por Que Ela Começa em Compressão (Você está aqui)

Existe uma lista. Ela circula há anos em fóruns, repositórios e conversas de corredor, atribuída a Ilya Sutskever, acompanhada de uma promessa que ninguém sabe se ele realmente fez: quem entender estes trinta trabalhos entenderá noventa por cento do que importa em aprendizado profundo. A promessa é boa demais para ser verdade e boa demais para ser ignorada.

O problema da lista não é o conteúdo. É que ela é uma lista de artigos, e um artigo científico é escrito por quem já sabe por que ele existe e para quem está pesquisando o mesmo assunto. Isso exclui este pobre escriba e, provavelmente, a esperançosa leitora. Por exemplo, Rissanen não explica teoria da informação no seu artigo; ele a usa. Ele e seus coautores não explicam retropropagação; eles assumem que a inocente leitora a derivou ontem. Ler a lista na ordem em que ela aparece é como entrar numa conversa longa no meio da terceira hora de discussão.

Esta série existe para transformar a lista em um curso para autodidatas. Não em resumos, em derivações completas, exercícios que se resolvem com papel e lápis, e código C++23 que compila. Serão cinquenta e dois artigos, seis partes, e uma tese que amarra tudo. A ambição é o meu fraco, não o meu pecado favorito.

Vou repetir só para não esquecer: código C++23, eu vou na vibe do Elon Musk, e da maioria dos desenvolvedores de laboratórios chineses. Performance é fundamental. Mas, se a leitora tiver estomago para isso, pode usar Python, será mais fácil e, dependendo da sua experiência, deve dar menos trabalho enquanto estamos aprendendo.

Se a corajosa leitora concordar e quiser continuar, começaremos por um problema que cabe em duas linhas.

1. Uma lista que parece um sorteio

Antes da tese, o incômodo. A lista de Ilya, agrupada como ela costuma aparecer, contém complexidade de Kolmogorov e geração aumentada por recuperação. Contém um autômato celular que simula café com leite se misturando e um sistema de reconhecimento de fala em mandarim. Contém um ensaio de blog sobre redes recorrentes e uma tese de doutorado sobre a definição matemática de inteligência. Em fim, parece uma boa, complexa e difícil lista de artigos, relacionados pelo campo de estudo e por alguma maldade pedagógica. A assustada leitora deve lembrar que nada é tão complexo que não possa ser analisado, ou dividido em blocos. Neste caso, vamos dividir em seis blocos:

Fundamentos de aprendizado e complexidade. O tutorial de Rissanen sobre comprimento de descrição mínima, o tratado de Li e Vitányi sobre complexidade de Kolmogorov, o artigo de Hinton e van Camp sobre pagar bits pelos pesos de uma rede, o autômato do café, e o ensaio de Aaronson sobre a primeira lei da complexodinâmica.

Redes convolucionais. AlexNet, o curso CS231n de Stanford, a ResNet, o artigo de mapeamentos identidade que a explica, e as convoluções dilatadas de Yu e Koltun.

Modelos de sequência. O ensaio de Karpathy sobre a eficácia irracional das redes recorrentes, o de Olah sobre LSTMs, a regularização de RNNs de Zaremba, Sutskever e Vinyals, e as redes recorrentes relacionais de Santoro.

Atenção e Transformers. Bahdanau, Cho e Bengio; Attention Is All You Need; o Annotated Transformer de Harvard. Aqui, vamos complementar e expandir usando a série transformers deste mesmo blog.

Arquiteturas avançadas. Pointer Networks, Order Matters, máquinas de Turing neurais, passagem de mensagens para química quântica, redes de relação, e o autoencoder variacional com perdas.

Escala, eficiência e superinteligência. Deep Speech 2, as leis de escala de Kaplan, o GPipe, a tese sobre superinteligência de máquina, previsão multi-token, recuperação densa de passagens e RAG.

A atenta leitora que olhar essa coleção e concluir que alguém juntou trabalhos de que gostava está sendo razoável. Mas está errada. Há uma tese escondida na lista, e o resto deste artigo é dedicado a torná-la visível, não como slogan, mas como uma conta que a leitora vai refazer no papel antes de terminar a Seção 4.

Para isso, precisamos de duas sequências de bits.

2. Duas sequências que a estatística não distingue

Considere duas sequências binárias de comprimento $n = 64$. Escrevo as duas literalmente, porque uma sequência aleatória é algo que a leitora não pode conferir.

A primeira é

e a segunda é

Contemos os símbolos. Em $A$, os zeros ocupam as posições pares e os uns as ímpares: $32$ de cada. Em $B$, contando com paciência, também: $32$ zeros e $32$ uns. As duas sequências têm exatamente a mesma distribuição empírica de símbolos.

Precisamos agora de uma forma de medir quanto custa descrever uma sequência. Qualquer sequência.

Um modelo $Q$ é uma regra que atribui, a cada posição $t$, uma probabilidade $Q(s_t \mid \text{contexto}_t)$ ao símbolo que ali aparece. Dado um modelo, definimos o comprimento de descrição da sequência $s$ sob $Q$ como

medido em bits. Um símbolo que o modelo julgava certo ($Q = 1$) custa zero; um que ele julgava impossível ($Q = 0$) custa infinito; um símbolo sobre o qual ele não tinha opinião ($Q = 1/2$) custa exatamente um bit.

Por ora, trate essa fórmula como definição de trabalho. Ela parece uma conta de conveniência, e a atenta leitora tem todo o direito de exigir prova de que existe um código real que atinja esse custo. A prova existe, é construtiva, e é o assunto do Artigo 3 da série. Sem pressa chegaremos lá. Aqui, basta saber que o número significa alguma coisa.

O modelo de ordem zero, ou memoryless, ignora o contexto: atribui a cada símbolo sua frequência empírica na sequência inteira. Como as duas sequências têm $32$ zeros e $32$ uns, esse modelo atribui $\hat p(0) = \hat p(1) = 1/2$ às duas, e o custo é

Sessenta e quatro bits para descrever sessenta e quatro bits. O modelo não economizou nada, e, mais importante, não economizou nada nas duas séries.

Empate exato. E aqui está o incômodo: para qualquer leitora humana, $A$ e $B$ são obviamente diferentes. Uma se descreve em nove palavras, zero e um, repetidos trinta e duas vezes, e a outra não se descreve em nenhuma quantidade razoável de palavras. Se não acreditar em mim, tente. Não tenha pressa, eu espero.

Se a nossa medida diz que elas custam o mesmo, a medida está errada ou o modelo está cego.

O modelo está cego. Vejamos com o quê.

3. Contar pares em vez de símbolos

Um modelo de ordem um, ou de Markov de primeira ordem, atribui a cada símbolo uma probabilidade condicionada ao símbolo imediatamente anterior. Em vez de uma distribuição sobre ${0, 1}$, ele guarda duas: $Q(\cdot \mid 0)$ e $Q(\cdot \mid 1)$. Estimamos ambas por contagem das transições observadas.

Uma sequência de $64$ símbolos tem $63$ transições. Contemos.

Em $A = 0101\ldots01$, toda posição par é um zero seguido de um um, e toda posição ímpar é um um seguido de um zero. Como a sequência começa em zero e termina em um, há $32$ transições $0 \to 1$ e $31$ transições $1 \to 0$, e nenhuma outra. Em $B$, as quatro transições possíveis aparecem todas. A tabela completa será:

Some as colunas: $63$ em cada, como deve ser.

As probabilidades condicionais empíricas saem dividindo cada contagem pelo total de vezes que o contexto ocorreu. Em $A$, o zero aparece $32$ vezes como contexto, todas as suas ocorrências, exceto nenhuma, já que a sequência termina em um. E todas as $32$ são seguidas de um. Logo

Simetricamente, o um aparece $31$ vezes como contexto e todas as $31$ são seguidas de zero:

O primeiro símbolo não tem contexto, então o pagamos sob um modelo uniforme: $1$ bit. Os outros $63$ custam

e portanto

Um bit. A sequência inteira, sessenta e quatro símbolos, descrita por um único bit, o valor do primeiro símbolo, mais um modelo que diz alterne. Que é, palavra por palavra, a descrição em nove palavras que a leitora já tinha na cabeça.

Agora $B$. As quatro probabilidades condicionais, com o zero aparecendo $32$ vezes como contexto e o um $31$:

Nenhuma delas é próxima de zero ou de um; todas rondam a metade. O custo, somando as $63$ transições e o bit do primeiro símbolo, é

Contra $64$ bits brutos, o modelo de ordem um economizou em $B$ menos de um bit. Contra $A$, a razão é

Duas sequências que a estatística de primeira ordem declarou idênticas custam, sob o mesmo modelo de segunda ordem, sessenta e três vezes uma da outra.

Vale a pena parar e olhar para o que aconteceu.

Não trocamos os dados. Não trocamos a medida. Trocamos apenas a classe de perguntas que o modelo tem permissão de fazer sobre os dados. De com que frequência aparece cada símbolo? para com que frequência aparece cada par? E o veredito mudou por um fator de sessenta.

Isto é a primeira das três lições deste artigo: quanta informação existe em um dado não é propriedade do dado. É propriedade do par formado pelo dado e pelo modelo. Perguntar qual a entropia deste arquivo? sem dizer sob qual modelo é uma pergunta malformada, ainda que se ouça o tempo todo.

4. O modelo também custa bits

Há uma trapaça na conta anterior, e a atenta leitora já a percebeu. Descrevemos $A$ em um bit, mas isso só funciona se quem recebe a descrição já souber o modelo. Se a destinatária não sabe que a regra é alterne, um bit não lhe diz nada.

Um protocolo honesto tem dois passos. Primeiro transmitimos o modelo; depois transmitimos os dados sob o modelo. O custo total é a soma, e ela merece ser nomeada:

na qual $H$ é a hipótese, ou modelo, e $D$ são os dados. O termo $L(D \mid H)$ é o que calculamos na seção anterior. Falta $L(H)$.

Nosso modelo de ordem um tem dois graus de liberdade: quantas vezes o zero foi seguido de um, e quantas vezes o um foi seguido de um. Ambas as contagens estão entre $0$ e $63$, e $63 < 2^6$, então seis bits bastam para cada uma:

Esta escolha é crua e eu a registro como tal. Existem codificações melhores para inteiros pequenos, e a pergunta de qual precisão usar para cada parâmetro é séria o bastante para ocupar dois artigos desta série. Por enquanto, vamos com os seis bits por contagem.

A tabela completa fica sendo:

Olhe a última linha com atenção.

Descrever $B$ pelo protocolo de dois passos custa setenta e cinco bits para transmitir sessenta e quatro. O modelo cobrou doze bits e devolveu menos de um. Foi um péssimo negócio, e a conta o entrega sem que precisemos de nenhum critério externo, nenhum conjunto de validação, nenhuma heurística. Só boa vontade e atenção.

Esta é a segunda lição: um modelo que não descreve os dados não é neutro; ele é caro.

A intuição comum diz que um modelo inadequado não ajuda; a contabilidade de bits diz que ele atrapalha, e diz exatamente quanto. Onze bits, neste caso.

O argumento inteiro do princípio de comprimento de descrição mínima está nessas duas linhas de tabela. Rissanen o formalizou em 1978, e esta série dedica dois artigos ao assunto: um para a versão crua que acabamos de usar, outro para a versão refinada, na qual a precisão dos parâmetros deixa de ser escolha nossa e passa a sair da teoria. Não vou antecipá-los. O que importa aqui é que a leitora viu o mecanismo funcionar em números que cabem no espaçõ de folha de papel tingida de lápis.

5. Por que bits e não erro

Falta a terceira lição, e ela é a mais incômoda.

Suponha que tivéssemos avaliado os dois modelos de ordem um pela medida usual em aprendizado de máquina: erro de predição. Para cada posição, o modelo aposta no símbolo mais provável dado o contexto; contamos os acertos. Em $A$, o modelo acerta as $63$ posições previsíveis, ou 100%. Em $B$, com o mesmo critério de aposta, acerta $36$ das $63$, ou $57,1\%$, pouco acima do chute não informado.

Repare que a razão entre as taxas de acerto é $100/57{,}1 = 1{,}75$, ao passo que a razão entre os custos de descrição é $63{,}05$.

A medida de acerto comprime a diferença entre os dois casos em um fator inferior a dois; a medida de bits a expande em sessenta e três. Não é que uma esteja certa e a outra errada. É que elas medem coisas distintas, e só uma delas cobra do modelo o custo de existir.

Esse é o defeito estrutural do erro de predição.

Um modelo de ordem cinco sobre $B$ acertaria mais; um modelo que memorizasse $B$ inteira acertaria tudo. O erro de treino desce monotonicamente conforme o modelo cresce, e por isso, sozinho, ele nunca diz onde parar.

A prática inventou várias muletas para esse problema. Regularização, que soma ao erro um termo proporcional ao tamanho dos pesos. Contagem de parâmetros, que penaliza modelos grandes por decreto. Validação cruzada, que separa dados para julgar o modelo em material que ele não viu. Navalha de Occam, que é um conselho estético do século XIV promovido a método. Todas funcionam até certo ponto, e todas têm o mesmo defeito: são acréscimos, escolhidos de fora, com constantes que alguém precisa ajustar.

A contabilidade de bits não é acréscimo. O custo do modelo aparece porque a destinatária precisa recebê-lo, e ponto. Não há hiperparâmetro de regularização a escolher, não há partição de validação a sortear, não há constante mágica: há um canal que só transporta bits e uma conta que precisa fechar.

É essa propriedade, a de que a penalidade por complexidade emerge em vez de ser imposta, que faz da compressão um candidato fundamental, e não apenas mais uma técnica. E é por isso que a lista de Ilya começa onde começa.

Vale registrar o limite honesto do argumento antes de seguir.

Nada do que dissemos, até agora, prova que comprimir bem implica generalizar bem; existem contraexemplos construídos, e a relação entre comprimento de descrição e desempenho fora da amostra tem sutilezas que a série vai enfrentar nos artigos sobre MDL (Minimum Description Length) refinado e sobre a medida universal de inteligência. O que os números desta seção sustentam é mais modesto e ainda assim considerável: bits medem algo que erro de treino não mede, e medem sem pedir permissão.

MDL?

Quando falamos de inteligência artificial e aprendizado de máquina, a sigla MDL significa Minimum Description Length (Princípio do Comprimento Mínimo de Descrição).

Esse conceito vem da teoria da informação e da teoria da aprendizagem estatística, sendo uma formalização prática da famosa Navalha de Ockham: a explicação mais simples para um conjunto de dados tende a ser a melhor.

No contexto de modelos refinados (ou otimização de modelos), o MDL avalia o custo total de um modelo dividindo-o em duas partes:

\[L(M_{\text{total}}) = L(M) + L(D \mid M)\]

1. $L(M)$ — Comprimento do Modelo: O tamanho da descrição do próprio modelo (número de parâmetros, complexidade da rede, regras de decisão). Um modelo imenso ou altamente complexo tem um $L(M)$ alto.
2. $L(D \mid M)$ — Comprimento dos Dados dado o Modelo: O tamanho da descrição dos erros de previsão do modelo em relação aos dados reais (os resíduos). Se o modelo for ruim, a lista de erros será enorme, resultando em um $L(D \mid M)$ alto. O objetivo no refinamento de um modelo usando MDL é minimizar a soma dessas duas partes.

• Evitar o Underfitting: Um modelo simples demais tem $L(M)$ baixo, mas erra tanto que seu $L(D \mid M)$ explode.
• Evitar o Overfitting: Um modelo extremamente complexo decora o ruído dos dados, tornando $L(D \mid M)$ muito pequeno, mas seu $L(M)$ fica gigante.

O ponto ideal de refinamento encontra o equilíbrio exato onde o modelo é complexo o suficiente para capturar o padrão real dos dados sem se tornar excessivamente pesado ou ajustado ao ruído.

6. O mesmo cálculo, dez bilhões de vezes

A objeção previsível, neste ponto, é de escala. Sessenta e quatro bits e um modelo com dois parâmetros são um brinquedo didático pedagógico sem aplicação prática. O que acontece quando os dados são um corpus de texto e o modelo tem bilhões de pesos?

Acontece exatamente a mesma coisa. A fórmula não muda de forma; muda de tamanho.

Um modelo de linguagem atribui, a cada posição de uma sequência de tokens, uma distribuição sobre o vocabulário. O custo de descrever o token observado é $-\log_2 Q(x_t \mid x_{<t})$, e a média desse custo sobre o corpus tem nome consagrado: entropia cruzada, quando medida em nats, e bits por token, quando medida em bits. São o mesmo número em unidades diferentes, e a série Transformers já derivou a relação entre eles em detalhe.

nats?

No contexto de Teoria da Informação, aprendizado de máquina e modelos de linguagem, a palavra nats (singular: nat) é a unidade de medida padrão para informação, entropia e entropia cruzada quando os cálculos de logaritmo utilizam a base natural (o número de Euler, $e$). E a inocente leitora achando que nunca iria usar o número de Euler.

Assim como o bit é a unidade de informação obtida ao aplicar o logaritmo na base 2 ($\log_2$), o nat é a unidade obtida ao utilizar o logaritmo natural ($\ln$ ou $\log_e$).

O nome vem da contração de natural unit of information (unidade natural de informação).

Enquanto 1 bit quantifica a incerteza associada à escolha entre 2 opções igualmente prováveis (como o cara ou coroa), 1 nat quantifica a incerteza associada a uma escolha entre $e \approx 2{,}71828$ opções igualmente prováveis.

Para converter o valor de entropia ou custo de um modelo de linguagem de uma unidade para outra, aplica-se a mudança de base do logaritmo:

\[1 \text{ nat} = \frac{1}{\ln(2)} \text{ bits} \approx 1{,}442695 \text{ bits}\] \[1 \text{ bit} = \ln(2) \text{ nats} \approx 0{,}693147 \text{ nats}\]

Tome um vocabulário de $V = 50\,257$ tokens, que é o do GPT-2 e virou referência de comparação. Um modelo que não soubesse nada atribuiria probabilidade uniforme $1/V$ a cada posição, custando

Um modelo treinado faz melhor. Quanto melhor, e o que isso significa em compressão:

Nada de novo na conta. É o mesmo $-\log_2 Q$ do exemplo de $64$ bits, que vimos, somado dez bilhões de vezes em vez de sessenta e quatro.

Falta a outra metade do protocolo: o modelo também precisa ser transmitido. Com números de ordem de grandeza, e declarando que são estimativas grosseiras:

Três gigabytes de modelo mais dois e meio de resíduo descrevem quarenta gigabytes de texto. O modelo se paga, e se paga com folga de sete vezes.

Compare com a linha de $B$ na tabela da Seção 4, na qual o modelo custou doze bits e economizou menos de um. É o mesmo julgamento, com os mesmos termos, aplicado a objetos que diferem em dez ordens de grandeza. A diferença entre um modelo que vale a pena e um que não vale nunca foi qualitativa; sempre foi uma subtração.

Duas perguntas nascem daqui, e a série reserva artigos inteiros para cada uma. A primeira: quando o modelo deixa de se pagar? A segunda: quanto ele melhora conforme cresce, e essa melhora tem forma previsível? A resposta à segunda é uma lei de potência estável ao longo de sete ordens de grandeza, e a leitora vai derivá-la na Parte VI, junto com a correção que a reescreveu dois anos depois de publicada. Mas, por agora, guarde isso: lei de potência estável. Será importante.

7. As três correções à lista

Antes do mapa, um serviço de manutenção. A lista circula com três erros, e repetir erro de citação é precisamente o oposto do que esta série se propõe a ensinar.

O primeiro é o que mais muda a leitura do conjunto. O item Machine Super Intelligence aparece atribuído a Nick Bostrom. Não é dele. É a tese de doutorado de Shane Legg, defendida em 2008 na Università della Svizzera Italiana, sob orientação de Marcus Hutter.

A diferença não é bibliográfica. Bostrom escreveu filosofia sobre riscos de superinteligência, trabalho relevante, mas de outra natureza. Legg escreveu uma definição matemática de inteligência, construída sobre complexidade de Kolmogorov e sobre a distribuição universal de Solomonoff. A medida que ele propõe soma o desempenho de um agente sobre todos os ambientes computáveis, ponderando cada ambiente pela sua simplicidade descritiva:

Não precisamos entender cada símbolo agora. O artigo 48 desta série é dedicado a essa fórmula. O que importa é reconhecer o $K(\mu)$ ali dentro: é complexidade de Kolmogorov, o mesmo objeto do segundo item da lista.

Com a atribuição errada, o último bloco termina em filosofia avulsa e a lista parece se desfazer no fim. Com a atribuição correta, a lista fecha em círculo: ela começa em complexidade descritiva porque termina em complexidade descritiva, agora escrita como definição de agente. Um erro de nome apagava a arquitetura inteira.

O segundo. Variational Lossy Autoencoder aparece atribuído a Alemi et al. É de Chen, Kingma, Salimans, Duan, Dhariwal, Schulman, Sutskever e Abbeel, publicado no ICLR de 2017. Alexander Alemi é autor de Fixing a Broken ELBO, de 2018, trabalho vizinho e igualmente citável, e que a série vai citar, no mesmo artigo, como leitura complementar. A confusão é compreensível e ainda assim vale corrigir, porque o VLAE está na lista por um motivo específico: sua explicação para o latente ignorado é um argumento de bits-back coding, isto é, a Parte I desta série reaparecendo dentro de um modelo generativo.

O terceiro. CS231n não é um artigo; é um curso semestral de Stanford, com dezesseis semanas de aula. Tratá-lo como um item entre trinta seria desonesto com o leitor e com o curso. Esta série o converte em quatro artigos, cobrindo o que ele ensina e o que os papers da lista pressupõem sem explicar: a aritmética de formas da convolução, a inicialização de pesos, a normalização em lote e os otimizadores.

8. O mapa da série

Cinquenta e dois artigos, seis partes, oito ciclos de produção. Cada parte ataca um pedaço da tese. Como eu disse antes, falta de ambição eu não tenho.

Parte I — Compressão, complexidade e o que significa aprender (13 artigos). Formaliza o que este artigo apresentou informalmente. Códigos de prefixo e a desigualdade de Kraft; codificação aritmética e a demonstração de que um modelo probabilístico é um compressor; MDL cru e refinado; complexidade de Kolmogorov, sua incomputabilidade e a indução de Solomonoff; o argumento bits-back de Hinton e van Camp; o autômato do café e a primeira lei da complexodinâmica.

Parte II — Convolução e visão (10 artigos). A convolução discreta derivada do zero, com sua retropropagação e sua conversão em multiplicação de matrizes; AlexNet com a tabela de parâmetros e FLOPs conferida camada a camada; inicialização, normalização e otimizadores; ResNet e a derivação do caminho limpo de gradiente; campo receptivo e dilatação.

Parte III — Recorrência e sequências (6 artigos). A recorrência e seu desdobramento; retropropagação no tempo derivada por completo, com a condição espectral que separa gradiente que desaparece de gradiente que explode; a LSTM porta por porta; GRU; regularização de RNNs; e memória como conjunto, que já traz atenção para dentro da célula.

Parte IV — Atenção e Transformers (3 artigos). Aqui a série é deliberadamente econômica, porque a série Transformers deste blog já é dona do assunto. São três artigos-ponte: Bahdanau lido como documento histórico; Attention Is All You Need auditado, com a derivação completa da tabela de complexidade por camada que quase ninguém refaz; e o Annotated Transformer reimplementado em C++23, já que o original é PyTorch.

Parte V — Arquiteturas avançadas (10 artigos). Pointer Networks, invariância a permutações, máquinas de Turing neurais em dois artigos, passagem de mensagens em grafos, redes de relação, e o autoencoder variacional com perdas — que fecha a parte reencontrando o bits-back da Parte I dentro de um modelo generativo.

Parte VI — Escala, eficiência e superinteligência (10 artigos). A perda CTC derivada por programação dinâmica; a engenharia de treino do Deep Speech 2; leis de escala e a correção do Chinchilla; a fração de bolha do GPipe; a medida universal de Legg e Hutter; previsão multi-token; recuperação densa e a marginalização do RAG. O último artigo diz, sem meias palavras, o que a lista não contém.

8.1 O laboratório

Cada artigo da série vem com pelo menos um laboratório interativo, e este é o primeiro. O painel de cima refaz a conta das Seções 3 e 4 para qualquer sequência que a leitora digitar, sob as ordens zero, um e dois, somando o custo do modelo. Os três presets são $A$, $B$ e a sequência $C$ de blocos de dezesseis que aparece na solução do Exercício 4.

Vale gastar dois minutos com uma pergunta específica: existe alguma ordem que faça $B$ descer abaixo dos 64 bits brutos? Aumente a ordem e observe as duas colunas se moverem em direções opostas. O painel de baixo é o mapa navegável dos 52 artigos.

8.2 Decisões de produção que afetam a leitora

Três, e valem a pena declarar de saída.

Todo código é C++23, puro, sem dependências. Nada de LibTorch, nada de Eigen, nada de BLAS. A razão é didática: uma biblioteca de tensores esconde exatamente a aritmética que queremos mostrar, e um exemplo que exige toolchain CUDA é um exemplo que a maioria não roda. A compilação de referência é

g++ -std=c++23 -O3 -march=native -Wall -Wextra arquivo.cpp -o arquivo

e todo programa publicado roda em menos de trinta segundos em um núcleo de CPU, com semente fixa e saída determinística. Onde o paper original treinou por semanas em um cluster, o código publicado implementa a peça que define o paper , o bloco residual e sua contagem de FLOPs, a perda CTC, o pipeline de endereçamento da máquina de Turing neural, e o artigo diz isso na cara, sem fingir que treinou a ImageNet num laptop.

Todo artigo tem exercícios com gabarito. Entre seis e dez, todos resolvíveis com papel, lápis e no máximo uma calculadora, em menos de vinte minutos cada. Isso proíbe exercícios do tipo “treine uma rede” e obriga a projetar exemplos minúsculos. Toda solução é conferida programaticamente antes de publicar.

Todo número foi conferido. Sem exceção. Os valores deste artigo. Os $63{,}0541$ bits, o fator $63{,}05$, os $75{,}0541$, os $15{,}6170$, saem de um programa que roda e imprime a tabela. Adjetivo sem número é opinião, e opinião não ensina.

9. Exercícios

1. Calcule $L_0(s)$ para $s = 11110000$ sob o modelo memoryless empírico.

2. Monte a tabela de transições de $s = 11110000$ e calcule $L_1(s)$, incluindo o bit do primeiro símbolo.

3. Converta uma entropia cruzada de $1{,}8$ bit por token em razão de compressão contra um vocabulário uniforme de $32\,000$ símbolos.

4. Construa uma terceira sequência de 64 bits com 32 uns cujo custo de dados sob o modelo de ordem um fique estritamente entre o de $A$ e o de $B$, e justifique a construção antes de calcular.

5. Recalcule a tabela da Seção 4 codificando cada contagem em quatro bits em vez de seis. A conclusão sobre $B$ muda?

6. Um modelo de ordem dois sobre alfabeto binário tem quatro contextos. Estime $L(H)$ com a mesma convenção de seis bits por contexto, e verifique se ele se paga em $B$.

7. Prove que, para qualquer sequência binária de comprimento $n$ com $k$ uns, o custo sob o modelo memoryless empírico é exatamente $n \cdot H_2(k/n)$, na qual $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$ é a entropia binária.

8. Mostre que o custo de ordem um de uma sequência periódica de período dois é exatamente 1 bit, independentemente de $n$, e identifique em que passo da conta a periodicidade entra.

9. Apresentei $B$ como uma sequência sem estrutura. Exiba um modelo — de qualquer natureza — sob o qual $B$ comprima abaixo de 64 bits, e explique por que exibi-lo não contradiz nada afirmado neste artigo.

10. O argumento da Seção 6 usa 16 bits por peso. Discuta o que acontece com a conclusão sob quantização de 4 bits, e por que a resposta não é simplesmente “comprime quatro vezes mais”.

10. Soluções

1. A sequência tem quatro uns e quatro zeros, logo $\hat p(0) = \hat p(1) = 1/2$ e cada símbolo custa 1 bit:

O modelo memoryless não economiza nada, como no caso de $A$ e $B$.

2. As sete transições são $1\to1$ (três vezes), $1\to0$ (uma vez) e $0\to0$ (três vezes). O contexto $1$ ocorre quatro vezes e o contexto $0$ ocorre três. Daí $\hat Q(1\mid1) = 3/4$, $\hat Q(0\mid1) = 1/4$ e $\hat Q(0\mid0) = 3/3 = 1$. O custo:

Quase metade do custo de ordem zero, com uma sequência de apenas oito símbolos.

3. $\log_2 32\,000 = 14{,}9658$ bits por token sob o uniforme, logo a razão é

4. A construção natural é reduzir o número de transições sem eliminá-las. Uma sequência com blocos longos tem poucas transições e cada uma delas é surpreendente, o que dá custo intermediário. Tome

com 32 uns como exigido. As transições são $0\to0$ trinta vezes, $0\to1$ duas vezes, $1\to1$ trinta vezes e $1\to0$ uma vez. O custo de dados resulta

confortavelmente entre $1{,}0000$ e $63{,}0541$. A intuição estava certa: estrutura parcial dá custo parcial.

5. Com quatro bits por contagem, $L(H) = 8$. Então $A$ custa $1{,}0000 + 8 = 9{,}0000$ bits e $B$ custa $63{,}0541 + 8 = 71{,}0541$ bits. A conclusão sobre $B$ não muda: 71 ainda é mais que 64, e o modelo continua sendo mau negócio. Reduzir o preço do modelo pela metade não salva um modelo que não descreve nada.

6. Quatro contextos a seis bits dão $L(H) = 24$ bits. O custo de dados de $B$ sob ordem dois é $60{,}2531$ bits, e o total, $84{,}2531$ — pior que os $75{,}0541$ da ordem um e muito pior que os 64 brutos. A tabela completa é instrutiva:

O custo dos dados desce — na ordem cinco, chega a 26 bits — mas o custo do modelo dobra a cada ordem, e o total só piora. É a segunda lição do artigo em forma de sequência: comprar modelo para dados que não o sustentam é caro, e fica mais caro quanto mais se compra.

7. Sob o modelo memoryless empírico, cada um dos $k$ uns custa $-\log_2(k/n)$ e cada um dos $n-k$ zeros custa $-\log_2\bigl((n-k)/n\bigr)$. Somando e escrevendo $p = k/n$:

Para $s = 11110000$, temos $p = 1/2$ e $H_2(1/2) = 1$, logo $L_0 = 8$, conferindo com o Exercício 1.

8. Em uma sequência de período dois, todo símbolo determina o seguinte. As contagens condicionais são portanto degeneradas: $\hat Q(1 \mid 0) = 1$ e $\hat Q(0 \mid 1) = 1$, ou o par simétrico. Cada transição custa $-\log_2 1 = 0$, e sobra apenas o bit do primeiro símbolo. O total é $1$ bit para qualquer $n$ par — verificado para $n = 8$, $16$, $64$ e $256$.

A periodicidade entra exatamente na estimativa das condicionais: é ela que faz o numerador e o denominador da fração coincidirem. E note o que a conta diz: descrever uma sequência periódica de um milhão de símbolos custa o mesmo um bit. O comprimento da sequência é irrelevante quando a regra é curta, o que é uma primeira e crua aproximação da ideia central da complexidade de Kolmogorov.

9. Considere o código que enumera todas as sequências de 64 bits com exatamente 32 uns e transmite o índice de $B$ nessa lista. Existem

tais sequências, e nomear uma delas custa

Logo $B$ comprime. Duas observações fazem deste exercício algo mais que um truque.

A primeira é que o código precisa que a destinatária saiba o número de uns; transmiti-lo custa mais seis bits, e o total sobe para $66{,}6686$, acima dos 64 brutos. O ganho combinatório evapora quando pagamos por ele, o que é a lição da Seção 4 aparecendo mais uma vez.

A segunda é que esse mesmo código dá exatamente o mesmo custo para $A$, já que $A$ também tem 32 uns. Um código que só usa a contagem não distingue as duas sequências — é o modelo de ordem zero em outra roupa.

Não há contradição com o artigo. Afirmei que $B$ não tem estrutura de baixa ordem, o que os números da solução 6 confirmam. Nunca afirmei que $B$ seja incompressível sob todo modelo concebível — e, de fato, provar que uma sequência específica é incompressível sob todo modelo concebível é impossível, no sentido técnico e demonstrável do termo. Esse resultado tem nome e dono, e a série chega nele em três artigos.

10. A tentação é dizer que quantizar de 16 para 4 bits divide $L(H)$ por quatro, levando os 3,00 GB de modelo para 0,75 GB e o total de 5,50 para 3,25 GB. A aritmética está certa e o raciocínio está incompleto, porque os dois termos não são independentes: quantizar degrada a qualidade da previsão, e previsão pior significa mais bits por token, isto é, $L(D \mid H)$ maior.

Suponha que a quantização de 4 bits eleve a entropia cruzada de $2{,}0$ para $2{,}4$ bits por token, o que é uma degradação plausível para quantização agressiva sem calibração. Então:

O total cai, mas de $5{,}50$ para $3{,}75$ — uma redução de 32%, não de 75%. E existe um ponto, mais adiante na curva, em que a degradação come toda a economia e o total volta a subir.

A leitora que quiser o argumento completo precisa de duas coisas que a série entrega depois: a curva empírica de degradação por precisão, e a observação de que essa curva é ela própria uma lei de escala. Por ora, basta a lição estrutural: em um código de duas partes, as duas partes conversam, e otimizar uma ignorando a outra é a forma mais comum de errar a conta.

11. Onde vamos

Fecho com a frase que este artigo se propôs a tornar defensável.

Duas sequências de sessenta e quatro bits, indistinguíveis para quem conta símbolos, separadas por um fator de sessenta e três para quem conta pares. Um modelo que cobra doze bits e devolve menos de um. Um modelo de três gigabytes que descreve quarenta. A mesma subtração, das duas vezes.

Um modelo não guarda os dados; guarda a razão pela qual os dados são mais curtos do que parecem.

O próximo artigo pega a definição de trabalho que usamos aqui — o custo $-\log_2 Q$ — e prova que ela não é conveniência de notação: existe código real que a atinge, a desigualdade de Kraft diz exatamente quais comprimentos são realizáveis, e a entropia é um piso que nenhum código atravessa. Também mostra por que o melhor código clássico ainda desperdiça até um bit por símbolo, o que em aprendizado de máquina é um desperdício ruinoso — e o que se faz a respeito.

Progresso na lista: este artigo não fecha nenhum item — é pré-requisito. Continuam 0 de 30 itens estudados, 30 pela frente.

12. Acrônimos e Abreviações neste artigo

A seguir está a lista de todos os acrônimos e abreviações identificados neste artigo, organizados em ordem alfabética com o termo original em inglês e a tradução para o português:

13. Referências

AARONSON, S. The First Law of Complexodynamics. Shtetl-Optimized, 2011. Disponível em: https://scottaaronson.blog/?p=762.

AARONSON, S.; CARROLL, S. M.; OUELLETTE, L. Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton. arXiv:1405.6903, 2014.

AMODEI, D. et al. Deep Speech 2: End-to-End Speech Recognition in English and Mandarin. arXiv:1512.02595, 2015.

BAHDANAU, D.; CHO, K.; BENGIO, Y. Neural Machine Translation by Jointly Learning to Align and Translate. arXiv:1409.0473, 2014.

CHEN, X. et al. Variational Lossy Autoencoder. In: INTERNATIONAL CONFERENCE ON LEARNING REPRESENTATIONS, 5., 2017.

COVER, T. M.; THOMAS, J. A. Elements of Information Theory. 2. ed. Hoboken: Wiley, 2006.

GILMER, J. et al. Neural Message Passing for Quantum Chemistry. arXiv:1704.01212, 2017.

GLOECKLE, F. et al. Better & Faster Large Language Models via Multi-token Prediction. arXiv:2404.19737, 2024.

GRAVES, A.; WAYNE, G.; DANIHELKA, I. Neural Turing Machines. arXiv:1410.5401, 2014.

GRÜNWALD, P. D. The Minimum Description Length Principle. Cambridge: MIT Press, 2007.

HE, K. et al. Deep Residual Learning for Image Recognition. arXiv:1512.03385, 2015.

HE, K. et al. Identity Mappings in Deep Residual Networks. arXiv:1603.05027, 2016.

HINTON, G. E.; VAN CAMP, D. Keeping the Neural Networks Simple by Minimizing the Description Length of the Weights. In: CONFERENCE ON COMPUTATIONAL LEARNING THEORY, 6., 1993, p. 5–13.

HUANG, Y. et al. GPipe: Efficient Training of Giant Neural Networks Using Pipeline Parallelism. arXiv:1811.06965, 2018.

KAPLAN, J. et al. Scaling Laws for Neural Language Models. arXiv:2001.08361, 2020.

KARPATHY, A. The Unreasonable Effectiveness of Recurrent Neural Networks. 2015. Disponível em: http://karpathy.github.io/2015/05/21/rnn-effectiveness/.

KARPUKHIN, V. et al. Dense Passage Retrieval for Open-Domain Question Answering. arXiv:2004.04906, 2020.

KRIZHEVSKY, A.; SUTSKEVER, I.; HINTON, G. E. ImageNet Classification with Deep Convolutional Neural Networks. In: ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS, 25., 2012.

LEGG, S. Machine Super Intelligence. Tese (Doutorado) — Università della Svizzera Italiana, Lugano, 2008.

LEWIS, P. et al. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. arXiv:2005.11401, 2020.

LI, M.; VITÁNYI, P. An Introduction to Kolmogorov Complexity and Its Applications. 4. ed. Cham: Springer, 2019.

MacKAY, D. J. C. Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press, 2003.

OLAH, C. Understanding LSTM Networks. 2015. Disponível em: http://colah.github.io/posts/2015-08-Understanding-LSTMs/.

RISSANEN, J. Modeling by Shortest Data Description. Automatica, v. 14, n. 5, p. 465–471, 1978.

RUSH, A. M. et al. The Annotated Transformer. Harvard NLP, 2018. Disponível em: https://nlp.seas.harvard.edu/2018/04/03/attention.html.

SANTORO, A. et al. A Simple Neural Network Module for Relational Reasoning. arXiv:1706.01427, 2017.

SANTORO, A. et al. Relational Recurrent Neural Networks. arXiv:1806.01822, 2018.

SHANNON, C. E. A Mathematical Theory of Communication. Bell System Technical Journal, v. 27, n. 3, p. 379–423, 1948.

VASWANI, A. et al. Attention Is All You Need. arXiv:1706.03762, 2017.

VINYALS, O.; BENGIO, S.; KUDLUR, M. Order Matters: Sequence to Sequence for Sets. arXiv:1511.06391, 2015.

VINYALS, O.; FORTUNATO, M.; JAITLY, N. Pointer Networks. arXiv:1506.03134, 2015.

YU, F.; KOLTUN, V. Multi-Scale Context Aggregation by Dilated Convolutions. arXiv:1511.07122, 2015.

ZAREMBA, W.; SUTSKEVER, I.; VINYALS, O. Recurrent Neural Network Regularization. arXiv:1409.2329, 2014.