Distributed word representations

This codelab is about methods for creating effective distributed semantic word representations. Here, "distributed" just means that the representations are vectors of real numbers, and these models are also often called vector space models (VSMs). My focus is largely on methods derived from co-occurrence patterns in text, but the section Supervised signals illustrates a simple method for imbuing distributional word vectors with label information.

A usage note: the term distributional representatation is sometimes reserved for those derived purely from count data, and distributed representation is sometimes reserved for those that involve some kind of supervised optimization. Here, I use distributed representation in its most general form. As we will see, many models blur the supervised/distributional distinction.

Code and data requirements

Download or clone this Github repository so that you have all the files it includes.

Download the data distribution for this unit, unpack it, and place it in the directory containing the above Github directory.

In addition, make sure you have the following installed:

• Numpy, Scipy, and matplotlib. (Mac users: I suggest the Scipy Superpack)
• scikit.learn

If you want to work in and modify this notebook, you should also install the latest iPython.

Contents

1. Distributional matrices
2. Vector comparison
   1. Euclidean distance
   2. Length normalization
   3. Cosine distance
   4. Matching-based methods
   5. Summary
3. Distributional neighbors
4. Matrix reweighting
   1. Normalization
   2. Pointwise Mutual Information
   3. TF-IDF
5. Dimensionality reduction
6. Visualization
7. The semantic orientation method
8. Word-sense ambiguities
9. GloVe word representations
10. Supervised signals
    1. Shallow neural network model
    2. Logical operator example
    3. Sentiment lexicon example
    4. Word-level inference relations
11. Word similarity evaluation
12. Word analogies evaluation
13. Exercises
    1. Exploratory and open-ended
    2. Straightforward
    3. Challenging

Distributional matrices

Here's a basic recipe for building a word $\times$ word matrix:

1. Define a notion of co-occurrence context. This could be an entire document, a paragraph, a sentence, a clause, an NP — whatever domain seems likely to capture the associations you care about.
2. Scan through your corpus building a dictionary $d$ mapping word-pairs to counts. Every time a pair of words $w$ and $w'$ occur in the same context (as you defined it in 1), increment $d[(w, w')]$ by $1$.
3. Using the count dictionary $d$ that you collected in 2, establish your full vocabulary $V$, an ordered list of words types. For large collections of documents, $|V|$ will typically be huge. You will probably want to winnow the vocabulary at this point. You might do this by filtering to a specific subset, or just imposing a minimum count threshold. You might impose a minimum count threshold even if $|V|$ is small — for words with very low counts, you simply don't have enough evidence to say anything interesting.
4. Now build a matrix $M$ of dimension $|V| \times |V|$. Both the rows and the columns of $M$ represent words. Each cell $M[i, j]$ is filled with the count $d[(w_i, w_j)]$.

For different design matrices, the procedure differs slightly. For example, if you are building a word $\times$ document matrix, then the rows of $M$ represent words and the columns of $M$ represent documents. The scan in step 2 then just keeps track of (word, document) pairs — compiling the number of times that word appears in document. Such matrices are often used in information retrieval, because the columns are multi-set representations of documents. They are much sparser than the the word $\times$ word matrices we will work with here. (In my experience, they yield lower quality lexicons, but others have reported good results with them.)

This codebook is distributed with two pre-computed matrices of co-occurrence counts in IMDB move reviews. The build function allows you to read them in:

Let's read these in now for use in later examples:

There are some great pre-computed matrices available online too. These aren't matrices of counts, but rather more abstract values computed using methods like those under discussion here. Just for kicks, load in the GloVe vectors included in the data distribution:

Vector comparison

Vector comparisons form the heart of our analyses in this context. For the most part, we are interested in measuring the distance between vectors. The guiding idea is that semantically related words should be close together in the vector spaces we build, and semantically unrelated words should be far apart.

The scipy.spatial.distance module has a lot of vector comparison methods, so you might check them out if you want to go beyond the functions defined and explored here. Read the documentation closely, though: many of those methods are defined only for binary vectors, whereas the VSMs we'll use allow all float values in principle.

Euclidean distance

The most basic and intuitive distance measure between vectors is euclidean distance. The euclidean distance between two vectors $u$ and $v$ of dimension $n$ is

