Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Skalierte Skalarprodukt-Attention

Implementiere die Attention-Operation, das Herzstück von Transformern und großen Sprachmodellen.

Das lernst du

  • Queries gegen Keys bewerten
  • Softmax anwenden, um Attention-Gewichte zu erhalten
  • Values mit diesen Gewichten mischen

Problem

Attention lässt jede Position einer Sequenz auf alle anderen Positionen schauen und deren Informationen mischen. Sie ist der Kern der Transformer-Architektur, die große Sprachmodelle verwenden:

Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V

Für jede Query-Zeile q:

  1. Bewerte jede Key-Zeile k: score = (q · k) / √d, wobei d die Anzahl der Spalten von K ist.
  2. Wandle die Scores mit Softmax in Gewichte um (ziehe den größten Score ab, bevor du e^x berechnest).
  3. Die Ausgabezeile ist die gewichtete Summe der Value-Zeilen: Σ weight_j × values[j].

Implementiere attention(queries, keys, values).

Eingabe

queries: n Zeilen mit je d Zahlen.

keys: m Zeilen mit je d Zahlen.

values: m Zeilen (eine pro Key) mit je v Zahlen.

Ausgabe

Gib die n × v-Ausgabematrix zurück.

Einschränkungen

1 ≤ n, m ≤ 50, 1 ≤ d, v ≤ 32

-10 ≤ jeder Wert ≤ 10

Beispiele

Beispiel 1
Eingabe:
queries = [
    [1.0, 0.0]
]
keys = [
    [1.0, 0.0],
    [1.0, 0.0]
]
values = [
    [2.0, 4.0],
    [6.0, 8.0]
]

Erwartete Ausgabe:
expected = [
    [4.0, 6.0]
]
Eingabe:
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}
};

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {4.0, 6.0}
};
Eingabe:
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}
};

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {4.0, 6.0}
};

Erläuterung

Beide Keys ergeben denselben Score, also sind die Softmax-Gewichte 0.5 und 0.5. Die Ausgabe ist der Mittelwert der Value-Zeilen: [(2 + 6) / 2, (4 + 8) / 2] = [4, 6].

Beispiel 2
Eingabe:
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]
]

Erwartete Ausgabe:
expected = [
    [3.0]
]
Eingabe:
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}
};

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {3.0}
};
Eingabe:
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}
};

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {3.0}
};

Erläuterung

Eine Null-Query hat gegenüber jedem Key den Score 0, also verteilt sich die Attention gleichmäßig: (1 + 2 + 6) / 3 = 3.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Vergleiche für jede Query sie mit jedem Key per Skalarprodukt, skaliert durch die Wurzel der Key-Dimension.

Hinweis 2

Wandle die Scores mit einer numerisch stabilen Softmax in Gewichte um und mische dann die Value-Zeilen mit diesen Gewichten.

Hinweis 3

Jede Query erzeugt eine Ausgabereihe, und die Value-Vektoren bestimmen die Ausgabebreite, nicht Queries oder Keys.

Erwartete Komplexität

Zeit O(n m (d + v)), zusätzlicher Speicher O(m)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 833 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.