Abstract
In many real-world ranking scenarios, data is often sparse or imbalanced across numerous tasks, leading to a "cold start" problem for new or low-activity users. This paper proposes Ranking Function Propagation (RFP), a graph-based framework that treats linear ranking functions as probability distributions. By propagating these distributions across a similarity graph using the Hellinger distance, RFP allows "weak" or "unknown" tasks to benefit from the learned parameters of "strong" tasks. Experimental results on acoustic retrieval and personalized movie ranking demonstrate that RFP significantly outperforms traditional label propagation methods.
Introduction
Standard "Learning to Rank" (LTR) algorithms typically treat individual ranking tasks in isolation. However, in applications like personalized recommendations, thousands of unique ranking functions may be required, many of which lack sufficient training data. Existing graph-based label propagation techniques, such as Gaussian Fields and Harmonic Functions (GFHF) or Local and Global Consistency (LGC), are often ill-suited for this problem because they treat features as independent and fail to account for the ordinal nature of distribution-based data (e.g., histograms or spectrograms).
Methodology
The core of the RFP framework involves three key components:
- Ranking Functions as Distributions: Linear ranking functions (weight vectors) are preprocessed into probability distributions. This transformation is valid because adding a constant or scaling a linear ranking vector does not alter the resulting rank order.
- Hellinger Distance Metric: Unlike Euclidean distance, the Hellinger distance is designed for comparing distributions. It is robust to noise and preserves the relationship between adjacent bins in a histogram, which is crucial for ordinal data.
- Optimization and Propagation: The authors define a cost function that balances smoothness (similar tasks should have similar functions) with a penalty for deviating from known "strong" models. A global optimal solution is derived in a closed matrix form, ensuring computational efficiency.
Experimental Evaluation
The authors evaluated RFP on two distinct real-world problems. First, in Acoustic Bird Species Retrieval, they learned ranking functions for 19 bird species using Statistical Spectrogram Descriptors. Second, in Personalized Movie Ranking, they tested user preferences for movie genres based on color histograms of movie posters.
As shown in the results, RFP approaches the performance upper bound much faster than competing methods as training data increases. Furthermore, the inferred models show higher fidelity to the ground truth, as measured by cosine similarity between the inferred ranking functions and those trained on full data.
Conclusion and Future Work
RFP provides a robust solution for the cold-start problem in multi-task ranking. By leveraging the mathematical properties of rank invariance and the Hellinger distance, it preserves the structural information of ranking functions during propagation. While currently limited to linear models, future work could explore extending this framework to non-linear ranking functions and improving scalability for massive graphs involving millions of nodes.
Summary updated