Modelos de Linguagem

Exercício 1: uma Cadeia de Markov

Uma Cadeia de Markov é um autômato finito probabilístico. As Cadeias de Markov recebem esse nome por que foram estudadas por um matemático russo chamado Markov no fim do Século XIX. A Cadeia de Markov serve para descrever sistemas que, a cada iteração, sempre assumem um entre um número finito de estados. Daí, na próxima iteração, o próximo estado é sorteado à partir de uma distribuição de probabilidades condicionada ao estado atual, isto é, usando as probabilidades de transição:

\[ P(e_{t+1} = i | e_t = j) \]

Discuta como o caso das bicicletas de Montreal (da aula passada) pode ser modelada usando uma Cadeia de Markov. Encontre:

a) O que cada estado da cadeia representa? Que entidade do grafo (vértice ou aresta) é usada para representrar o estado?

b) O que cada probabilidade de transição representa? Que entidade do grafo (vértice ou aresta) é usada para representar as probabilidades de transição?

Exercício 2: um Modelo de Linguagem simples!

As cadeias de Markov podem ser usadas para fazer modelos de linguagem. Um modelo de linguagem é um modelo probabilítisco que gera palavras com base nas palavras anteriores. Poderíamos fazer um modelo gerador para "Hey Jude", por exemplo, usando a seguinte estrutura:

graph LR; HEY --> JUDE; JUDE --> DONT; DONT --> LET; LET --> ME; ME --> DOWN; DONT --> BE; BE --> AFRAID;

Neste exercício, vamos fazer uma poesia generativa e, após, analisar essa poesia:

  1. Escolha 5 palavras.
  2. Defina probabilidades de transição entre essas palavras, isto é, defina todos os valores de \(P(e_{t+1} = i | e_t = j)\).
  3. Defina a matriz de transição \(A\) relacionada às probabilidades \(P(e_{t+1} = i | e_t = j)\), dando mais probabilidade a transições que fazem mais sentido para você.
  4. Faça um programa que começa de uma palavra qualquer, e, após, escolhe a próxima palavra usando as probabilidades que você definiu.
  5. Faça com que seu programa gere a palavra seguinte (\(e_{t+2}\)) usando a palavra que foi gerada inicialmente (\(e_{t+1}\)), e assim por diante.
  6. Deixe seu programa gerar muitas palavras (pelo menos 10000).
  7. Calcule a probabilidade \(P(w = n)\) de, se sortearmos uma palavra aleatória \(w\) entre as geradas, ela ser uma instância da palavra \(n\) que você definiu no seu vocabulário.
  8. Use np.linalg.eig para calcular os auto-vetores e auto-valores de \(A\). Como eles explicam o resultado encontrado no ítem anterior?

Exercício 3: Viéses da Cadeia de Markov

Vamos reproduzir o resultado do ítem anterior para um caso mais controlado. Considere a seguinte Cadeia de Markov:

graph LR; A -->|0.2| A; A -->|0.5| B; A -->|0.3| C; B -->|0.1| A; B -->|0.6| B; B -->|0.3| C; C -->|0.4| A; C -->|0.2| B; C -->|0.4| C;
  1. Faça um programa que começa do estado A e então "caminha" pela cadeia, gerando uma sequência de 10000 estados.
  2. Verifique se a proporção entre os estados percorridos corresponde a aquela que é apontada pelos auto-valores e auto-vetores da matriz de transições da cadeia.
  3. As transições da Cadeia de Markov acontecem porque algumas transições entre estados são mais prováveis que outras (por exemplo: na música dos Beatles, a palavra "Jude" sempre é seguida da palavra "Don't"). Porém, isso leva a um viés: algumas palavras serão inevitavelmente mais prováveis que outras. Usando a formulação \(A=PQP^{-1}\), crie uma matriz de transições que leve a uma Cadeia de Markov sem esse tipo de viés. O que acontece com as probabilidades de transição?
  4. Com base nos resultados que já tivemos até aqui, discuta: é possível criar uma Cadeia de Markov que não seja enviesada a usar alguns estados mais frequentemente e que, simultaneamente, possa representar uma ideia de "sentido semântico", isto é, a ideia de que algumas sequências de estados são mais prováveis do que outras?

Exercício 4

Uma Cadeia de Markov pode ser usada para modelar linguagens através da ideia de que a probabilidade de gerar uma palavra (\(w_{t}\)) seja condicionada à última palavra gerada (\(w_{t-1}\)) através da distribuição \(P(w_t | w_{t-1})\). Poderíamos fazer uma Cadeia de Markov de ordem 2, na qual a geração de cada palavra é condicionada às duas anteriores, isto é:

\[ P(w_t | w_{t-1}, w_{t-2}) \]

Nesse caso, nosso estado representa as duas últimas palavras geradas. Se tivéssemos duas palavras (A e B), teríamos o seguinte grafo representando os estados - veja que o estado é descrito pela última sequência gerada, isto é, se a sequência AB leva à geração de B, então o primeiro A é descartado e o estado seguinte passa a ser BB.

graph LR; AB -->|"Gerou B"| BB; AB --> |"Gerou A"| BA; AA -->|"Gerou B"| AB; AA --> |"Gerou A"| AA; BB -->|"Gerou B"| BB; BB --> |"Gerou A"| BA; BA -->|"Gerou B"| AB; BA --> |"Gerou A"| AA;

Poderíamos aumentar ainda mais esse processo para uma Cadeia de Markov de ordem \(n\). Na verdade, os Large Language Models (LLMs) fazem exatamente isso: são grandes Cadeias de Markov de ordem \(n\) (e os transformers e embeddings são formas bastante espertas de representar os parâmetros do modelo).

Mostre que todo LLM, inevitalmente, tende a repetir mais algumas palavras do que outras.