Research On Learning To Rank Based On B-cell Algorithm

Learning to rank is a task to automatically construct a ranking model using training data and widely used in Information Retrieval(IR). Traditional learning to rank methods based on loss function have the flaws of indirect optimization and complex computation. For treating the evaluation measures in information retrieval as the optimization target, scholars have proposed the methods based on genetic algorithm and clonal selection algorithm. Though the optimization target is direct, the learning time still has not been effectively improved. In order to guarantee quality of optimal ranking function as well as reduce the learning time, the B cell algorithm applied to learning to rank is discussed in detail in this paper mainly including the following three aspects.(1) The antibody, antigen and affinity are defined for learning to rank in order to apply the B cell algorithm to it. The B cell algorithm is an immune algorithm based on clonal selection mechanism, which is applied to learning to rank through the definitions of antibodies, antigens and the affinity. In this study, an antibody is mapped to a candidate ranking function, an antigen is mapped to list of documents associated with a query and the affinity is mapped to evaluation functions in information retrieval.(2) The preordered encoding sequence of the antibody is constructed to achieve the continuous mutation mechanism of antibodies. Studies have shown that the B cell algorithm has a faster convergence rate than the clonal selection algorithm because of a continuous region mutation operator. The continuous region mutation can not be conducted with the tree representation of an antibody, so the preordered encoding sequence of the antibody tree is proposed and an analysis of the corresponding between the continuous region in the tree and that in the preordered encoding sequence is given. The continuous region mutation operator and the mutation principles are proposed based on the preordered encoding sequence. The other advantage of the preordered encoding sequence is a lower computing complexity of learning to rank, due to mutations on each node take place in the linear sequence instead of the antibody tree.(3) The parallel B cell algorithm is proposed to improve the learning efficiency. The B cell algorithm is fast and simple swarm intelligence optimization algorithm, which has natural parallel characteristics. This paper gives a parallel B cell algorithm on the basis of research on other parallel algorithms. The parallel B cell algorithm can make full use of the advantages of multi-core CPU of the modern computer. Besides the running time reduced, the parallel B cell algorithm has to improve accuracy on test dataset through the addition of cross over to enrich diversity of the population.On the basis of the researches above, two novel learning to rank algorithms named Rank BCA and PRank BCA are proposed based the B cell algorithm and the parallel B cell algorithm respectively. The two algorithms are compared with Rank SVM, Rank Boost, Ada Rank-MAP and List Net. The results show that Rank BCA outperforms Rank SVM and Rank Boost on OHSUMED, moreover PRank BCA outperforms all of them and has a more stable performance. On MQ2007, Rank BCA and PRank BCA outperform Ada Rank-MAP, but are inferior to Rank SVM, Rank Boost and List Net. PRank BCA is better than Rank BCA on both datasets. In respect of learning time, PRank BCA shows a good speed-up ratio and can reduce learning time sharply with the same problem scale. With the problem scale increases, the advantages of parallel algorithm will be highlighted. All the results show that the B cell algorithm is an effective solution to learning to rank.