<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Lab 4
Step8:  PMI
Point-wise mutual information is a measure of association used in information theory and statistics. In the words of Jurafsky and Martin
Step24:  Unigram and Skipgram
To train unigram and skipgram language models, you can use the following code.
Step25:  Text corpora
We have the following text corpora availlable for you
Step26:  The TedX talks
Step27:  The collection of Wikipedia entries
Step29:  1. Collocations with PPMI (40 points)
$PPMI$ can be used to find collocations; words that co-occur significantly more often than can be atrributed to chance. $PPMI$ is a natural measure for this task
Step30:  PTB
(a) Use the function you wrote to find collocations in the Penn Treebank dataset. Recall
Step31:  TedX
(b) Use the function you wrote to find collocations in the TedX dataset. (5 points)
Step32:  Wikipedia
(c) Find collocations in the Wikipedia dataset. (5 points)
Step33:  [Optional] Use the following template to query the model for PMI values for word-pairs. In particular, it is interesting to see what PMI our model assigns to the collocations in the PMI wikipedia entry
Step34:  (d) Now that you have (hopefully) been succesful at finding some collocations, take a moment to compare the lists of word-pairs from above, for which $PPMI(w_i,w_j)$ is high, with the list of word-pairs for which $p(w_i,w_j)$ is high. (5 points)
That means
Step36:  YOUR ANSWER HERE
2. Word-embeddings via PMI-SVD (60 points)
Inspired by this blog-post we consider a classic method to obtain word embeddings that combines $PMI$ with linear algebra.
Go ahead and read the post, it's an easy and quick read.
PPMI matrix
(a) The first step is to make a PPMI matrix $P$. This matrix will have entries
$$(P)_{ij} = PPMI(w_i, w_j)$$
Where $w_i$ and $w_j$ are the $i$-th and $j$-th words in our w2i dictionary. Finish the function make_ppmi_matrix. (20 points)
[Note] If you really want to scale up (more about that below), you can consider writing a second version of the function that uses a sparse matrix datastructe for the $PMI$ matrix. Most of the entries in it will be zero. Scipy sparse has a number of options. (You will not be able to plot this matrix with imshow though, like we will do a in a bit).
Step37:  (b) Use the function you wrote above to construct the $PPMI$ matrix for a corpus of your choice. (10 points)
[Note] You are adviced to start with the relatively small PTB dataset, and a small list of words, for example only the top 1000 most frequent words. If you get this working, you can scale up to the TedX and Wikipedia datasets, and to a list of the top 5,000 or 10,000 words, or even more. (The upper limit depends on your patience, the memory availlable on your laptop, and whether you are using a sparse datastructure). But you should already expect to get good performance in the 5,000-10,000 words range!
Step38:  (c) Plot the $PPMI$ matrix with plt.imshow. You can use the following template code. What do you notice about the matrix? (10 points)
Step39:  YOUR ANSWER HERE
Singular Value Decomposition
Now that we have the $PPMI$ co-occurence matrix, we are ready to compute its singular value decomposition (SVD). 
Definition
SVD is a very elegant linear algebra technique. It is defined as follows. Let $A \in \mathbb{R}^{m\times n}$, then the singular value decomposition of A is given by
$$A = U\Sigma V^{\top},$$
where
Step40:  Reducing the dimension
Now we can create the rank $k$ matrix $\tilde{U}$ by selection only the first $k$ columns of $U$. The value $k$ will be the embedding dimension of our word vectors. Now we have our word embeddings! They are the rows of $\tilde{U}$.
Step41:  When we look at the word embeddings we can see that, unlike the full $PMI$ matrix, the vectors in $\tilde{U}$ are dense
Step43:  Visualization with t-SNE
A simple and rewarding way to evaluate to the word embeddings is by visualizing them.
When visualizing the vectors, we ideally show them in their $k$-dimensional vector space, but that is impossible to do. To plot them we need to reduce their dimension much beyond $k$.
A very popular method for this is t-SNE. t-SNE is a very effective technique for dimensionality reduction that is particularly well suited for the visualization of high-dimensional datasets. What it does is find a lower dimensional surface on which to project the high-dimensional data in such a way that the local structure of the original data is preserved as much as possible in the projected data. In simple words
Step44:  (d) Use the function emb_scatter to plot the word-vector in $\tilde{U}$. You are adviced to plot only the first 500-1000 word-vectors to make the resulting plot not too cluttered. (10 points)
Now go find some interesting clusters!
<ASSISTANT_TASK:>
Python Code:
from collections import defaultdict, Counter
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
Explanation: Lab 4: Pointwise Mutual Information
This lab is about applications of Pointwise Mutual Information (PMI) in natural language processing.
Tasks
Find collocations with PMI.
Create dense vector representations for words (also known as word embeddings) by taking the singular value decomposition of a PMI co-occurence matrix.
Rules
The lab exercises should be made in groups of two people.
The deadline is Sunday 10 Dec 23:59.
The assignment should submitted to Blackboard as .ipynb. Only one submission per group.
The filename should be lab4_lastname1_lastname2.ipynb, so for example lab4_Levy_Goldberg.ipynb.
The notebook is graded on a scale of 0-100. The number of points for each question is indicated in parantheses. 
Notes on implementation:
You should write your code and answers in this iPython Notebook (see http://ipython.org/notebook.html for reference material). If you have problems, please contact your teaching assistant.
Use only one cell for code and one cell for markdown answers!    
Put all code in the cell with the # YOUR CODE HERE comment.
For theoretical question, put your solution in the YOUR ANSWER HERE cell.
Test your code and make sure we can run your notebook
End of explanation
class TextData:
    
    Stores text data with additional attributes.
    :param fname: a path to a txt file
    
    def __init__(self, fname):
        self._fname = fname
        self._data = []
        self._w2i = defaultdict(lambda: len(self._w2i))
        self._i2w = dict()
        self._counter = Counter()
        self._ntokens = 0    # number of tokens in dataset
        
        self._read()
        
    def _read(self):
        with open(self._fname, "r") as fh:
            for line in fh:
                tokens = line.strip().lower().split()
                self._data.append(tokens)
                self._counter.update(tokens)
        
        # Store number of tokens in the text
        self._ntokens = sum(self._counter.values())
        
        # Store the words in w2i in order of frequency from high to low
        for word, _ in self._counter.most_common(self._ntokens):
            self._i2w[self._w2i[word]] = word
        
    def __len__(self):
        
        Number of tokens in the dataset
        
        return self._ntokens
    
    @property
    def data(self):
        
        The data as list of lists
        
        return self._data
    
    @property
    def counter(self):
        
        The word-counts as counter
        
        return self._counter
    
    @property
    def vocab_size(self):
        
        Number of words in the dataset
        
        return len(self._w2i)
    
    @property
    def w2i(self):
        
        Word to index dictionary
        Words are sorted in order of frequency from high to low
        
        return self._w2i
    
    @property
    def i2w(self):
        
        Inverse dictionary of w2i: index to words
        
        return self._i2w
Explanation: PMI
Point-wise mutual information is a measure of association used in information theory and statistics. In the words of Jurafsky and Martin:
The point-wise mutual information is a measure of how often two events $x$ and $y$ occur, compared with what we would expect if they were independent.
It is formally defined as follows. Let $x$ and $y$ be outcomes of discrete random variables $X$ and $Y$. Then the point-wise mutual information between $x$ and $y$ is 
$$PMI(x,y) = \log\frac{p(x,y)}{p(x)p(y)}.$$
The values for $PMI$ range between minus and plus infinity. Large positive values indicate that $x$ and $y$ are strongly associated. A $PMI$ of zero means $x$ and $y$ are completely independent. And because of the logarithm, the values can also be negative, which indicates that $x$ and $y$ are co-occurring less often than we would expect by chance. Negative values tend to be unreliable though, often resulting from the lack of coocurence statistics for $x$ and $y$. A more robust measure therefore is a variant of $PMI$ called the $Positive$ $PMI$:
$$PPMI(x,y) = \max(0, PMI(x, y)).$$
In NLP applications, the $x$ and $y$ in the definition above are generally words, and the distributions based on their occurence in a text-corpus. Therefore from now on, let's refer to $x$ and $y$ as $w_i$ and $w_j$.
You can read more about $PMI$ and $PPMI$ in the following sources:
Jurafsky and Martin 15.2 is dedicated to $PMI$
The Wikipedia entry on PMI (it even has a language-related application of $PMI$)
Co-occurrence statistics
To compute the $PMI$ of two words $w_i$ and $w_j$ we need the probabilities $p(w_i)$, $p(w_j)$ and $p(w_i,w_j)$. What are they?
Unigram
The probabilites $p(w_i)$ and $p(w_j)$ are the probabilities of the words occuring by themselves in the corpus: they are the unigram probabilities of $w_i$ and $w_j$. We have seen before how to get these.
Skip-gram
The probability $p(w_i, w_j)$ is the probability of $w_i$ and $w_j$ co-occuring together in the corpus. Co-occurrence is often modelled with a skip-gram model. A skip-gram collects the co-occurence statistics of a word with the words that surround it within some fixed context window, to the left of the word, and to the right of the word. 
Consider the following fragment of a sentence in which a context window of 3 words around the word fox are shown:
... the quick brown fox jumped over the ...
The skipgram counts that we then extract from this fragment are 
$$C(quick, fox) = C(brown, fox)= C(jumped, fox) = C(over, fox) = 1,$$
and 
$$C(the, fox) = 2.$$
After all theses counts have been collected, we normalize and divide, giving probabilities $p(quick, fox), p(brown, fox)$ etc. such that
$$\sum_{{w,v}} p(w,v) = 1.$$
[Note] The word-pairs ${w,v}$ are unordered. So $p(quick, fox) = p(fox, quick)$.
We have provided you below with all the code nessecary to obtain these distributions. Read this through, and pay some attention to the methods that they are provided with. These will be usefull in some of the questions.
Read in data
As always, we will obtain the distributions from a large text corpus. To read in such a text we provide you with the following class:
End of explanation
class Unigram:
    
    A unigram language model
    
    def __init__(self, data):
        self._data = data
        self._unigram_counts = defaultdict(int)
        self._unigram_probs = defaultdict(float)
        self._unigram_counter = Counter()
        self._unigram_distribution = Counter()
        self._train()
        
    def _train(self):
        
        Trains the model trained on data
        
        # Get the word counts
        for sent in self._data:
            for word in sent:
                self._unigram_counts[word] += 1
            
        # Normalize the word counts
        s = sum(self._unigram_counts.values())
        for word_pair, count in self._unigram_counts.items():
            self._unigram_probs[word_pair] = count / s
        
        # There are some advantages to additionally use a Counter
        self._unigram_counter = Counter(self._unigram_counts)
        self._unigram_distribution = Counter(self._unigram_probs)
        
    def prob(self, w):
        
        Returns the unigram probability p(w)
        
        return self._unigram_probs[w]
    
        
    def count(self, w):
        
        Returns the unigram count c(w)
        
        return self._unigram_counts[w]
    
    @property
    def data(self):
        
        Returns the data
        
        return self._data
    @property
    def counter(self):
        
        Returns the unigram counts as Counter
        
        return self._unigram_counter
    
    @property
    def distribution(self):
        
        Returns the unigram distribution as Counter
        
        return self._unigram_distribution
    
    
class Skipgram:
    
    A skip-gram language model
    Note: p(w,v) = p(v,w)
    
    def __init__(self, data, context_window=5):
        self._data = data
        self._context_window = context_window
        self._skipgram_counts = defaultdict(int)
        self._skipgram_probs = defaultdict(float)
        self._skipgram_counter = Counter()
        self._skipgram_distribution = Counter()
        self._train()
        
    def _train(self):
        
        Trains the model
        
        # Get the co-occurrence counts
        for sent in self._data:
            for i in range(self._context_window, len(sent) - self._context_window):
                context = [sent[i - j] for j in range(1, self._context_window + 1)] + \
                          [sent[i + j] for j in range(1, self._context_window + 1)]    
                w = sent[i]
                for v in context:
                    word_pair = tuple(sorted([w, v])) # causes p(w,v) = p(v,w)
                    self._skipgram_counts[word_pair] += 1
            
        # Turn the co-occurrence counts into probabilities
        s = sum(self._skipgram_counts.values())
        for word_pair, count in self._skipgram_counts.items():
            self._skipgram_probs[word_pair] = count / s
        
        # There are some advantages to additionally use a Counter
        self._skipgram_counter = Counter(self._skipgram_counts)
        self._skipgram_distribution = Counter(self._skipgram_probs)
        
    def prob(self, w, v):
        
        Returns the skip-gram probability
        Note: p(w,v) = p(v,w)
        
        word_pair = tuple(sorted([w,v]))
        
        return self._skipgram_probs[word_pair]
    
    def count(self, w, v):
        
        Returns the skip-gram counts count(w,v) = count(v,w)
        
        word_pair = tuple(sorted([w,v]))
        
        return self._skipgram_counts[word_pair]
    
    @property
    def data(self):
        
        Returns the data
        
        return self._data
    
    @property
    def context_window(self):
        
        Returns the context window size
        
        return self._context_window
    
    @property
    def counter(self):
        
        Returns the skipgram counte as Counter,
        so that we can use the method most_common.
        
        return self._skipgram_counter
    
    @property
    def distribution(self):
        
        Returns the skipgram probs as Counter,
        so that we can use the method most_common.
        
        return self._skipgram_distribution
            
Explanation: Unigram and Skipgram
To train unigram and skipgram language models, you can use the following code.
End of explanation
%time ptb = TextData("ptb.txt")
print("Number of tokens: ", len(ptb))
print("Vocabulary size: ", ptb.vocab_size)
%time ptb_skipgram = Skipgram(ptb.data)
%time ptb_unigram = Unigram(ptb.data)
Explanation: Text corpora
We have the following text corpora availlable for you:
* A fragment of the Penn Treebank with around 900.000 tokens
* A collection of TedX talks with around 5 million tokens
* A collection of Wikipedia entries, contained around 83 million tokens
The Penn Treebank:
End of explanation
%time ted = TextData("ted.txt")
print("Number of tokens: ", len(ted))
print("Vocabulary size: ", ted.vocab_size)
%time ted_skipgram = Skipgram(ted.data)
%time ted_unigram = Unigram(ted.data)
Explanation: The TedX talks:
End of explanation
%time wiki = TextData("wiki.txt")
print("Number of tokens: ", len(wiki))
print("Vocabulary size: ", wiki.vocab_size)
%time wiki_skipgram = Skipgram(wiki.data)
%time wiki_unigram = Unigram(wiki.data)
Explanation: The collection of Wikipedia entries: (This will take some time. Expect around 15 mins for the skipgram model.)
End of explanation
def PPMI(unigram, skipgram, x, y):
    
    Returns the positive PMI of x and y
    
        PPMI(x, y) = max(0, PMI(x, y))
        
    where PMI(x,y) is computed using the 
    unigram and skipgram language model
        
        PMI(x,y) = log [p(x,y) / p(x)p(y)]
        
    :param unigram: an instance of Unigram
    :param skipgram: an instance of Skipgram
    :returns ppmi: a float between 0 and +inf
    
    ### YOUR CODE HERE
    return ppmi
Explanation: 1. Collocations with PPMI (40 points)
$PPMI$ can be used to find collocations; words that co-occur significantly more often than can be atrributed to chance. $PPMI$ is a natural measure for this task: the collocations are precisely the word-pairs $w_i$ and $w_j$ for which $PPMI(w_i,w_j)$ is high!
Have a look at the bottom of the PMI wikipedia entry: there it lists a number of such collocations found with $PMI$.
You will try to find collocations in the text-data that we've provided you with. First, you will need a function that computes the $PPMI$ given a $p(x)$, $p(y)$ and $p(x,y)$.
(a) Complete the function PPMI below. (20 points)
End of explanation
### YOUR CODE HERE
Explanation: PTB
(a) Use the function you wrote to find collocations in the Penn Treebank dataset. Recall: these are word-pairs in the corpus that have a high $PPMI$. Print a list of at most 30 of word-pairs (and they don't all have to make total sense!).  (5 points)
[Hint] You might find that highest $PPMI$ word-pairs are not really what you are looking for. They make no sense as collocations, for example due to noise arrising from insufficient statistics. In that case you should search a little bit further down the line, with words that have a little lower $PPMI$. Note for example that the collocations in the PMI wikipedia entry have PMI's between 8 and 11.
End of explanation
### YOUR CODE HERE
Explanation: TedX
(b) Use the function you wrote to find collocations in the TedX dataset. (5 points)
End of explanation
### YOUR CODE HERE
Explanation: Wikipedia
(c) Find collocations in the Wikipedia dataset. (5 points)
End of explanation
# extend this list as you like
wiki_collocations = [("puerto", "rico"), ("los", "angeles"), ("hong", "kong"), ("carbon", "dioxide"),
                     ("star", "trek"), ("star", "wars"), ("nobel", "prize"), ("prize", "laureate"), 
                     ("donald", "knuth"), ("discrete", "mathematics"), ("the", "and"), ("of", "it")] 
print("{}{}{}".format("word 1".ljust(15), "word 2".ljust(15), "PMI"))
print("-----------------------------------------------")
for (w, v) in wiki_collocations:
    print("{}{}{}".format(w.ljust(15), v.ljust(15), PPMI(wiki_unigram, wiki_skipgram, w, v)))
Explanation: [Optional] Use the following template to query the model for PMI values for word-pairs. In particular, it is interesting to see what PMI our model assigns to the collocations in the PMI wikipedia entry:
End of explanation
### YOUR CODE HERE
Explanation: (d) Now that you have (hopefully) been succesful at finding some collocations, take a moment to compare the lists of word-pairs from above, for which $PPMI(w_i,w_j)$ is high, with the list of word-pairs for which $p(w_i,w_j)$ is high. (5 points)
That means: 
* Print out a list of word-pairs for which $p(w_i,w_j)$ is high (the top 30 will suffice, for the corpus of your choice). 
* What difference do you see? Is the list of top $p(w_i,w_j)$ word-pairs as useful as the list of top $PPMI(w_i,w_j)$ word-pairs?
End of explanation
def make_ppmi_matrix(words, unigram, skipgram):
    
    Constructs a PPMI matrix of with the words
    in words.
    :param words: the list of words (not indices!) for which the PPMI
                  values will be stored in the matrix
    :param unigram: an instance of Unigram
    :param skipgram: an instance of Skipgram
    :returns P: a numpy array such that P[i,j] = PPMI[words[i], words[j]]
    
    ### YOUR CODE HERE
    return P
Explanation: YOUR ANSWER HERE
2. Word-embeddings via PMI-SVD (60 points)
Inspired by this blog-post we consider a classic method to obtain word embeddings that combines $PMI$ with linear algebra.
Go ahead and read the post, it's an easy and quick read.
PPMI matrix
(a) The first step is to make a PPMI matrix $P$. This matrix will have entries
$$(P)_{ij} = PPMI(w_i, w_j)$$
Where $w_i$ and $w_j$ are the $i$-th and $j$-th words in our w2i dictionary. Finish the function make_ppmi_matrix. (20 points)
[Note] If you really want to scale up (more about that below), you can consider writing a second version of the function that uses a sparse matrix datastructe for the $PMI$ matrix. Most of the entries in it will be zero. Scipy sparse has a number of options. (You will not be able to plot this matrix with imshow though, like we will do a in a bit).
End of explanation
### YOUR CODE HERE
Explanation: (b) Use the function you wrote above to construct the $PPMI$ matrix for a corpus of your choice. (10 points)
[Note] You are adviced to start with the relatively small PTB dataset, and a small list of words, for example only the top 1000 most frequent words. If you get this working, you can scale up to the TedX and Wikipedia datasets, and to a list of the top 5,000 or 10,000 words, or even more. (The upper limit depends on your patience, the memory availlable on your laptop, and whether you are using a sparse datastructure). But you should already expect to get good performance in the 5,000-10,000 words range!
End of explanation
# ppmi_matrix = ...
# The whole PPMI matrix
ax, fig = plt.subplots(figsize=(10,10))
plt.imshow(ppmi_matrix)
plt.colorbar()
plt.show()
# Only the top-left corner (which hold the most frequent words)
ax, fig = plt.subplots(figsize=(10,10))
plt.imshow(ppmi_matrix[0:300, 0:300])
plt.colorbar()
plt.show()
Explanation: (c) Plot the $PPMI$ matrix with plt.imshow. You can use the following template code. What do you notice about the matrix? (10 points)
End of explanation
from scipy.linalg import svd
%time U, s, Vt = svd(wiki_ppmi_matrix)
Explanation: YOUR ANSWER HERE
Singular Value Decomposition
Now that we have the $PPMI$ co-occurence matrix, we are ready to compute its singular value decomposition (SVD). 
Definition
SVD is a very elegant linear algebra technique. It is defined as follows. Let $A \in \mathbb{R}^{m\times n}$, then the singular value decomposition of A is given by
$$A = U\Sigma V^{\top},$$
where:
$U$ is an $m \times m$ unitary matrix.
A real-valued matrix $U$ is called unitary when $U^{\top}U = UU^{\top} = I$. In other words: $U$ forms an orthonormal basis for $\mathbb{R}^{m}$.
$\Sigma$ is a diagonal $m \times n$ matrix with non-negative real numbers.
The diagonal values are the so called singular values $\sigma_1, \sigma_2,\dots,\sigma_n$ (supposing $n \leq m$). The convention is that in the matrix $\Sigma$ these are ordered from large to small: $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_n \geq 0$. 
$V$ is an $n \times n$ unitary matrix (and $V^{\top}$ its transpose)
Low-rank approximation
When we select only the first $k$ collums of $U$ and $V$ and the first $k$ singular values in $\Sigma$ we get 
* $\tilde{U} \in \mathbb{R}^{m \times k}$
* $\tilde{\Sigma} \in \mathbb{R}^{k \times k}$
* $\tilde{V} \in \mathbb{R}^{n \times k}.$
The reduced matrices can be used to make a rank $k$ matrix $\tilde{A} \in \mathbb{R}^{m\times n}$. The matrix $\tilde{A}$ is an approximation of the matrix $A$:
$$A \approx \tilde{U}\tilde{\Sigma} \tilde{V}^{\top} = \tilde{A}.$$
Moreover, this approximation is the 'best' approximation of $A$ in the sense that in minimizes the distance to $A$ in a type of matrix norm called the Frobenius norm:
$$\tilde{A} = \arg \min_{A'} || A - A'||_{F}$$
You can learn more about SVD from these sources:
Jurafksy and Martin 16.1 (3rd edition)
The Wikipedia page (with a very good visual illustration)
Or this long but good blog-post series (if you have some time!)
For the purposes of this tutorial, however, all we need to know to get our embeddings is how to use SVD in python. And that is straightforward:
End of explanation
k = 300
U_tilde = U[:,:k]
Explanation: Reducing the dimension
Now we can create the rank $k$ matrix $\tilde{U}$ by selection only the first $k$ columns of $U$. The value $k$ will be the embedding dimension of our word vectors. Now we have our word embeddings! They are the rows of $\tilde{U}$.
End of explanation
ax, fig = plt.subplots(figsize=(15,15))
plt.imshow(U_tilde[:800])
plt.colorbar()
plt.show()
Explanation: When we look at the word embeddings we can see that, unlike the full $PMI$ matrix, the vectors in $\tilde{U}$ are dense: almost all values non-zero.
End of explanation
from sklearn.cluster import KMeans
from sklearn.manifold import TSNE
from bokeh.models import ColumnDataSource, LabelSet
from bokeh.plotting import figure, show, output_file
from bokeh.palettes import d3
from bokeh.io import output_notebook
output_notebook()
def emb_scatter(data, names, perplexity=30.0, N=20):
    
    Uses t-SNE with given perplexity to reduce the dimension of the 
    vectors in data to 2, plots these in a bokeh 2d scatter plot, 
    and colors them with N colors using K-means clustering of the 
    originial vectors. The colored dots are tagged with labels from
    the list names.
    
    :param data: numpy array of shape [num_vectors, embedding_dim]
    :param names: a list of words of length num_vectors in the same order as data
    :param perplexity: the perplexity for t-SNE
    :param N: the number of clusters to find by K-means
    
    ## Try to find some clusters ##
    print("Finding clusters")
    kmeans = KMeans(n_clusters=N)
    kmeans.fit(data)
    klabels = kmeans.labels_
    ## Get a tsne fit ##
    print("Fitting tsne")
    tsne = TSNE(n_components=2, perplexity=perplexity)
    emb_tsne = tsne.fit_transform(data)
    
    ## Plot the tsne of the embeddings with bokeh ##
    # source: https://github.com/oxford-cs-deepnlp-2017/practical-1
    p = figure(tools="pan,wheel_zoom,reset,save",
               toolbar_location="above",
               title="T-SNE for most common words")
    # Set colormap as a list
    colormap = d3['Category20'][N]
    colors = [colormap[i] for i in klabels]
    source = ColumnDataSource(data=dict(x1=emb_tsne[:,0],
                                        x2=emb_tsne[:,1],
                                        names=names,
                                        colors=colors))
    p.scatter(x="x1", y="x2", size=8, source=source, color='colors')
    labels = LabelSet(x="x1", y="x2", text="names", y_offset=6,
                      text_font_size="8pt", text_color="#555555",
                      source=source, text_align='center')
    p.add_layout(labels)
    show(p)
Explanation: Visualization with t-SNE
A simple and rewarding way to evaluate to the word embeddings is by visualizing them.
When visualizing the vectors, we ideally show them in their $k$-dimensional vector space, but that is impossible to do. To plot them we need to reduce their dimension much beyond $k$.
A very popular method for this is t-SNE. t-SNE is a very effective technique for dimensionality reduction that is particularly well suited for the visualization of high-dimensional datasets. What it does is find a lower dimensional surface on which to project the high-dimensional data in such a way that the local structure of the original data is preserved as much as possible in the projected data. In simple words: data-points that are close to each other in the original space end up close to each other in the projected space. (Note: this does not hold large distances! Points that are far apart in the original space do not necessarily end up far apart in the projected space.) 
So, t-SNE is like Principal Component Analysis (PCA), another popular dimensionality reduction technique. But, due to the non-linear nature of the surface it finds (the 'manifold') t-SNE has more flexibility.
If you want to know more about t-SNE you can read the following sources:
* How to Use t-SNE Effectively on Distill discusses, among others, the effects of the perplexity parameter in t-SNE
* This Scikit-learn example
The code plots below uses t-SNE to make a two-dimensional plot with our word-embeddings. We also throw in some K-means clustering in the original high-dimensional space so that we can color our dimension-reduced word-embeddings. This gives us some for additional interpretative abilities.
End of explanation
### YOUR CODE HERE
Explanation: (d) Use the function emb_scatter to plot the word-vector in $\tilde{U}$. You are adviced to plot only the first 500-1000 word-vectors to make the resulting plot not too cluttered. (10 points)
Now go find some interesting clusters!
End of explanation
<END_TASK>