Research On Top Rank Learning And Its Applications

Learning to rank is an important research direction in machine learning.In tra-ditional research,it is often expected to optimize the quality of the whole ranked list.However,in many practical applications such as information retrieval and recommen-dation system,only the top ranked instances will be exploited.If traditional methods are used,great efforts will be used to improve the ranking quality of the instances that will not be exploited,leading to unnecessary consumption of computing resources.There-fore,top rank learning,which aims to efficiently improve the ranking accuracy at the top,has received much attention.In the past few years,advances have been achieved on this topic,and related methods have been successfully applied in many applications.However,there are still some crucial issues unsolved and worth studying,such as the computational efficiency,the scalability,the disposition of class imbalance.In this dissertation,we focus on these issues,and main results are summarised as follows.1.An efficient approach TopPush is proposed,whose time complexity is linear in the number of training examples.To make m positive instances ranked above n negative ones,existing methods often build the model by considering the re-lationship between each positive and negative instance pair,leading to high time complexity O(m × n).In this dissertation,we propose an approach TopPush.By selecting representative negative instance and considering the relationship between positive instances and this representative negative instance,TopPush achieves lin-ear time complexity which is for the first time in top rank learning methods.Ex-perimental results show TopPush is 10-100 times faster than existing methods,also achieves state-of-the-art performance.2.An effective approach CAPO is proposed,which exploits related existing mod-els to help build better ranking model.In many practical applications,before we start one task,there are often some existing models,such as the ones trained on historical dataset and the one trained on the same dataset but for different tar-gets.Existing top rank learning methods build the model solely based on training data,leaving these existing models unexploited.By using classifier adaptation tech-niques,the proposed CAPO approach can take advantage of these information to improve model representability and also speed-up the learning process.The effec-tiveness of CAPO is validated by experimental results.3.A fast approach NearPush is proposed,which is very efficient on large-scale class-imbalance dataset.The class-imbalance phenomenon,i.e.,there can be much more negative instances than positive ones,often occurs in real applications.The large number of negative instances will make top rank learning methods inefficient.If sampling part of negative instances,information loss will be inevitable,leading to sub-optimal performance.By keeping the key negative instances and effectively eliminating unnecessary negative instances,the proposed NearPush approach sig-nificantly improves the training efficiency,whilst keeping the ranking quality.Both theoretical analysis and experimental results validate the effectiveness of NearPush.4.Two multi-label ranking approaches MUCA and MUSE are proposed.Ex-isting research on top rank learning focus on ranking instances;however,in multi-label learning,it is often needed to rank class labels for each instances,it is expected that relevant class labels will be ranked at the top.In this dissertation,we propose two approaches MUCA and MUSE.By building multi-label ranking models on the base of existing multi-label classification methods,MUCA and MUSE can solve this multi-label top rank learning problem effectively.Experimental results show the effectiveness of MUCA and MUSE.Furthermore,we also successfully apply these proposed approaches to two real-world applications,i.e.,GPS trajectory outlier detection and potential customer prediction,and achieve good performance.