Introduction
In modern information retrieval and recommendation systems, providing a diverse set of results is often as critical as providing relevant ones. For instance, a search for "Venice" should ideally return a representative summary including canals, architecture, and cultural events, rather than a redundant set of similar landmarks. Mathematically, this challenge is addressed using Probabilistic Submodular Models (PSMs), which assign higher probabilities to sets that are both relevant and diverse.
While Determinantal Point Processes (DPPs) have long been the standard for modeling such distributions, they suffer from a significant computational bottleneck: their complexity scales cubically ($O(N^3)$) with the number of items $N$. This limitation renders them impractical for large-scale datasets. To address this, researchers have introduced FLID (Facility LocatIon Diversity), a new probabilistic model that achieves linear scaling ($O(N)$) while maintaining the expressivity of state-of-the-art models.
The FLID Model
The FLID model decomposes the score of a set into two primary components: relevance and diversity. Relevance is modeled by a weight vector $u$, where $u_i$ represents the individual quality of item $i$. Diversity is captured through a latent vector embedding approach inspired by facility location functions.
Each item $i$ is embedded into a latent $L$-dimensional space, represented by a vector $w_i \in \mathbb{R}_+^L$. Each dimension $d \in \{1, \dots, L\}$ corresponds to a latent "concept." The diversity term penalizes the inclusion of multiple items that cover the same concept, effectively modeling "substitutability." If two items are highly similar in the latent space, adding the second item to a set yields diminishing returns.
Efficient Training via Noise Contrastive Estimation (NCE)
A major challenge in training PSMs is the computation of the partition function—a normalization constant that is often intractable. Traditional Maximum Likelihood Estimation (MLE) requires calculating this constant, which is computationally expensive for large sets.
FLID overcomes this by employing Noise Contrastive Estimation (NCE). Instead of modeling the distribution directly, NCE transforms the learning task into a binary classification problem: distinguishing between "real" data samples and "noise" samples generated from a known distribution. This approach bypasses the need for the partition function, allowing the model to scale linearly with the number of items per iteration.
Experimental Evaluation
The authors evaluated FLID against DPP baselines using several datasets, including Amazon Baby Registries and a new large-scale Amazon dataset containing over 7,000 items and 32,000 registries to test scalability.
Key Results
FLID demonstrates a transformative shift in computational efficiency. On the large-scale Amazon dataset, DPPs failed to complete training within a two-hour window, whereas FLID finished in approximately seven minutes.
Beyond speed, FLID maintains high competitive performance. As shown in the experimental results, FLID achieves a Log-likelihood Relative Improvement (LLRI) on par with DPPs across most categories. In recommendation tasks, it consistently outperformed modular (non-diversity) baselines and matched or exceeded the accuracy of DPPs, particularly in categories like "strollers" and "carseats." Qualitative analysis of image summarization also showed that FLID-generated sets were diverse and closely aligned with human-selected summaries.
Conclusion and Future Work
FLID represents a significant advancement in probabilistic diversity modeling, offering a scalable alternative to DPPs without sacrificing performance. By combining latent embeddings with NCE, it enables the application of submodular models to large-scale real-world datasets.
Future research directions include addressing the non-convexity of the FLID objective function to avoid local optima and developing more efficient exact sampling methods to replace current greedy or Gibbs sampling approximations. Additionally, exploring more sophisticated noise distributions for NCE could further enhance model robustness.
Summary updated