🔢 mathematics

The LZ78 Source

Este artigo caracteriza as propriedades entropicas e distribucionais de uma família de processos gerados pelo compressor universal LZ78, demonstrando que, embora sejam "quase estacionários" e satisfaçam uma propriedade do tipo Shannon-McMillan-Breiman, sua compressibilidade por estados finitos excede estritamente a taxa de entropia devido a um "gap de Jensen", permitindo assim avaliar modelos sequenciais e o aprendizado em contexto em transformers.

Autores originais: Naomi Sagan, Amir Dembo, Matthew Ho, Tsachy Weissman

Publicado 2026-04-20

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Naomi Sagan, Amir Dembo, Matthew Ho, Tsachy Weissman

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um livro de receitas infinito que você está escrevendo enquanto come. Cada vez que você escreve um ingrediente, você olha para o que já escreveu para decidir o próximo. Se você já escreveu "farinha, açúcar, ovos" antes, você sabe que o próximo provavelmente será "manteiga".

Agora, imagine um algoritmo muito inteligente chamado LZ78. Ele é como um chef que não apenas segue receitas, mas cria um mapa mental gigante (uma árvore) de todas as combinações de ingredientes que já viu. Se ele vê "farinha, açúcar" pela primeira vez, ele cria um novo ramo no mapa. Se vê de novo, ele usa o que já sabe.

Este artigo de pesquisa pergunta uma pergunta curiosa: E se usássemos esse mapa mental do LZ78 não para comprimir dados, mas para gerar novos dados aleatórios? Ou seja, e se o próprio algoritmo de compressão fosse o "pai" que decide qual letra vem a seguir em uma história?

Os autores criaram uma "fonte de dados" baseada nisso e descobriram coisas fascinantes sobre como essa história se comporta. Aqui está a explicação simplificada:

1. A Fonte LZ78: O "Gênio Desorganizado"

Pense na Fonte LZ78 como um narrador de histórias que é um gênio, mas um pouco louco.

Ele não segue um padrão fixo (não é "estacionário"). Ele muda de humor.
Ele olha para o passado recente para decidir o futuro, mas o quanto ele olha para trás cresce conforme a história fica mais longa. No começo, ele só olha 1 palavra atrás. Depois, 10. Depois, 100.
Isso cria uma história que parece aleatória, mas tem uma estrutura profunda e complexa escondida.

2. A Grande Descoberta: A "Lacuna de Jensen" (O Abismo da Previsão)

Aqui está a parte mais legal, usando uma analogia de previsão do tempo:

A Entropia (A Verdade Real): Imagine que você sabe exatamente como o clima funciona no universo. Você tem uma fórmula perfeita. A "entropia" é o nível mínimo de incerteza possível. É o quanto o clima é realmente imprevisível, mesmo com toda a informação.
A Previsão de Estado Finito (O Meteorologista Comum): Agora, imagine um meteorologista que só pode lembrar dos últimos 3 dias. Ele faz o melhor trabalho possível com essa memória limitada.
O Abismo (A Lacuna): Com a Fonte LZ78, os autores descobriram que existe um abismo inevitável entre o que o meteorologista limitado consegue prever e a verdade real.
- Em fontes normais (como um dado viciado), se você tem memória suficiente, você chega perto da verdade.
- Na Fonte LZ78, não importa quanta memória você tenha (seja 10 dias, 100 dias ou 1000 dias), você nunca conseguirá prever tão bem quanto a "verdade teórica". Sempre haverá um "erro extra" que não pode ser eliminado. É como se o narrador estivesse sempre um passo à frente do seu cérebro, criando um padrão que exige um mapa mental infinito para ser entendido perfeitamente.

3. O Comportamento "Quase Aleatório"

Apesar de ser complexa, a Fonte LZ78 tem um truque: se você olhar para pequenas partes da história, ela parece perfeitamente aleatória (como jogar moedas).

Imagine que você pega um pedaço de 10 palavras da história. Parece aleatório.
Pega outro pedaço de 10 palavras. Parece aleatório.
Mas, se você olhar a história inteira, percebe que não é aleatória; é uma estrutura complexa.
Isso é chamado de "quase i.i.d." (quase independente e identicamente distribuído). É como se o narrador fosse um ator que faz uma improvisação perfeita a cada cena, mas o roteiro geral é muito complexo.

4. A Aplicação: Testando a Inteligência Artificial (Transformers)

Por que isso importa para o mundo real? Os autores usaram essa fonte para testar os Modelos de Linguagem (como o GPT, que usa uma arquitetura chamada Transformer).

O Desafio: Os modelos de IA modernos são famosos por "Aprendizado em Contexto" (In-Context Learning). Isso significa que, se você der a eles um exemplo de como resolver um problema no meio do texto, eles aprendem a fazer isso na hora, sem precisar ser re-treinados.
O Teste: Os autores treinaram esses modelos de IA com histórias geradas pela Fonte LZ78.
O Resultado:
- Modelos pequenos (poucas camadas) falharam miseravelmente. Eles não conseguiam entender o padrão que crescia.
- Modelos maiores (mais camadas) conseguiram aprender um pouco melhor, conseguindo prever um pouco melhor do que os modelos clássicos.
- Mas: Mesmo os melhores modelos de IA ainda não conseguiam fechar a "Lacuna de Jensen". Eles não conseguiam prever tão bem quanto a teoria diz que é possível.

