Sequence-to-Set Generative Models

Longtao Tang, Ying Zhou, Yu Yang

In the world of machine learning, we are highly adept at modeling sequences (like sentences) and grids (like images). But what about sets? Consider an e-commerce shopping cart: the specific items in your basket matter, but the chronological order in which you clicked "add to cart" usually does not.

Modeling these "order-invariant" collections is surprisingly difficult for deep learning. A paper from researchers at the City University of Hong Kong, titled Sequence-to-Set Generative Models, proposes a clever framework to bridge the gap between sequence models and set data.

The Challenge of Permutation Invariance

The fundamental hurdle with sets is permutation invariance. If a set contains $n$ items, there are $n!$ (n-factorial) possible sequences that could represent it. For a relatively small basket of just 10 items, that translates to over 3.6 million possible sequences.

Traditional sequence models, such as those used in Natural Language Processing, are inherently "order-aware." To calculate the true probability of a set using these models, one must technically sum the probabilities of every possible sequence that could form that set. This becomes computationally intractable for anything but the smallest collections.

Previous attempts to solve this either made oversimplifying assumptions (treating items as entirely independent) or were restricted to tiny sets of 4 or 5 items. This paper aims to bring the full power of deep representation learning to sets of any size.

The Sequence-to-Set Framework

The authors propose a general Sequence-to-Set framework. The core intuition is to treat a set as being "induced" by a sequence, where the specific order of items is treated as a latent (hidden) variable.

1. Overcoming the Math with Importance Sampling

To avoid the $n!$ summation nightmare, the authors utilize Importance Sampling. Instead of calculating every possible path to form a set, they devised an efficient algorithm to estimate the gradient of the log-likelihood by sampling only the most relevant paths. This mathematical workaround allows them to train deep models on large sets without the exponential computational cost.

2. Two Novel Architectures: GRU2Set and SetNN

The framework is instantiated in two distinct models:

  • GRU2Set: This model uses a Gated Recurrent Unit (GRU) to maintain a "history" of the items added so far. While GRUs are sequential by nature, the specialized training process ensures the final set probability is what the model optimizes for.
  • SetNN: This is a more "pure" set model utilizing a permutation-invariant architecture.
Architecture of the SetNN model, illustrating how item embeddings are aggregated and passed through an MLP to predict the next item.

As shown above, SetNN aggregates item embeddings (e.g., via mean pooling) to create a unified set embedding. This representation is then passed through a Multi-Layer Perceptron (MLP) to generate a choice vector, which dictates the probability of adding the next item.

3. The Size-Bias Trick

During their research, the authors noticed a recurring issue: generative models are generally much better at learning the distribution of small sets than large ones. To counter this, they introduced a heuristic called the size-bias trick. This trick slightly adjusts the predicted size distribution of the sets to favor smaller, more accurately modeled sizes. Surprisingly, this adjustment improves the overall accuracy of the model across all set sizes.

Datasets and Evaluation

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

Dataset statistics for TMALL and HKTVMALL.
  • TMALL: Data from the Chinese retail giant, featuring 1,363 unique items and 100,000 training sets.
  • HKTVMALL: Data from a major Hong Kong online shopping platform, featuring 782 items and 200,000 training sets.

Key Insights and Results

The primary metric used to evaluate success was the $\ell_1$-distance (where lower is better) between the model's predicted set distribution and the true distribution found in the test data.

  • Outperforming Baselines: Both GRU2Set and SetNN consistently outperformed traditional statistical baselines, such as Discrete Choice Models (DCM) and Markov Random Walks (MRW).
  • The Power of the Trick: Applying the "size-bias trick" yielded empirical improvements for every single model tested.
  • Beating the Benchmark: On the TMALL dataset, the GRU2Set + Size Bias model achieved an average score of 0.87, outperforming the standard empirical benchmark (0.95) by roughly 4%. On HKTVMALL, it outperformed the benchmark by 2.5%.
  • Sparse Item Graphs for Speed: To accelerate the model, the researchers built a "sparse item graph" from the training data. The model only considers adding an item to a set if those items have been seen together before, drastically reducing the search space during generation.

Limitations and Future Work

While highly effective, the authors acknowledge that learning high-quality item and set embeddings could potentially lead to user privacy leaks if not handled carefully in production environments.

Looking forward, the Sequence-to-Set framework is highly modular. While this paper utilized GRUs and MLPs, future work could integrate more sophisticated modules like Set Transformers to capture even more complex dependencies between items. Furthermore, while tested on e-commerce shopping data, this framework could theoretically be applied to any set-based data, opening doors for advancements in modeling social groups, chemical compounds, or point clouds.

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 Yu Yang},
  title = {{Sequence-to-Set Generative Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=0dt8wdYIAV},
}
Figure