Deep learning: Nearest neighbours of a word

Find the words an embedding considers most alike.

What to build

A program that lists the most similar words to each query word.

Requirements

  • Compare a query with every other word by cosine similarity. Rank from most to least similar; equal similarities (to four decimal places) are ordered alphabetically.
  • Print QUERY: W1 (S1), W2 (S2), … with similarities to four decimal places.

Input

Line 1: n and d. Then n lines: a word and d numbers. Then q and q lines WORD k.

Output

q lines.

Constraints

n ≤ 500; d ≤ 50; k < n.

Example

Input:

4 2
cat 1 0
dog 1 1
car 0 1
sea -1 0
2
cat 2
dog 2

Output:

cat: dog (0.7071), car (0.0000)
dog: car (0.7071), cat (0.7071)

Why it works

Words used in similar ways get vectors pointing in similar directions, so ranking by cosine similarity finds related words.

Examples

Example 1 · Input
4 2
cat 1 0
dog 1 1
car 0 1
sea -1 0
2
cat 2
dog 2
Expected output
cat: dog (0.7071), car (0.0000)
dog: car (0.7071), cat (0.7071)
Example 2 · Input
3 3
x 1 0 0
y 0 1 0
z 1 1 0
1
z 2
Expected output
z: x (0.7071), y (0.7071)

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

Hints

Hint 1

Compute the cosine similarity between the query's vector and every other word's vector.

Hint 2

Sort by similarity from high to low, breaking ties alphabetically, and keep the first k.

Solution

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

n, d = map(int, input().split())
vectors = {}
for _ in range(n):
    word, *values = input().split()
    vectors[word] = list(map(float, values))


def cosine(a, b):
    dot = sum(x * y for x, y in zip(a, b))
    return dot / (math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b)))


for _ in range(int(input())):
    word, k = input().split()
    scores = [(round(cosine(vectors[word], v), 4) + 0.0, w) for w, v in vectors.items() if w != word]
    scores.sort(key=lambda item: (-item[0], item[1]))
    print(f"{word}: " + ", ".join(f"{w} ({s:.4f})" for s, w in scores[: int(k)]))

Lesson: Embeddings →