Resumo em uma frase

Este artigo criou um "monstro matemático" (a Fonte LZ78) que é impossível de prever perfeitamente com qualquer memória finita, e usou esse monstro para mostrar que, embora as Inteligências Artificiais modernas sejam incríveis, elas ainda têm um limite fundamental quando tentam aprender padrões que crescem infinitamente complexos.

É como tentar ensinar um cachorro a entender uma linguagem que muda de gramática a cada palavra que ele aprende: ele pode aprender algumas frases, mas nunca dominará o idioma perfeitamente.

Título: A Fonte LZ78: Definição, Propriedades Entrópicas e Aplicação à Aprendizagem em Contexto (In-Context Learning)

Autores: Naomi Sagan, Amir Dembo, Matthew Ho e Tsachy Weissman (Stanford University).

1. Problema e Motivação

O algoritmo de compressão universal LZ78 é amplamente estudado e utilizado em esquemas universais, previsão de sequências e modelagem de probabilidade. No entanto, a literatura carece de uma investigação profunda sobre o LZ78 como uma fonte de probabilidade (um processo estocástico gerador de dados), em vez de apenas como um compressor de dados determinísticos.

A maioria dos estudos anteriores foca em fontes estacionárias e ergódicas (como processos de Markov) ou em compressão com perdas. Este trabalho visa preencher essa lacuna ao:

Definir formalmente uma família de processos estocásticos gerados pelas Atribuições de Probabilidade Sequencial (SPAs) induzidas pelo LZ78.
Caracterizar suas propriedades entrópicas e distribucionais fundamentais.
Investigar como modelos modernos, especificamente Transformers, lidam com essa fonte não-Markoviana e não-estacionária no contexto de Aprendizagem em Contexto (In-Context Learning - ICL).

O problema central é entender os limites fundamentais de compressão e modelagem de probabilidade para dados que possuem dependências complexas e de longo alcance, onde a "memória" necessária para prever o próximo símbolo cresce com o comprimento da sequência.

2. Metodologia e Definição da Fonte

Os autores definem a Fonte LZ78 ( $Q_{LZ, \Pi}$ ) como um processo estocástico sobre um alfabeto finito $A$ , construído através de uma árvore de prefixo LZ78 dinâmica:

Construção:
1. Fixa-se uma distribuição de prior $\Pi$ sobre o simplex de distribuições de probabilidade $M(A)$ .
2. Gera-se uma sequência i.i.d. de parâmetros $\Theta_0, \Theta_1, \dots$ a partir de $\Pi$ .
3. O processo $X = (X_1, X_2, \dots)$ $X = (X_{1}, X_{2}, \dots)$ é gerado iterativamente:
  - Em cada passo $t$ , o nó atual na árvore LZ78 possui um parâmetro $\Theta$ associado (inicialmente o nó raiz tem $\Theta_0$ ).
  - O símbolo $X_t$ é gerado de acordo com a distribuição definida por esse $\Theta$ (ex: $X_t \sim \text{Bernoulli}(\Theta)$ ).
  - A árvore LZ78 é atualizada (travessia ou expansão de nova folha) baseada em $X_t$ . Se uma nova folha for criada, um novo $\Theta$ é atribuído a ela e a travessia retorna à raiz.
Características Chave:
- Não-Estacionariedade: A distribuição dos parâmetros condicionais muda ao longo do tempo, pois a estrutura da árvore e os nós visitados evoluem.
- Não-Markoviana: O contexto necessário para prever o próximo símbolo cresce indefinidamente com o comprimento da sequência, diferentemente de processos de Markov de ordem fixa.
- "Quase i.i.d." Localmente: Apesar da dependência complexa, as distribuições empíricas de dimensão finita convergem para uma lei i.i.d. determinística.

3. Principais Contribuições Teóricas

O artigo estabelece resultados rigorosos sobre as propriedades entrópicas da fonte:

A. Taxa de Entropia e Convergência (Teorema do Tipo Shannon-McMillan-Breiman)

A taxa de entropia da fonte LZ78 é dada por $H_{rate} = \mathbb{E}_{\Theta \sim \Pi}[H(\Theta)]$ , onde $H(\Theta)$ é a entropia de Shannon do parâmetro $\Theta$ .
Resultado: A probabilidade log-normalizada de uma realização da fonte converge quase certamente para essa taxa de entropia:
$\lim_{n \to \infty} \frac{1}{n} \log \frac{1}{Q_{LZ, \Pi}(X^n)} = \mathbb{E}[H(\Theta)] \quad \text{a.s.}$

B. Compressibilidade de Estado Finito e o "Gap de Jensen"

