Đề bài
Mô hình ngôn ngữ chọn token tiếp theo từ một phân phối xác suất. Hai thiết lập định hình phân phối đó:
- Top-k: chỉ giữ k token có logit cao nhất (nếu logit bằng nhau, chỉ số nhỏ hơn xếp trên).
- Temperature T: chia các logit được giữ cho T trước khi tính softmax. T thấp làm lựa chọn dễ đoán hơn; T cao làm nó ngẫu nhiên hơn.
Để có thể kiểm thử, số ngẫu nhiên được cho sẵn:
- Giữ k token đứng đầu, rồi liệt kê chúng theo chỉ số ban đầu (tăng dần).
- Tính softmax(logit / T) trên các token được giữ (trừ giá trị lớn nhất trước khi tính e^x).
- Đi qua danh sách và cộng dồn xác suất; trả về chỉ số của token đầu tiên làm tổng cộng dồn lớn hơn
random_value. Nếu không có token nào (do làm tròn), trả về token được giữ cuối cùng.
Với k = 1, đây là giải mã tham lam: luôn chọn token khả năng cao nhất.
Hãy cài đặt sample_token(logits, temperature, k, random_value).
Đầu vào
logits: Mỗi token trong từ vựng một điểm.
temperature: T, lớn hơn 0.
k: Số token đứng đầu cần giữ.
random_value: Một số ngẫu nhiên trong [0, 1).
Đầu ra
Trả về chỉ số của token được chọn.
Ràng buộc
1 ≤ k ≤ số logit ≤ 1.000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ mỗi logit ≤ 100
Ví dụ
Đầu vào:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Kết quả mong đợi:
expected = 1
Đầu vào:
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;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Kết quả mong đợi:
long expected = 1;
Giải thích
k = 1 chỉ giữ logit cao nhất, 3.0 ở chỉ số 1. Xác suất của nó là 1, nên nó được chọn bất kể số ngẫu nhiên: đây là giải mã tham lam.
Đầu vào:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Kết quả mong đợi:
expected = 1
Đầu vào:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Kết quả mong đợi:
long expected = 1;
Giải thích
Top-2 giữ chỉ số 0 và 1 (logit 2 và 1). softmax cho khoảng 0.731 và 0.269. Tổng cộng dồn là 0.731 sau chỉ số 0 (chưa vượt 0.8) và 1 sau chỉ số 1, nên chọn chỉ số 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trước hết chọn các token có logit cao nhất, phá hòa bằng index nhỏ hơn, rồi sắp lại các token đó theo thứ tự index tăng dần.
Gợi ý 2
Chuyển các logit được giữ thành xác suất sau khi chia cho temperature, dùng softmax ổn định về mặt số học.
Gợi ý 3
Khi quét xác suất tích lũy, trả về index đầu tiên vượt qua giá trị random, nhưng nếu làm tròn khiến không có điểm vượt thì dùng token được giữ cuối cùng.
Độ phức tạp mong đợi
thời gian O(m log m), bộ nhớ phụ O(m)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.