<h1 id="R%C3%A9gression-logistique-pour-la-g%C3%A9n%C3%A9ration-de-pr%C3%A9noms:-corrig%C3%A9">Régression logistique pour la génération de prénoms: corrigé¶</h1><p>Cours des grands algos d'hier et ajd, séance 1.</p>
  • pur python
  • regression logistique par descente de gradient, calcul explicite du gradient.
In [1]:
import math
import random
random.seed(42)
<h2 id="Le-jeu-de-donn%C3%A9es">Le jeu de données¶</h2><p>Une liste de prénoms (un par ligne).</p>
In [2]:
import os
if not os.path.exists('input.txt'):
    import urllib.request
    names_url = 'https://raw.githubusercontent.com/karpathy/makemore/988aa59/names.txt'
    urllib.request.urlretrieve(names_url, 'input.txt')
names = [line.strip() for line in open('input.txt') if line.strip()]
random.shuffle(names)
print(f'num names: {len(names)}')
print(names[:8])

num names: 32033
['yuheng', 'diondre', 'xavien', 'jori', 'juanluis', 'erandi', 'phia', 'samatha']
<h2 id="Le-tokeniseur">Le tokeniseur¶</h2><p>Les tokens sont les caractères de l'alphabet, plus un token spécial stop_token (début/fin de mot). Il y a donc T = 27 tokens.</p>
In [3]:
characters = sorted(set(''.join(names)))
stop_token = len(characters)
T = len(characters) + 1
print(f'vocab size: T = {T}')

def encode(name):
    return [stop_token] + [characters.index(char) for char in name] + [stop_token]

print('anna ->', encode('anna'))

vocab size: T = 27
anna -> [26, 0, 13, 13, 0, 26]
<h2 id="3.-Alg%C3%A8bre-lin%C3%A9aire-en-Python-pur">3. Algèbre linéaire en Python pur¶</h2><p>Un vecteur = une liste de flottants ; une matrice = une liste de vecteurs lignes.</p>
In [4]:
# vecteurs
rand_vec = lambda d, std=1: [random.gauss(0, std) for _ in range(d)]
one_hot = lambda t, T: [1.0 if i == t else 0.0 for i in range(T)]
ext_vec = lambda alpha, u: [alpha * ui for ui in u]
dot_prod = lambda u, v: sum(ui * vi for ui, vi in zip(u, v))
vec_add = lambda u, v: [ui + vi for ui, vi in zip(u, v)]
norm = lambda u: math.sqrt(dot_prod(u, u))
In [5]:
# tests
u, v = [1., 1.], [-1.,-1.]
print(f"{rand_vec(3, 1)=}")
print(f"{one_hot(1,3)=}")
print(f"{ext_vec(0.5, v)=}")
print(f"{dot_prod(u,v)=}, {dot_prod(u,u)=}")
print(f"{vec_add(u,v)=}")
print(f"{norm(u)=}")

rand_vec(3, 1)=[-0.5341476169657658, 0.9620173494831367, 1.3555262632633958]
one_hot(1,3)=[0.0, 1.0, 0.0]
ext_vec(0.5, v)=[-0.5, -0.5]
dot_prod(u,v)=-2.0, dot_prod(u,u)=2.0
vec_add(u,v)=[0.0, 0.0]
norm(u)=1.4142135623730951
In [6]:
# matrices
rand_mat = lambda n, m, std=1: [rand_vec(m, std) for _ in range(n)]
transpose = lambda M: list(zip(*M))
mat_vec  = lambda M, v: [dot_prod(mi_, v) for mi_ in M]
mat_mat  = lambda A, B: [[dot_prod(ai_, b_j) for b_j in transpose(B)] for ai_ in A]
# mat_mat  = lambda A, B: [[dot_prod(ai_, b_j) for ai_ in A] for b_j in transpose(B)]