$$\sqrt{\sum_{i=1}^{n} |u_{i}-v_{i}|^2}$$

In two-dimensions, this corresponds to the length of the most direct line between the two points. Here, we just rely on scipy to define it:

The comment above shows how to define this measure yourself. The function used there is the length of a vector $u$ of dimension $n$, which is defined as

$$\|u\| = \sqrt{\sum_{i=1}^{n} u_{i}^{2}}$$

Here's the code:

Here's the tiny vector space from the screencast on vector comparisons associated with this codelab:

The euclidean distances align well with the raw visual distance in the plot:

However, suppose we think of the vectors as word meanings in the vector-space sense. In that case, the values don't look good: the distributions of B and C are more or less directly opposed, suggesting very different meanings, whereas A and B are rather closely aligned, abstracting away from the fact that the first is far less frequent than the second. In terms of the large models we will soon explore, A and B resemble a pair like superb and good, which have similar meanings but very different frequencies. In contrast, B and C are like good and disappointing — similar overall frequencies but different distributions with respect to the overall vocabulary.

Length normalization

These affinities are immediately apparent if we normalize the vectors by their length. To do this, we use vector_length to define length_norm:

Here, the connection between A and B is more apparent, as is the opposition between B and C.

Cosine distance

Cosine distance takes overall length into account. The cosine distance between two vectors $u$ and $v$ of dimension $n$ is

$$1 - \left(\frac{\sum_{i=1}^{n} u_{i} \cdot v_{i}}{\|u\|\cdot \|v\|}\right)$$

The similarity part of this (the righthand term of the subtraction) is actually measuring the angles between the two vectors. The result is the same (in terms of rank order) as one gets from first normalizing both vectors using vector_length and then calculating their Euclidean distance.

Matching-based methods

Matching-based methods are also common in the literature. The basic matching measure effectively creates a vector consisting of all of the smaller of the two values at each coordinate, and then sums them:

One approach to normalizing the matching values is the Jaccard coefficient. The numerator is the matching coefficient. The denominator — the normalizer — is intuitively like the set union: for binary vectors it gives the cardinality of the union of the two being compared:

Summary

Suppose we set for ourselves the goal of associating A with B and disassociating B from C, in keeping with the semantic intuition expressed above. Then we can assess distance measures by whether they achieve this goal:

Distributional neighbors

The neighbors function is an investigative aide. For a given word, it ranks all the words in the vocabulary rownames according to their distance from word, as measured by distfunc in matrix mat:

By playing around with this function, you can start to get a sense for how the distance functions differ. Here are some example calls; you might try some new words to get a feel for what these matrices are like and how different words look.

The above rankings actually tend to look pretty good, with cosine less likely to associate words that happen to have similar frequency.

The GloVe vectors look even better — but they are based on much more than just raw counts, as we'll see soon:

Matrix reweighting

The goal of reweighting is to amplify the important, trustworthy, and unusual, while deemphasizing the mundane and the quirky. Absent a defined objective function, this will remain fuzzy, but the intuition behind moving away from raw counts is that frequency is a poor proxy for our target semantic ideas.

Normalization

Normalization (row-wise or column-wise) is perhaps the simplest form of reweighting. With length_norm, we normalize using vector_length. We can also normalize each row by the sum of its values, which turns each row into a probability distribution over the columns:

These normalization measures are insensitive to the magnitude of the underlying counts. This is often a mistake in the messy world of large data sets; $[1,10]$ and $[1000,10000]$ are very different in ways that will be partly or totally obscured by normalization.

Pointwise Mutual Information

Pointwise Mutual Information (PMI) addresses this issue, at least in part. The PMI for word $\times$ context pair $(w,c)$ is

$$\log\left(\frac{P(w,c)}{P(w) \cdot P(c)}\right)$$

with $\log(0) = 0$. This is a measure of how far that cell's value deviates from what we would expect given the row and column sums for that cell.

Positive PMI (PPMI) maps all negative PMI values to 0.0. Our function pmi has positive=True as a default, in light of the arguments in Levy and Goldberg 2014, section 3.3.

Here, we reweight the word $\times$ word IMDB matrix from above using PPMI:

