N1 Representing Words

Expressing and processing the nuance and wildness of language—while achieving the strong transfer of information that language is intended to achieve—makes representing words an endlessly fascinating problem.

To better compute with words, we need to represent them as vectors. So we move to some methods. Remember our goal.

Goal

Learn rich representations of complex objects from data to get the word vectors

Independent Word Vectors

One-hot Vectors: The simplest way to represent words is to use a vector of length $V$, where $V$ is the number of words in the vocabulary. Each word is represented by a vector of length $V$, where the $i-th$ element of the vector is 1 if the word is the $i-th$ word in the vocabulary, and 0 otherwise.

For example, a vocabulary set $\{...,tea,...,coffee,...,cat,...,dog\}$ will be represented as:

$$v_{\text{tea}}=[0,0,1,\dots ,0]v_{\text{coffee}}=[\dots ,0,0,1,\dots ]\text{\hspace{1em}(1)}$$ $$v_{tea}^{\top }{v}_{coffee}=v_{coffee}^{\top }{v}_{tea}=0\text{\hspace{1em}(2)}$$

Limitation: Well, one-hot vector encoding is very simple to build, but it has a big problem—sparsity—every two words are orthogonal with NO similarities at all. But in fact there are many words that share the similar meaning or context. Then we go next step.

---

Human-annotated Word Vectors

There is grammatical information, like plurality, there’s derivational information, like how the runners is something like the verb to run plus a notion of “doer”, or agent (think one who runs.) There’s also semantic information, like how runners might be a hyponym of humans, or animals, or entities. (A hyponym is a member of an is-a relationship; e.g., a runner is a human.)

1. WordNet ¹: it annotates for synonyms, hyponyms, and other semantic relations;
2. UniMorph ²: it annotates for morphology (subword structure) information across many languages.

$$v_{\text{tea}}=\left[\begin{array}{c}0\\ 0\\ 1\\ ⋮\\ 1\end{array}\right]\begin{array}{l}\text{(plural noun)}\\ \text{(3rd singular verb)}\\ \text{(hyponym-of-beverage)}\\ ⋮\\ \text{(synonym-of-chai)}\end{array}\text{\hspace{1em}(3)}$$

Limitation

• Updating these resources is costly and they’re always incomplete.
• A very high-dimensional vector (much larger than the vocabulary size) to represent all of these categories.

---

Distributional Vectors

Take part of the data (maybe a word in a sentence) and attempt to predict other parts of the data (other words) with it. While simple, this is one of the most influential and successful ideas in all of modern NLP.

Co-occurrence matrices

This is a document-level method. It is a matrix $X$ ($X_{tea}\in {\mathbb{R}}^{|\mathcal{V}|}$, a row in the matrix) where each row and column represents a word in the corpus. The cell (i, j) represents the number of times word i and word j appear together in a specific window size throughout the corpus.

$$[It’shotanddelicious.[Ipoured[the\underset{centerword}{\underbrace{tea}}for{]}_{1}myuncle{]}_3{]}_{document}$$

Feature

• Larger notions of co-occurrence (e.g., large windows or documents) lead to more semantic or even topic - encoding representations; shorter windows lead to more syntax - encoding representations.
• It’s a sparse representation based on statistics.

Limitation

• $\mathcal{V}$ - sized vectors are unweildy for large vocabularies (usually > 10k).
• Overemphesize of the very common words like: The, a, etc.

Pointwise mutual information (PMI) matrix

PMI³ is the log of the ratio of the joint probability of a word pair to the product of the individual probabilities of each word.

For original PMI, when $PMI(w,c)=\log 0=-\infty$, we set it to 0 in a common way. A more consistent way is to use the PPMI (positive PMI)⁴

$$\begin{array}{rl}\text{PMI}(w,c)& =\ln \frac{p(w,c)}{p(w)p(c)}=\ln \frac{N(w,c)\cdot N}{N(w),N(c)}\\ \text{PPMI}(w,c)& =\max (\text{PMI}(w,c),,0)\end{array}\text{\hspace{1em}(4)}$$

Limitation:

• A rare word pair may have a high PMI, but it’s not a good representation of the word pair.
• For example, A rare context $c$ that co-occurred with a target word $w$ even once, will often yield relatively high PMI score because $P(c)$

Latent semantic analysis (LSA)⁵

In traditional LSA, we use the co-occurrence matrix (originally, the row represents word and the colomn represents doc) to compute a lower dimension vector for word. But we can also use PMI matrix to do so.

Word2Vec model⁶

