Deep learning: Solve analogies with vectors

Use vector arithmetic in an embedding space to answer analogy questions.

What to build

A program that answers analogy questions using word embeddings.

Requirements

  • For each question a b c, the answer is the word (other than a, b and c) whose vector has the highest cosine similarity with b − a + c.
  • Print a : b :: c : ANSWER (S) with the similarity to four decimal places.

Input

Line 1: n and d. Then n lines: a word and d numbers. Then q and q lines a b c.

Output

q lines.

Constraints

n ≤ 500; d ≤ 50.

Example

Input:

5 4
king 0.9 0.9 0.1 0
queen 0.9 0.1 0.9 0
man 0.1 0.9 0.1 0
woman 0.1 0.1 0.9 0
apple 0 0.1 0.1 0.9
1
man king woman

Output:

man : king :: woman : queen (1.0000)

Why it works

If the difference between a and b is a consistent direction in the space, adding it to c should land near the word that relates to c in the same way.

Examples

Example 1 · Input
5 4
king 0.9 0.9 0.1 0
queen 0.9 0.1 0.9 0
man 0.1 0.9 0.1 0
woman 0.1 0.1 0.9 0
apple 0 0.1 0.1 0.9
1
man king woman
Expected output
man : king :: woman : queen (1.0000)
Example 2 · Input
5 4
king 0.9 0.9 0.1 0
queen 0.9 0.1 0.9 0
man 0.1 0.9 0.1 0
woman 0.1 0.1 0.9 0
apple 0 0.1 0.1 0.9
1
king queen man
Expected output
king : queen :: man : woman (1.0000)

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

Hints

Hint 1

For "a : b :: c : ?", compute the target b − a + c, element by element.

Hint 2

Search every word except a, b and c for the highest cosine similarity with the target; on a tie take the alphabetically first.

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(u, v):
    dot = sum(x * y for x, y in zip(u, v))
    return dot / (math.sqrt(sum(x * x for x in u)) * math.sqrt(sum(y * y for y in v)))


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

Lesson: Embeddings →