NLP: Compare word vectors

Measure how similar words are from their embedding vectors.

What to build

A program that prints the cosine similarity of pairs of word vectors.

Requirements

  • Each vector line is a word followed by its numbers; all vectors have the same length and none is all zeros.
  • For each query pair a b print a b C with the cosine similarity to three decimal places, or unknown word W for the first of the two words that has no vector.

Input

Line 1: n. Then n vector lines. Then q and q pairs.

Output

q lines.

Constraints

n ≤ 1,000; vectors have at most 300 numbers.

Example

Input:

3
king 0.9 0.8
queen 0.9 -0.8
man 0.1 0.8
2
king queen
king man

Output:

king queen 0.117
king man 0.752

Why it works

Dividing the dot product by both lengths leaves only the cosine of the angle between the vectors, so the result measures direction (meaning) and not length.

Examples

Example 1 · Input
3
king 0.9 0.8
queen 0.9 -0.8
man 0.1 0.8
2
king queen
king man
Expected output
king queen 0.117
king man 0.752
Example 2 · Input
2
cat 1 0
dog 0 1
2
cat dog
cat cow
Expected output
cat dog 0.000
unknown word cow

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

Hints

Hint 1

cos = sum of products ÷ (√(sum of squares of u) × √(sum of squares of v)).

Hint 2

Check that both words are in the table before computing.

Solution

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

vectors = {}
for _ in range(int(input())):
    parts = input().split()
    vectors[parts[0]] = [float(x) for x in parts[1:]]
for _ in range(int(input())):
    a, b = input().split()
    missing = [w for w in (a, b) if w not in vectors]
    if missing:
        print(f"unknown word {missing[0]}")
        continue
    u, v = vectors[a], vectors[b]
    dot = sum(x * y for x, y in zip(u, v))
    norm = math.sqrt(sum(x * x for x in u)) * math.sqrt(sum(y * y for y in v))
    print(f"{a} {b} {dot / norm:.3f}")

Lesson: Word embeddings →