NLU CS224U Stanford

Stanford - CS224U, Natural Language Understanding

Spring 2020

· Zhejian Peng · 11 min read

CS224U: Natural Language Understanding is the first course I took in the Stanford AI Certification Program. This blog is a short summary of the material and what I took away from it.

The instructors for recent terms have been Prof. Christopher Potts and Bill MacCartney, and this year was no exception. Both are major figures in the field; Apple’s Siri is one of the products Bill led. Because of COVID-19, the course went fully online for remote students and Stanford on-campus students alike, taught over Zoom. Combined enrollment was around 120+. I teamed with a Stanford undergrad on the homework. The final project was me, that undergrad, and a CS PhD at Northwestern. The final project became optional because of the pandemic.

Course website

2019 course videos

Lecture 1, Introduction and course overview

Lecture 1 slides

NLP VS. NLU

In the first lecture the instructors gave a short intro and then contrasted NLP (Natural Language Processing) with NLU (Natural Language Understanding). My take is that NLU is a sub-area of NLP: NLU focuses on machine understanding of language, NLP on processing it. The course covers Grounded Language Understanding, a classic NLU problem. They used the Pragmatic Color Describer to introduce Grounding. When you describe a color in language, the words you pick depend on the surrounding context. Enter our orange cats:

A light orange cat

A deep orange cat

When describing the two orange cats we can distinguish them as the lighter orange cat vs the darker one. If the comparison cat is not orange, we do not need to specify the shade; we just say orange cat. For example:

The two cats side by side

When we use contrastive language we assume the listener shares our understanding of color shades. That shared understanding is Grounding. More on the Pragmatic Color Describer later.

A brief history of NLU

The instructors gave a short history of NLU

  • 1966: Eliza
  • 1988: Latent Semantic Analysis
  • January 2011: IBM Watson beats Jeopardy! Champions
  • October 2011: Apple Siri launches in beta
  • April 2014: Microsoft Cortana demoed
  • May 2016: Google Assistant

CS224u topics

They then listed the NLU topics for the term: eight topics, two lectures each. Plenty of material.

  1. Vector-space models
  2. Sentiment analysis
  3. Relation extraction
  4. Natural Language Inference
  5. Grounding
  6. Contextual word representations
  7. Adversarial testing
  8. Methods and metrics

The professor then sketched progress in each area and recommended SUPERINTELLIGENCE - NICK BOSTROM. I found it worthwhile: it is about the future of AI and the social issues that might follow. Little technical content, simple language. A decent English-practice read if you have time.

Finally they pointed to a few starter tutorials: setting up the course virtualenv, intro to PyTorch and NumPy, etc. Strongly recommend following the setup tutorial and cloning the course GitHub; there is a lot of useful material.

CS224U virtual environment setup tutorial

Lecture 2, Distributed word representations

This lecture covers the most basic but still central idea in NLP: word vectors. Prof. Potts started from co-occurrence matrices and went through GloVe, Word2Vec, and related methods.

Vector representations are a core idea in deep learning; the running joke is “everything can be an embedding.” In retail, every product and every store can be a high-dimensional vector. You can study product relationships the same way. Alibaba, Walmart, and Amazon have all done substantial work here. A Product2Vec paper if you want to dig in ( Studying Product Competition Using Representation Learning).

Word vector representations are now the default effective method in the field, but they rest on a deep linguistic idea. It goes back to the question: what defines the meaning of a word? The answer here is that the other words that appear with it in a sentence define its meaning.

You shall know a word by the company it keeps. - Firth (1957)

“distributional statements can cover all of the material of a language without requiring support from other types of information. - Firth (1957)

The simplest co-occurrence matrix captures meaning by counting how often words appear together.

How to build a co-occurrence matrix

Building a co-occurrence matrix has two main parameters.

  1. Window Size: the range around a center word in which co-occurrence is counted
  2. Scaling: used to adjust the co-occurrence values

Example from a line of Shakespeare: “For thy sweet love remembered such wealth brings That then I scorn to change my state with kings.”

Co-occurrence matrix

Choice of these two parameters follows this logic

  • Larger window size and smoother scaling capture more semantic information
  • Smaller window size and heavier scaling capture more syntactic information

Compute the co-occurrence matrix over a huge collection of sentences and documents; the counts of how often each word appears with every other word give the simplest word vectors. Each row in the figure below can be treated as a word embedding. Raw counts are not enough; next we look at statistical methods that improve vector quality. Window-based co-occurrence has an obvious flaw: words like the, and, or, is co-occur with almost everything but carry little meaning. Later we cover reweighting methods such as PMI and PPMI that mitigate this.

Word-by-word design matrix

How to compare two vectors

Once words are vectors we need systematic ways to compare them. The course covers:

  1. Euclidean distance
  2. Euclidean distance with L-2
  3. Cosine distance
  4. Matching-based methods
  5. KL divergence

Euclidean distance

Distance between n-dimensional vectors u, v:

\[{euclidean(u, v)=\sqrt{\sum_{i=1}^{n}{|u_i - v_i|^2}}}\]

