Problema
I modelli linguistici scelgono il token successivo da una distribuzione di probabilità. Due impostazioni le danno forma:
- 'Top-k: tieni solo i k token con i logit più alti (a parità di logit, l''indice minore viene prima).'
- 'Temperatura T: dividi i logit tenuti per T prima del softmax. Una T bassa rende la scelta più prevedibile, una T alta più casuale.'
Per rendere il campionamento verificabile, il numero casuale viene fornito:
- Tieni i token del top-k ed elencali per indice originale (crescente).
- Calcola softmax(logit / T) sui token tenuti (sottrai il maggiore prima di calcolare e^x).
- Scorri la lista sommando le probabilità; restituisci l'indice del primo token in cui il totale cumulato supera
random_value. Se non succede mai (arrotondamento), restituisci l'ultimo token tenuto.
Con k = 1 è la decodifica greedy: sempre il token più probabile.
Implementa sample_token(logits, temperature, k, random_value).
Input
logits: Un punteggio per ogni token del vocabolario.
temperature: T, maggiore di 0.
k: Quanti token migliori tenere.
random_value: Un numero casuale in [0, 1).
Output
Restituisci l'indice del token scelto.
Vincoli
1 ≤ k ≤ numero di logit ≤ 1.000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ ogni logit ≤ 100
Esempi
Input:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Output atteso:
expected = 1
Input:
std::vector<double> logits = {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long long k = 1;
double random_value = 0.99;
Output atteso:
long long expected = 1;
Input:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Output atteso:
long expected = 1;
Spiegazione
k = 1 tiene solo il logit più alto, 3.0 all'indice 1. La sua probabilità è 1, quindi viene scelto qualunque sia il numero casuale: decodifica greedy.
Input:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Output atteso:
expected = 1
Input:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Output atteso:
long long expected = 1;
Input:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Output atteso:
long expected = 1;
Spiegazione
Il top-2 tiene gli indici 0 e 1 (logit 2 e 1). Il softmax dà circa 0.731 e 0.269. Il totale cumulato è 0.731 dopo l'indice 0 (non supera 0.8) e 1 dopo l'indice 1, quindi viene scelto l'indice 1.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Scegli prima i token con logit più alti, risolvendo i pari merito con l'indice più piccolo, poi riporta quei token in ordine crescente di indice.
Suggerimento 2
Converti i logit mantenuti in probabilità dopo aver diviso per la temperatura, usando una softmax numericamente stabile.
Suggerimento 3
Quando scansioni la probabilità cumulativa, restituisci il primo indice che supera il valore casuale, ma torna all'ultimo token mantenuto se l'arrotondamento impedisce il superamento.
Complessità attesa
tempo O(m log m), spazio aggiuntivo O(m)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.