NLP: Solve word analogies

Answer "a is to b as c is to ?" with vector arithmetic, the famous word2vec test.

What to build

A program that solves analogy questions with word vectors.

Requirements

  • Each query a b c asks: a is to b as c is to what? Compute the target b − a + c and find the word, other than a, b and c, with the highest cosine similarity to it; ties (equal to 9 decimal places) go to the alphabetically first word.
  • Print a : b :: c : d (S) with the similarity S to three decimal places, or a : b :: c : ? (unknown word) if a, b or c has no vector.

Input

Line 1: n. Then n lines word v1 v2 .... Then q and q queries.

Output

q lines.

Constraints

n ≥ 4; at most 1,000 words with at most 300 numbers each; no vector is all zeros.

Example

Input:

6
king 0.9 0.8 0.0
queen 0.9 -0.8 0.0
man 0.1 0.8 0.0
woman 0.1 -0.8 0.0
apple 0.0 0.0 0.9
prince 0.7 0.6 0.0
2
man king woman
man woman king

Output:

man : king :: woman : queen (1.000)
man : woman :: king : queen (1.000)

Why it works

If the difference between b and a is a direction such as "royalty" or "capital of", adding it to c moves c the same way, so the word nearest that point is the one that stands in the same relation to c.

Examples

Example 1 · Input
6
king 0.9 0.8 0.0
queen 0.9 -0.8 0.0
man 0.1 0.8 0.0
woman 0.1 -0.8 0.0
apple 0.0 0.0 0.9
prince 0.7 0.6 0.0
2
man king woman
man woman king
Expected output
man : king :: woman : queen (1.000)
man : woman :: king : queen (1.000)
Example 2 · Input
5
paris 1 0 1
france 1 0 0
rome 0 1 1
italy 0 1 0
tokyo 0.5 0.5 1
2
france paris italy
paris france rome
Expected output
france : paris :: italy : rome (1.000)
paris : france :: rome : italy (1.000)

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

Hints

Hint 1

For `a b c`, the target vector is b − a + c, computed number by number.

Hint 2

Rank the other words with `key=lambda w: (-round(cosine(target, vectors[w]), 9), w)` so near-equal scores fall back to alphabetical order.

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:]]


def cosine(u, v):
    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))
    return dot / norm if norm else 0.0


for _ in range(int(input())):
    a, b, c = input().split()
    if any(w not in vectors for w in (a, b, c)):
        print(f"{a} : {b} :: {c} : ? (unknown word)")
        continue
    target = [vb - va + vc for va, vb, vc in zip(vectors[a], vectors[b], vectors[c])]
    others = [w for w in vectors if w not in (a, b, c)]
    best = min(others, key=lambda w: (-round(cosine(target, vectors[w]), 9), w))
    print(f"{a} : {b} :: {c} : {best} ({cosine(target, vectors[best]):.3f})")

Lesson: Word embeddings →