समस्या
अटेंशन किसी अनुक्रम की हर स्थिति को बाकी सभी स्थितियों को देखने और उनकी जानकारी मिलाने देता है। यह ट्रांसफ़ॉर्मर आर्किटेक्चर का मूल है, जिसे बड़े लैंग्वेज मॉडल इस्तेमाल करते हैं:
Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V
हर क्वेरी पंक्ति q के लिए:
- हर की (key) पंक्ति k का स्कोर निकालें: score = (q · k) / √d, जहाँ d, K के कॉलम की संख्या है।
- सॉफ्टमैक्स से स्कोर को वेट में बदलें (e^x निकालने से पहले सबसे बड़ा स्कोर घटाएँ)।
- आउटपुट पंक्ति वैल्यू पंक्तियों का वेटेड योग है: Σ weight_j × values[j]।
attention(queries, keys, values) लागू करें।
इनपुट
queries: n पंक्तियाँ, हर एक में d संख्याएँ।
keys: m पंक्तियाँ, हर एक में d संख्याएँ।
values: m पंक्तियाँ (हर की के लिए एक), हर एक में 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}
};
व्याख्या
दोनों की का स्कोर बराबर है, इसलिए सॉफ्टमैक्स वेट 0.5 और 0.5 हैं। आउटपुट वैल्यू पंक्तियों का औसत है: [(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}
};
व्याख्या
शून्य क्वेरी का हर की के साथ स्कोर 0 है, इसलिए अटेंशन बराबर बँटता है: (1 + 2 + 6) / 3 = 3।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर query के लिए, उसे हर key से dot product के जरिए compare करें, और उसे key dimension के square root से scale करें।
संकेत 2
Scores को numerically stable softmax से weights में बदलें, फिर उन weights का उपयोग करके value rows को blend करें।
संकेत 3
हर query एक output row बनाती है, और output width queries या keys नहीं बल्कि value vectors तय करते हैं।
अपेक्षित जटिलता
समय O(n m (d + v)), अतिरिक्त स्थान O(m)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।