Ok, rethink about the problem we are facing now and our goal of building word vector. We want it to be:

1) Smaller (better in hundreds dimensions)
2) and Representing Ability (syntatic & semantic)

Skip-gram

Idea

Predict the context words using the center word. $P{(}^{\prime }i{t}^{\prime }{,}^{\prime }seem{s}^{\prime }{,}^{\prime }sh{e}^{\prime }{,}^{\prime }yo{u}^{\prime }{,}^{\prime }s{o}^{\prime }{,}^{\prime }muc{h}^{\prime }{|}^{\prime }love{s}^{\prime })$

graph TD
    loves((loves))
    loves--> It((It))
    loves --> seems((seems))
    loves --> she((she))
    loves --> you((you))
    loves --> so((so))
    loves --> much((much))

• Given a corpus, build a low-dimensional vector representation for each word.

1. divide the corpus into sentences.
2. set a window size.
3. extract the center word and the context words around it within the window size.
4. build two embedding matrices (low dimension), $V$ for center words and $U$ for context words.
5. OUR GOAL: find the best $V$ and $U$ make the context words close to the center words which is resonable semantically.
6. suppose that these words within a window size in a document should have something meaningful in common. So the probability of the co-occurrence of these words shall be as high as it could be. Then do some math ↓ .

$V$? $U$?

• Indeed, there will be two embedding matrices, so each word has two embedding vectors: one as center word and the other as context word.
• However, practically we only use center word embedding matrix $V$ or we use average of $U$ and $V$.

Algorithm

for some convenience, here $w_i=v_c$ as the center word and $w_{i+j}=u_o$ as the context words, equals that $P_{U,V}(u_o|v_c)=P_{U,V}(w_{i+j}|w_i)$; $k$ is the window size and $i-k$ is the start index of the window. $T$ is the length of the sentence $d$ and $d$ is one sentence in the corpus $D$.

1. Objective is the probability of context word $u_o$ given center word $v_c$ as:

$$P_{U,V}(u_o|v_c)=\frac{exp(u_o^{\top }{v}_c)}{{\sum }_{w\in \mathcal{V}}exp(u_w^{\top }{v}_c)}\text{\hspace{1em}(4a)}$$

• Then we want to maximize the probability:

$$\prod _{d\in D}\prod _{i=1}^T\prod _{j=-k,j\ne 0}^k{P}_{U,V}(w_{i+j}|w_i)\text{\hspace{1em}(4b)}$$

2. Maximize $P_{U,V}(u_o|v_c)$, which is equivalent to minimize the negative log-likelihood, and for the whole corpus $D$, define the negative log-likelihood Loss:

$$L(U,V)=-\sum _{d\in D}\sum _{i=1}^T\sum _{j=-k,j\ne 0}^k\log P_{U,V}(w_{i+j}|w_i)\text{\hspace{1em}(5)}$$

3. Work out the gradient of Loss with respect to $v_c$:

$${\nabla }_{v_c}L(U,V)=-\sum _{d\in D}\sum _{i=1}^T\sum _{j=-k,j\ne 0}^k\underset{focuseonthis}{\underbrace{{\nabla }_{v_c}\log P_{U,V}(w_{i+j}|w_i)}}\text{\hspace{1em}(6)}$$

4. Propogate the gradient gradually (change $P_{U,V}(w_{i+j}|w_i)=P_{U,V}(u_o|v_c)$ back), and with Eqn4 we can get:

$$\begin{array}{rl}{\nabla }_{v_c}\log P_{U,V}(u_o\mid v_c)& ={\nabla }_{v_c}\log \frac{\exp (u_o^{\top }{v}_c)}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}\\ & =\underset{PartA}{\underbrace{{\nabla }_{v_c}\log \exp (u_o^{\top }{v}_c)}}-\underset{PartB}{\underbrace{{\nabla }_{v_c}\log \sum _{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}}\end{array}\text{\hspace{1em}(7)}$$

5. Part A:

$${\nabla }_{v_c}\log \exp (u_o^{\top }{v}_c)={\nabla }_{v_c}{u}_o^{\top }{v}_c=u_o\text{\hspace{1em}(8a)}$$

6. Part B:

$$\begin{array}{rl}{\nabla }_{v_c}\log \sum _{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)& =\frac{1}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}{\nabla }_{v_c}\sum _{x\in \mathcal{V}}\exp (u_x^{\top }{v}_c)\\ & =\frac{1}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}\sum _{x\in \mathcal{V}}{\nabla }_{v_c}\exp (u_x^{\top }{v}_c)\\ & =\frac{1}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}\sum _{x\in \mathcal{V}}\exp (u_x^{\top }{v}_c){\nabla }_{v_c}{u}_x^{\top }{v}_c\\ & =\frac{1}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}\sum _{x\in \mathcal{V}}\exp (u_x^{\top }{v}_c)u_x\\ & =\sum _{x\in \mathcal{V}}\underset{Eqn4!}{\underbrace{\frac{\exp (u_x^{\top }{v}_c)}{{\sum }_{w\in \mathcal{V}}\exp (u_w^{\top }{v}_c)}}}{u}_x\\ & =\underset{Expectation}{\underbrace{\sum _{x\in \mathcal{V}}{P}_{U,V}(u_x|v_c)u_x}}\\ & =\mathbb{E}[u_x](x\in \mathcal{V})\end{array}\text{\hspace{1em}(8b)}$$