Este é um dos resultados mais significativos. Para fontes estacionárias ergódicas, a compressibilidade de estado finito coincide com a taxa de entropia.
Para a Fonte LZ78, a compressibilidade de estado finito (ou o log-loss ótimo de qualquer modelo de Markov de ordem finita) converge quase certamente para um valor estritamente maior que a taxa de entropia.
O Gap: A diferença é dada por:
$\mu(X) - H_{rate} = H(\mathbb{E}[\Theta]) - \mathbb{E}[H(\Theta)] = I(\Theta; Y)$
Esta diferença é o Gap de Jensen (devido à concavidade da entropia) e representa a informação mútua entre o parâmetro latente $\Theta$ e o símbolo gerado $Y$ . Isso implica que modelos com memória finita (como modelos de Markov de ordem $k$ ) nunca conseguirão atingir a taxa de entropia ótima, mesmo assintoticamente.

C. Divergência com Leis Markovianas

Os autores derivam a divergência de Kullback-Leibler (relativa) entre a Fonte LZ78 e qualquer lei de Markov de ordem $k$ .
Mostram que, assintoticamente, a melhor aproximação Markoviana é a lei constante $\mathbb{E}[\Theta]$ , e modelos de ordem superior não melhoram a aproximação assintótica, embora ajudem em regimes de amostras finitas.

D. Propriedades da Distribuição Empírica

Demonstram que, apesar da estrutura de dependência não trivial, as distribuições empíricas de $r$ -tuplas da sequência gerada convergem quase certamente para uma lei i.i.d. com distribuição $\mathbb{E}[\Theta]$ . Isso torna a fonte "localmente quase i.i.d.".

4. Resultados Experimentais e Aplicação a Transformers

Os autores utilizam a Fonte LZ78 como um benchmark desafiador para estudar a Aprendizagem em Contexto (ICL) em modelos Transformer.

Configuração: Treinaram Transformers de diferentes profundidades (1 a 5 camadas) em sequências geradas pela Fonte LZ78 com diferentes priores (Dirichlet, misturas Dirac-Dirichlet).
Comparação: Avaliaram o log-loss dos Transformers contra:
- A entropia da fonte (limite teórico inferior).
- O log-loss de modelos de Markov de ordem $k$ ( $\mu_k$ ).
- O algoritmo Context Tree Weighting (CTW).
- A própria probabilidade da fonte LZ78.
Descobertas Principais:
1. Desempenho Superior a Modelos Clássicos: Transformers com profundidade adequada (3-5 camadas) superaram consistentemente o CTW e modelos de Markov de ordem fixa, demonstrando capacidade de aprender algoritmos de previsão complexos em contexto.
2. Limites Fundamentais: Mesmo os melhores Transformers não conseguem atingir a taxa de entropia teórica da fonte (devido ao Gap de Jensen inerente à natureza não-Markoviana e à memória finita do modelo), mas conseguem se aproximar significativamente do log-loss de modelos de Markov de ordem muito alta.
3. Generalização: Modelos treinados na Fonte LZ78 demonstraram capacidade de generalizar para dados genômicos reais (sequências de DNA), exibindo padrões de perda decrescente semelhantes aos do CTW, sugerindo que os heurísticos aprendidos via ICL são transferíveis para dados do mundo real.
4. Efeito da Profundidade: A profundidade do Transformer é crucial para capturar dependências de longo alcance. Modelos mais profundos conseguem manter um log-loss baixo por sequências mais longas antes de convergir para o limite de estado finito.

5. Significado e Impacto

Novo Benchmark Teórico: A Fonte LZ78 oferece um novo tipo de processo estocástico para testar modelos de aprendizado de máquina. Diferente de processos de Markov (onde a ordem é fixa), a Fonte LZ78 exige que o modelo adapte dinamicamente seu contexto, tornando-a um teste mais rigoroso para ICL.
Compreensão de Limites: O trabalho esclarece matematicamente por que modelos com memória finita (incluindo redes neurais com janela de contexto limitada) não podem comprimir certas fontes não-Markovianas até a entropia de Shannon, introduzindo o conceito do "Gap de Jensen" como uma barreira fundamental.
Validação de ICL: Os resultados empíricos fornecem fortes evidências de que Transformers não apenas memorizam estatísticas de treinamento, mas aprendem algoritmos de previsão sequencial (semelhantes a CTW ou LZ78) que generalizam para dados fora da distribuição (out-of-distribution).
Conexão entre Teoria da Informação e Deep Learning: O artigo conecta profundamente a teoria clássica de compressão (LZ78, Shannon-McMillan-Breiman) com a capacidade moderna de modelos de atenção, oferecendo uma base teórica para entender o comportamento de ICL.

Em resumo, o artigo define uma nova classe de fontes de dados complexas, prova propriedades entrópicas surpreendentes (como a divergência entre entropia e compressibilidade de estado finito) e utiliza essas fontes para demonstrar, tanto teoricamente quanto empiricamente, a capacidade e os limites dos Transformers na aprendizagem de algoritmos sequenciais.