โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การสุ่มด้วย temperature และ top-k

เลือก token ถัดไปแบบโมเดลภาษา: เก็บ logit สูงสุด k ตัว ใช้ temperature แล้วสุ่ม

สิ่งที่คุณจะได้เรียนรู้

  • เก็บ token ตัวเลือก k อันดับแรก
  • ควบคุมความสุ่มด้วย temperature
  • สุ่มจากการแจกแจงความน่าจะเป็น

โจทย์

โมเดลภาษาเลือก token ถัดไปจากการแจกแจงความน่าจะเป็น โดยมีการตั้งค่าสองอย่างที่กำหนดรูปร่างของมัน:

  • 'Top-k: เก็บเฉพาะ k token ที่มี logit สูงที่สุด (ถ้า logit เท่ากัน index ที่น้อยกว่าอยู่อันดับสูงกว่า)'
  • 'Temperature T: หาร logit ที่เก็บไว้ด้วย T ก่อน softmax ค่า T ต่ำทำให้การเลือกคาดเดาได้มากขึ้น ค่า T สูงทำให้สุ่มมากขึ้น'

เพื่อให้ทดสอบการสุ่มได้ จึงกำหนดตัวเลขสุ่มมาให้:

  1. เก็บ token ใน top-k และเรียงตาม index เดิม (จากน้อยไปมาก)
  2. คำนวณ softmax(logit / T) บน token ที่เก็บไว้ (ลบค่าที่มากที่สุดก่อนคำนวณ e^x)
  3. ไล่ตามรายการพร้อมบวกความน่าจะเป็นสะสม คืนค่า index ของ token แรกที่ผลรวมสะสมมากกว่า random_value ถ้าไม่เกิดขึ้นเลย (จากการปัดเศษ) ให้คืน token สุดท้ายที่เก็บไว้

เมื่อ k = 1 จะเป็น greedy decoding: เลือก token ที่น่าจะเป็นมากที่สุดเสมอ

จง implement sample_token(logits, temperature, k, random_value)

อินพุต

logits: คะแนนหนึ่งค่าต่อ token ในคลังคำศัพท์

temperature: T ซึ่งมากกว่า 0

k: จำนวน token อันดับต้นที่จะเก็บไว้

random_value: ตัวเลขสุ่มใน [0, 1)

เอาต์พุต

คืนค่า index ของ token ที่ถูกเลือก

เงื่อนไข

1 ≤ k ≤ จำนวน logit ≤ 1,000

0 < temperature ≤ 100, 0 ≤ random_value < 1

-100 ≤ แต่ละ logit ≤ 100

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
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;

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

k = 1 เก็บเฉพาะ logit สูงสุด คือ 3.0 ที่ index 1 ความน่าจะเป็นของมันคือ 1 จึงถูกเลือกไม่ว่าตัวเลขสุ่มจะเป็นเท่าใด: greedy decoding

ตัวอย่างที่ 2
อินพุต:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

Top-2 เก็บ index 0 และ 1 (logit 2 และ 1) softmax ได้ประมาณ 0.731 และ 0.269 ผลรวมสะสมเป็น 0.731 หลัง index 0 (ไม่เกิน 0.8) และเป็น 1 หลัง index 1 ดังนั้นจึงเลือก index 1

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

เลือก token ที่มี logit สูงสุดก่อน โดยใช้ index ที่น้อยกว่ากรณีเสมอกัน แล้วค่อยเรียง token ที่เลือกตาม index จากน้อยไปมาก

คำใบ้ 2

แปลง logits ที่เก็บไว้เป็น probabilities หลังหารด้วย temperature โดยใช้ softmax แบบ numerically stable

คำใบ้ 3

ตอนสแกน cumulative probability ให้คืนค่า index แรกที่เกินค่า random แต่ถ้า rounding ทำให้ไม่เกินเลยให้ fallback เป็น token สุดท้ายที่เลือกไว้

ความซับซ้อนที่คาดหวัง

เวลา O(m log m), หน่วยความจำเพิ่ม O(m)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก