Multi-space probabilistic sequence modeling

Shuo Chen, Jiexun Xu, Thorsten Joachims

Introduction

Probabilistic embedding models, such as Logistic Markov Embeddings (LME), are powerful tools for predicting sequences in domains like music recommendation and natural language processing. By mapping items into a Euclidean space, these models represent transition probabilities as a function of distance. However, they face a significant scalability "wall." Calculating transition probabilities requires computing a partition function—a sum over every item in the library—resulting in $O(|S|^2)$ complexity. For a library of 75,000 songs, training a monolithic model can take over two weeks on a single machine, and standard parallelization fails to overcome the underlying quadratic bottleneck.

The Multi-LME Framework

To address this, the authors introduce Multi-space Logistic Markov Embedding (Multi-LME). This framework exploits the natural "locality" of sequence data—the observation that items typically transition to similar neighbors (e.g., songs within the same genre) rather than random ones.

The global item set is partitioned into $c$ clusters, each with its own local coordinate system. This allows each cluster to be trained independently and in parallel with zero communication during the main optimization phase. To maintain connectivity between these independent spaces, the authors introduce a novel "portal" mechanism.

The portal mechanism handles transitions within a cluster (intra-cluster) and between different clusters (inter-cluster) via virtual entry and exit points.

The Portal Mechanism

Each cluster contains its primary items plus virtual "entry" and "exit" portals for every other cluster.

  • Intra-cluster transitions: A jump between two items in the same cluster is modeled using standard Euclidean distance.
  • Inter-cluster transitions: A jump from item $s_a$ in cluster $u$ to $s_b$ in cluster $v$ is modeled as a two-step process: $s_a$ transitions to an exit portal in $u$, which then connects to an entry portal in $v$ that leads to $s_b$.

Mathematically, this treats the transition matrix between distant clusters as a rank-one approximation, simplifying complex inter-group relationships into a single efficient "bridge."

Experimental Results

The researchers evaluated Multi-LME using radio playlist data from Yes.com, scaling up to the yes_complete dataset containing 75,262 songs.

Empirical results showing the reduction in training time as the number of cores increases, demonstrating the scalability of the Multi-LME framework.

Performance and Scalability

  • Massive Speedup: On the largest dataset, Multi-LME reduced training time from over two weeks to less than three hours.
  • High Fidelity: Despite the approximations, prediction accuracy (test log-likelihood) remained comparable to monolithic models. In some instances, Multi-LME outperformed the original LME, as independent local spaces could better capture sub-genre nuances without global coordinate constraints.
  • Optimal Partitioning: The authors identified a "sweet spot" for partitioning (approximately 100 clusters for their data) where the speed gains from parallelization outweigh the overhead of managing additional portals.

Conclusion

Multi-LME successfully bypasses the quadratic complexity of traditional embedding models by combining space partitioning with virtual portals. By transforming a monolithic optimization problem into a distributed one with near-linear complexity, the framework enables the training of large-scale sequence models that were previously computationally intractable. Future work may extend this "portal trick" to other probabilistic models like Stochastic Neighbor Embedding (SNE).

Summary updated

Abstract

Learning algorithms that embed objects into Euclidean space have become the methods of choice for a wide range of problems, ranging from recommendation and image search to playlist prediction and language modeling. Probabilistic embedding methods provide elegant approaches to these problems, but can be expensive to train and store as a large monolithic model. In this paper, we propose a method that trains not one monolithic model, but multiple local embeddings for a class of pairwise conditional models especially suited for sequence and co-occurrence modeling. We show that computation and memory for training these multi-space models can be efficiently parallelized over many nodes of a cluster. Focusing on sequence modeling for music playlists, we show that the method substantially speeds up training while maintaining high model quality.
BibTeX
@inproceedings{chen2013multi,
  author = {Shuo Chen and Jiexun Xu and Thorsten Joachims},
  title = {{Multi-space probabilistic sequence modeling}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2013},
  doi = {10.1145/2487575.2487632},
}
Figure