Online ranking algorithm based on perceptron with margins

Learning to rank is a unique and important issue in the field of machine learning. In this paper, we propose an online ranking algorithm, referred to as PMRank. In our approach, the perceptron with margins is employed to learn a ranking model. Since margins are introduced into the training process, our approach can achieve nearly or even ranking results of the maximal margin based ranking approaches. In the meanwhile, as an online ranking algorithm, our approach is much more efficient than them. Moreover, there are degrees of freedom to set the margins in our approach, which can make the training process of our approach focused on instances from particular ranks. That is an especially favorable property in real-word applications, such as information retrieval where the errors made on relevant documents are much more serious than the errors on irrelevant documents. We discuss our approach from a theoretical point of view and provide a theoretical justification. Experimental results on synthetic and real-world datasets show that our approach is an effective and efficient ranking algorithm.