Estimating Probabilities in Recommendation Systems

Mingxuan Sun, Guy Lebanon, Paul Kidwell

Abstract

Traditional recommendation systems often struggle with the factorial complexity of ranking data and the rigid assumptions of parametric models. This paper presents a non-parametric framework for estimating probability distributions over incomplete rankings. By employing a triangular kernel based on Kendall’s Tau distance and leveraging combinatorial generating functions, the proposed method achieves polynomial-time complexity. Experimental results on large-scale datasets like Netflix and MovieLens demonstrate that this approach captures the multimodal nature of human preferences more effectively than standard models, providing superior log-likelihood and enabling probabilistic rule discovery.

Introduction

In modern recommendation systems, user preferences are typically represented as ranked lists. However, two fundamental challenges impede the effective use of this data. First, rankings are almost always incomplete; in a catalog of thousands of items, a user may only interact with a handful. Second, the computational complexity of non-parametric models usually scales factorially ($n!$) with the number of items, making them intractable for real-world applications.

Furthermore, traditional parametric models, such as the Mallows model, assume a unimodal distribution of preferences. In reality, human tastes are diverse and multimodal—users often belong to distinct "genre clusters" that a simple bell-curve model cannot capture.

Figure 5: Illustration of a multimodal preference distribution, showing how users cluster into distinct taste groups.

Methodology

The authors introduce a framework for Non-parametric Kernel Smoothing tailored for incomplete rankings.

The Triangular Kernel

The core of the estimator is a "triangular kernel" derived from Kendall’s Tau distance, which counts the number of pairwise disagreements between two rankings. This kernel is chosen for its statistical efficiency (98.6%) and its mathematical properties that facilitate efficient computation over partial data.

Combinatorial Generating Functions

To overcome the $n!$ bottleneck, the paper utilizes generating functions from discrete mathematics. This technique allows for the counting of permutations and the calculation of normalization constants without explicit enumeration. This shift transforms the problem from factorial time to polynomial time: $O(n^4)$ for offline pre-computation and $O(k^2)$ for online inference, where $k$ is the number of items ranked by a specific user.

Experimental Results

The proposed kernel estimator was evaluated against the Mallows model and empirical baselines using several benchmark datasets: MovieLens 1M, Netflix, and EachMovie.

Log-Likelihood Performance

As shown in Figure 6, the kernel method consistently outperforms both the parametric Mallows model and empirical baselines in terms of test-set log-likelihood across all major datasets. This indicates a significantly better fit to the underlying distribution of user preferences.

Figure 6: Test-set log-likelihood comparison across MovieLens 1M, Netflix, and EachMovie datasets. The Kernel method (solid black) consistently achieves higher likelihood than the Mallows (red) and Empirical (blue) models.

Probabilistic Rule Discovery

Beyond simple rank prediction, the probabilistic nature of the model allows for "Rule Discovery." For instance, the model can quantify the probability that a user who prefers The Fellowship of the Ring over a romantic comedy will also prefer The Two Towers. In the Netflix dataset, the model successfully identified logical sequels and genre-based "dislike" rules (e.g., a strong preference for romance often correlates with a predicted dislike for high-octane action).

Discussion and Conclusion

The primary contribution of this work is the demonstration that non-parametric models can be made computationally feasible for large-scale ranking data. By bypassing the factorial complexity through combinatorial algebra, the authors provide a tool that is both statistically flexible and practically scalable.

While the $O(n^4)$ offline cost remains a consideration for extremely large catalogs, the benefits of capturing multimodal distributions and providing full probability estimates offer a significant advantage for complex recommendation tasks. Future work may explore alternative distance metrics to capture different dimensions of ranking behavior.

Summary updated

Abstract

Recommendation systems are emerging as an important business application with significant economic impact. Currently popular systems include Amazon's book recommendations, Netflix's movie recommendations, and Pandora's music recommendations. In this paper we address the problem of estimating probabilities associated with recommendation system data using non-parametric kernel smoothing. In our estimation we interpret missing items as randomly censored observations and obtain efficient computation schemes using combinatorial properties of generating functions. We demonstrate our approach with several case studies involving real world movie recommendation data. The results are comparable with state-of-the-art techniques while also providing probabilistic preference estimates outside the scope of traditional recommender systems.
BibTeX
@article{sun2011estimating,
  author = {Mingxuan Sun and Guy Lebanon and Paul Kidwell},
  title = {{Estimating Probabilities in Recommendation Systems}},
  journal = {AISTATS},
  year = {2011},
}
Figure