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})")