Đề bài
Attention cho phép mỗi vị trí trong chuỗi nhìn vào mọi vị trí khác và trộn thông tin của chúng. Đây là lõi của kiến trúc Transformer mà các mô hình ngôn ngữ lớn sử dụng:
Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V
Với mỗi hàng query q:
- Chấm điểm từng hàng key k: score = (q · k) / √d, với d là số cột của K.
- Biến điểm thành trọng số bằng softmax (trừ điểm lớn nhất trước khi tính e^x).
- Hàng đầu ra là tổng có trọng số của các hàng value: Σ weight_j × values[j].
Hãy cài đặt attention(queries, keys, values).
Đầu vào
queries: n hàng, mỗi hàng d số.
keys: m hàng, mỗi hàng d số.
values: m hàng (mỗi key một hàng), mỗi hàng v số.
Đầu ra
Trả về ma trận đầu ra kích thước n × v.
Ràng buộc
1 ≤ n, m ≤ 50, 1 ≤ d, v ≤ 32
-10 ≤ mỗi giá trị ≤ 10
Ví dụ
Đầu vào:
queries = [
[1.0, 0.0]
]
keys = [
[1.0, 0.0],
[1.0, 0.0]
]
values = [
[2.0, 4.0],
[6.0, 8.0]
]
Kết quả mong đợi:
expected = [
[4.0, 6.0]
]
Đầu vào:
std::vector<std::vector<double>> queries = {
{1.0, 0.0}
};
std::vector<std::vector<double>> keys = {
{1.0, 0.0},
{1.0, 0.0}
};
std::vector<std::vector<double>> values = {
{2.0, 4.0},
{6.0, 8.0}
};
Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
{4.0, 6.0}
};
Đầu vào:
double[][] queries = new double[][] {
new double[] {1.0, 0.0}
};
double[][] keys = new double[][] {
new double[] {1.0, 0.0},
new double[] {1.0, 0.0}
};
double[][] values = new double[][] {
new double[] {2.0, 4.0},
new double[] {6.0, 8.0}
};
Kết quả mong đợi:
double[][] expected = new double[][] {
new double[] {4.0, 6.0}
};
Giải thích
Hai key cho cùng một điểm, nên trọng số softmax là 0.5 và 0.5. Đầu ra là trung bình của các hàng value: [(2 + 6) / 2, (4 + 8) / 2] = [4, 6].
Đầu vào:
queries = [
[0.0, 0.0]
]
keys = [
[3.0, 1.0],
[-2.0, 5.0],
[7.0, 7.0]
]
values = [
[1.0],
[2.0],
[6.0]
]
Kết quả mong đợi:
expected = [
[3.0]
]
Đầu vào:
std::vector<std::vector<double>> queries = {
{0.0, 0.0}
};
std::vector<std::vector<double>> keys = {
{3.0, 1.0},
{-2.0, 5.0},
{7.0, 7.0}
};
std::vector<std::vector<double>> values = {
{1.0},
{2.0},
{6.0}
};
Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
{3.0}
};
Đầu vào:
double[][] queries = new double[][] {
new double[] {0.0, 0.0}
};
double[][] keys = new double[][] {
new double[] {3.0, 1.0},
new double[] {-2.0, 5.0},
new double[] {7.0, 7.0}
};
double[][] values = new double[][] {
new double[] {1.0},
new double[] {2.0},
new double[] {6.0}
};
Kết quả mong đợi:
double[][] expected = new double[][] {
new double[] {3.0}
};
Giải thích
Query toàn số 0 cho điểm 0 với mọi key, nên attention chia đều: (1 + 2 + 6) / 3 = 3.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Với mỗi query, so sánh nó với mọi key bằng dot product được chia cho căn bậc hai của số chiều key.
Gợi ý 2
Đổi các score thành weights bằng một softmax ổn định số học, rồi trộn các hàng value theo các weight đó.
Gợi ý 3
Mỗi query tạo ra một hàng output, và các vector value quyết định độ rộng đầu ra chứ không phải queries hay keys.
Độ phức tạp mong đợi
thời gian O(n m (d + v)), 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.