Deep learning: One attention head

Compute the full output of attention for one query.

What to build

A program that computes scaled dot-product attention for one query over a set of keys and values.

Requirements

  • Weights are the softmax of the scaled scores; the output is the weighted sum of the value vectors.
  • Print weights: and the weights, then output: and the output vector, all with four decimal places.

Input

Line 1: the query. Line 2: m. Then m keys, then m values.

Output

Two lines.

Constraints

m ≤ 100.

Example

Input:

1 0
2
1 0
1 0
2 0
0 4

Output:

weights: 0.5000 0.5000
output: 1.0000 2.0000

Why it works

The softmax turns match scores into a share of attention for each position, and the output mixes the values in those shares.

Examples

Example 1 · Input
1 0
2
1 0
1 0
2 0
0 4
Expected output
weights: 0.5000 0.5000
output: 1.0000 2.0000
Example 2 · Input
1
2
0
1
10
0
Expected output
weights: 0.2689 0.7311
output: 2.6894

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Compute the scaled scores, then a stable softmax to get the weights.

Hint 2

The output is the sum over the keys of weight × value vector.

Solution

Show one correct solution (try it yourself first)
import math

q = list(map(float, input().split()))
m = int(input())
keys = [list(map(float, input().split())) for _ in range(m)]
values = [list(map(float, input().split())) for _ in range(m)]
scores = [sum(a * b for a, b in zip(q, k)) / math.sqrt(len(q)) for k in keys]
top = max(scores)
e = [math.exp(s - top) for s in scores]
weights = [v / sum(e) for v in e]
output = [sum(w * v[c] for w, v in zip(weights, values)) for c in range(len(values[0]))]
print("weights: " + " ".join(f"{w:.4f}" for w in weights))
print("output: " + " ".join(f"{v + 0.0:.4f}" for v in output))

Lesson: Attention →