TF-IDF

Perhaps the best known reweighting schemes is Term Frequency–Inverse Document Frequency (TF-IDF), which is, I believe, still the backbone of today's Web search technologies. As the name suggests, it is built from TF and IDF measures:

For a word $w$ and collection of documents $D$ containing document $d$:

• TF$(w,d)$: $P(w \mid c)$. (In our VSMs, this is column-normalization using prob_norm.)
• IDF$(w,D)$: $\log\left(\frac{|D|}{|\{d \in D : w \in d\}|}\right)$, where $\log(0)=0$.
• TFIDF$(w,d,D)$: TF$(w,d)$ * IDF$(w,D)$

TF-IDF generally performs best with sparse matrices. It severely punishes words that appear in many documents; if a word appears in every document, then its IDF value is 0. As a result, it can even be problematic with verb dense word $\times$ word matrices like ww, where most words appear with most other words due to the permissive notion of co-occurrence used to create it.

Here's an example using our word x document matrix wd:

Dimensionality reduction

The above methods deliver solid results. However, they are not capable of capturing higher-order associations in the data. For example, both gnarly and wicked are used as slangily positive adjectives. We thus expect them to have many of the same neighbors. However, at least stereotypically, gnarly is Californian and wicked is Bostonian. Thus, they are unlikely to occur often in the same texts. Dimensionality reduction techniques are often capable of capturing their semantic similarity (and have the added advantage of shrinking the size of our data structures).

The general goal of dimensionality reduction is eliminate rows/columns that are highly correlated while bringing similar things together and pushing dissimilar things apart. Latent Semantic Analysis (LSA) is a prominent method. It is an application of truncated singular value decomposition (SVD). SVD is a central matrix operation; 'truncation' here means looking only at submatrices of the full decomposition. LSA seeks not only to find a reduced-sized matrix but also to capture similarities that come not just from direct co-occurrence, but also from second-order co-occurrence.

Here's a look at the example from the slides:

We see that gnarly and wicked are not close to each other. (Well, it's a small space, but they are as close as gnarly and lame.) Reweighting by PMI, PPMI, or TF-IDF is no help. LSA to the rescue:

Visualization

You can begin to get a feel for what your matrix is like by poking around with the neighbors function to see who is close to or far from whom. But this kind of sampling is unlikely to lead to robust new insights, unless you luck out and start to see an interesting cluster of associations developing.

t-Distributed Stochastic Neighbor Embedding (t-SNE) is a powerful method for visualizing high-dimensional vector spaces in 2d. It allows you to find associations in an intuitive way, to guide later and more precise investigations. Its lead developer, Laurens van der Maaten, distributes a number of implementations of it. The following function uses his Python version, together with matplotlib to visualize the results.

Here's the code for running this on ww_pmi using the default settings:

It takes a while to produce this, so here's an example of the output: fig/imdb-wordword-ppmi.pdf. (t-SNE's output will vary somewhat from run to run).

For more on the techniques, we highly recommend van der Maaten's compelling talk Visualizing Data Using t-SNE.

The semantic orientation method

The t-SNE visualization of our running example suggests some lexical clusters that in turn suggest the beginnings of a lexicon. The semantic orientation method of Turney and Littman 2003 is a general method for building such lexicons for any desired semantic dimension.

The method simply exploits our above insights about vector similarity. Here are the steps:

1. Define two seed-sets $S_1$ and $S_2$ of words (they should be opposing in some way that is appropriate for your matrix).
2. Pick a vector distance measure $f$.
3. For the word $w$ of interest, use $f$ to get the sum of all distances between $w$ and the words in $S_1$. Do the same for $S_2$.
4. The score is the sum for $S_1$ minus the sum for $S_2$.

Here's an implementation; the default seed values correspond to Turney and Littman's basic sentiment experiment.

An example function call using ww_ppmi:

Word-sense ambiguities

Distributional approaches are often criticized on the grounds that they do not allow for word-sense ambiguities. This is a fair criticism of the models explored so far. A method for addressing this shortcoming was proposed by Reisinger and Mooney (2010) building on ideas from Schütze (1998). Here is a simplified version of their method:

