Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Multi-Head Self-Attention

Project the input into queries, keys and values, run attention in several heads in parallel, and combine them.

Das lernst du

  • Project inputs into queries, keys and values
  • Run attention in several heads
  • Concatenate heads and project the result

Problem

Übersetzung anzeigen

Multi-head attention lets a Transformer attend to different things at once. With input X (n tokens × d columns) and weight matrices of size d × d:

  1. Q = X × w_q, K = X × w_k, V = X × w_v
  2. Split the d columns into num_heads heads of d_k = d / num_heads consecutive columns (head h uses columns h×d_k to (h+1)×d_k - 1).
  3. For each head, run scaled dot-product attention on its columns: for token i, score_j = (Q_i · K_j) / √d_k over that head's columns, softmax over all n tokens j, and output = Σ weight_j × V_j (that head's columns).
  4. Put the heads' outputs back in their columns (concatenate) and multiply by w_o.

Implement multi_head_attention(x, w_q, w_k, w_v, w_o, num_heads).

Input

x: n × d input matrix.

w_q, w_k, w_v, w_o: d × d weight matrices.

num_heads: Number of heads (d is divisible by it).

Output

Return the n × d output matrix.

Einschränkungen

1 ≤ n ≤ 30, 1 ≤ d ≤ 32, 1 ≤ num_heads ≤ d and d is divisible by num_heads

-5 ≤ each value ≤ 5

Beispiele

Beispiel 1
Eingabe:
x = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_q = [
    [0.0, 0.0],
    [0.0, 0.0]
]
w_k = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_v = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_o = [
    [1.0, 0.0],
    [0.0, 1.0]
]
num_heads = 1

Erwartete Ausgabe:
expected = [
    [0.5, 0.5],
    [0.5, 0.5]
]
Eingabe:
std::vector<std::vector<double>> x = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_q = {
    {0.0, 0.0},
    {0.0, 0.0}
};
std::vector<std::vector<double>> w_k = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_v = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_o = {
    {1.0, 0.0},
    {0.0, 1.0}
};
long long num_heads = 1;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {0.5, 0.5},
    {0.5, 0.5}
};
Eingabe:
double[][] x = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_q = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {0.0, 0.0}
};
double[][] w_k = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_v = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_o = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
long num_heads = 1;

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

Erläuterung

w_q is all zeros, so every score is 0 and each token averages the value rows: V = X, so both rows become [0.5, 0.5].

Beispiel 2
Eingabe:
x = [
    [2.0, 4.0]
]
w_q = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_k = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_v = [
    [1.0, 0.0],
    [0.0, 1.0]
]
w_o = [
    [0.0, 1.0],
    [1.0, 0.0]
]
num_heads = 2

Erwartete Ausgabe:
expected = [
    [4.0, 2.0]
]
Eingabe:
std::vector<std::vector<double>> x = {
    {2.0, 4.0}
};
std::vector<std::vector<double>> w_q = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_k = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_v = {
    {1.0, 0.0},
    {0.0, 1.0}
};
std::vector<std::vector<double>> w_o = {
    {0.0, 1.0},
    {1.0, 0.0}
};
long long num_heads = 2;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {4.0, 2.0}
};
Eingabe:
double[][] x = new double[][] {
    new double[] {2.0, 4.0}
};
double[][] w_q = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_k = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_v = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {0.0, 1.0}
};
double[][] w_o = new double[][] {
    new double[] {0.0, 1.0},
    new double[] {1.0, 0.0}
};
long num_heads = 2;

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

Erläuterung

With a single token each head attends only to itself, so the concatenated output is V = [2, 4]. w_o swaps the two columns: [4, 2].

So gehst du vor

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

Hinweis 1

Project the input into queries, keys, and values first, then split the feature dimension into equal head-sized chunks.

Hinweis 2

Run the same attention procedure inside each head independently, using the smaller head dimension for scaling.

Hinweis 3

Concatenate head outputs in their original column order before the final output projection, and keep matrix dimensions aligned carefully.

Erwartete Komplexität

O(n^2 * d + n * d^2) time, O(n * d) extra space

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 839 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.