<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 1
Step1:  YOUR ANSWER HERE
For the rest of this exercise you should use the original orthography of the data when answering the questions.
(b) Plot a graph of word frequency versus rank of a word, in this corpus. Does this corpus obey Zipf’s law?
Step2:  (c) What are the 20 most common words in the corpus and how often do they occur? What is the 50th most common word, the 100th and the 1000th and how often do they occur?
Step3:  (d) How many different Part-of-speech tags are present in the corpus?
Step4:  (e) Print a list of the 10 most commonly occurring POS tags in the data. For each of these POS tags, what are the 3 most common words that belong to that class?
Step5:  (f) A single word may have several POS-tags. For example, record can be a both a noun (buy a record) or a verb (record a lecture). This make POS-tags extremely useful for disambiguation.
What percentage of the words in the vocabulary is ambiguous? (i.e. have more than one POS tag?) What are the 10 most frequent combinations of POS tags in the case of ambitguity? Which words are most ambiguous? Give some of them.
Step6:  (g)  Print some of these words with their multiple POS-tags. Do you understand the ambiguity? Use figure 10.1 mentioned above to interpret the POS-tags.
Step7:  (h) Ambiguous words do not account for a great percentage of the vocabulary. Yet they are among the most commonly occuring words of the English language. What percentage of the dataset is ambiguous?
Step8:  Exercise 1.2 (10 points, 5 per subquestion)
You are also provided with another file called sec00.gold.tagged. 
Section 00 of the Penn Treebank is typically used as development data.
(a) How many unseen words are present in the development data (i.e., words that have not occurred in the training data)?
Step9:  (b) What are the three POS tag categories that the most unseen words belong to?
Step10:  2. Language Models
This part of the lab will be covered in the Wednesday lecture. If you have prior exposure to NLP, go ahead and finish this part! If you don't, start anyway, and this part will be clear after the lecture. 
Reference chapter 4 of J&M Language Modeling with N-Grams. 
Models that assign probabilities to sequences of words are called language language
modelels or LMs. The simplest model that assigns probabilities to sentences and sequences of words is the N-gram model.
Recall that an N-gram language model uses conditional probabilities of the form
$$P(w_k \mid w_{k-N+1} \dots w_{k-1})$$
to approximate the full joint probability
$$P(w_1 \dots w_n)$$
of a sequence of words $w_1 \dots w_n$.
The easiest way of obtaining estimates for the probabilities $P(w_k \mid w_{k-N+1} \dots w_{k-1})$ is to use the maximum likelihood estimate or MLE, a widely used statistical estimation method (read more. You count and normalize
Step11:  Compare that to an ordinary dictionary
Step12:  Other datatypes as default_factory
Step13:  Converting an already existing dict
Step14:  This doesn't work
Step15:  Use a lambda to make the number 10 callable"
Step18:  Clever use of a defaultdict can be the solution to the problem of data-storing in a smoothing $N$-gram pointed out above
Step19:  Exercise 2.2 (5 points)
You can use an N-gram language model to generate text. The higher the order N the better your model will be able to catch the long-range dependecies that occur in actual sentences and the better your changes are at generating sensible text. But beware
Step20:  Inverse transform sampling in the words of Jurafsky and Martin
Step21:  [Optional]
For how many of the histories $w_{k-N+1}\dots w_{k-1}$ is the number of continuations $w_n$ equal to one? Calculate the percentage of such cases for the different orders N.
And which history has the most possible continuations?
Step22:  Excercise 2.3 (5 points)
Let $V$ denote our vocabulary. Recall that for any $w$ in $V$ bigram[w] defines a conditional probability $p(v|w)$ over $v$ in $V$. In the case of an unsmoothed bigram, $p(v|w) = 0$ for most $v\in V$, whereas in the smoothed bigram smoothing took care that $p(v|w) \geq 0$ for all $v$.
The function plot_bigram_dist(word, bigram, smoothbigram, k=30) plots shows $p(v|word)$ for the k words $v$. One bar shows the probabilities in bigram and one in smoothbigram. 
(a) Use this function to plot the distribution for at least two words w and answer the questions
* What is the effect of smoothing on the bigram distribution of frequent words? 
* What is the effect in the case of infrequent words?
* Explain the difference between the two based on the raw counts of w 
(b) Now experiment with $k$ much smaller than 1 (but greater than 0!) 
* What are the effects?
[Hint] Remember that add-1 smoothing turns 
$$P(w_n\mid w_{n-1}) = \frac{C(w_{n-1}w_{n})}{C(w_{n-1})}$$
into
$$P_{add-1}(w_n\mid w_{n-1}) = \frac{C(w_{n-1}w_{n}) + 1}{C(w_{n-1}) + |V|}.$$
What happens when $C(w_{n-1})$ is relatively big (similiar in of size as $ |V| $)? And what if $C(w_{n-1})$ is small?
Step23:  YOUR ANSWERS HERE
Recall that if we have a sentence $w_1,\dots,w_n$ we can write
$$P(w_1\dots w_n) = P(w_1)P(w_2|w_1) \cdots P(w_i|w_1 \dots w_{n-1}) \approx P(w_1)P(w_2|w_1)\cdots P(w_{N-1}|w_1\dots w_{N-2})\prod_{i=N}^{n} P(w_i|w_{i-(N-1)}\dots w_{i-1})$$
where in the last step we make an $N$-gram approximation of the full conditionals.
For example, in the case of a bigram (N=2), the above expression reduces to
$$P(w_1 \dots w_n)\approx P(w_1)\prod_{i=2}^{n} P(w_i| w_{i-1}).$$
Exercise 2.4 (5 points)
The following sentences are taken from the training data. Use your unsmoothed unigram, bigram, and trigram language model to estimate their probabilities
Step24:  YOUR ANSWERS HERE
Exercise 2.5 (5 points)
The above sentences were taken from the training set, hence they will all have probability greater than 0. The big challenge for our language model are of course with sentence that contain unseen N-grams
Step25:  YOUR ANSWERS HERE
[Optional]
Optional What percentage of the sentences in the test set get assigned probability 0 under your smoothed and unsmoothed language models?
Step26:  Exercise 2.6 (5 points)
Perplexity is very frequently used metric for evaluating probabilistic models such as language models. The perplexity (sometimes called PP for short) of a language model on a sentence is the inverse probability of the sentence, normalized by the number of words
<ASSISTANT_TASK:>
Python Code:
## YOUR CODE HERE ##
Explanation: Lab 1: Text Corpora and Language Modelling
This lab is meant to help you get familiar with some language data, and use this data to estimate N-gram language models
First you will use the Penn Treebank, which is a collection of newspaper articles from the newspaper 
The Wall Street Journal. The idea is to examine the data and notice interesting properties. This will not take more than a few lines of code.
Then you will use a corpus consisting of TedX talks. This you will use to estimate an N-gram language model for different orders of N, and use this this for some tasks.
The datasets are on blackboard under course materials. Download the zip and make sure to put the files in the same directory as the notebook.
Rules
The lab exercises should be made in groups of two people.
The deadline is Tuesday 7 nov 16:59.
The assignment should submitted to Blackboard as .ipynb. Only one submission per group.
The filename should be lab1_lastname1_lastname2.ipynb, so for example lab1_Jurafsky_Martin.ipynb.
The notebook is graded on a scale of 0-10. The number of points for each question is indicated in parantheses. 
The questions marked optional are not graded; they are an additional challenge for those interested in going the extra mile. 
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
1. Penn treebank
Exercise 1.1 (40 points, 5 points per subquestion )
You are provided with a corpus containing words with their Part-of-Speech tags (POS-tags for short). The format is
word|POS (one sentence per line) and the file name is sec02-22.gold.tagged. This data is extracted from Sections 02-22 from the Penn Treebank: these sections are most commonly used for training statistical models like POS-taggers and parsers.
[Hint] Figure 10.1 in chapter 10 of Jurafsky and Martin (see here) holds a summary of the 45 POS-tags used in the Penn Treebank tagset together with their meaning and some examples. (If you are keen on learning more about the word-classes represented POS-tags and their definitions you can do a litle reading ahead for next week and already have a look at section 10.1 of the same chapter).
[Hint] the Python library collections has an object called Counter which will come in handy for this exercise.
(a) How large is the corpus? (i.e. how many tokens). And what is the size of the vocabulary used in this corpus? 
Estimate the vocabulary size both by lowercasing all the words as well as by leaving the words in their original orthography. What is an advantage of lowercasing all the words in your corpus? What is a notable downside? Give examples.
End of explanation
## YOUR CODE HERE ##
Explanation: YOUR ANSWER HERE
For the rest of this exercise you should use the original orthography of the data when answering the questions.
(b) Plot a graph of word frequency versus rank of a word, in this corpus. Does this corpus obey Zipf’s law?
End of explanation
## YOUR CODE HERE ##
Explanation: (c) What are the 20 most common words in the corpus and how often do they occur? What is the 50th most common word, the 100th and the 1000th and how often do they occur?
End of explanation
## YOUR CODE HERE ##
Explanation: (d) How many different Part-of-speech tags are present in the corpus?
End of explanation
## YOUR CODE HERE ##
Explanation: (e) Print a list of the 10 most commonly occurring POS tags in the data. For each of these POS tags, what are the 3 most common words that belong to that class?
End of explanation
## YOUR CODE HERE ##
Explanation: (f) A single word may have several POS-tags. For example, record can be a both a noun (buy a record) or a verb (record a lecture). This make POS-tags extremely useful for disambiguation.
What percentage of the words in the vocabulary is ambiguous? (i.e. have more than one POS tag?) What are the 10 most frequent combinations of POS tags in the case of ambitguity? Which words are most ambiguous? Give some of them.
End of explanation
## YOUR CODE HERE ##
Explanation: (g)  Print some of these words with their multiple POS-tags. Do you understand the ambiguity? Use figure 10.1 mentioned above to interpret the POS-tags.
End of explanation
## YOUR CODE HERE ##
Explanation: (h) Ambiguous words do not account for a great percentage of the vocabulary. Yet they are among the most commonly occuring words of the English language. What percentage of the dataset is ambiguous?
End of explanation
## YOUR CODE HERE ##
Explanation: Exercise 1.2 (10 points, 5 per subquestion)
You are also provided with another file called sec00.gold.tagged. 
Section 00 of the Penn Treebank is typically used as development data.
(a) How many unseen words are present in the development data (i.e., words that have not occurred in the training data)?
End of explanation
## YOUR CODE HERE ##
Explanation: (b) What are the three POS tag categories that the most unseen words belong to?
End of explanation
from collections import defaultdict
d = defaultdict(float)
d["new key"]
Explanation: 2. Language Models
This part of the lab will be covered in the Wednesday lecture. If you have prior exposure to NLP, go ahead and finish this part! If you don't, start anyway, and this part will be clear after the lecture. 
Reference chapter 4 of J&M Language Modeling with N-Grams. 
Models that assign probabilities to sequences of words are called language language
modelels or LMs. The simplest model that assigns probabilities to sentences and sequences of words is the N-gram model.
Recall that an N-gram language model uses conditional probabilities of the form
$$P(w_k \mid w_{k-N+1} \dots w_{k-1})$$
to approximate the full joint probability
$$P(w_1 \dots w_n)$$
of a sequence of words $w_1 \dots w_n$.
The easiest way of obtaining estimates for the probabilities $P(w_k \mid w_{k-N+1} \dots w_{k-1})$ is to use the maximum likelihood estimate or MLE, a widely used statistical estimation method (read more. You count and normalize:
$$P_{MLE}(w_k \mid w_{k-N+1} \dots w_{k-1}) = \frac{C(w_{k-N+1} \dots w_{k-1} w_k)}{C(w_{k-N+1} \dots w_{k-1})}.$$
Exercise 2.1 (25 points)
(a)  Complete the function train_ngram so that you can train a count-based $N$-gram language model on the data found in data/ted-train.txt and train this for $N=2,3,4$. 15 points
(b)  Extend the function above so that it accepts a parameter k for optional add-$k$ smoothing. 10 points
[Datastructure hint] If you store the smoothed language in a naive manner (that is, to store all the numbers separately) your datastructure will get huge! If $V$ is the vocabulary then the smoothed bigram model assigns probabilities to $|V|^2$ entries. If $|V|$ is around 80k, the naive way requires you to store more than 64 billion floats. Yet almost all of these are actually just $P(w_n|w_{n-1}) = \frac{k}{N + k|V|}$, with $k$ the value with which you smooth and $N=C(w_{n-1})$. Think about how you use this fact to make your model work in practice.
[Python hint] The collections library has another useful datastructure: the defaultdict. Some example uses:
End of explanation
d = dict()
d["new key"]
Explanation: Compare that to an ordinary dictionary:
End of explanation
d = defaultdict(int)
d["new key"]
d = defaultdict(list)
d["new key"]
Explanation: Other datatypes as default_factory:
End of explanation
d1 = {k: "value" for k in range(1, 11)}
d = defaultdict(float, d1) # convert it to a defaultdict
print(d[5])
print(d[100])
Explanation: Converting an already existing dict:
End of explanation
d = defaultdict(10)
Explanation: This doesn't work:
End of explanation
d = defaultdict(lambda: 10)
d["new key"]
d = defaultdict(lambda: defaultdict(float))
d["new key"]
Explanation: Use a lambda to make the number 10 callable":
End of explanation
train_file = "ted-train.txt"
def read(fname, max_lines=np.inf):
    
    Reads in the data in fname and returns it as
    one long list of words. Also returns a vocabulary in
    the form of a word2index and index2word dictionary.
    
    data = []
    # w2i will automatically keep a counter to asign to new words
    w2i = defaultdict(lambda: len(w2i))
    i2w = dict()
    start = "<s>"
    end = "</s>"
    
    with open(fname, "r") as fh:
        for k, line in enumerate(fh):
            if k > max_lines:
                break
            words = line.strip().split()
            # assign an index to each word
            for w in words:
                i2w[w2i[w]] = w # trick
            
            sent = [start] + words + [end]
            data.append(sent)
    return data, w2i, i2w
def train_ngram(data, N, k=0):
    
    Trains an n-gram language model with optional add-k smoothing
    and additionaly returns the unigram model
    
    :param data: text-data as returned by read
    :param N: (N>1) the order of the ngram e.g. N=2 gives a bigram
    :param k: optional add-k smoothing
    :returns: ngram and unigram
    
    ngram = defaultdict(Counter) # ngram[history][word] = #(history,word)
    unpacked_data = [word for sent in data for word in sent]
    unigram = defaultdict(float, Counter(unpacked_data)) # default prob is 0.0           
    ## YOUR CODE HERE ##
    
    return ngram, unigram
data, w2i, i2w = read(train_file)
# bigram, unigram = train_ngram(data, N=2, k=0)
# bigram_smoothed, unigram_smoothed = train_ngram(data, N=2, k=1)
data[2]
Explanation: Clever use of a defaultdict can be the solution to the problem of data-storing in a smoothing $N$-gram pointed out above:
ngram = defaultdict(lambda: k/(N+kV), ngram)
The following function is given:
End of explanation
from random import random
P = [0.2,0.5,0.2,0.1]
def sample(P):
    u = random() # uniformly random number between 0 and 1
    p = 0
    for i, p_i in enumerate(P):
        if p > u: 
            return i # the first i s.t. p1 + ... + pi > u
        p += p_i
        
print(sample(P))
print(Counter([sample(P) for i in range(1000)])) # check to see if the law of large numbers is still true
Explanation: Exercise 2.2 (5 points)
You can use an N-gram language model to generate text. The higher the order N the better your model will be able to catch the long-range dependecies that occur in actual sentences and the better your changes are at generating sensible text. But beware: sparsity of language data will quickly cause your model to reproduce entire lines from your training data; in such cases only one $w_k$ was observed for the histories $w_{k-N+1}\dots w_{k-1}$ in the entire training-set.
Complete the function generate_sent. It takes a language model lm and an order N and should generate a sentence by sampling from the language model.
[Hint] You can use the method of inverse transform sampling to generate a sample from a categorical distribution, $p_1\dots p_k$ such that $p_i \geq 0$ and $\sum_{i=1}^k p_i = 1$, as follows:
End of explanation
def generate_sent(lm, N):
    ## YOUR CODE HERE ##
    raise NotImplementedError
Explanation: Inverse transform sampling in the words of Jurafsky and Martin:
Imagine all the words of the English language covering the probability space
between 0 and 1, each word covering an interval proportional to its frequency. We
choose a random value between 0 and 1 and print the word whose interval includes
this chosen value.
(J&M, section 4.3)
End of explanation
### ANSWER ###
Explanation: [Optional]
For how many of the histories $w_{k-N+1}\dots w_{k-1}$ is the number of continuations $w_n$ equal to one? Calculate the percentage of such cases for the different orders N.
And which history has the most possible continuations?
End of explanation
import pandas as pd
import seaborn as sns    
def plot_bigram_dist(word, bigram, smoothbigram, k=30):
    d = bigram[word]
    ds = smoothbigram[word]
    
    # sort the probabilities
    d_sort = sorted(d.items(), reverse=True, key=lambda t: t[1])[0:k]
    ds_sort = sorted(ds.items(), reverse=True, key=lambda t: t[1])[0:k]
    
    _, probs = zip(*d_sort)
    smooth_ws, smooth_probs = zip(*ds_sort)
    
    # make up for the fact that in the unsmoothed case  probs is generally less than k long
    probs = probs + (0,) * (k-len(probs)) 
    w_data = pd.DataFrame({"w": smooth_ws * 2,
                           "P({}|w)".format(word): probs + smooth_probs,
                           "smoothing": ["unsmoothed"]*k + ["smoothed"]*k})
    
    fig, ax = plt.subplots(figsize=(10,10))
    plt.xticks(rotation=90)
    g = sns.barplot(ax=ax, x="w", y="P({}|w)".format(word), hue="smoothing",
                    data=w_data, palette="Blues_d")    
## YOUR CODE HERE ##
Explanation: Excercise 2.3 (5 points)
Let $V$ denote our vocabulary. Recall that for any $w$ in $V$ bigram[w] defines a conditional probability $p(v|w)$ over $v$ in $V$. In the case of an unsmoothed bigram, $p(v|w) = 0$ for most $v\in V$, whereas in the smoothed bigram smoothing took care that $p(v|w) \geq 0$ for all $v$.
The function plot_bigram_dist(word, bigram, smoothbigram, k=30) plots shows $p(v|word)$ for the k words $v$. One bar shows the probabilities in bigram and one in smoothbigram. 
(a) Use this function to plot the distribution for at least two words w and answer the questions
* What is the effect of smoothing on the bigram distribution of frequent words? 
* What is the effect in the case of infrequent words?
* Explain the difference between the two based on the raw counts of w 
(b) Now experiment with $k$ much smaller than 1 (but greater than 0!) 
* What are the effects?
[Hint] Remember that add-1 smoothing turns 
$$P(w_n\mid w_{n-1}) = \frac{C(w_{n-1}w_{n})}{C(w_{n-1})}$$
into
$$P_{add-1}(w_n\mid w_{n-1}) = \frac{C(w_{n-1}w_{n}) + 1}{C(w_{n-1}) + |V|}.$$
What happens when $C(w_{n-1})$ is relatively big (similiar in of size as $ |V| $)? And what if $C(w_{n-1})$ is small?
End of explanation
## YOUR CODE HERE ##
Explanation: YOUR ANSWERS HERE
Recall that if we have a sentence $w_1,\dots,w_n$ we can write
$$P(w_1\dots w_n) = P(w_1)P(w_2|w_1) \cdots P(w_i|w_1 \dots w_{n-1}) \approx P(w_1)P(w_2|w_1)\cdots P(w_{N-1}|w_1\dots w_{N-2})\prod_{i=N}^{n} P(w_i|w_{i-(N-1)}\dots w_{i-1})$$
where in the last step we make an $N$-gram approximation of the full conditionals.
For example, in the case of a bigram (N=2), the above expression reduces to
$$P(w_1 \dots w_n)\approx P(w_1)\prod_{i=2}^{n} P(w_i| w_{i-1}).$$
Exercise 2.4 (5 points)
The following sentences are taken from the training data. Use your unsmoothed unigram, bigram, and trigram language model to estimate their probabilities:
1. Every day was about creating something new .
2. In this machine , a beam of protons and anti-protons are accelerated to near the speed of light and brought 
   together in a collision , producing a burst of pure energy .
Repeat this with the smoothed (add-1) versions of the N-grams. What is the effect of smoothing on the probabilities?
End of explanation
### YOUR CODE HERE ###
Explanation: YOUR ANSWERS HERE
Exercise 2.5 (5 points)
The above sentences were taken from the training set, hence they will all have probability greater than 0. The big challenge for our language model are of course with sentence that contain unseen N-grams: if such an N-gram occurs our model immediately assigns the sentence probability zero.
The following three senteces are taken from the test set availlable in the file ted-test.txt. What probabilities do your smoothed and unsmoothed language models asign in this case?
1. Because these robots are really safe .
2. We have sheer nothingness on one side , and we have this vision of a reality that encompasses every 
   conceivable world at the other extreme : the fullest possible reality , nothingness , the simplest possible 
   reality .
End of explanation
### ANSWER HERE ###
Explanation: YOUR ANSWERS HERE
[Optional]
Optional What percentage of the sentences in the test set get assigned probability 0 under your smoothed and unsmoothed language models?
End of explanation
### YOUR CODE HERE ###
Explanation: Exercise 2.6 (5 points)
Perplexity is very frequently used metric for evaluating probabilistic models such as language models. The perplexity (sometimes called PP for short) of a language model on a sentence is the inverse probability of the sentence, normalized by the number of words:
$$PP(w_1 \dots w_n) = P(w_1\dots w_n)^{-\frac{1}{n}}.$$
Here we can again approximate $P(w_1 \dots w_n)$ with N-gram probabilities, as above.
Note: $(x_1\cdots x_n)^{-\frac{1}{n}}$ is the geometric mean of the numbers $x_1,\dots,x_n$. It is like the (regular) artithmetic mean, but with products instead of sums. The geometric mean is a more natural choice in the case of PP because behind $P(w_1\dots w_n)$ is a series of $n$ products (more here).
Compute the perplexity of the training sentences from excercise 2.1. What big difference between the probabilities of the sentences and the perplexities of the sentences do you notice?
End of explanation
<END_TASK>