NLP: Vectors from co-occurrence counts

Build word vectors from the company words keep, the idea behind GloVe and word2vec.

What to build

A program that builds a co-occurrence matrix and compares words with cosine similarity.

Requirements

  • Lowercase the sentences and split them on whitespace; the vocabulary is all their words, sorted. Windows never cross from one sentence to another.
  • For every occurrence of a word, add 1 to its vector at the column of each word within w positions before or after it in the same sentence.
  • Print vocabulary: ..., then word: c1 c2 ... for every vocabulary word in order. Then, for each query pair, print a b C with the cosine similarity of their vectors to three decimal places (0.000 if either vector is all zeros).

Input

Line 1: the window size w. Line 2: n. Then n sentences. Then q and q pairs of vocabulary words.

Output

The vocabulary line, one line per word, then q lines.

Constraints

w ≤ 5; at most 30 distinct words.

Example

Input:

1
3
i like tea
i like coffee
you drink tea
2
tea coffee
like drink

Output:

vocabulary: coffee drink i like tea you
coffee: 0 0 0 1 0 0
drink: 0 0 0 0 1 1
i: 0 0 0 2 0 0
like: 1 0 2 0 1 0
tea: 0 1 0 1 0 0
you: 0 1 0 0 0 0
tea coffee 0.707
like drink 0.289

Why it works

Words that appear in the same contexts collect counts in the same columns, so their rows point in similar directions even if the two words never appear together.

Examples

Example 1 · Input
1
3
i like tea
i like coffee
you drink tea
2
tea coffee
like drink
Expected output
vocabulary: coffee drink i like tea you
coffee: 0 0 0 1 0 0
drink: 0 0 0 0 1 1
i: 0 0 0 2 0 0
like: 1 0 2 0 1 0
tea: 0 1 0 1 0 0
you: 0 1 0 0 0 0
tea coffee 0.707
like drink 0.289
Example 2 · Input
2
1
a b c
2
a c
a b
Expected output
vocabulary: a b c
a: 0 1 1
b: 1 0 1
c: 1 1 0
a c 0.500
a b 0.500

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

Hints

Hint 1

For the word at position i, its neighbours are positions max(0, i − w) to min(len − 1, i + w), except i itself.

Hint 2

Give each vocabulary word an index (`{t: i for i, t in enumerate(vocab)}`) so you can add 1 to the right column.

Solution

Show one correct solution (try it yourself first)
import math

w = int(input())
sentences = [input().lower().split() for _ in range(int(input()))]
vocab = sorted(set(t for s in sentences for t in s))
index = {t: i for i, t in enumerate(vocab)}
vec = {t: [0] * len(vocab) for t in vocab}
for s in sentences:
    for i, t in enumerate(s):
        for j in range(max(0, i - w), min(len(s), i + w + 1)):
            if j != i:
                vec[t][index[s[j]]] += 1
print("vocabulary:", " ".join(vocab))
for t in vocab:
    print(f"{t}: {' '.join(map(str, vec[t]))}")
for _ in range(int(input())):
    a, b = input().split()
    u, v = vec[a], vec[b]
    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))
    print(f"{a} {b} {dot / norm:.3f}" if norm else f"{a} {b} 0.000")

Lesson: Word embeddings →