Name: [Solved] Character-based Language Models : Assignment 5
Brand: Assignment Chef
SKU: [Solved] Character-based Language Models : Assignment 5
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

In the textbook, language modeling was defined as the task of predicting the next word in a sequence given the previous words. In this assignment, we will focus on the related problem of predicting the next character in a sequence given the previous characters.

The learning goals of this assignment are to:

Understand how to compute language model probabilities using maximum likelihood estimation
Implement basic smoothing, back-off and interpolation.
Have fun using a language model to probabilistically generate texts.
Use a set of language models to perform text classification.

Part 1: Unsmoothed Maximum Likelihood Character-Level Language Models

Were going to be starting with some nice, compact code for character-level language models. that was written by Yoav Goldberg. Below is Yoavs code for training a language model.

Train a language model

Note: we provide you this code in the Python stub file.

def train_char_lm(fname, order=4, add_k=1):  ''' Trains a language model.  This code was borrowed from   http://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139  Inputs:    fname: Path to a text corpus.    order: The length of the n-grams.    add_k: k value for add-k smoothing. NOT YET IMPLMENTED  Returns:    A dictionary mapping from n-grams of length n to a list of tuples.    Each tuple consists of a possible net character and its probability.  '''  # TODO: Add your implementation of add-k smoothing.  data = open(fname).read()  lm = defaultdict(Counter)  pad = "~" * order  data = pad + data  for i in range(len(data)-order):    history, char = data[i:i+order], data[i+order]    lm[history][char]+=1  def normalize(counter):    s = float(sum(counter.values()))    return [(c,cnt/s) for c,cnt in counter.items()]  outlm = {hist:normalize(chars) for hist, chars in lm.items()}  return outlm

fname is a file to read the characters from. order is the history size to consult. Note that we pad the data with leading ~ so that we also learn how to start.

Now you can train a language model. First grab some text like this corpus of Shakespeare:

Now train the model:

lm = train_char_lm("shakespeare_input.txt", order=4)

P(hello world)

Ok. Now we can look-up the probability of the next letter given some history. Here are some example queries:

>>> lm['hell'][('!', 0.06912442396313365), (' ', 0.22119815668202766), ("'", 0.018433179723502304), ('i', 0.03225806451612903), ('
', 0.018433179723502304), ('-', 0.059907834101382486), (',', 0.20276497695852536), ('o', 0.15668202764976957), ('.', 0.1336405529953917), ('s', 0.009216589861751152), (';', 0.027649769585253458), (':', 0.018433179723502304), ('?', 0.03225806451612903)]

Actually, lets pretty print the output, and sort the letters based on their probabilities.

import pprintimport operatordef print_probs(lm, history):    probs = sorted(lm[history],key=lambda x:(-x[1],x[0]))    pp = pprint.PrettyPrinter()    pp.pprint(probs)

OK, print again:

>>> print_probs(lm, "hell")[(' ', 0.22119815668202766), (',', 0.20276497695852536), ('o', 0.15668202764976957), ('.', 0.1336405529953917), ('!', 0.06912442396313365), ('-', 0.059907834101382486), ('?', 0.03225806451612903), ('i', 0.03225806451612903), (';', 0.027649769585253458), ('
', 0.018433179723502304), ("'", 0.018433179723502304), (':', 0.018433179723502304), ('s', 0.009216589861751152)]

This means that hell can be followed by any of these dozen characters:

,o.!-?i; ':s

and that the probability of o given hell is 15.7%, $p (o ∣ h e l l) = 0.157$ . The most probable character to see after hell is a space, $p (o ∣ h e l l) = 0.221$ .

The distribution of letters that occur after worl is different than the distribution of letters that occur after hell. Here is that distribution:

>>> print_probs(lm, "worl")[('d', 1.0)]

What does that mean? It means that in our corpus, the only possible continuation that we observed for worl was the letter d, and we assign 100% of probability mass to it, $p (d ∣ w o r l) = 1.0$ .

Lets write some Shakespeare!

Generating text with the model is simple. To generate a letter, we will look up the last n characters, and then sample a random letter based on the probability distribution for those letters. Heres Yoavs code for that:

def generate_letter(lm, history, order):  ''' Randomly chooses the next letter using the language model.    Inputs:    lm: The output from calling train_char_lm.    history: A sequence of text at least 'order' long.    order: The length of the n-grams in the language model.      Returns:     A letter  '''    history = history[-order:]  dist = lm[history]  x = random()  for c,v in dist:    x = x - v    if x <= 0: return c

To generate a passage of text, we just seed it with the initial history and run letter generation in a loop, updating the history at each turn. Well stop generating after a specified number of letters.

def generate_text(lm, order, nletters=500):  '''Generates a bunch of random text based on the language model.    Inputs:  lm: The output from calling train_char_lm.  order: The length of the n-grams in the language model.  nletters: the number of characters worth of text to generate    Returns:     A letter    '''  history = "~" * order  out = []  for i in range(nletters):    c = generate_letter(lm, history, order)    history = history[-order:] + c    out.append(c)  return "".join(out)

Now, try generating some Shakespeare with different order n-gram models. You should try running the following commands.

>>> lm = train_char_lm("shakespeare_input.txt", order=2)>>> print(generate_text(lm, 2))>>> lm = train_char_lm("shakespeare_input.txt", order=3)>>> print(generate_text(lm, 3))>>> lm = train_char_lm("shakespeare_input.txt", order=4)>>> print(generate_text(lm, 4))>>> lm = train_char_lm("shakespeare_input.txt", order=7)>>> print(generate_text(lm, 7))

What do you think? Is it as good as 1000 monkeys working at 1000 typewriters?

What the F?

Try generating a bunch of short passages:

>>> print(generate_text(lm, 5, 40))First, and quenceShall we gave it. Now>>> print(generate_text(lm, 5, 40))First die.KING OF FRANCE:I prithee, >>> print(generate_text(lm, 5, 40))First marriage,And scarce it: wretches >>> print(generate_text(lm, 5, 40))First, the midsummer;We make us allia s>>> print(generate_text(lm, 5, 40))First chooseWhich now,Where like thee.>>> lm = train_char_lm("shakespeare_input.txt", order=4)>>> print(generate_text(lm, 4, 40))First bloodassuranceTo grace and leade>>> print(generate_text(lm, 4, 40))First, are almightly,Am I to bedew the >>> print(generate_text(lm, 4, 40))First Senato, come unexamination hast br>>> lm = train_char_lm("shakespeare_input.txt", order=2)>>> print(generate_text(lm, 2, 40))FirmHisted mor ituffe bonguis hon tract>>> print(generate_text(lm, 2, 40))Fir my fat,Forromfor intre You to lor c

Do you notice anything? They all start with F! In fact, after we hit a certain order, the first word is always First? Why is that? Is the model trying to be clever? First, generate the word First. Explain what is going on in your writeup.

Part 2: Perplexity, smoothing, back-off and interpolation

In this part of the assignment, youll adapt Yoavs code in order to implement several of the techniques described in Section 4.2 of the Jurafsky and Martin textbook.

Perplexity

How do we know whether a LM is good? There are two basic approaches:

Task-based evaluation (also known as extrinsic evaluation), where we use the LM as part of some other task, like automatic speech recognition, or spelling correcktion, or an OCR system that tries to covert a professors messy handwriting into text.
Intrinsic evaluation. Intrinsic evaluation tries to directly evalute the goodness of the language model by seeing how well the probability distributions that it estimates are able to explain some previously unseen test set.

Heres what the textbook says:

For an intrinsic evaluation of a language model we need a test set. As with many of the statistical models in our field, the probabilities of an N-gram model come from the corpus it is trained on, the training set or training corpus. We can then measure the quality of an N-gram model by its performance on some unseen data called the test set or test corpus. We will also sometimes call test sets and other datasets that are not in our training sets held out corpora because we hold them out from the training data.

So if we are given a corpus of text and want to compare two different N-gram models, we divide the data into training and test sets, train the parameters of both models on the training set, and then compare how well the two trained models fit the test set.

But what does it mean to fit the test set? The answer is simple: whichever model assigns a higher probability to the test set is a better model.

Well implement the most common method for intrinsic metric of language models: perplexity. The perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words. For a test set $W = w_{1} w_{2} . . . w_{N}$ :

OK lets implement it. Heres a possible function signature for perplexity. (We might update it during class on Wednesday). Give it a go.

def perplexity(test_filename, lm, order=4):  '''Computes the perplexity of a text file given the language model.    Inputs:    test_filename: path to text file    lm: The output from calling train_char_lm.    order: The length of the n-grams in the language model.  '''  test = open(test_filename).read()  pad = "~" * order  test = pad + data    # TODO: YOUR CODE HERE

A couple of things to keep in mind:

Remember to pad the front of the file
Numeric underflow is going to be a problem, so consider using logs.
Perplexity is undefined if LM assigns any zero probabilities to the test set. In that case your code should return positive infinity float("inf").
On your unsmoothed models, youll definitely get some zero probabilities for the test set. To test you code, you should try computing perplexity on the trianing set, and you should compute perplexity for your LMs that use smoothing and interpolation.

In your report:

Discuss the perplexity for text that is similar and different from Shakespeares plays. We provide you two dev text files, a New York Times article and several of Shakespeares sonnets, but feel free to experiment with your own text.

Note: you may want to create a smoothed language model before calculating perplexity, otherwise you will get a perplexity of 0.

Laplace Smoothing and Add-k Smoothing

Laplace Smoothing is described in section 4.4.1. Laplace smoothing adds one to each count (hence its alternate name add-one smoothing). Since there are V words in the vocabulary and each one was incremented, we also need to adjust the denominator to take into account the extra V observations.

A variant of Laplace smoothing is called Add-k smoothing or Add-epsilon smoothing. This is described in section Add-k 4.4.2. Lets change the function definition of train_char_lm so that it takes a new argument, add_k, which specifies how much to add. By default, well set it to one, so that it acts like Laplace smoothing:

def train_char_lm(fname, order=4, add_k=1):    # Your code here...

Interpolation

Next, lets implement interpolation. The idea here is to calculate the higher order n-gram probabilities also combining the probabilities for lower-order n-gram models. Like smoothing, this helps us avoid the problem of zeros if we havent observed the longer sequence in our training data. Heres the math:

where $λ_{1} + λ_{2} + λ_{3} = 1$ .

Now, write a back-off function:

def calculate_prob_with_backoff(char, history, lms, lambdas):  '''Uses interpolation to compute the probability of char given a series of      language models trained with different length n-grams.   Inputs:     char: Character to compute the probability of.     history: A sequence of previous text.     lms: A list of language models, outputted by calling train_char_lm.     lambdas: A list of weights for each lambda model. These should sum to 1.      Returns:    Probability of char appearing next in the sequence.  '''   # TODO: YOUR CODE HERE  pass

You should also write a helper function to set the lambdas. Heres a function definition that gives you access to a development set. You can also experiment with setting them manually.

# returns a list of lambda values that weight the contribution of n-gram modeldef set_lambdas(lms, dev_filename):  '''Returns a list of lambda values that weight the contribution of each n-gram model  This can either be done heuristically or by using a development set.  Inputs:    lms: A list of language models, outputted by calling train_char_lm.    dev_filename: Path to a development text file to optionally use for tuning the lmabdas.   Returns:    Probability of char appearing next in the sequence.  '''  # TODO: YOUR CODE HERE  pass

In your report:

Experiment with a couple different lambdas and values of k, and discuss their effects.

Part 3: Text Classification using LMs

Language models can be applied to text classification. If we want to classify a text $D$ into a category $c \in C = c_{1}, . . ., c_{N}$ . We can pick the category $c$ that has the largest posterior probability given the text. That is,

Using Bayes rule, this can be rewritten as:

If we assume that all classes are equally likely, then we can just drop the $P (c)$ term:

Here $P (D ∣ c)$ is the likelihood of $D$ under category $c$ , which can be computed by training language models for all texts associated with category $c$ . This technique of text classification is drawn from literature on authorship identification, where the approach is to learn a separate language model for each author, by training on a data set from that author. Then, to categorize a new text D, they use each language model to calculate the likelihood of D under that model, and pick the category that assigns the highest probability to D.

Try it! We have provided you training and validation datsets consisting of the names of cities. The task is to predict the country a city is in. The following countries are including in the dataset.

Leaderboard

Well set up a leaderboard for the text classification task. Your job is to configure a set of language models that perform the best on the text classification task. We will use the city names dataset, which you should have already downloaded. The test set has one unlabeled city name per line. Your code should output a file labels.txt with one two-letter country code per line.

In next weeks assignment, you will use a recurrent neural network on the same dataset in order to compare performance.

In your report:

Describe the parameters of your final leaderboard model and any experimentation you did before settling on it.

Deliverables

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[Solved] Character-based Language Models : Assignment 5

Part 1: Unsmoothed Maximum Likelihood Character-Level Language Models

Train a language model

P(hello world)

Lets write some Shakespeare!

What the F?

Part 2: Perplexity, smoothing, back-off and interpolation

Perplexity

In your report:

Laplace Smoothing and Add-k Smoothing

Interpolation

In your report:

Part 3: Text Classification using LMs

In your report:

Deliverables

Recommended readings

Reviews

Whatsapp Us

[Solved] Character-based Language Models : Assignment 5

Part 1: Unsmoothed Maximum Likelihood Character-Level Language Models

Train a language model

P(hello world)

Lets write some Shakespeare!

What the F?

Part 2: Perplexity, smoothing, back-off and interpolation

Perplexity

In your report:

Laplace Smoothing and Add-k Smoothing

Interpolation

In your report:

Part 3: Text Classification using LMs

In your report:

Deliverables

Recommended readings

Reviews

Related products

[Solved] Vector Space Models : Assignment 3

[Solved] Learning Hypernyms : Assignment 8

[Solved] Text Classification : Assignment 2

[Solved] Advanced Vector Space Models : Assignment 4

[Solved] Neural Language Models : Assignment 6 Solution

[Solved] Named Entity Recognition : Assignment 7