1. For each word $w$ in a word $\times$ context matrix $M$, cluster the columns (contexts) containing $w$ using a clustering algorithm.
2. For each token of $w$ in each of its contexts $d$, subscript $w$ with the cluster index of $d$ according to the clustering done in step 1.
3. Rebuild the matrix with the rows now labeled with the expanded vocabulary obtained at step 2.

The success of this method will depend a lot on the clustering algorithm used. The implementation below uses Affinity Propagation, which allows different numbers of clusters for each word, which seems desirable. K-means actually works well too, and one could think about methods for setting $k$ for each word $w$ based on properties of the documents containing $w$.

Here's a small idealized example meant to highlight what the algorithm does mechanically and what it is supposed to do empirically. The idea is that crane is ambiguous between a piece of machinery and a bird. The words bird and fly bias heavily in favor of the 'bird' sense, and the words equipment and hoist bias heavily in favor of the 'machine' sense. 'tall' is more subtly biased in favor of the machine sense.

When we run disambiguate things work out nicely for the target crane. The algorithm creates a lot of spurious ambiguities, but these seem to remain close together in vector space, so we might be able to collapse them in a follow-up step. (For example if two words $w_i$ and $w_j$ are sufficiently close in the vector space and share the same orthographic form, then we collapse them back down again.)

GloVe word representations

We've so far performed our matrix manipulations without an explicit objective function. Rather, we've just had in mind informal ideas about capturing semantic relatedness. The advantage of an explicit objective function is that we can apply standard optimization techniques.

Pennington et al. (2014) introduce an objective function for semantic word representations. Roughly speaking, the objective is to learn vectors for words $w_{1}$ and $w_{j}$ such that their dot product is proportional to their co-occurrence count. I won't venture a full technical summary of the GloVe method here. Check out the GloVe project homepage, which links to C code, word vectors, and other resources. I also highly recommend Jeffrey Pennington's EMNLP talk 'Global vectors for word representation'.

The following implementation is an attempt to give the most stripped-down, bare-bones version of the GloVe method possible. In the papers and associated implementation, the authors use the Adaptive Gradient (AdaGrad) learning method. Jon Gauthier released a Python version that uses that method as well. Both of these implementations also do considerably more sophisticated things when it comes to compiling the basic co-occurrence counts. The code here is really just meant for instructional purposes. That said, it's a testament to the power of the method that it delivers high quality word vectors even in this basic form!

The following take a while to run, but the results look good, and they can be improved by adding more vocabulary items, allowing more iterations, and increasing the dimension size. For the output with 100 dimensions and 100 iterations, check out this image: fig/imdb-wordword-glove100.pdf.

Supervised signals

The above methods rely entirely on co-occurrence patterns to achieve word representations. From a semantic perspective, this can seem unnatural. Grounding in the world is a crucial part of natural language meaning; without some connection to the world, we're missing important aspects of meaning.

Distributed approaches are compatible with grounding, though. The goal of the current section is to illustrate this possibility with a simple example involving sentiment. The guiding idea is that the labels in a sentiment lexicon provide one very specific kind of grounding, in emotional states. This information is probably not recoverable entirely from distributional facts, but we can bring it into our distributed representations.

The method employed here for imbuing distributional vectors with sentiment information is a shallow neural network. The inputs to the network are matrices as we constructed them above. I particularly recommend applying PPMI first (count vectors will be problematic), and LSA might also be a valuable preprocessing step. Using the backpropagation algorithm, we learn a weight vector that derives hidden representations from our inputs. These hidden representations are our word representations. If all goes well, they will encode both the distributional information present in the input vectors and the label information from our lexicon.

Shallow neural network model

Here's a very basic shallow neural network implementation with stochastic gradient descent (SGD) training. (See the exercises for suggestions on how to improve this code.)

Logical operator example

Logical operators like 'iff' and 'xor' provides early motivation for hidden representations (see Rumelhart et al. 1985), so it's satisfying to show that the above code can learn such operators (at least on most runs). Here an example involving 'iff':

Sentiment lexicon example

To close this section, let's look a somewhat more useful and complex example involving a multidimensional sentiment lexicon. This is actually on its way to being a useful general purpose sentiment resource!

