โจทย์
Attention ทำให้แต่ละตำแหน่งในลำดับมองเห็นตำแหน่งอื่นทั้งหมดและผสมข้อมูลของตำแหน่งเหล่านั้น นี่คือแกนหลักของสถาปัตยกรรม Transformer ที่โมเดลภาษาขนาดใหญ่ใช้:
Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V
สำหรับแต่ละแถว query q:
- ให้คะแนนแต่ละแถว key k: score = (q · k) / √d โดย d คือจำนวนคอลัมน์ของ K
- เปลี่ยนคะแนนเป็นน้ำหนักด้วย softmax (ลบคะแนนที่มากที่สุดออกก่อนคำนวณ e^x)
- แถวเอาต์พุตคือผลรวมถ่วงน้ำหนักของแถว value: Σ weight_j × values[j]
จงเขียน attention(queries, keys, values)
อินพุต
queries: n แถว แต่ละแถวมีตัวเลข d ตัว
keys: m แถว แต่ละแถวมีตัวเลข d ตัว
values: m แถว (หนึ่งแถวต่อ key หนึ่งตัว) แต่ละแถวมีตัวเลข v ตัว
เอาต์พุต
คืนค่าเมทริกซ์เอาต์พุตขนาด n × v
เงื่อนไข
1 ≤ n, m ≤ 50, 1 ≤ d, v ≤ 32
-10 ≤ แต่ละค่า ≤ 10
ตัวอย่าง
อินพุต:
queries = [
[1.0, 0.0]
]
keys = [
[1.0, 0.0],
[1.0, 0.0]
]
values = [
[2.0, 4.0],
[6.0, 8.0]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[4.0, 6.0]
]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<double>> expected = {
{4.0, 6.0}
};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
double[][] expected = new double[][] {
new double[] {4.0, 6.0}
};
คำอธิบาย
key ทั้งสองให้คะแนนเท่ากัน น้ำหนัก softmax จึงเป็น 0.5 และ 0.5 เอาต์พุตคือค่าเฉลี่ยของแถว value: [(2 + 6) / 2, (4 + 8) / 2] = [4, 6]
อินพุต:
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]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[3.0]
]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<double>> expected = {
{3.0}
};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
double[][] expected = new double[][] {
new double[] {3.0}
};
คำอธิบาย
query ที่เป็นศูนย์ได้คะแนน 0 กับทุก key ดังนั้น attention จึงกระจายเท่าๆ กัน: (1 + 2 + 6) / 3 = 3
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สำหรับแต่ละ query ให้เทียบกับทุก key ด้วย dot product ที่สเกลด้วยรากที่สองของมิติของ key
คำใบ้ 2
แปลง scores เป็น weights ด้วย softmax ที่เสถียรเชิงตัวเลข แล้วผสมแถวของ value ด้วย weights เหล่านั้น
คำใบ้ 3
แต่ละ query จะสร้าง output ได้หนึ่งแถว และขนาดความกว้างของ output มาจาก value vectors ไม่ใช่ queries หรือ keys
ความซับซ้อนที่คาดหวัง
เวลา O(n m (d + v)), หน่วยความจำเพิ่ม O(m)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน