Semantic search with averaged embeddings

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

Example 1 · 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
Expected output
1: semantic 1.000, shared words 0
2: semantic 0.316, shared words 0
Example 2 · Input
2
a 1 0
b 0 1
3
a
b
c
b
Expected output
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}")

Lesson: Semantic search →