The first function just processes the sentiment lexicon included in the data distribution (Warriner_et_al emot ratings.csv). We keep only the overall values for the three sentiment dimensions, and we rescale them into the space [-1,1]. (Somewhat counter intuitively, for the valence dimensions, the low values are positive and the high values are negative, because of the original rating scale.)

The next function uses a distributional matrix and a lexicon to create a training set consisting of all the items in the matrix that are also in the lexicon:

We're now ready to train the model and view the results:

The function sentiment_lexicon_example takes a while to run with reasonable keyword arguments. To see what the results tend to look like with the default values, here's an informal comparison of the matrix ww, reweighted with Positive PMI, before and after supervised sentiment training: fig/imdb-wordword-ppmi-nn.pdf.

Word-level inference relations

Bowman et al. (2015) use neural networks to predict the relationship between words. The data distribution for this unit includes one of their experiment files, longer_shuffled_synset_relations.tsv. The left column gives the semantic relation (hyponym, hypernym, coordinate), and the middle and right columns give the two words. We can use ShallowNeuralNetwork to train models that perform this prediction task, beginning either from randomly initialized input vectors or from distributional vectors.

Word similarity evaluation

The function word_similarity_evaluation lets you evaluate a matrix mat against the human word similarity judgments in words in the WordSim-353 dataset. If you haven't already, download that data set and unzip it so that the directory wordsim353 is inside the directory containing this file.

Evaluation is then simple. Here's the evaluation using the ww_ppmi matrix we built above:

Word analogies evaluation

Exercises

Exploratory and open-ended

These are largely meant to give you a feel for the material, but some of them could lead to projects. These are not for credit.

1. Pick a few words from a single domain and see what their neighbors are like in one the VSMs (ww, wd, ww_ppmi, ww_tfidf, glv), using neighbors, comparing cosine with euclidean.

2. We saw that euclidean distance favors raw frequencies. Find words in the matrix ww that help make this point: a pair that are semantically unrelated but close according to euclidean, and a pair that are semantically related by far apart according to euclidean.

3. Starting from ww or wd, toy around with different combinations of (i) weighting scheme, (ii) dimensionality reduction (if any), and (iii) distance measure. Which VSM seems to provide the best reconstruction of our intuitive notion of semantic relatedness.

4. What happens if you set k=1 using lsa. What do the results look like then? What do you think this first (and now only) dimension is capturing?

5. Use sentiment_lexicon_example on a different matrix, with different settings, to see what the results are like. You might also modify the code so that it trains on just a subset of the lexicon values.

6. Read in distributedwordreps-data/gigawordnyt-advmod-matrix.csv. This is an adjective $\times$ adverb matrix derived from the Gigaword corpus. Each cell contains the number of times that the modifier phrase ADV ADJ appeared in Gigaword, where ADJ is the row value and ADV is the column value. You can read it in with build above. Using the above techniques and measures, try to get a feel for what can be done with this matrix.

7. Use the word2vec implementation in gensim for some purpose.

8. Find new labels sources to include in your training of a ShallowNeuralNetwork instance.

Straightforward

1. Implement Jensen–Shannon distance and run it on the toy matrix ABC defined above. Does this measure place A and B close together relative to B and C (our goal for that example)? Submit: (i) your implementation, and (ii) the JS distance values between A and B and between B and C.

2. Implement the Dice coefficient for real-valued vectors, as

   $$1.0 - \left(\frac{2\sum_{i=1}^{n}\min(u_{i}, v_{i})}{\sum_{i=1}^{n}u_{i}+v_{i}}\right)$$

   Run your code on the toy matrix ABC defined above. Does this measure place A and B close together relative to B and C (our goal for that example)? Submit: (i) your implementation, and (ii) the Dice coefficient values for A and B and for B and C.

3. Consider the matrix np.array([[1.0, 0.0, 0.0], [1000.0, 1000.0, 4000.0], [1000.0, 2000.0, 999.0]]). Reweight this matrix using pmi with positive=True. Submit: (i) the value obtained for cell [0,0], and (ii) a 1–2 sentence explanation of what is what is likely problematic about this value.

