Ranking Methods in Machine Learning - SIAM: Society for ...

1 Ranking Methods in Machine LearningA Tutorial IntroductionShivani AgarwalComputer Science & Artificial Intelligence LaboratoryMassachusetts Institute of TechnologyExample 1: Recommendation SystemsExample 2: Information RetrievalinformationExample 2: Information RetrievalinformationExample 2: Information RetrievalProblem:Millions of structures in a chemical do we identify the most promising ones?Example 3: Drug DiscoveryHuman genetics is now at a critical juncture. The molecular Methods used successfully to identify the genes underlying rare mendelian syndromes are failing to find the numerous genes causing more common, familial, non-mendelian diseases ..Nature405:847 856, 2000 Example 4: BioinformaticsNature405:847 856, 2000 With the human genome sequence nearing completion, new opportunities are being presented for unravelling the complex genetic basis of nonmendelian disorders based on large-scale genomewide studies ..Example 4: BioinformaticsTypes of Ranking ProblemsInstance RankingLabel RankingSubset RankingRank Aggregation?

2 Instance Ranking >, 10>, > politicshealth > > sportsmoney > 1>,doc3doc5>..doc2query 2>,..doc4doc11doc3>Rank 2resultsof search engine 1resultsof search engine 2desiredrankingresultsof search engine search engine 2desiredrankingTypes of Ranking ProblemsInstance RankingLabel RankingSubset RankingRank Aggregation?This tutorialTutorial Road MapPart I: Theory & AlgorithmsPart II: ApplicationsFurther Reading & ResourcesBipartite Rankingk- partite RankingRanking with Real-Valued LabelsGeneral Instance RankingRankSVMRankBoostRankNetApplicatio ns to BioinformaticsApplications to Drug DiscoverySubset Ranking and Applications to Information RetrievalPart ITheory & Algorithms[for Instance Ranking ]Bipartite RankingRelevant (+)..doc1+doc2+doc3+Irrelevant (-)..doc1-doc2-doc3-doc4-Bipartite RankingBipartite RankingIs Bipartite Ranking Different from Binary Classification?Is Bipartite Ranking Different from Binary Classification?Is Bipartite Ranking Different from Binary Classification?

3 Is Bipartite Ranking Different from Binary Classification?Is Bipartite Ranking Different from Binary Classification?Is Bipartite Ranking Different from Binary Classification?Bipartite Ranking :Basic Algorithmic FrameworkBipartiteRankSVM Algorithm[Herbrich et al, 2000; Joachims, 2002; Rakotomamonjy, 2004]BipartiteRankSVM AlgorithmBipartite RankBoost Algorithm[Freund et al, 2003]Bipartite RankBoost AlgorithmBipartite RankNet Algorithm[Burges et al, 2005]k- partite RankingRating partite Rankingk- partite Ranking :Basic Algorithmic FrameworkRanking with Real-Valued with Real-Valued LabelsRanking with Real-Valued Labels:Basic Algorithmic FrameworkGeneral Instance Ranking >, r1>, doc2doc2 General Instance RankingriGeneral Instance RankingGeneral Instance Ranking :Basic Algorithmic FrameworkGeneral RankSVM Algorithm[Herbrich et al, 2000; Joachims, 2002]General RankBoost Algorithm[Freund et al, 2003]General RankNet Algorithm[Burges et al, 2005]Tutorial Road MapPart I: Theory & AlgorithmsPart II: ApplicationsFurther Reading & ResourcesBipartite Rankingk- partite RankingRanking with Real-Valued LabelsGeneral Instance RankingRankSVMRankBoostRankNetApplicatio ns to BioinformaticsApplications to Drug DiscoverySubset Ranking and Applications to Information RetrievalPart IIApplications[and Subset Ranking ]Human genetics is now at a critical juncture.

4 The molecular Methods used successfully to identify the genes underlying rare mendelian syndromes are failing to find the numerous genes causing more common, familial, non-mendelian diseases ..Nature405:847 856, 2000 Application to BioinformaticsNature405:847 856, 2000 With the human genome sequence nearing completion, new opportunities are being presented for unravelling the complex genetic basis of nonmendelian disorders based on large-scale genomewide studies ..Application to BioinformaticsIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataIdentifying Genes Relevant to a DiseaseUsing Microarrray Gene Expression DataFormulation as a BipartiteRanking ProblemNot Gene Expression Data Sets[Golub et al, 1999; Alon et al, 1999]Selection of Training GenesTo p- Ranking Genes for Leukemia Returned by RankBoost[Agarwal & Sengupta, 2009]Biological Validation[Agarwal et al, 2010]Problem:Millions of structures in a chemical do we identify the most promising ones?

