<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Introduction
We introduce the vector space model in this notebook. 
This notebook is adapted from http
Step1:  Now we construct the vocabulary and the doc-term matrix.
Step2:  Now we transform raw tf to tf by $1 + \log(tf)$.
Step3:  Adding idf
The above vectors in vec_list only keep track of term frequencies (tfs). Now we make each element $w_{d, t} = tf(d, t) \cdot idf(t)$. 
Note that the textbook version of idf will have 0 if df == ndocs. Therefore, we follow the implementation in Lucene
(https
Step4:  We will eventually record in voc the idf values. You can look at the raw df value and the resulting idf values from the outputs of the above the below cells.
Step5:  Now we can look at the final weighted vectors of the documents. 
We choose to implement it based on matrix operations supported by numpy. E.g., to obtained ${a_i b_i}{i=1}^n$ from two vector $\vec{A} = {a_i}{i=1}^n$ and $\vec{B} = {b_i}_{i=1}^n$, we first construct a diagonal matrix $\mathbf{D_A}$ whose diagonal elements are $a_i$, then we can obtain the desired result by the standard matrix multiplication of $\vec{B} \mathbf{D_A}$.
Step6:  Look at the matrix m before normalization. 
* m[0][6] = 1.405. This is because $tf(d_0, 'linda') = 1$, and $idf('linda') = 1.4054651081081644$. 
* m[0][8] = 0.828. This is because $tf(d_0, 'me') = 1.693$, and $idf('me') = 0.4891743762340093$.  
Measuring the Similarity of Two Documents
We use the cosine to measure the similarity of two weighted vectors.
Step7:  Modelling a Query as a Document
We implement an equivalent form of the lnc.ltc model. Therefore, there is no idf weighting on the query terms, since it is already used in the document matrix.
Step8:  Scoring Documents
<ASSISTANT_TASK:>
Python Code:
from pprint import pprint
import numpy as np
import contextlib
@contextlib.contextmanager
def printoptions(*args, **kwargs):
    original = np.get_printoptions()
    np.set_printoptions(*args, **kwargs)
    yield 
    np.set_printoptions(**original)
## compact print (numpy array) 
def cprint(x):
    with printoptions(precision=3, suppress=True, linewidth=120):
        print(x)        
    
# test
x = np.random.random(10)
cprint(x)
#examples taken from here: http://stackoverflow.com/a/1750187
doc_list = ['Julie loves me more than Linda loves me',
            'Jane likes me more than Julie loves me',
            'He likes basketball more than baseball']
bags = []
from collections import Counter
# we use lower() here so that the sorted vocabulary is easier to see.  
bags = [Counter(doc.lower().split()) for doc in doc_list]
for bag in bags:
    print(bag)
Explanation: Introduction
We introduce the vector space model in this notebook. 
This notebook is adapted from http://stanford.edu/~rjweiss/public_html/IRiSS2013/text2/notebooks/tfidf.html
From Documents to Bags-of-words
In the Vector Space Model (VSM), we view each document as a bag of words. (Bag means multiset)
In python, the best way to represent a bag is via collections.counter.
End of explanation
import itertools
vocabulary = sorted(list(set(itertools.chain(*[list(b) for b in bags]))))
vocabulary
def print_vocabulary_vertically(voc, leading_str = '', spacing=2, align=1):
    # align = 0: align top; otherwise, align bottom
    max_len = max([len(v) for v in voc])
    for i in range(max_len):
        if align == 0:
            line = [v[i] if i < len(v) else ' ' for v in voc]
        else:
            line = [' ' if i < max_len - len(v) else v[i-max_len] for v in voc]
        print('{}{}'.format(leading_str, (' '*spacing).join(line)))
print_vocabulary_vertically(vocabulary, align=0)
for doc in doc_list:
    print(doc)
print()
vec_list = []
print_vocabulary_vertically(vocabulary, leading_str=' ')
print('-'*70)
for bag in bags:
    vec = [bag[v] for v in vocabulary] # Counter['non-existing-key'] = 0
    vec_list.append(vec)
    print(vec)
    
Explanation: Now we construct the vocabulary and the doc-term matrix.
End of explanation
from math import log
def normalize_tf(tf):
    if tf == 0:
        return 0.0
    else:
        return 1.0 + log(tf)
tf_vec_list = []
for vec in vec_list:
    tf_vec_list.append([normalize_tf(val) for val in vec])
print_vocabulary_vertically(vocabulary, leading_str='   ', spacing=6)
print('-'*80)
cprint(np.matrix(tf_vec_list))
Explanation: Now we transform raw tf to tf by $1 + \log(tf)$.
End of explanation
from math import log
def idf(cnt, ndocs): 
    # here we use ln(). The base of the log does not matter much. 
    return 1.0 + log(ndocs/(cnt+1))  
ndocs = len(doc_list)
# voc = [ (v, [b[v] for b in bags]) for v in vocabulary] # if you want to see the individual counts
voc = [(v, sum([b[v] for b in bags])) for v in vocabulary]
pprint(voc)
Explanation: Adding idf
The above vectors in vec_list only keep track of term frequencies (tfs). Now we make each element $w_{d, t} = tf(d, t) \cdot idf(t)$. 
Note that the textbook version of idf will have 0 if df == ndocs. Therefore, we follow the implementation in Lucene
(https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html) which gives: 
$$idf(t) = 1 + \log(\frac{ndocs}{df + 1})$$
BTW, on the above page, you can see the detailes and justifications of all major deviations of Lucene's implementation from the standard VSM. You will always need to do this to tackle new or specific problems you are facing when you join the workforce, :p. Therefore, a deep understanding of the principles behind the knowledge you learned in the uni is more important.
End of explanation
voc = [(v, idf( sum([b[v] for b in bags]), ndocs)) for v in vocabulary]
idf_dict = dict(voc)
pprint(voc)
print(idf_dict['he'])
Explanation: We will eventually record in voc the idf values. You can look at the raw df value and the resulting idf values from the outputs of the above the below cells.
End of explanation
import numpy as np
def build_idf_matrix(idf_vector):
    idf_mat = np.zeros((len(idf_vector), len(idf_vector)))
    np.fill_diagonal(idf_mat, idf_vector)
    return idf_mat
idf_matrix = build_idf_matrix([v[1] for v in voc])
cprint(idf_matrix)
import math
def l2_normalizer(vec):
    denom = np.sum([el**2 for el in vec])
    return [(el / math.sqrt(denom)) for el in vec]
doc_term_matrix_tfidf = []
#performing tf-idf matrix multiplication
for vec in tf_vec_list:
    doc_term_matrix_tfidf.append(np.dot(vec, idf_matrix))
cprint(np.matrix(doc_term_matrix_tfidf)) # np.matrix() just to make it easier to look at
#normalizing
print('\nAfter normalization ...')
doc_term_matrix_tfidf_l2 = []
for tf_vector in doc_term_matrix_tfidf:
    doc_term_matrix_tfidf_l2.append(l2_normalizer(tf_vector))
cprint(np.matrix(doc_term_matrix_tfidf_l2)) 
Explanation: Now we can look at the final weighted vectors of the documents. 
We choose to implement it based on matrix operations supported by numpy. E.g., to obtained ${a_i b_i}{i=1}^n$ from two vector $\vec{A} = {a_i}{i=1}^n$ and $\vec{B} = {b_i}_{i=1}^n$, we first construct a diagonal matrix $\mathbf{D_A}$ whose diagonal elements are $a_i$, then we can obtain the desired result by the standard matrix multiplication of $\vec{B} \mathbf{D_A}$.
End of explanation
import numpy as np
def normalize(v):
    norm = np.linalg.norm(v)
    if norm == 0: 
       return v
    return v / norm
def cosine(u, v):
    a = normalize(u)
    b = normalize(v)
    return np.inner(a, b)
cosine(doc_term_matrix_tfidf[0], doc_term_matrix_tfidf[1])
cosine(doc_term_matrix_tfidf[0], doc_term_matrix_tfidf[2])
cosine(doc_term_matrix_tfidf[1], doc_term_matrix_tfidf[2])
Explanation: Look at the matrix m before normalization. 
* m[0][6] = 1.405. This is because $tf(d_0, 'linda') = 1$, and $idf('linda') = 1.4054651081081644$. 
* m[0][8] = 0.828. This is because $tf(d_0, 'me') = 1.693$, and $idf('me') = 0.4891743762340093$.  
Measuring the Similarity of Two Documents
We use the cosine to measure the similarity of two weighted vectors.
End of explanation
q = 'Linda likes me'
def encode(q, voc):
    c = Counter(q.lower().split())
    return [normalize_tf(c[v]) if (v in c) else normalize_tf(0) for v in voc]
vec_q = encode(q, vocabulary)
print_vocabulary_vertically(vocabulary, leading_str=' ', spacing=4)
vec_q
Explanation: Modelling a Query as a Document
We implement an equivalent form of the lnc.ltc model. Therefore, there is no idf weighting on the query terms, since it is already used in the document matrix.
End of explanation
for i, vec in enumerate(vec_list):
    print('score of doc[{}] = {}'.format(i, cosine(doc_term_matrix_tfidf[i], vec_q)))
def topk(query, k):
    v_q = encode(query, vocabulary)
    out = []
    for i, vec in enumerate(vec_list):
        out.append((i, cosine(doc_term_matrix_tfidf[i], v_q)))
    answer = sorted(out, key=lambda r: r[1], reverse=True)[:k]
    return answer
topk('loves baseball', 3)
Explanation: Scoring Documents
End of explanation
<END_TASK>