Sparse Word Embeddings Using ℓ1 Regularized Online Learning

Fei Sun, Jiafeng Guo, Yanyan Lan, Jun Xu, Xueqi Cheng

Introduction

Standard word embedding models, such as Word2Vec, typically generate dense vectors where information is distributed across all dimensions. While effective for many downstream tasks, these "black box" representations lack human interpretability, as individual dimensions rarely correspond to discrete semantic concepts. Previous attempts to introduce sparsity often relied on computationally expensive post-processing techniques that do not scale well to large datasets.

This paper introduces a novel approach to learning sparse word embeddings directly during the training phase. By incorporating $\ell_1$ regularization into the Continuous Bag of Words (CBOW) architecture and utilizing the Regularized Dual Averaging (RDA) algorithm, the authors produce vectors that are over 90% sparse while matching or exceeding the performance of traditional dense models.

Methodology

The proposed method modifies the standard CBOW model through three primary components:

  1. $\ell_1$ Regularization: An $\ell_1$ penalty is added to the word vectors to encourage sparsity, effectively pushing many parameters toward zero.
  2. Regularized Dual Averaging (RDA): Unlike standard Stochastic Gradient Descent (SGD), which often fails to produce exact zeros in an online setting due to gradient noise, RDA tracks the running average of gradients. This allows the optimization process to "snap" weights to zero, achieving true sparsity.
  3. Negative Sampling: To maintain computational efficiency and scalability for billion-word corpora, the model employs negative sampling to approximate the softmax function.

Experimental Results

The model was trained on a 1-billion-word Wikipedia dump and evaluated across several word similarity and analogy tasks, including WordSim-353, SimLex-999, and the Rare Word (RW) dataset.

Performance and Sparsity

The Sparse CBOW model achieved a sparsity level of 90.06%. Despite this significant reduction in active parameters, it outperformed dense counterparts on several benchmarks. Notably, on the challenging SimLex-999 dataset, Sparse CBOW achieved a score of 44.47, compared to 38.82 for dense CBOW.

Comparison of Sparse CBOW against dense and post-processed sparse models across various tasks.

Stability and Scalability

A key finding was the stability of the sparse model relative to vector dimensionality. While the performance of dense CBOW tends to degrade as dimensionality increases beyond a certain point (e.g., 300), Sparse CBOW maintains high performance even at 1000 dimensions. This suggests that the $\ell_1$ regularization acts as an effective safeguard against overfitting in high-dimensional spaces.

Average performance of CBOW and Sparse CBOW as a function of vector dimensionality.

Interpretability and Discussion

The sparse representations offer significantly better interpretability. In "word intrusion" tasks, dimensions in the Sparse CBOW model were found to be highly coherent. For instance, specific dimensions were observed to activate exclusively for clusters of related terms, such as statistical learning concepts (poisson, markov, bayesian).

While Sparse CBOW excels in semantic similarity, it slightly trails the best dense models in purely syntactic analogies, such as verb tense variations. This suggests that while sparsity captures semantic concepts effectively, dense representations may still hold an advantage for certain linguistic regularities. Future work may explore the addition of non-negativity constraints to further enhance interpretability.

Summary updated

Abstract

Recently, Word2Vec tool has attracted a lot of interest for its promising performances in a variety of natural language processing (NLP) tasks. However, a critical issue is that the dense word representations learned in Word2Vec are lacking of interpretability. It is natural to ask if one could improve their interpretability while keeping their performances. Inspired by the success of sparse models in enhancing interpretability, we propose to introduce sparse constraint into Word2Vec. Specifically, we take the Continuous Bag of Words (CBOW) model as an example in our study and add the ll regularizer into its learning objective. One challenge of optimization lies in that stochastic gradient descent (SGD) cannot directly produce sparse solutions with l1 regularizer in online training. To solve this problem, we employ the Regularized Dual Averaging (RDA) method, an online optimization algorithm for regularized stochastic learning. In this way, the learning process is very efficient and our model can scale up to very large corpus to derive sparse word representations. The proposed model is evaluated on both expressive power and interpretability. The results show that, compared with the original CBOW model, the proposed model can obtain state-of-the-art results with better interpretability using less than 10% non-zero elements.
BibTeX
@inproceedings{sun2016sparse,
  author = {Fei Sun and Jiafeng Guo and Yanyan Lan and Jun Xu and Xueqi Cheng},
  title = {{Sparse Word Embeddings Using ℓ1 Regularized Online Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=FBiJp62Fwot},
}
Figure