Parte IV · Cap. 35 — Cadeia de Markov & Modelos de Linguagem n-grama

Probabilístico · Sequências · O ancestral sem memória do LLM. Uma cadeia de Markov prevê o próximo símbolo apenas a partir do estado atual; um modelo de linguagem n-grama é essa ideia direcionada ao texto — o precursor direto de todo preditor de próximo token em cap. 01, LLM. Card: ../02-types-of-ai/03-probabilistic.kmd.

🎨 Figura F-IV.35.0 — A cadeia que escreve. Brief: uma fileira de estados-palavra ligados da esquerda para a direita, cada seta rotulada com uma probabilidade de transição; um ponteiro amostrador caminha pela cadeia emitindo uma frase, com um leque de atenção Transformer esmaecido atrás para mostrar a linhagem.

1. Definição e breve história

Uma cadeia de Markov é um processo estocástico cujo próximo estado depende apenas do estado presente, não do histórico completo — a propriedade de ausência de memória. Um modelo de linguagem n-grama a aplica à linguagem: a probabilidade do próximo token é condicionada aos \(n-1\) tokens anteriores (uma cadeia de Markov de ordem \((n-1)\) sobre o vocabulário).

A linhagem começa com duas pessoas contando letras. Andrey Markov (1913) analisou a sequência de vogais/consoantes de Eugene Onegin, de Pushkin, para provar que eventos dependentes obedecem à lei dos grandes números — a primeira cadeia de Markov ajustada a dados reais (história completa no Compêndio de CC, cap. 01). Claude Shannon (1948, A Mathematical Theory of Communication) a transformou em um gerador: amostrando das estatísticas de letras — e depois de palavras — do inglês, ele produziu texto cuja "semelhança com o inglês comum aumenta bastante notavelmente a cada passo" — o primeiro *modelo de geração de linguagem*. Modelos n-grama então movimentaram o PLN estatístico, o reconhecimento de fala e a tradução automática dos anos 1980 até por volta dos anos 2010.

2. Fundamentos

• Processos estocásticos — cadeias de Markov; a suposição de Markov (sem memória).
• Teoria da informação — entropia de Shannon de uma linguagem; perplexidade como \(2^{\text{cross-entropy}}\) (a surpresa por token de um modelo).
• Probabilidade & estatística — estimação de máxima verossimilhança a partir de contagens de corpus; smoothing como uma priori sobre eventos não vistos.

3. Algoritmos e arquiteturas

• O modelo — \(P(w_1\dots w_T) \approx \prod_t P(w_t \mid w_{t-n+1}\dots w_{t-1})\).
• Estimação — MLE por contagens: \(P(w_t\mid \text{ctx}) = \dfrac{\text{count}(\text{ctx}, w_t)}{\text{count}(\text{ctx})}\).
• Smoothing (n-gramas não vistos não podem receber probabilidade 0, ou a perplexidade fica infinita):

  add-one