> $w$ and $x$ both represent the each word in the vocabulary, counting independently in the same equation.

7. Put two parts together, we get the derivative of Loss with respect to $v_c$:

$${\nabla }_{v_c}L(U,V)=\sum _{d\in D}\sum _{i=1}^T\sum _{j=-k,j\ne 0}^k-(u_o-\mathbb{E}[u_w])(w\in \mathcal{V})\text{\hspace{1em}(9)}$$

Summary

• Now that we’ve got a very simple model as shown in Eqn 1~9.
• However when we implement it on computers, it’s not possible to go through all the words in the vocabulary for each center word to calculate $P_{U,V}(u_w|v_c)u_w$.
• Negative sampling is a method to address this problem.
• Discussed in Traing methods

Continuous Bag-of-Words (CBOW)

Idea

Predict the center word using the context words. $P{(}^{\prime }love{s}^{\prime }{|}^{\prime }i{t}^{\prime }{,}^{\prime }seem{s}^{\prime }{,}^{\prime }sh{e}^{\prime }{,}^{\prime }yo{u}^{\prime }{,}^{\prime }s{o}^{\prime }{,}^{\prime }muc{h}^{\prime })$

graph TD
    loves((loves))
    It((It)) --> loves
    seems((seems)) --> loves
    she((she)) --> loves
    you((you)) --> loves
    so((so)) --> loves
    much((much)) --> loves

Algorithm CBOW is similar to Skip-gram, but predicting is inverse.

Similarly

1. Objective:

$$P_{U,V}(u_c|v_{o_1},\dots ,v_{o_{2k}})=\frac{exp(\frac{1}{2k}{u}_c^{\top }(v_{o_1}+,\dots ,v_{o_{2k}}))}{{\sum }_{w\in \mathcal{V}}exp(\frac{1}{2k}{u}_w^{\top }(v_{o_1}+,\dots ,v_{o_{2k}}))}\text{\hspace{1em}(12)}$$

2. Suppose ${\mathcal{W}}_o=\{o_1,\dots ,o_{2k}\}$ and ${\bar{v}}_o=\frac{1}{2k}(v_{o_1}+,\dots ,v_{o_{2k}})$, then we can get the objective:

$$P_{U,V}(u_c|{\mathcal{W}}_o)=\frac{exp(u_c^{\top }{\bar{v}}_o)}{{\sum }_{w\in \mathcal{V}}exp(u_w^{\top }{\bar{v}}_o)}\text{\hspace{1em}(13)}$$

3. Negative log-likelihood Loss (take one element):

$$\begin{array}{rl}L(U,V)& =-\log P_{U,V}(u_c|{\mathcal{W}}_o)\\ & =-(u_c^{\top }{\bar{v}}_o-\log \sum _{w\in \mathcal{V}}exp(u_w^{\top }{\bar{v}}_o))\end{array}\text{\hspace{1em}(14)}$$

4. Gradient:

$$\begin{array}{rl}{\nabla }_{{\bar{v}}_o}L(U,V)& =-\frac{1}{2m}\left(u_c-\sum _{x\in \mathcal{V}}{P}_{U,V}(u_x|{\mathcal{W}}_o)u_x\right)\\ & =-\frac{1}{2m}\left(u_c-\mathbb{E}[u_w]\right)\end{array}\text{\hspace{1em}(15)}$$

Global Vectors (GloVe) ⁷

GloVe Idea

This is a great idea that combines both matrix factorization and shallow window-based methods.