Euclidean distance is the straight-line distance between two points. If two vectors point the same way but have different magnitudes, the Euclidean distance is still large. For word vectors direction usually matters more than magnitude; vectors that point the same way tend to have similar meaning, so Euclidean distance is not a good comparison method.

Euclidean distance with L-2 norm

If we L2-normalize the vectors, every vector has magnitude 1. Euclidean distance then ignores magnitude and only reflects direction.

Cosine distance

Cosine distance measures only the angle between vectors; magnitude is irrelevant. It is one of the most common ways to compare word vectors in NLP.

Cosine similarity between two vectors

\[{cosine(u, v)=1 - {\frac{\sum_{i=1}^{n}{u_i \times v_i}}{||u||_2 \times ||v||_2}}}\]

One thing worth noting: ranking by Euclidean distance after L2 normalization is the same as ranking by cosine distance. The numeric values differ, but the order when comparing multiple vectors is identical. In word-vector applications they can be treated as equivalent.

Matching-based methods

Matching-based methods are not used much in NLU. The course only mentioned them briefly; I just list the formulas here.

Matching-based distance measures

KL divergence

KL divergence is a way to compare two probability distributions. For a deeper dive see KL divergence.

\[D(p || q) = \sum_{i=1}^{n} {p_ilog(\frac{p_i}{q_i})}\]

In NLU, to compare two word vectors we first turn each vector into a probability distribution that sums to 1, then apply KL divergence. The lecture gave this example. A, B, and C have already been turned into distributions that sum to 1. The method only works if the vectors can be interpreted as distributions; negative values make it inapplicable.

KL divergence

Normalizing the co-occurrence matrix

We have covered how to build a co-occurrence matrix and how it yields word vectors. Frequency-based vectors have a serious problem: raw frequency is not very meaningful for language understanding. A simple example: 妖魔鬼怪 vs 魑魅魍魉. The two idioms mean essentially the same thing, but 妖魔鬼怪 appears far more often in student essays because 魑魅魍魉 is hard to write and you lose points if you get it wrong. Frequency is therefore a poor signal; we can reduce its effect with normalization. L2 normalization and converting the vector to a probability distribution are two options. Next is a common method: Observed/Expected.

Observed/Expected is

Observed over expected weighting

How should we interpret the expected count? It is the expected frequency if the row word and column word were independent. In the figure, keep appears 60 times and tabs 21 times. If they were independent, the probability they co-occur would be P(keep) * P(tabs) = 60/101 * 21/101. Observed/Expected compares the actual count with that independence assumption.

From Observed/Expected we also get Pointwise Mutual Information (PMI) and Positive PMI (PPMI). PMI is log(Observed/Expected); PPMI sets every negative PMI (from the log) to 0. Note that log(0) is undefined in math, but in this setting we take log(0)=0.

TF-IDF

TF: Term frequency: P(word | document) IDF: Inverse document frequency (IDF)

Detailed explanation of IDF

The professor also mentioned t-test weighting, pairwise distance matrices, etc., but they are not used much in this course so I will not expand on them.

Dimensionality reduction

Co-occurrence matrices are huge; a word representation can easily have thousands or tens of thousands of dimensions. Using them raw does not extract meaning well, so we need dimensionality reduction. The course covers four families of methods:

  • Latent Semantic Analysis
    • Singular value decomposition (SVD)
    • Principal Components Analysis (PCA)
    • Non-negative Matrix Factorization (NMF)
    • Probabilistic LSA (PLSA; Hofmann 1999)
    • Latent Dirichlet Allocation (LDA; Blei et al. 2003)
    • t-SNE (van der Maaten and Hinton 2008)
  • Autoencoders
  • GloVe
  • Word2Vec

The methods under LSA are less common in NLP today, and SVD and PCA are basic dimensionality-reduction techniques, so I will not go into them. We focus on Autoencoder, GloVe, and Word2Vec.

Autoencoder

An autoencoder is a deep neural architecture used for dimensionality reduction. The lecture showed a simple autoencoder:

Autoencoder architecture

The main difference from a usual network is that a standard net needs an input X and a target Y. Training an autoencoder only needs X, because the input and the target are both X. The objective is to make the output X_hat equal the input X. The code below is the autoencoder in the figure; input_dim_ and output_dim_ are equal (the dimension of X).

import torch
import torch.nn as nn
def define_graph(self):
    return nn.Sequential(
        nn.Linear(self.input_dim_, self.hidden_dim),
        nn.Tanh(),
        nn.Linear(self.hidden_dim, self.output_dim_))

GloVe

GloVe is a landmark result in NLP; almost every NLP course covers it. Here is a short look at how it works. The GloVe objective is to learn word vectors whose dot products are proportional to their co-occurrence probabilities.

Before GloVe there were two main families of word-vector methods: 1. Matrix Factorization Methods based on the co-occurrence matrix (everything we discussed above). 2. Shallow window-based methods that use a local context window. That family includes the skip-gram model and the continuous bag-of-words model. Both families have clear weaknesses. In the first, high-frequency words such as the, is, and do not represent meaning well. The second family only sees a local window, so it cannot fully exploit a large corpus.

Comments

Loading…
Jazzik