Abstract
This paper presents a novel semi-supervised algorithm for bipartite ranking that utilizes a normalized Rayleigh coefficient. By integrating principles from Quadratic Discriminant Analysis (QDA) with manifold regularization, the proposed method effectively leverages unlabeled data to derive optimal linear ranking functions. To address non-linearities and computational efficiency, the approach employs kernel projection via Incomplete Kernel Gram-Schmidt Orthogonalization. Experimental results on the OPTDIGITS dataset demonstrate that the method achieves high Area Under the ROC Curve (AUC) scores even with a small fraction of labeled samples, highlighting its robustness in data-scarce environments.
Introduction
Bipartite ranking is a fundamental machine learning task where the objective is to learn a function that orders items such that "positive" examples (class +1) are ranked higher than "negative" examples (class -1). This task is central to information retrieval and recommendation systems. While supervised ranking is well-studied, obtaining labeled data is often expensive and time-consuming. Conversely, unlabeled data is typically abundant. This research addresses the gap in semi-supervised ranking by proposing a method that utilizes the underlying structure of unlabeled data to improve ranking performance.
Methodology
The core of the proposed approach is the Normalized Rayleigh Coefficient, which draws inspiration from Fisher’s Linear Discriminant Analysis (FDA). The methodology consists of several key components:
- Optimal Ranking via Covariance: While standard FDA uses scatter matrices for classification, the authors demonstrate that using class covariance matrices (the "normalized" version) results in a weight vector $\mathbf{w}$ that is theoretically optimal for minimizing ranking risk under Gaussian distribution assumptions.
- Manifold Regularization: To incorporate unlabeled data, the algorithm employs manifold regularization. A graph of nearest neighbors is constructed for all data points, and a Normalized Laplacian matrix ($L$) is computed. This term penalizes the ranking function if it assigns significantly different scores to data points that are close to each other on the underlying data manifold.
- Kernel Projection: To handle non-linear relationships without the full computational burden of the "kernel trick," the authors project data into a lower-dimensional subspace using Incomplete Kernel Gram-Schmidt Orthogonalization. This ensures the algorithm remains scalable while capturing complex patterns.
- Closed-Form Solution: The final ranking function is derived through a closed-form solution that integrates class means, covariances, and the Laplacian regularizer.
Experimental Setup
The algorithm was evaluated using the OPTDIGITS dataset from the UCI repository, which contains handwritten digits (0-9). The training set comprised approximately 3,900 patterns, while the test set included 1,800 patterns. Two primary tasks were defined:
- Task A (0 vs. all): Ranking the digit '0' higher than all other digits.
- Task B (0-4 vs. 5-9): Ranking digits 0-4 higher than digits 5-9.
The robustness of the method was tested by varying the percentage of labeled data from 10% to 100%.
Results and Discussion
Performance was measured using the Area Under the ROC Curve (AUC). The results indicate that the algorithm is highly effective even when labeled data is extremely sparse.
In the "0 vs. all" task, the algorithm achieved a near-perfect AUC of 99.5% with only 10% of the data labeled, maintaining this stability as more labels were added. This suggests that the manifold regularization successfully captured the class structure early on. In the more challenging "0-4 vs. 5-9" task, the AUC began at 70.6% (with 10% labels) and improved to 81.2% as the labeling reached 100%. These results are highly competitive with existing state-of-the-art semi-supervised methods.
Conclusion
The use of the normalized Rayleigh coefficient, combined with manifold regularization, provides a powerful framework for semi-supervised bipartite ranking. The "aha moment" of the research is the realization that covariance matrices, rather than scatter matrices, are the appropriate tool for optimal ranking under Gaussian assumptions.
While the method shows great promise, it currently relies on the assumption that data follows a Gaussian distribution. Future work will focus on testing the algorithm against non-Gaussian or multi-modal distributions and establishing formal generalization bounds to provide mathematical guarantees on performance for unseen data.
Summary updated