## Description

Vector Space Models : Assignment 3

In this assignment you will implement many of the things you learned in Chapter 15 of the textbook

(https://web.stanford.edu/~jurafsky/slp3/15.pdf). If you haven’t read it yet, now would be a good time to do

that. We’ll wait. Done? Great, let’s move on.

We will provide a corpus of Shakespeare plays, which you will use to create a term-document matrix and a

term-context matrix. You’ll implement a selection of the weighting methods and similarity metrics defined in

the textbook. Ultimately, your goal is to use the resulting vectors to measure how similar Shakespeare plays

are to each other, and to find words that are used in a similar fashion. All (or almost all) of the code you write

will be direct implementations of concepts and equations described in Chapter 15

(https://web.stanford.edu/~jurafsky/slp3/15.pdf).

All difficulties are easy when they are known.

Here are the materials that you should download for this assignment:

Skeleton python code (/downloads/hw3/main.py)

Data – csv of the complete works of Shakespeare (/downloads/hw3/will_play_text.csv)

Data – vocab the complete works of Shakespeare (/downloads/hw3/vocab.txt)

Data – list of all plays in dataset (/downloads/hw3/play_names.txt)

Term-Document Matrix

You will write code to compile a term-document matrix for Shakespeare’s plays, following the description in

section 15.1.1 in textbook.

In a term-document matrix, each row represents a word in the vocabulary and

each column represents a document from some collection. The figure below

shows a small selection from a term-document matrix showing the occurrence

of four words in four plays by Shakespeare. Each cell in this matrix represents

the number of times a particular word (defined by the row) occurs in a particular

document (defined by the column). Thus clown appeared 117 times in *Twelfth

Night

As You Like ItTwelfth NightJulias CaesarHenry V

battle 1 1 8 15

soldier 2 2 12 36

fool 37 58 1 5

crown 5 117 0 0

The dimensions of your term-document matrix will be the number of documents (in this case, the number

of Shakespeare’s plays that we give you in the corpus by the number of unique word types in that

collection. The columns represent the documents, and the rows represent the words, and each cell represents

the frequency of that word in that document.

In your code you will write a function to create_term_document_matrix . This will let you be the hit of your

next dinner party by being able to answer trivia questions like how many words did Shakespeare use?, which

may give us a hint to the answer to [How many words did Shakespeare know?] The table will also tell you how

many words Shakespeare used only once. Did you know that there’s a technical term for that? In corpus

linguistics they are called hapax legomena (https://en.wikipedia.org/wiki/Hapax_legomenon), but I prefer the

term singleton, because I don’t like snooty Greek or Latin terms.

Comparing plays

The term-document matrix will also let us do cool things like figure out which plays are most similar to each

other, by comparing the column vectors. We could even look for outliers to see if some plays are so dissimilar

from the rest of the canon that maybe they weren’t authored by Shakespeare after all

(https://en.wikipedia.org/wiki/Shakespeare_authorship_question).

Let’s begin by considering the column representing each play. Each column is a -dimensional vector. Let’s

use some math to define the similarity of these vectors. By far the most common similarity metric is the cosine

of the angle between the vectors. The cosine similarity metric is defined in Section 15.3 of the textbook.

The cosine, like most measures for vector similarity used in NLP, is based on the

dot product operator from linear algebra, also called the inner product:

dot-product(

The dot product acts as a similarity metric because it will tend to be high just

when the two vectors have large values in the same dimensions. Alternatively,

vectors that have zeros in different dimensions (orthogonal vectors) will have a

dot product of 0, representing their strong dissimilarity.

This raw dot-product, however, has a problem as a similarity metric: it favors

long vectors. The vector length is defined as

D

|V|

|V|

v, w

⃗ )⃗

= v ⋅⃗

w =

⃗ ∑ = + + … + N

i=1 viwi v1w1 v2w2 vNwN

|v| ⃗

= ∑N

i=1 v2

i

‾‾‾‾‾‾‾ √

The dot product is higher if a vector is longer, with higher values in each

dimension. More frequent words have longer vectors, since they tend to cooccur with more words and have higher co-occurrence values with each of

them. The raw dot product thus will be higher for frequent words. But this is a

problem; we would like a similarity metric that tells us how similar two words are

regardless of their frequency.

The simplest way to modify the dot product to normalize for the vector length is

to divide the dot product by the lengths of each of the two vectors. This

normalized dot product turns out to be the same as the cosine of the angle

between the two vectors, following from the definition of the dot product

between two vectors and as:

The cosine similarity metric between two vectors and thus can be

computed

The cosine value ranges from 1 for vectors pointing in the same direction, through 0 for vectors that are

orthogonal, to -1 for vectors pointing in opposite directions. Since our term-document matrix contains raw

frequency counts, it is non-negative, so the cosine for its vectors will range from 0 to 1. 1 means that the

vectors are identical, 0 means that they are totally dissimilar.

Please implement compute_cosine_similarity , and for each play in the corpus, score how similar each

other play is to it. Which plays are the closet to each other in vector space (ignoring self similarity)? Which

plays are the most distant from each other?

How do I know if my rankings are good?

v

⃗

w

⃗

v ⋅⃗

w =

⃗ |v||⃗

w|c

⃗

osΘ

= cosΘ v⋅w⃗ ⃗

|v||⃗w|⃗

v

⃗

w

⃗

cosine(v, w

⃗ )⃗

= =

v⋅w⃗ ⃗

|v||⃗w|⃗

∑N

i=1 viwi

∑N

i=1 v2 √ i ∑N

i=1 w2 √ i

First, read all of the plays. Then perform at least three of them. Now that you are a true thespian, you should

have a good intuition for the central themes in the plays. Alternately, take a look at this grouping of

Shakespeare’s plays into Tragedies, Comedies and Histories

(https://en.wikipedia.org/wiki/Shakespeare%27s_plays#Canonical_plays). Do plays that are thematically

similar to the one that you’re ranking appear among its most similar plays, according to cosine similarity?

Another clue that you’re doing the right thing is if a play has a cosine of 1 with itself. If that’s not the case, then

you’ve messed something up. Another good hint, is that there are a ton of plays about Henry. They’ll probably

be similar to each other.

Measuring word similarity

Next, we’re going to see how we can represent words as vectors in vector space. This will give us a way of

representing some aspects of the meaning of words, by measuring the similarity of their vectors.

In our term-document matrix, the rows are word vectors. Instead of a -dimensional vector, these row

vectors only have dimensions. Do you think that’s enough to represent the meaning of words? Try it out. In

the same way that you computed the similarity of the plays, you can compute the similarity of the words in the

matrix. Pick some words and compute 10 words with the highest cosine similarity between their row vector

representations. Are those 10 words good synonyms?

Term-Context Matrix

Instead of using a term-document matrix, a more common way of computing word similarity is by

constructing a term-context matrix (also called a word-word matrix), where columns are labeled by words

rather than documents. The dimensionality of this kind of a matrix is by . Each cell represents how

often the word in the row (the target word) co-occurs with the word in the column (the context) in a training

corpus.

For this part of the assignment, you should write the create_term_context_matrix function. This function

specifies the size word window around the target word that you will use to gather its contexts. For instance, if

you set that variable to be 4, then you will use 4 words to the left of the target word, and 4 words to its right

for the context. In this case, the cell represents the number of times in Shakespeare’s plays the column word

occurs in +/-4 word window around the row word.

You can now re-compute the most similar words for your test words using the row vectors in your termcontext matrix instead of your term-document matrix. What is the dimensionality of your word vectors now?

Do the most similar words make more sense than before?

Weighting terms

Your term-context matrix contains the raw frequency of the co-occurrence of two words in each cell. Raw

frequency turns out not to be the best way of measuring the association between words. There are several

methods for weighting words so that we get better results. You should implement two weighting schemes:

Positive pointwise mutual information (PPMI)

Term frequency inverse document frequency (tf-idf)

|V|

D

|V| |V|

These are defined in Section 15.2 of the textbook.

Warning, calculating PPMI for your whole -by- matrix might be slow. Our intrepid TA’s implementation

for PPMI takes about 10 minutes to compute all values. She always writes perfectly optimized code on her first

try. You may improve performance by using matrix operations a la MATLAB.

Weighting terms

There are several ways of computing the similarity between two vectors. In addition to writing a function to

compute cosine similarity, you should also write functions to compute_jaccard_similarity and

compute_dice_similarity . Check out section 15.3.1. of the textbook for the defintions of the Jaccard and

Dice measures.

Your Tasks

All of the following are function stubs in the python code. You just need to fill them out.

Create matrices:

fill out create_term_document_matrix

fill out create_term_context_matrix

fill out create_PPMI_matrix

fill out compute_tf_idf_matrix

Compute similarities:

fill out compute_cosine_similarity

fill out compute_jaccard_similarity

fill out compute_dice_similarity

Do some ranking:

fill out rank_plays

fill out rank_words

Report

In the ranking tasks, play with different vector representations and different similarity functions. Does one

combination appear to work better than another? Do any interesting patterns emerge? Include this discussion

in your writeup.

Some patterns you could touch upon:

The fourth column of will_play_text.csv contains the name of the character who spoke each line.

Using the methods described above, which characters are most similar? Least similar?

Shakespeare’s plays are traditionally classified into comedies, histories, and tragedies

(https://en.wikipedia.org/wiki/Shakespeare%27s_plays). Can you use these vector representations to

cluster the plays?

Do the vector representations of female characters

|V| |V|

(https://en.wikipedia.org/wiki/Category:Female_Shakespearean_characters) differ distinguishably from

male ones (https://en.wikipedia.org/wiki/Category:Male_Shakespearean_characters)?

Extra credit

Quantifying the goodness of one vector space representation over another can be very difficult to do. It might

ultimately require testing how the different vector representations change the performance when used in a

downstream task like question answering. A common way of quantifying the goodness of word vectors is to

use them to compare the similarity of words with human similarity judgments, and then calculate the

correlation of the two rankings.

If you would like extra credit on this assignment, you can quantify the goodness of each of the different vector

space models that you produced (for instance by varying the size of the context window, picking PPMI or tfidf, and selecting among cosine, Jaccard, and Dice). You can calculate their scores on the SimLex999 data set

(https://www.cl.cam.ac.uk/~fh295/simlex.html), and compute their correlation with human judgments using

Kendall’s Tau (https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient).

Add a section to your writeup explaining what experiments you ran, and which setting had the highest

correlation with human judgments.

More Optional Fun Extra Credit options

So you’ve built some machinery that can measure similarity between words and documents. We gave you a

Shakespeare corpus, but you can use any body of text you like. For example, check out Project Gutenberg

(https://www.gutenberg.org/) for public domain texts. The sky’s the limit on what you can do, but here are

some ideas:

Term-Character Matrix. Our data set.

Novel recommender system. Maybe you enjoyed reading Sense and Sensibility and War and Peace.

Can you suggest some similar novels? Or maybe you need some variety in your consumption. Find

novels that are really different.

Other languages. Do these techniques work in other languages? Project Gutenberg has texts in a

variety of languages. Maybe you could use this to measure language similarity?

Modernizing Shakespeare. When I read Shakespeare in high school, I had the dickens of a time trying to

understand all the weird words in the play. Some people have re-written Shakespeare’s plays into

contemporary English. An awesome NLP researcher (https://cocoxu.github.io) has compiled that data

(https://github.com/cocoxu/Shakespeare). Use her data and your vector space models to find

contemporary words that mean similar things to the Shakespearean English.

Deliverables

Here are the deliverables that you will need to submit:

writeup.pdf

code (.zip). It should be written in Python 3.

Daphne Ippolito, Anne Cocos, Stephen Mayhew, and Chris Callison-Burch developed this homework assignment

for UPenn’s CIS 530 class in Spring 2018.

Recommended readings

Vector Semantics. (https://web.stanford.edu/~jurafsky/slp3/15.pdf) Dan Jurafsky and James H. Martin.

Speech and Language Processing (3rd edition draft) .

From Frequency to Meaning: Vector Space Models of Semantics. (https://www.jair.org/media/2934/live-2934-

4846-jair.pdf) Peter D. Turney and Patrick Pantel. Journal of Artificial Intelligence Research 2010. Abstract

BibTex

Paraphrasing for Style. (http://www.aclweb.org/anthology/C12-1177) Wei Xu, Alan Ritter, Bill Dolan, Ralph

Grisman, and Colin Cherry. Coling 2012. Abstract BibTex

Evaluation methods for unsupervised word embeddings. (http://www.aclweb.org/anthology/D15-1036) Tobias

Schnabel, Igor Labutov, David Mimno, Thorsten Joachims. EMNLP 2015. Abstract BibTex

Community Evaluation and Exchange of Word Vectors at wordvectors.org.

(http://www.aclweb.org/anthology/P14-5004) Manaal Faruqui and Chris Dyer. ACL demos 2014. Abstract

BibTex