Sequence-to-Set Generative Models

Longtao Tang, Ying Zhou, Yang Yu

TL;DR

This paper introduces a "Sequence-to-Set" framework that transforms standard sequence generative models (like GRUs) into powerful set generative models. By leveraging a novel importance sampling algorithm and a "size-bias trick," the authors successfully model complex item correlations in e-commerce data, outperforming traditional statistical methods in predicting "shopping cart" distributions.

What Problem Does This Paper Address?

Generative modeling has seen massive success in sequential data (like text or time series), but sets—collections where the order of items doesn't matter—remain a challenge. Think of a customer's e-commerce order: the items in the cart are a set.

The fundamental hurdle is the "combinatorial explosion." A set of $n$ items can be generated by $n!$ (n-factorial) different sequences. To calculate the exact probability of a set, a model would theoretically need to sum over every possible permutation, which becomes computationally impossible as the set size grows. Previous attempts either made oversimplified independence assumptions or were limited to very small sets (size $\le 4$). This paper seeks a way to use the power of deep learning to model large, complex sets efficiently.

Methods

The authors propose the Sequence-to-Set framework, which treats a set as the result of a sequential generation process where the order is eventually ignored.

  • Importance Sampling: To avoid the $n!$ summation problem, they developed an efficient importance sampling algorithm. This allows the model to estimate the gradient of the log-likelihood by only sampling "valid" paths that lead to the target set, rather than exploring every possible permutation.
  • Two Model Instances:
    • GRU2Set: Uses a Gated Recurrent Unit (GRU) to maintain a "history" of items added to the set.
  • SetNN: A permutation-invariant model based on "Deep Sets" theory, ensuring that the order in which items are processed doesn't change the final set representation.
  • Sparse Item Graphs: To speed up training, they build a graph of items that co-occur in the training data. This prunes the search space, as the model only considers adding items that have a historical precedent of appearing together.
  • The Size-Bias Trick: A heuristic that adjusts the predicted distribution of set sizes. It "invests" more probability mass into smaller sets, which are statistically easier to learn accurately.

Datasets

The models were evaluated on two real-world e-commerce datasets:

  1. TMALL: 1,363 items and 100,000 training sets (orders).
  2. HKTVMALL: 782 items and 200,000 training sets. The authors treated monthly order collections as separate instances to test the models' ability to generalize across different time periods.

Key Insights and Ideas

  • Small Sets are "Low-Hanging Fruit": The authors observed that small sets are much easier to learn because the number of possible combinations is lower. Their "size-bias trick" exploits this by prioritizing accuracy on smaller sets to lower the overall $\ell_1$ error of the distribution.
  • Order Matters (Even for Sets): Interestingly, GRU2Set (which is sensitive to order) slightly outperformed SetNN (which is permutation-invariant). This suggests that the "history" captured by sequential models provides a useful inductive bias, even when the final output is unordered.
  • The Hybrid Advantage: The authors found that a simple histogram is actually the optimal way to model sets of size 1. By combining a histogram for single-item orders with their deep models for multi-item orders, they created a "Hybrid Model" that achieved the best overall performance.

Key Results

  • Superiority over Baselines: Both GRU2Set and SetNN significantly outperformed traditional baselines like the Discrete Choice Model (DCM) and Markov Random Walk (MRW).
  • Effectiveness of the Size-Bias Trick: Applying the size-bias trick improved the quality of the learned set distribution for every model tested, including the baselines.
  • Quantitative Gains: On the TMALL dataset, the GRU2Set model with the size-bias trick outperformed the benchmark histogram method by 4%, proving that deep models can extrapolate beyond just "memorizing" the training data.

Limitations and Future Work

  • Privacy Concerns: The authors acknowledge that learning high-dimensional embeddings for items and sets could potentially lead to user privacy leaks, a common risk in recommendation and generative systems.
  • Architecture Evolution: The current models use standard GRUs and MLPs. The authors suggest that replacing these with more advanced architectures, like Set Transformers, could further improve the expressive power of the framework.
  • Computational Ceiling: While importance sampling makes the problem tractable, extremely large sets (e.g., hundreds of items) would still present a significant computational challenge for evaluating exact probability densities.

Summary updated

Abstract

In this paper, we propose a sequence-to-set method that can transform any sequence generative model based on maximum likelihood to a set generative model where we can evaluate the utility/probability of any set. An efficient importance sampling algorithm is devised to tackle the computational challenge of learning our sequence-to-set model. We present GRU2Set, which is an instance of our sequence-to-set method and employs the famous GRU model as the sequence generative model. To further obtain permutation invariant representation of sets, we devise the SetNN model which is also an instance of the sequence-to-set model. A direct application of our models is to learn an order/set distribution from a collection of e-commerce orders, which is an essential step in many important operational decisions such as inventory arrangement for fast delivery. Based on the intuition that small-sized sets are usually easier to learn than large sets, we propose a size-bias trick that can help learn better set distributions with respect to the $\ell_1$-distance evaluation metric. Two e-commerce order datasets, TMALL and HKTVMALL, are used to conduct extensive experiments to show the effectiveness of our models. The experimental results demonstrate that our models can learn better set/order distributions from order data than the baselines. Moreover, no matter what model we use, applying the size-bias trick can always improve the quality of the set distribution learned from data.
BibTeX
@inproceedings{tang2022sequence,
  author = {Longtao Tang and Ying Zhou and Yang Yu},
  title = {{Sequence-to-Set Generative Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=0dt8wdYIAV},
}
Figure