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.
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:
- 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