5 Application to Drug DiscoveryFormulation as a Ranking Problemwith Real-Valued LabelsCheminformatics Data Sets[Sutherland et al, 2004]DHFR Results Using RankSVM[Agarwal et al, 2010]Application to Information Retrieval (IR) Learning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRLearning to Rank in IRGeneral Subset 1>,doc3doc5>..doc2query 2>,..doc4doc11doc3>General Subset RankingSubset Ranking with Real-ValuedRelevance 1y1, ,y3y1,y2,y3 Subset Ranking with Real-ValuedRelevance LabelsRankSVM Applied to IR/Subset Ranking [Joachims, 2002]Standard RankSVMRankSVM Applied to IR/Subset RankingRankSVM with Query Normalization & Relevance Weighting[Agarwal & Collins, 2010; also Cao et al, 2006] Ranking Performance Measures in IRMean Average Precision (MAP) Ranking Performance Measures in IRNormalized Discounted Cumulative Gain (NDCG) Ranking Algorithms for OptimizingMAP/NDCGLETOR Data Set[Liu et al, 2007]OHSUMED Results NDCGOHSUMED Results MAPF urther Reading & Resources[Incomplete!]

6 ]Early Papers on RankingW. W. Cohen, R. E. Schapire, and Y. Singer, Learning to order things, Journal of Artificial Intelligence Research, 10:243 270, Herbrich, T. Graepel, and K. Obermayer, Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers, Joachims, Optimizing search engines using clickthrough data, KDD Freund, R. Iyer, R. E. Schapire, and Y. Singer, An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933 969, Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, G. Hullender, Learning to rank using gradient descent, ICML Bounds for RankingS. Agarwal, T. Graepel, R. Herbrich, S. Har-Peled, D. Roth, Generalization bounds for the area under the ROC curve, Journal of Machine Learning Research, 6:393 425, Agarwal, P. Niyogi, Generalization bounds for Ranking algorithms via algorithmic stability, Journal of Machine Learning Research, 10:441 474, Rudin, R.

7 Schapire, Margin-based Ranking and an equivalence between AdaBoost and RankBoost, Journal of Machine Learning Research, 10: 2193 2232, 2009 Bioinformatics/Drug DiscoveryApplicationsS. Agarwal and S. Sengupta, Ranking genes by relevance to a disease, CSB 2009. S. Agarwal, D. Dugar, and S. Sengupta, Ranking chemical structures for drug discovery: A new Machine Learning approach. Journal of Chemical Information and Modeling, DOI , 2010. Other ApplicationsNatural Language ProcessingM. Collins and T. Koo, Discriminative reranking for natural language parsing,Computational Linguistics,31:25 69, 2005. Collaborative FilteringM. Weimer, A. Karatzoglou, Q. V. Le, and A. Smola, CofiRank - Maximum margin matrix factorization for collaborative Ranking , NIPS Event PredictionC. Rudin, R. Passonneau, A. Radeva, H. Dutta, S. Ierome, and D. Isaac , A process for predicting manhole events in Manhattan, Machine Learning , DOI , Ranking AlgorithmsY. Cao, J. Xu, Liu, H.

8 Li, Y. Hunag, and Hon, Adapting Ranking SVM to document retrieval, SIGIR Burges, R. Ragno, and Le, Learning to rank with non-smooth cost functions. NIPS Xu and H. Li, AdaRank: A boosting algorithm for information retrieval. SIGIR Yue, T. Finley, F. Radlinski, and T. Joachims, A support vector method for optimizing average precision. SIGIR Taylor, J. Guiver, S. Robertson, T. Minka, Softrank: optimizing non-smooth rank metrics. WSDM Ranking AlgorithmsS. Chakrabarti, R. Khanna, U. Sawant, and C. Bhattacharyya, Structured Learning for nonsmooth Ranking losses. KDD Cossock and T. Zhang, Statistical analysis of Bayes optimal subset Ranking , IEEE Transactions on Information Theory,54:5140 5154, Qin, Zhang, Tsai, Wang, Liu, and H. Li. Query-level loss functions for information retrieval. Information Processing and Management,44:838 855, Chapelle and M. Wu, Gradient descent optimization of smoothed information retrieval metrics.

9 Information Retrieval(To appear), Agarwal and M. Collins, Maximum margin Ranking algorithms for information retrieval, ECIR Workshop 2005 Learning to RankNIPS Workshop 2009 Advances in RankingSIGIR Workshops 2007-2009 Learning to Rank for Information RetrievalAmerican Institute of MathematicsWorkshop in Summer 2010 The Mathematics of RankingTie-Yan Liu, Learning to Rank for Information Retrieval, Foundations & Trends in Information Retrieval, Agarwal, A Tutorial introduction to Ranking Methods in Machine Learning , In Agarwal (Ed.), Advances in Ranking Methods in Machine Learning , Springer-Verlag, In Articles & Books