समस्या
भाषा मॉडल अगला टोकन एक प्रायिकता वितरण से चुनते हैं। दो सेटिंग इसे आकार देती हैं:
- 'टॉप-k: केवल सबसे ऊँचे logit वाले k टोकन रखें (बराबर logit होने पर छोटा इंडेक्स ऊपर रहता है)।'
- 'टेम्परेचर T: softmax से पहले रखे गए logit को T से भाग दें। कम T चुनाव को अधिक अनुमानित बनाता है, ऊँचा T अधिक यादृच्छिक।'
सैंपलिंग को टेस्ट करने लायक बनाने के लिए यादृच्छिक संख्या दी जाती है:
- टॉप-k टोकन रखें और उन्हें उनके मूल इंडेक्स (बढ़ते क्रम) से सूचीबद्ध करें।
- रखे गए टोकन पर softmax(logit / T) निकालें (e^x निकालने से पहले सबसे बड़ा मान घटाएँ)।
- सूची पर चलते हुए प्रायिकताएँ जोड़ें; उस पहले टोकन का इंडेक्स लौटाएँ जहाँ कुल योग
random_valueसे बड़ा हो जाए। अगर ऐसा कभी न हो (राउंडिंग के कारण), तो आख़िरी रखा गया टोकन लौटाएँ।
k = 1 पर यह ग्रीडी डिकोडिंग है: हमेशा सबसे संभावित टोकन।
sample_token(logits, temperature, k, random_value) लागू करें।
इनपुट
logits: शब्दावली के हर टोकन के लिए एक स्कोर।
temperature: T, 0 से बड़ा।
k: कितने शीर्ष टोकन रखने हैं।
random_value: [0, 1) में एक यादृच्छिक संख्या।
आउटपुट
चुने गए टोकन का इंडेक्स लौटाएँ।
सीमाएँ
1 ≤ k ≤ logit की संख्या ≤ 1,000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ हर logit ≤ 100
उदाहरण
इनपुट:
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 रखता है, इंडेक्स 1 पर 3.0। इसकी प्रायिकता 1 है, इसलिए यादृच्छिक संख्या कुछ भी हो, यही चुना जाता है: ग्रीडी डिकोडिंग।
इनपुट:
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;
व्याख्या
टॉप-2 इंडेक्स 0 और 1 रखता है (logit 2 और 1)। Softmax लगभग 0.731 और 0.269 देता है। कुल योग इंडेक्स 0 के बाद 0.731 है (0.8 से अधिक नहीं) और इंडेक्स 1 के बाद 1 है, इसलिए इंडेक्स 1 चुना जाता है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
पहले highest-logit tokens चुनें, ties को smaller index से तोड़ें, फिर उन tokens को ascending index order में restore करें.
संकेत 2
Temperature से divide करने के बाद kept logits को probabilities में बदलें, numerically stable softmax use करके.
संकेत 3
Cumulative probability scan करते समय, random value को cross करने वाले first index को return करें, लेकिन अगर rounding की वजह से crossing न हो तो last kept token पर fall back करें.
अपेक्षित जटिलता
समय O(m log m), अतिरिक्त स्थान O(m)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।