4. The t-test statistic can be thought of as a reweighting scheme. For a word–context pair $(w, c)$, the weighted value is

   $$\frac{P(w, c)-(P(w)P(c))}{\sqrt{P(w)P(c)}}$$

   Implement this as a function ttest comparable to pmi and tfidf. Submit: your implementation.

5. Using glv (which has a large and diverse set or rownames/words), pick a new semantic opposition and see how well semantic_orientation captures it. Submit: (i) the name of the semantic opposition you seek to capture (e.g., "positive/negative"), and (ii) your seed sets.

6. Using iff_example as an example, write a function boolean_nn that can train a ShallowNeuralNetwork on any binary logical connective that the user supplies as training data (in the same format as the training data in iff_example). Give the user the option to set the hidden layer dimensionality as a keyword argument. Submit: (i) your function boolean_nn, and (ii) an example function call training on the XOR connective. (XOR is the function $f$ such that, for truth-valued arguments $x$ and $y$, $f(x,y)$ is true iff $x$ and $y$ are different.)

7. The default activation function for ShallowNeuralNetwork is tanh. Implement a sigmoid activation function, defined as $f(x) = \frac{1}{1 + \exp(-x)}$. Submit: (i) your implementation of this function, and (ii) its derivative (the value of d_afunc).

Challenging

1. Use pickle.load(file('distributedwordreps-data/imdb-posneg-lexicon.pickle')) to read in a positive/negative sentiment lexicon restricted to the vocabulary of ww (same as the rows of wd). The dictionary has training and testing lists for the positive and negative categories. Your task: (i) write a function that uses semantic_orientation to induce a positive/negative sentiment lexicon on a given matrix by imposing a boundary or boundaries on what counts as positive and what counts as negative, and (ii) write a function to evaluate this function against the training data in distributedwordreps-data/imdb-posneg-lexicon.pickle. Submit: the two functions you wrote for (i) and (ii).

2. Use pickle.load(file('distributedwordreps-data/imdb-posneg-lexicon.pickle')) to read in a positive/negative sentiment lexicon restricted to the vocabulary of ww (same as the rows of wd). The dictionary has training and testing lists for the positive and negative categories. Your task: write a function that (i) reads in a distributional matrix, (ii) does some manipulation of it, (iii) trains a ShallowNeuralNetwork instance on the training portion of imdb-posneg-lexicon.pickle, and (iv) evaluates the trained model on the testing portion of imdb-posneg-lexicon.pickle. Submit: the function you wrote (which can call smaller functions that you include to make the code manageable).

3. The file distributedwordreps-data/gigawordnyt-advmod-matrix.csv contains an adjective $\times$ adverb matrix derived from the Gigaword corpus. Each cell contains the number of times that the modifier phrase ADV ADJ appeared in Gigaword, where ADJ is the row value and ADV is the column value. You can read it in with build above. Your task: without introducing any new data, get at least 190 examples right on the analogy file distributedwordreps-data/question-data/gram3-comparative.txt. Submit: a function that implements your model and returns the evaluation (the output of analogy_evaluation above). (If your function depends on other code you wrote that isn't included in this codelab, include that code as well.)

4. Turney and Pantel 2010, p. 158, propose a "contextual discounting" extension of PMI to try to address its bias for low-frequency events. Extend pmi so that the user has the option of performing this discounting with the keyword argument discounting=True. Submit: your revised pmi in full.

5. Modify disambiguate so that words with the same "root" (e.g., bird_0 and bird_1) are collapsed back down to the same vector if their separate vectors are within a user-supplied distance of one another (to remove spurious ambiguities). Submit: your modified disambiguate implementation.

6. Modify glove so that it uses the AdaGrad optimization method. It's fine to use the authors' implementation or Jon Gauthier's implementation as a reference, but you might enjoy the challenge of doing this with no peeking at their code. Submit: your revised glove code in full.

7. Modify the train method of ShallowNeuralNetwork so that the user can take advantage of the optimization methods in scipy.optimize. Submit: your revised ShallowNeuralNetwork code in full.

8. Revise ShallowNeuralNetwork to DeepNeuralNetwork by adding the capability to handle any number of hidden layers. Submit: your revised DeepNeuralNetwork code in full.