Build the lesson's semantic search and see how it differs from keyword matching.
What to build
A program that ranks documents by the cosine similarity of averaged word embeddings, and also counts shared words.
Requirements
- Embed each text as the average of the embeddings of its words that are in the table.
- Score each document by cosine similarity with the query (0 if the document has no known words).
- Print every document as
D: semantic S, shared words W, highest S first (equal scores by document number), S with 3 decimals and W the number of different query words found in the document.
Input
Line 1: m. Then m lines word x1 x2 .... Then n and n documents. Then the query.
Output
n lines.
Constraints
1 ≤ m, n ≤ 1000; the query has at least one known word; texts are lower-case words.
Example
Input:
6
car 2 0
automobile 2 0
repair 1 1
service 1 1
pizza 0 2
recipe 0 2
2
car service
pizza recipe
automobile repair
Output:
1: semantic 1.000, shared words 0
2: semantic 0.316, shared words 0
Why it works
Averaging embeddings gives each text a direction in meaning space, so a document can score high with no shared words, which keyword counting cannot do.
Examples
6 car 2 0 automobile 2 0 repair 1 1 service 1 1 pizza 0 2 recipe 0 2 2 car service pizza recipe automobile repair
1: semantic 1.000, shared words 0 2: semantic 0.316, shared words 0
2 a 1 0 b 0 1 3 a b c b
2: semantic 1.000, shared words 1 1: semantic 0.000, shared words 0 3: semantic 0.000, shared words 0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A text's embedding is the average of the vectors of its known words; unknown words are ignored.
Hint 2
A document with no known words scores 0; otherwise use cosine similarity with the query's embedding.
Hint 3
Shared words: the number of different query words that also appear in the document.
Solution
Show one correct solution (try it yourself first)
import math
m = int(input())
vectors = {}
for _ in range(m):
word, *nums = input().split()
vectors[word] = list(map(float, nums))
n = int(input())
docs = [input().split() for _ in range(n)]
query = input().split()
def embed(words):
known = [vectors[w] for w in words if w in vectors]
if not known:
return None
return [sum(v[i] for v in known) / len(known) for i in range(len(known[0]))]
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)))
q = embed(query)
rows = []
for i, d in enumerate(docs):
e = embed(d)
score = cosine(q, e) if e else 0.0
shared = len(set(query) & set(d))
rows.append((-score, i + 1, shared))
for s, i, shared in sorted(rows):
print(f"{i}: semantic {-s:.3f}, shared words {shared}")