scal_mat = lambda a, M: [[a * mij for mij in mi_] for mi_ in M]
mat_add  = lambda A, B: [vec_add(ai_, bi_) for ai_, bi_ in zip(A, B)]
col_mat = lambda v: [[vi] for vi in v]
row_mat = lambda v: [v]
In [7]:
# tests
I = [[1., 0.], [0.,1.]]
M1 = [[0., 1.], [0.,0.]]
ones = [1., 1.]
print(f"{transpose(M1)=}")
print(f"{mat_vec(I, v)=}")
print(f"{mat_mat(I,M1)=}")
print(f"{mat_mat(M1,M1)=}")
print(f"{mat_mat(col_mat(ones), row_mat(ones))=}")

transpose(M1)=[(0.0, 0.0), (1.0, 0.0)]
mat_vec(I, v)=[-1.0, -1.0]
mat_mat(I,M1)=[[0.0, 1.0], [0.0, 0.0]]
mat_mat(M1,M1)=[[0.0, 0.0], [0.0, 0.0]]
mat_mat(col_mat(ones), row_mat(ones))=[[1.0, 1.0], [1.0, 1.0]]
<h2 id="4.-La-repr%C3%A9sentation-du-contexte-(feature)">4. La représentation du contexte (feature)¶</h2><p>On résume le contexte $(t_0,\dots,t_{l-1})$ par la moyenne des one-hot des tokens vus : $$ v = \frac{1}{l}\sum_{k=0}^{l-1} \mathbf{1}_{t_k} \in \mathbb{R}^T. $$ La coordonnée $m$ de $v$ est la fréquence du token $m$ dans le contexte.</p>
In [8]:
def features(context):
    v = one_hot(context[0], T)
    for t in context[1:]:
        v = vec_add(v, one_hot(t, T))
    return ext_vec(1 / len(context), v)
<h2 id="5.-Le-mod%C3%A8le-:-softmax(M-v)">5. Le modèle : softmax(M v)¶</h2>
In [9]:
# fonction softmax
def softmax(z):
    m = max(z) # numerical stability
    exp_z = [math.exp(zi - m) for zi in z]
    return ext_vec(1 / sum(exp_z), exp_z)
softmax([0., 0., 0., 0.])
Out[9]:
[0.25, 0.25, 0.25, 0.25]
In [10]:
def generate_name(M, max_chars=100):
    context = [stop_token]
    sample = []
    for _ in range(max_chars):
        v = features(context)
        z = mat_vec(M, v)
        p = softmax([zi for zi in z])
        token = random.choices(range(T), weights=p)[0]
        if token == stop_token:
            break
        sample.append(characters[token])
        context.append(token)
    return ''.join(sample)
In [11]:
# pas d'entrainement, on ne s'attend pas a un miracle
# random.seed(42)
M = [[0]*T]*T # matrice nulle, probas uniformes
n_names = 10
gen_names = [generate_name(M) for _ in range(n_names)]
gen_names
Out[11]:
['raxwrgvbzeuaaebzljrzyaiweucvalaigtpa',
 'kyftdddb',
 'g',
 'drbkrcrqbcugigcgeek',
 'vetgwlhdinivqlahnlhutpjlmsqxgroqemgkujekzkiwhukevxnqlihvjgwsexuzyktsjpssluxpxuefyukyecmemrzzuoghzhon',
 'lsavkohmrquuvccxsncynfmaavmkmewacolnotpdtpd',
 '',
 'kfuvlerwu',
 'rksjkyfcdzxpyakpnr',
 'crskhmqmslygiqazcjuaktphpucghhmrwrfsocbpvhtzxnfbgocahrprubiyeyepxxykoa']
<h2 id="6.-Le-gradient-explicite-(comme-dans-le-cours)">6. Le gradient explicite (comme dans le cours)¶</h2><p>Pour un token, forward puis backward à la main :</p>
  • forward : $z = Mv$, $p = \mathrm{softmax}(z)$, loss $= -\log p_{t_l}$ ;
  • backward : $\nabla_z \mathcal{L} = p - \mathbf{1}_{t_l}$, puis $\nabla_M \mathcal{L} = (p - \mathbf{1}_{t_l})\, v^{\top}$ (produit extérieur).