1. Notation: Let the matrix of word-word co-occurrence counts be denoted by $X$ , whose entries $X_{ij}$ tabulate the number of times word j occurs in the context of word i. Let $X_i={\sum }_k{X}_{ik}$ be the number of times any word appears in the context of word i. Finally, let $P_{ij}=P(j|i)=X_{ij}/X_i$ be the probability that word j appear in the context of word i.
2. Co-occurrence probabilities: If we take three words like $i=ice$, $j=steam$ and $k=solid,gas$, then we expect the ratio $P_{ik}/P_{jk}$ to be some value bigger when k is close to i and smaller when k is close to j.

$$\begin{array}{rl}\frac{P_{ik}}{P_{jk}}& =F(w_i,w_j,\widetilde{w_k})\\ & =F((w_i-w_j{)}^{\top }\widetilde{w_k})\\ & =\frac{F(w_i^{\top }\widetilde{w_k})}{F(w_j^{\top }\widetilde{w_k})}\\ & =\frac{P_{ik}/P_k}{P_{jk}/P_k}\end{array}\text{\hspace{1em}(16)}$$

Where F is $exp$. We can get the relations between word vectors and the co-occurrence counts ↓ Objective

$$\begin{array}{rl}{w}_i^{\top }\widetilde{w_k}& =\log (P_{ik})\\ & =\log (X_{ik})-\log (X_i)\\ & \to toeraselog(X_i)andkeepsymmetry\\ w_i^{\top }\widetilde{w_k}+b_i+\widetilde{b_k}& =\log X_{ik}\end{array}\text{\hspace{1em}(17)}$$

For Eqn. 17, there is one drawback: it weighs the co-occurrence counts equally. But in fact we want give less weight to less common words and fixed weights to the most common words (like the, a).

3. Loss:

$$\begin{gathered} J=\sum _{i,j=1}^{V}f(X_{ij})(w_i^{\top }\widetilde{w_j}+b_i+\widetilde{b_j}-\log X_{ij}{)}^2 \\ f(x)=\{\begin{array}{l}(x/x_{max}{)}^{\alpha },ifx<x_{max}\\ 1,otherwise\end{array}\text{\hspace{1em}(18)} \end{gathered}$$

Where $\alpha =3/4$ and $x_{max}=100$

Relations with Word2Vec

1. The Eqn.5 can be:

$$\begin{gathered} J=-\sum _{ \\ \begin{array}{c}i\in corpus\\ j\in context(i)\end{array}}\log Q_{ij}\text{\hspace{1em}(19)} \end{gathered}$$

2. If we use the co-occrence matrix $X$, we can get:

$$\begin{array}{rl}J& =-\sum _{i=1}^V\sum _{j=1}^V{X}_{ij}\log Q_{ij}\\ & =-\sum _{i=1}^V{X}_i\sum _{j=1}^V{P}_{ij}\log Q_{ij}\\ & =\sum _{i=1}^V{X}_{i}corross\_entropy(P_i,Q_i)\end{array}\text{\hspace{1em}(20)}$$

3. While cross_entropy is not good to capture the distribution with long tails. Then introduce the least square loss:

$$\begin{array}{rl}\hat{J}& =\sum _{i,j}{X}_i(\widehat{P_{ij}}-\widehat{Q_{ij}}{)}^2\\ & =\sum _{i,j}{X}_i(w_i^{\top }\widetilde{w_j}-\log X_{ij}{)}^2\\ \hat{J}& =\sum _{i,j}f(X_{ij})(w_i^{\top }\widetilde{w_j}(+b_i+\widetilde{b_j})-\log X_{ij}{)}^2\end{array}\text{\hspace{1em}(21)}$$

---

Training Methods ⁸

1. Dynamic context window: The window size is dynamic and the weights of the context words are different. For example, a size-5 window will weigh its contexts by 5/5, 4/5, 3/5, 2/5, 1/5.
2. Subsampling: This is used to diluting very frequent words with a threshold of $t$. $p=1-\sqrt{\frac{t}{f}}$.
3. Delete rare words.
4. Context distribution smoothing: In order to smooth the original contexts’ distribution, all context counts are raised to the power of $\alpha =0.75$
5. Number of negative samples: $N=5$
6. Add context vectors or not
7. Vector normalization: None, Row, Column, Both

Negative sampling ⁹

Let’s re-look at the probability of the context word $u_o$ given the center word $v_c$:

$$P_{U,V}(u_o|v_c)=\frac{exp(u_o^{\top }{v}_c)}{{\sum }_{w\in \mathcal{V}}exp(u_w^{\top }{v}_c)}\text{\hspace{1em}(22)}$$

1. Notice that:

• The so-called probability here is not the same with the statistical probability. We just borrow the concept and want $P_{U,V}(u_o|v_c)$ is as high as possible. There are two components:
• The $exp$ function ensure the value to be positive while the partition term is to make the sum of all the $exp$ values to be 1. The non-negative function can also be done by sigmoid $\sigma =\frac{1}{1+exp(-x)}$.
• $exp(u_o^{\top }{v}_c)$ encourages the model to make $u_o$ more like $v_c$; ${\sum }_{w\in \mathcal{V}}exp(u_w^{\top }{v}_c)$ encourages the model to make all the other $u_w$ for $w\ne o$ less like $v_c$. We could still use the window sized context words to encorage but only sample $k$ other words in the vocabulary to discourage instead.

2. Then the Objective could be:

$$P_{U,V}(u_o|v_c)=\sigma (u_o^{\top }{v}_c)\sum _{l=1}^k\sigma (-u_l^{\top }{v}_c)\text{\hspace{1em}(23)}$$

3. Negative log-likelihood Loss (take one element):

$$\begin{array}{rl}L(U,V)& =-\log P_{U,V}(u_o|v_c)\\ & =-\log \left(\sigma (u_o^{\top }{v}_c)\sum _{l=1}^k\sigma (-u_l^{\top }{v}_c)\right)\\ & =-\log \sigma (u_o^{\top }{v}_c)-\log \sum _{l=1}^k\sigma (-u_l^{\top }{v}_c)\end{array}\text{\hspace{1em}(24)}$$

Evaluation ¹⁰

There are two schemes to evaluate the model:

1. Extransic
   • Use word embeddings as input to a downstream task and evaluate the performance like part-of-speech tagging and named-entity recognition.
   • It is not clear how it connects to other measures.
2. Intransisic
   • Test the syntactic or semantic relationship between words directly using query inventories.

Cosine similarity

$$similarity(a,b)=\frac{a\cdot b}{||a||\cdot ||b||}\text{\hspace{1em}(25)}$$

Absolute intransic evaluation

1. Relatedness These datasets contain relatedness scores for pairs of words; the cosine similarity of the embeddings for two words should have high correlation (Spearman or Pearson) with human relatedness scores.

2. Analogy This task was popularized by Mikolov. The goal is to find a term x for a given term y so that x : y best resembles a sample relationship a : b.

   $$\begin{gathered} \text{CosAdd}argmaxcos(b\ast ,a\ast -a+b)=argmaxcos(b\ast ,a\ast )-cos(b\ast ,a)+cos(b\ast ,b) \\ \text{CosMul}=argmax\frac{\cos (b\ast ,a\ast )\dot{\cos }(b\ast ,b)}{\cos (b\ast ,a)+\epsilon }\text{\hspace{1em}(26)} \end{gathered}$$

3. Categorization The goal is to recover a clustering of words into different categories. To do this, the corresponding word vectors of all words in a dataset are clustered and the purity of the returned clusters is computed with respect to the labeled dataset.

4. Selectional preference The goal is to determine how typical a noun is for a verb either as a subject or as an object (e.g., people eat, but we rarely eat people).

For Relatedness

• Query inventory: WordSim, MEN.
• (1) the frequency of rare words (2) the parts of speech of words and (3) abstractness vs. concreteness.

Comparative intransic evaluation

In comparative evaluation, users give direct feedback on the embeddings themselves, so we do not have to define a metric that compares scored word pairs.

Extrinsic evaluation

Extrinsic evaluations measure the contribution of a word embedding model to a specific task. There is an implicit assumption in the use of such evaluations that there is a consistent, global ranking of word embedding quality, and that higher quality embeddings will necessarily improve results on any downstream task. Different tasks favor different embeddings

Code Example

Simple code for skip-gram & CBOW with negative sampling

References

Footnotes

1. WordNet: a lexical database for English ↩

2. UniMorph 4.0: Universal Morphology ↩

3. Word association norms, mutual information, and lexicography ↩

4. Extracting Semantic Representations from Word Co-occurrence Statistics: A Computational Study ↩

5. Latent Semantic Analysis ↩

6. Efficient Estimation of Word Representations in Vector Space ↩

7. GloVe: Global Vectors for Word Representation ↩

8. Improving Distributional Similarity with Lessons Learned from Word Embeddings ↩

9. Negative Sampling for Word Embeddings ↩

10. Evaluation methods for unsupervised word embeddings ↩