| The general ranking problem is to learn a real-valued ranking function that induces a ranking or ordering based on a given input over an instance space. The number of domains in which ranking has found applications has grown quickly such as web-search, document retrieval. As a result, ranking has gained considerable attention in machine learning.In this thesis, we review background on ranking problem and introduce several specified methods for ranking. We propose a ranking algorithm that is based on mini-mizing a regularized least-squares approximation of a ranking error function that counts the number of incorrectly ranked pairs of data points.It is a kernel-based ranking algo-rithms that perform regularization in a reproducing kernel Hilbert space whose com-putational complexity is cubic with respect to the number of training examples. When nonlinear kernel functions are used, the training of the algorithm might be infeasible if the amount of examples is large. We propose a sparse approximation of the algorithm. Meanwhile, we derive generalization bounds for ranking algorithms that have good sta-bility properties and show that the proposed algorithm have such stability properties. Thus the bounds can be applied to our algorithm.We organize the thesis as follows:In Chapter1, we present a quick overview of background, significance and several learning methods of ranking.In Chapter2, we propose a regularized algorithm and apply the generalized repre-senter theorem to ranking function. Then we take advantage of dual regularized least-squares ranking to solve the problem by minimizing empirical ranking loss.In Chapter3, we discuss the spares of optimal solution for the algorithm proposed in chapter2to reduce the training complexity.In Chapter4, we analyse the generalization bounds of the algorithm propose in this thesis with the result gained by algorithm stability.Finally, in Chapter5, we summarize the paper and give expectations in the future. |
