Efficient Non-parametric Estimation of Multiple Embeddings per Word in Vector Space

Motivation

• Single-vector representations ignore polysemy and homonymy, causing words such as plant to average distinct contextual meanings.This can pull unrelated words associated with different senses toward one another.Source: §1 · pp. 1–2

Prior limitations

• Prior multi-sense methods pre-cluster token contexts, relabel the corpus, and then learn embeddings in a separate second step.Pre-clustering prevents joint learning of sense-discriminated vectors and clustering.Source: §1 · p. 2
• Prior approaches also use a fixed number of senses per word type and can be computationally expensive at billion-token scale.Huang et al. took one week to learn multiple embeddings for 6,000 vocabulary words on nearly a billion tokens.Source: §1 · p. 2

Proposed approach

• MSSG jointly learns sense-discriminated vectors and token-context assignments, using emerging sense representations to improve clustering.The method performs sense discrimination and embedding learning together during online training.Source: §1 · p. 2
• NP-MSSG non-parametrically discovers a varying number of senses per word type, while online joint training improves speed and scalability.The paper reports training on nearly a billion tokens in less than 6 hours, a 27x improvement over Huang et al.Source: §1 · p. 2

Results

• The methods surpass previous state of the art on SCWS and WordSim353 and dramatically outperform Huang et al. on Google Analogy.The paper also compares qualitative nearest-neighbor results across single-sense, parametric, and non-parametric models.Source: §1 · p. 2

Neural embedding models

• Neural language models replace n-gram conditional tables with networks that represent each word token using a small vector.This line of work estimates neural-network parameters and embeddings from data.Source: §2 · p. 2
• Skip-gram-style log-linear models remove hidden layers, use larger context windows and aggressive subsampling, and target useful word representations for downstream tasks.Their emphasis is representation quality rather than low perplexity.Source: §2 · p. 2

Alternative methods

• High-quality word vectors can also be estimated without neural or log-linear models, including with Canonical Correlation Analysis.Dhillon and Ungar use CCA to estimate word vector representations.Source: §2 · p. 3

Applications

• Word embeddings and Brown-cluster features have been applied across tasks including named entity recognition, parsing, chunking, sentiment analysis, and paraphrase detection.Embeddings have also been used to represent paragraphs and documents.Source: §2 · p. 3

Multi-sense embeddings

• Reisinger and Mooney and Huang et al. learn multiple embeddings after clustering contexts as a preprocessing step.Huang et al. add global document context and recursive neural networks for dense, low-dimensional embeddings.Source: §2 · p. 3

Model

• Skip-gram learns word embeddings that are useful for predicting surrounding words in a sentence.Each word w has a vector v(w) in R^d, where d is the embedding dimensionality.Source: §3 · p. 3

Training objective

• The training data pairs each target word with observed context words and randomly sampled noisy context words.D+ contains observed word-context pairs, while D− contains pairs with sampled noisy contexts.Source: §3 · p. 3
• The embeddings are learned by maximizing an objective over the observed positive and sampled negative word-context pairs.The objective is defined over the training sequence w1, w2, ..., wT.Source: §3 · p. 3

Context construction

• For each training word, the context contains up to Rt words on both the left and right, with Rt sampled uniformly from 1 through the maximum window size N.The context is ct = {w_t−R_t, ..., w_t−1, w_t+1, ..., w_t+R_t}.Source: §3 · p. 3

Negative sampling

• Noisy context words are sampled independently for each observed context word from a distribution based on the unigram frequencies and a normalization constant.The number of noisy samples per target context is S.Source: §3 · p. 3

Joint learning

• MSSG performs sense discrimination and embedding learning jointly, allowing current sense representations to participate in context clustering.This joint procedure is the central difference from previous approaches.Source: §4 · p. 4

Model representation

• MSSG associates each word with one global vector, K sense vectors, and K context-cluster centers, all with embedding dimension d.K is a model hyperparameter.Source: §4 · p. 4

Sense assignment

• For each token, MSSG represents its context by averaging the global vectors of the surrounding words.Global context vectors are used instead of context-word sense vectors to avoid predicting every context word’s sense.Source: §4 · p. 4
• The token’s sense is assigned to the context cluster whose center is most similar to the averaged context representation.The hard assignment resembles k-means, and experiments use cosine similarity.Source: §4 · p. 4

Online updates

• After assigning a sense, training updates that sense vector, the global vectors of observed and noisy context words, and the selected context-cluster center.The observed and noisy pairs follow the same construction as Skip-gram.Source: §4 · p. 5

Non-parametric sense learning

• NP-MSSG learns a varying number of senses per word type instead of using MSSG’s fixed number.The number of senses is learned during training rather than specified uniformly in advance.Source: §5 · p. 5

Online clustering

• A new sense and context cluster are created online when a word’s context has similarity below λ to every existing cluster center.The threshold λ is a model hyperparameter governing when additional senses are introduced.Source: §5 · p. 5

Context representation

• For each word occurrence, the context is represented by the average of its surrounding words’ global vectors.The surrounding context consists of words within the selected window around the target token.Source: §5 · p. 5

Sense assignment

• The method selects the closest existing sense by comparing context similarity with each cluster center, or creates a new sense when none meets the threshold.The selected cluster center is computed as the average of the vector representations of contexts assigned to that cluster.Source: §5 · p. 5

Model relationship

• NP-MSSG changes only word-sense discrimination; its objective function and probabilistic model remain those of MSSG.Thus, the non-parametric variant differs from MSSG in how senses are selected or created, not in the underlying word-context model.Source: §5 · p. 5

Experimental setup

• The evaluation uses a 990-million-token Wikipedia corpus, removes words occurring fewer than 20 times, and uses a maximum context window of five words on each side.MSSG uses three senses, while NP-MSSG learns the number of senses during training.Source: §6 · p. 6

Efficiency

• Training time improves substantially over Huang et al. while remaining within an order of magnitude of Skip-gram on similarly sized corpora and single-machine implementations.The experiments compare single-machine training times across models.Source: §6 · p. 6

Nearest neighbors

• Table 2 reports semantically coherent nearest neighbors for discovered senses, while NP-MSSG creates a reasonable number of senses.Neighbors are computed using cosine similarity between each sense embedding and other words’ context embeddings.Source: Table 2 · p. 6, §6.1 · p. 6

Word similarity

• SCWS evaluates in-context similarity using Spearman correlation between model scores and human judgments; avgSimC weights sense-pair similarity by contextual fit.GlobalSim ignores senses, whereas localSim independently selects one context-supported sense for each word.Source: §6.2 · p. 7
• 69.3 is MSSG’s best SCWS avgSimC score, exceeding Huang et al.’s 65.7% previous state of the art; performance also improves with larger embedding dimensions.NP-MSSG performs best for globalSim, avgSim, and localSim according to Table 4.Source: §6.2 · p. 8, Table 4 · p. 8

• MSSG jointly learns word-sense discrimination and multiple embeddings for each word type.Source: §7 · p. 11
• The non-parametric method automatically estimates a varying number of senses per word type.Source: §7 · p. 11
• The approach achieves new state-of-the-art results on word similarity in context.Source: §7 · p. 11
• Nearly 1 billion tokens are processed in less than 6 hours on one machine.Source: §7 · p. 11