Deep learning: Attention scores

Compute how strongly a query matches each key.

What to build

A program that computes scaled dot-product attention scores.

Requirements

  • sⱼ = (q · kⱼ) / √d.
  • Print the scores with four decimal places, separated by spaces.

Input

Line 1: the query. Line 2: m. Then m keys.

Output

One line.

Constraints

m ≤ 100; vectors of length at most 100.

Example

Input:

1 0
3
1 0
0 1
1 1

Output:

0.7071 0.0000 0.7071

Why it works

A dot product is large when two vectors point the same way, so the scores rank the keys by how well they match the query.

Examples

Example 1 · Input
1 0
3
1 0
0 1
1 1
Expected output
0.7071 0.0000 0.7071
Example 2 · Input
2 2 2 2
2
1 1 1 1
1 0 0 0
Expected output
4.0000 1.0000

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

Hints

Hint 1

Each score is the dot product of the query and one key.

Hint 2

Divide every score by math.sqrt(d), where d is the length of the vectors.

Solution

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

q = list(map(float, input().split()))
keys = [list(map(float, input().split())) for _ in range(int(input()))]
scale = math.sqrt(len(q))
print(" ".join(f"{sum(a * b for a, b in zip(q, k)) / scale + 0.0:.4f}" for k in keys))

Lesson: Attention →