<p>La fonction ci-dessous traite un prénom : elle accumule la loss et le gradient sur tous ses tokens, et renvoie leur moyenne.</p>
In [12]:
def loss_and_grad(tokens, M):
    grad_prenom = [[0.0] * T] * T   # accumulateur du gradient, meme forme que M
    total_loss = 0.0
    n_tok = 0
    for i in range(len(tokens) - 1):
        t0___tlm1 = tokens[:i + 1]
        tl  = tokens[i + 1]
        v = features(t0___tlm1)
        z = mat_vec(M, v)
        p = softmax(z)
        total_loss += -math.log(p[tl])
        n_tok += 1
        p_m_onehot = p
        p_m_onehot[tl] -= 1.0
        grad_tok = mat_mat(col_mat(p_m_onehot), row_mat(v))
        grad_prenom = mat_add(grad_prenom, grad_tok)
    # moyenne sur les tokens du prenom
    return total_loss / n_tok, scal_mat(1 / n_tok, grad_prenom)

M = [[0]*T]*T
loss_and_grad(encode('tommy'), M)[0], math.log(T)
Out[12]:
(3.295836866004329, 3.295836866004329)
<h2 id="7.-Entra%C3%AEnement-:-descente-de-gradient-stochastique">7. Entraînement : descente de gradient stochastique¶</h2><p>On tire un prénoms à chaque étape (ici batch_size = 1, soit la SGD puis on met à jour $M \leftarrow M - \eta\, \nabla_M \mathcal{L}$ avec un pas $\eta$ fixe. On enregistre la loss pour tracer la courbe.</p>
In [13]:
import time

M = [[0]*T]*T
random.seed(42)
start_time = time.time()
learning_rate = 1.0
num_steps = 1000
loss_history = []

for step in range(num_steps):
    tokens = encode(names[step])
    loss, grad = loss_and_grad(tokens, M)
    avg_loss = loss if step == 0 else (avg_loss * step + loss) / (step + 1)
    M = mat_add(M, scal_mat(-learning_rate, grad))      # M <- M - lr * grad
    loss_history.append(loss)
    if step % 250 == 0 or step == num_steps - 1:
        print(f'step {step + 1:5d} / {num_steps} | loss {loss:.4f} (avg {avg_loss:.4f})', end='\r')
print(f"\ndone in {time.time() - start_time:.2f}s")

step  1000 / 1000 | loss 2.6635 (avg 2.8069)
done in 1.46s
<h2 id="8.-La-courbe-d'entra%C3%AEnement">8. La courbe d'entraînement¶</h2><p>La loss brute (par prénom) est bruitée, ce n'est qu'un terme dans la fonction de coût qui est la moyenne sur tous les prénoms. On cacule une moyenne glissante pour lisser. Elle doit partir près de $\log T \approx 3.30$ et décroître.</p>
In [14]:
def moving_average(x, k=100):
    out, s = [], 0.0
    from collections import deque
    win = deque()
    for xi in x:
        win.append(xi); s += xi
        if len(win) > k: s -= win.popleft()
        out.append(s / len(win))
    return out

import matplotlib.pyplot as plt

plt.figure(figsize=(8, 4))
plt.plot(loss_history, alpha=0.3, label='loss (par prenom)')
plt.plot(moving_average(loss_history, num_steps // 100), label='moyenne glissante (100)')
plt.axhline(math.log(T), color='gray', ls='--', label='log(T) (uniforme)')
plt.xlabel('etape (SGD)')
plt.ylabel('log-vraisemblance negative')
plt.title('Courbe d\'entrainement — regression logistique (gradient explicite)')
plt.legend()
plt.tight_layout()
plt.ylim(2, 3.5)
plt.show()
No description has been provided for this image
In [16]:
gen_names = [generate_name(M) for _ in range(20)]
gen_names,  sum([len(nm) for nm in gen_names])/ len(gen_names), sum([len(nm) for nm in names]) / len(names)
Out[16]:
(['ali',
  'caljeg',
  'itna',
  'rzywclejaj',
  'crii',
  'zkobf',
  'kjpanmyc',
  'aeosie',
  'bnokon',
  'arfjqhivan',
  'zaei',
  'sthaytq',
  'mathr',
  'acaniy',
  'anio',
  'ralgayshyonab',
  'sktmaai',
  'rtydea',
  'shna',
  'szswash'],
 6.25,
 6.122217712983486)