Differentiable Expectation-Maximization for Set Representation Learning

Minyoung KimICLR 2022 · OpenReview

Introduction

This paper introduces DIEM (Differentiable Expectation-Maximization), a novel framework that treats set representation as a statistical data-fitting problem. By viewing set elements as samples from a Gaussian Mixture Model (GMM) and using differentiable EM steps to find the parameters, the authors create a flexible, regularized, and high-performing "set-to-vector" embedding that outperforms existing attention-based methods.

The Set Representation Problem

In machine learning, we often deal with "sets"—collections of data points where the order doesn't matter (permutation invariance) and the number of items can vary, such as a collection of atoms in a molecule or words in a sentence. The goal of set representation learning (or set2vec) is to compress these variable-sized sets into a single, fixed-length vector that a neural network can process.

Current state-of-the-art methods like Set Transformers use self-attention to capture interactions between set elements. While powerful, self-attention is computationally expensive, scaling quadratically ($O(n^2)$) relative to the set size. Recent "inducing-point" methods like Optimal Transport Kernel Embedding (OTKE) have reduced this cost, but they are often motivated purely by geometric or attention-based heuristics. This paper seeks a more principled statistical foundation for these embeddings.

Methods: The DIEM Framework

The authors propose approaching the problem from a generative modeling perspective:

  1. The Generative Assumption: Assume the elements of an input set are independent samples drawn from a Gaussian Mixture Model (GMM).
  2. The Embedding as an Estimate: Instead of using a standard neural layer, the set's "summary vector" is defined as the Maximum-A-Posteriori (MAP) estimate of that GMM's parameters (means, variances, and mixing proportions).
  3. Differentiable EM: To find these parameters, the model runs a fixed number ($k$) of Expectation-Maximization (EM) steps. Because these steps are just a series of matrix operations, the entire process is differentiable, allowing the model to be trained end-to-end via backpropagation.
  4. Bayesian Priors: Unlike previous methods, DIEM incorporates a prior distribution (Dirichlet-Normal-Inverse-Wishart) over the mixture parameters. This acts as a built-in regularizer, preventing the model from over-fitting to small or noisy sets.
DIEM Architecture

Key Insights

  • OTKE is a Special Case: One of the most significant theoretical contributions is the proof that the state-of-the-art OTKE method is actually a single-step EM update with specific constraints. DIEM generalizes this, showing that adding more EM steps and removing those constraints often leads to better representations.
  • Priors Matter: The inclusion of Bayesian priors allows the model to handle "empty" or "sparse" components gracefully. By tuning a single hyperparameter, researchers can control how much the model relies on the data versus its learned prior.
  • Unsupervised Learning for Free: Because DIEM is based on a likelihood framework, it can perform unsupervised learning naturally by maximizing the marginal likelihood (Empirical Bayes), even without task-specific labels.
  • Efficiency: By using a fixed number of "reference vectors" (mixture components), DIEM maintains a linear computational complexity relative to the set size, making it much faster than standard Transformers for large sets.

Key Results

The authors evaluated DIEM across a diverse range of tasks, including OMNIGLOT character counting, amortized clustering on CIFAR-100, protein fold classification (SCOP 1.75), and genomic sequence analysis (DeepSEA).

OMNIGLOT Counting Accuracy
  • Counting Accuracy: On the OMNIGLOT "Large set" task, DIEM achieved 44.4% accuracy, significantly outperforming Set Transformers (31.9%) and OTKE (33.5%).
  • Clustering: In amortized clustering on CIFAR-100, DIEM reached an Adjusted Rand Index (ARI) of 0.977, nearly matching the "Oracle" performance (0.984) and crushing the previous best of 0.938.
  • Bioinformatics: On the SCOP protein task, DIEM set a new state-of-the-art in both unsupervised (86.4% top-1) and supervised (90.5% top-1) settings.

Limitations and Future Work

While highly effective for large sets with complex interactions, DIEM's advantages are less pronounced on tasks with very short sequences (like the SST-2 sentiment task), where fine-tuned BERT models remain dominant. Additionally, the number of mixture components is currently a fixed hyperparameter; future work could explore "mixture order selection" to let the model automatically determine the optimal number of components. Finally, while the current implementation uses diagonal and spherical covariances for efficiency, exploring full covariance matrices could capture even richer interactions.

Summary updated

Abstract

We tackle the set2vec problem, the task of extracting a vector representation from an input set comprised of a variable number of feature vectors. Although recent approaches based on self attention such as (Set)Transformers were very successful due to the capability of capturing complex interaction between set elements, the computational overhead is the well-known downside. The inducing-point attention and the latest optimal transport kernel embedding (OTKE) are promising remedies that attain comparable or better performance with reduced computational cost, by incorporating a fixed number of learnable queries in attention. In this paper we approach the set2vec problem from a completely different perspective. The elements of an input set are considered as i.i.d.~samples from a mixture distribution, and we define our set embedding feed-forward network as the maximum-a-posterior (MAP) estimate of the mixture which is approximately attained by a few Expectation-Maximization (EM) steps. The whole MAP-EM steps are differentiable operations with a fixed number of mixture parameters, allowing efficient auto-diff back-propagation for any given downstream task. Furthermore, the proposed mixture set data fitting framework allows unsupervised set representation learning naturally via marginal likelihood maximization aka the empirical Bayes. Interestingly, we also find that OTKE can be seen as a special case of our framework, specifically a single-step EM with extra balanced assignment constraints on the E-step. Compared to OTKE, our approach provides more flexible set embedding as well as prior-induced model regularization. We evaluate our approach on various tasks demonstrating improved performance over the state-of-the-arts.
BibTeX
@inproceedings{kim2022differentiable,
  author = {Minyoung Kim},
  title = {{Differentiable Expectation-Maximization for Set Representation Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=MXdFBmHT4C},
}
Figure