Fast Dictionary Learning with a Smoothed Wasserstein Loss

Antoine Rolet, Marco Cuturi, Gabriel PeyréAISTATS 2016 · OpenReview

Abstract

We consider the dictionary learning problem when observations are normalized histograms of features. Traditional non-negative matrix factorization (NMF) approaches using Euclidean or Kullback-Leibler fitting errors are often "blind" to feature similarities. We propose using the Wasserstein distance as a fitting error to leverage prior knowledge of feature relationships. Our method utilizes entropic regularization and Fenchel duality to create a scalable, smooth optimization framework. We demonstrate the effectiveness of this approach on face images and text documents, including cross-lingual topic modeling.

1. Introduction

Dictionary learning seeks to represent data as linear combinations of a few basis elements. In applications like computer vision or natural language processing, data is often represented as histograms. Standard loss functions like KL divergence treat each bin independently, ignoring the underlying geometry of the feature space. For example, a small spatial shift in an image or a synonym in a text document can lead to large reconstruction errors under standard metrics. The Wasserstein distance, or Earth Mover's Distance (EMD), addresses this by incorporating a ground metric, but its high computational cost has limited its adoption in NMF.

2. Smoothed Wasserstein NMF

To overcome computational barriers, we introduce a smoothed Wasserstein loss. The smoothing is achieved through entropic regularization, which replaces the hard constraints of the transport plan with a soft, entropy-penalized version. This allows the use of Sinkhorn's algorithm, which scales linearly with the number of features.

Furthermore, by formulating the problem through Fenchel duality, we avoid the non-smoothness of the original Wasserstein distance. We derive a dual objective with a closed-form gradient, enabling the use of efficient block-coordinate descent and projected gradient methods. This approach allows the dictionary to "move" mass across the feature space, capturing semantic or spatial relationships that are invisible to separable losses.

3. Experimental Results

We evaluated our method against standard NMF baselines across several datasets, focusing on both geometric recovery and computational efficiency.

3.1 Toy Data and Geometry

On toy Gaussian mixtures, Wasserstein NMF demonstrates a superior ability to recover the underlying data distribution compared to KL-based methods. While KL NMF produces fragmented basis elements, the Wasserstein approach recovers intuitive "blobs" that match the data's geometric structure.

Comparison of KL NMF and Wasserstein NMF on toy data samples.

3.2 Performance and Scalability

On the ORL face dataset, our method achieved a 20-90 second runtime, a significant improvement over the 20 minutes required by previous EMD-NMF implementations. In text classification tasks (BBCsport), Wasserstein NMF reduced the error rate to 5.4%, compared to 9.4% for KL-NMF and 12.8% for Euclidean NMF. The ground metric allows the model to understand that missing words in a document are semantically related to words present in the dictionary.

3.3 Cross-Lingual Topic Modeling

A key advantage of the Wasserstein loss is the ability to learn across different feature spaces. By using bilingual word embeddings as a ground metric, we successfully learned French topics from an English corpus. This demonstrates that the dictionary can be learned in a "target" space that differs from the "source" space.

Cross-lingual dictionary learning using shared embeddings.

4. Conclusion

The proposed smoothed Wasserstein NMF framework provides a scalable and geometrically-aware alternative to traditional dictionary learning. By adding a small amount of entropy, we turn a combinatorial problem into a matrix balancing problem, allowing us to scale to dimensions previously impossible for Wasserstein-based methods. While the problem remains biconvex and requires careful initialization, the speedups and accuracy gains on high-dimensional data are substantial. Future research will explore additional regularizers for dictionary sparsity and further optimizations for large-scale vocabularies.

Summary updated

Abstract

We consider in this paper the dictionary learning problem when the observations are normalized histograms of features. This problem can be tackled using non-negative matrix factorization approaches, using typically Euclidean or Kullback-Leibler fitting errors. Because these fitting errors are separable and treat each feature on equal footing, they are blind to any similarity the features may share. We assume in this work that we have prior knowledge on these features. To leverage this side-information, we propose to use the Wasserstein (\textita.k.a. earth mover’s or optimal transport) distance as the fitting error between each original point and its reconstruction, and we propose scalable algorithms to to so. Our methods build upon Fenchel duality and entropic regularization of Wasserstein distances, which improves not only speed but also computational stability. We apply these techniques on face images and text documents. We show in particular that we can learn dictionaries (topics) for bag-of-word representations of texts using words that may not have appeared in the original texts, or even words that come from a different language than that used in the texts.
BibTeX
@inproceedings{rolet2016fast,
  author = {Antoine Rolet and Marco Cuturi and Gabriel Peyré},
  title = {{Fast Dictionary Learning with a Smoothed Wasserstein Loss}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=TKJKSe672E},
}
Figure