Liu Learning to Rank for Information Retrieval

2011
ISBN: 978-3-642-14267-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 285 Seiten

Due to the fast growth of the Web and the difficulties in finding desired information, efficient and effective information retrieval systems have become more important than ever, and the search engine has become an essential tool for many people. The ranker, a central component in every search engine, is responsible for the matching between processed queries and indexed documents. Because of its central role, great attention has been paid to the research and development of ranking technologies. In addition, ranking is also pivotal for many other information retrieval applications, such as collaborative filtering, definition ranking, question answering, multimedia retrieval, text summarization, and online advertisement. Leveraging machine learning technologies in the ranking process has led to innovative and more effective ranking models, and eventually to a completely new research area called 'learning to rank'. Liu first gives a comprehensive review of the major approaches to learning to rank. For each approach he presents the basic framework, with example algorithms, and he discusses its advantages and disadvantages. He continues with some recent advances in learning to rank that cannot be simply categorized into the three major approaches - these include relational ranking, query-dependent ranking, transfer ranking, and semisupervised ranking. His presentation is completed by several examples that apply these technologies to solve real information retrieval problems, and by theoretical discussions on guarantees for ranking performance. This book is written for researchers and graduate students in both information retrieval and machine learning. They will find here the only comprehensive description of the state of the art in a field that has driven the recent advances in search engine development.

Tie-Yan Liu is a lead researcher at Microsoft Research Asia. He leads a team working on learning to rank for information retrieval, and graph-based machine learning.   So far, he has more than 70 quality papers published in referred conferences and journals, including SIGIR(9), WWW(3), ICML(3), KDD, NIPS, ACM MM, IEEE TKDE, SIGKDD Explorations, etc.   He has about 40 filed US / international patents or pending applications on learning to rank, general Web search, and multimedia signal processing.   He is the co-author of the Best Student Paper for SIGIR 2008, and the Most Cited Paper for the Journal of Visual Communication and Image Representation (2004-2006). He is an Area Chair of SIGIR 2009, a Senior Program Committee member of SIGIR 2008, and Program Committee members for many other international conferences, such as WWW, ICML, ACL, and ICIP. He is the co-chair of the SIGIR workshop on learning to rank for information retrieval (LR4IR) in 2007 and 2008. He has been on the Editorial Board of the Information Retrieval Journal (IRJ) since 2008, and is the guest editor of the special issue on learning to rank of IRJ.   He has given tutorials on learning to rank at WWW 2008 and SIGIR 2008. Prior to joining Microsoft, he obtained his Ph.D. from Tsinghua University, where his research efforts were devoted to video content analysis.

Autoren/Hrsg.

Liu, Tie-Yan

Inhaltsverzeichnis

1;Preface;5
2;Acknowledgements;8
3;Contents;9
4;Part I: Overview of Learning to Rank;16
4.1;Chapter 1: Introduction;17
4.1.1;1.1 Overview;17
4.1.2;1.2 Ranking in Information Retrieval;21
4.1.2.1;1.2.1 Conventional Ranking Models ;21
4.1.2.1.1;1.2.1.1 Relevance Ranking Models;21
4.1.2.1.2;1.2.1.2 Importance Ranking Models;23
4.1.2.2;1.2.2 Query-Level Position-Based Evaluations;25
4.1.2.2.1;Mean Reciprocal Rank (MRR);26
4.1.2.2.2;Mean Average Precision (MAP);27
4.1.2.2.3;Discounted Cumulative Gain (DCG);27
4.1.2.2.4;Rank Correlation (RC);28
4.1.3;1.3 Learning to Rank;29
4.1.3.1;1.3.1 Machine Learning Framework;30
4.1.3.2;1.3.2 Definition of Learning to Rank;31
4.1.3.2.1;Feature Based;31
4.1.3.2.2;Discriminative Training;32
4.1.3.3;1.3.3 Learning-to-Rank Framework;32
4.1.3.3.1;1.3.3.1 The Pointwise Approach;34
4.1.3.3.2;1.3.3.2 The Pairwise Approach;34
4.1.3.3.3;1.3.3.3 The Listwise Approach;35
4.1.4;1.4 Book Overview;37
4.1.5;1.5 Exercises;38
4.1.6; References;39
5;Part II: Major Approaches to Learning to Rank;45
5.1;Chapter 2: The Pointwise Approach;46
5.1.1;2.1 Overview;46
5.1.2;2.2 Regression-Based Algorithms;46
5.1.2.1;2.2.1 Subset Ranking with Regression;47
5.1.3;2.3 Classification-Based Algorithms;48
5.1.3.1;2.3.1 Binary Classification for Ranking;48
5.1.3.1.1;SVM-Based Method;48
5.1.3.1.2;Logistic Regression-Based Method;49
5.1.3.2;2.3.2 Multi-class Classification for Ranking;50
5.1.3.2.1;Boosting Tree-Based Method;50
5.1.3.2.2;Association Rule Mining-Based Method;51
5.1.4;2.4 Ordinal Regression-Based Algorithms;52
5.1.4.1;2.4.1 Perceptron-Based Ranking (PRanking);52
5.1.4.2;2.4.2 Ranking with Large Margin Principles;53
5.1.4.3;2.4.3 Ordinal Regression with Threshold-Based Loss Functions;55
5.1.5;2.5 Discussions;55
5.1.5.1;2.5.1 Relationship with Relevance Feedback;56
5.1.5.2;2.5.2 Problems with the Pointwise Approach;57
5.1.5.3;2.5.3 Improved Algorithms;57
5.1.6;2.6 Summary;58
5.1.7;2.7 Exercises;58
5.1.8; References;59
5.2;Chapter 3: The Pairwise Approach;61
5.2.1;3.1 Overview;61
5.2.2;3.2 Example Algorithms;61
5.2.2.1;3.2.1 Ordering with Preference Function;61
5.2.2.2;3.2.2 SortNet: Neural Network-Based Sorting Algorithm;63
5.2.2.3;3.2.3 RankNet: Learning to Rank with Gradient Descent;64
5.2.2.4;3.2.4 FRank: Ranking with a Fidelity Loss;65
5.2.2.5;3.2.5 RankBoost;66
5.2.2.6;3.2.6 Ranking SVM;68
5.2.2.7;3.2.7 GBRank;70
5.2.3;3.3 Improved Algorithms;71
5.2.3.1;3.3.1 Multiple Hyperplane Ranker;71
5.2.3.2;3.3.2 Magnitude-Preserving Ranking;72
5.2.3.3;3.3.3 IR-SVM;73
5.2.3.4;3.3.4 Robust Pairwise Ranking with Sigmoid Functions;74
5.2.3.5;3.3.5 P-norm Push;75
5.2.3.6;3.3.6 Ordered Weighted Average for Ranking;76
5.2.3.7;3.3.7 LambdaRank;77
5.2.3.8;3.3.8 Robust Sparse Ranker;78
5.2.4;3.4 Summary;79
5.2.5;3.5 Exercises;79
5.2.6; References;80
5.3;Chapter 4: The Listwise Approach;83
5.3.1;4.1 Overview;83
5.3.2;4.2 Minimization of Measure-Specific Loss;84
5.3.2.1;4.2.1 Measure Approximation;84
5.3.2.1.1;4.2.1.1 SoftRank;84
5.3.2.1.2;4.2.1.2 Decision Theoretic Framework for Ranking;85
5.3.2.1.3;4.2.1.3 Approximate Rank;86
5.3.2.1.4;4.2.1.4 SmoothRank;88
5.3.2.2;4.2.2 Bound Optimization;89
5.3.2.2.1;4.2.2.1 SVMmap;89
5.3.2.3;4.2.3 Non-smooth Optimization;90
5.3.2.3.1;4.2.3.1 AdaRank;90
5.3.2.3.2;4.2.3.2 Genetic Programming Based Algorithms;91
5.3.2.4;4.2.4 Discussions;92
5.3.3;4.3 Minimization of Non-measure-Specific Loss;92
5.3.3.1;4.3.1 ListNet;93
5.3.3.2;4.3.2 ListMLE;94
5.3.3.3;4.3.3 Ranking Using Cumulative Distribution Networks;95
5.3.3.4;4.3.4 BoltzRank;96
5.3.4;4.4 Summary;97
5.3.5;4.5 Exercises;98
5.3.6; References;99
5.4;Chapter 5: Analysis of the Approaches;101
5.4.1;5.1 Overview;101
5.4.2;5.2 The Pointwise Approach;101
5.4.3;5.3 The Pairwise Approach;103
5.4.4;5.4 The Listwise Approach;106
5.4.4.1;5.4.1 Non-measure-Specific Loss;106
5.4.4.2;5.4.2 Measure-Specific Loss;107
5.4.5;5.5 Summary;110
5.4.6;5.6 Exercises;110
5.4.7; References;111
6;Part III: Advanced Topics in Learning to Rank;112
6.1;Chapter 6: Relational Ranking;113
6.1.1;6.1 General Relational Ranking Framework;114
6.1.1.1;6.1.1 Relational Ranking SVM;114
6.1.1.2;6.1.2 Continuous Conditional Random Fields;116
6.1.2;6.2 Learning Diverse Ranking;117
6.1.3;6.3 Discussions;120
6.1.4; References;121
6.2;Chapter 7: Query-Dependent Ranking;122
6.2.1;7.1 Query-Dependent Loss Function;122
6.2.2;7.2 Query-Dependent Ranking Function;124
6.2.2.1;7.2.1 Query Classification-Based Approach;124
6.2.2.2;7.2.2 K Nearest Neighbor-Based Approach;125
6.2.2.3;7.2.3 Query Clustering-Based Approach;127
6.2.2.4;7.2.4 Two-Layer Learning Approach;128
6.2.3;7.3 Discussions;129
6.2.4; References;130
6.3;Chapter 8: Semi-supervised Ranking;131
6.3.1;8.1 Inductive Approach;131
6.3.2;8.2 Transductive Approach;132
6.3.3;8.3 Discussions;133
6.3.4; References;133
6.4;Chapter 9: Transfer Ranking;135
6.4.1;9.1 Feature-Level Transfer Ranking;136
6.4.2;9.2 Instance-Level Transfer Ranking;136
6.4.3;9.3 Discussions;138
6.4.4; References;138
7;Part IV: Benchmark Datasets for Learning to Rank;139
7.1;Chapter 10: The LETOR Datasets;140
7.1.1;10.1 Overview;140
7.1.2;10.2 Document Corpora;140
7.1.2.1;10.2.1 The "Gov" Corpus and Six Query Sets;141
7.1.2.2;10.2.2 The OHSUMED Corpus;141
7.1.2.3;10.2.3 The "Gov2" Corpus and Two Query Sets;142
7.1.3;10.3 Document Sampling;142
7.1.4;10.4 Feature Extraction;143
7.1.5;10.5 Meta Information;143
7.1.6;10.6 Learning Tasks;145
7.1.7;10.7 Discussions;149
7.1.8; References;149
7.2;Chapter 11: Experimental Results on LETOR;151
7.2.1;11.1 Experimental Settings;151
7.2.2;11.2 Experimental Results on LETOR 3.0;152
7.2.3;11.3 Experimental Results on LETOR 4.0;155
7.2.4;11.4 Discussions;156
7.2.5;11.5 Exercises;157
7.2.6; References;157
7.3;Chapter 12: Other Datasets;159
7.3.1;12.1 Yahoo! Learning-to-Rank Challenge Datasets;159
7.3.2;12.2 Microsoft Learning-to-Rank Datasets;160
7.3.3;12.3 Discussions;161
7.3.4; References;161
8;Part V: Practical Issues in Learning to Rank;162
8.1;Chapter 13: Data Preprocessing for Learning to Rank;163
8.1.1;13.1 Overview;163
8.1.2;13.2 Ground Truth Mining from Logs;164
8.1.2.1;13.2.1 User Click Models;164
8.1.2.1.1;13.2.1.1 Dependent Click Model;165
8.1.2.1.2;13.2.1.2 Bayesian Browsing Model;166
8.1.2.1.3;13.2.1.3 Dynamic Bayesian Network Click Model;168
8.1.2.2;13.2.2 Click Data Enhancement;170
8.1.2.2.1;13.2.2.1 Learning a User Interaction Model;170
8.1.2.2.2;13.2.2.2 Smoothing Click-Through Data;171
8.1.3;13.3 Training Data Selection;172
8.1.3.1;13.3.1 Document and Query Selection for Labeling;173
8.1.3.1.1;13.3.1.1 Deep Versus Shallow Judgments;173
8.1.3.1.2;13.3.1.2 Actively Learning for Labeling;174
8.1.3.2;13.3.2 Document and Query Selection for Training;175
8.1.3.2.1;13.3.2.1 Document Selection Strategies;176
8.1.3.2.2;13.3.2.2 Data Selection by Optimizing PPC;177
8.1.3.3;13.3.3 Feature Selection for Training;179
8.1.4;13.4 Summary;180
8.1.5;13.5 Exercises;180
8.1.6; References;181
8.2;Chapter 14: Applications of Learning to Rank;184
8.2.1;14.1 Overview;184
8.2.2;14.2 Question Answering;184
8.2.2.1;14.2.1 Definitional QA;185
8.2.2.2;14.2.2 Quantity Consensus QA;186
8.2.2.3;14.2.3 Non-factoid QA;187
8.2.2.4;14.2.4 Why QA;188
8.2.3;14.3 Multimedia Retrieval;189
8.2.4;14.4 Text Summarization;190
8.2.5;14.5 Online Advertising;191
8.2.6;14.6 Summary;192
8.2.7;14.7 Exercises;193
8.2.8; References;193
9;Part VI: Theories in Learning to Rank;195
9.1;Chapter 15: Statistical Learning Theory for Ranking;196
9.1.1;15.1 Overview;196
9.1.2;15.2 Statistical Learning Theory;196
9.1.3;15.3 Learning Theory for Ranking;198
9.1.3.1;15.3.1 Statistical Ranking Framework;198
9.1.3.2;15.3.2 Generalization Analysis for Ranking;199
9.1.3.3;15.3.3 Statistical Consistency for Ranking;199
9.1.4;15.4 Exercises;200
9.1.5; References;200
9.2;Chapter 16: Statistical Ranking Framework;202
9.2.1;16.1 Document Ranking Framework;203
9.2.1.1;16.1.1 The Pointwise Approach;203
9.2.1.2;16.1.2 The Pairwise Approach;203
9.2.1.2.1;(1) The U-statistics View;204
9.2.1.2.2;(2) The Average View;204
9.2.1.3;16.1.3 The Listwise Approach;205
9.2.2;16.2 Subset Ranking Framework;205
9.2.2.1;16.2.1 The Pointwise Approach;206
9.2.2.2;16.2.2 The Pairwise Approach;206
9.2.2.3;16.2.3 The Listwise Approach;207
9.2.3;16.3 Two-Layer Ranking Framework;207
9.2.3.1;16.3.1 The Pointwise Approach;207
9.2.3.2;16.3.2 The Pairwise Approach;208
9.2.3.2.1;(1) The U-statistics View;208
9.2.3.2.2;(2) The Average View;208
9.2.3.3;16.3.3 The Listwise Approach;209
9.2.4;16.4 Summary;209
9.2.5;16.5 Exercises;209
9.2.6; References;210
9.3;Chapter 17: Generalization Analysis for Ranking;211
9.3.1;17.1 Overview;211
9.3.2;17.2 Uniform Generalization Bounds for Ranking;212
9.3.2.1;17.2.1 For Document Ranking;212
9.3.2.2;17.2.2 For Subset Ranking;214
9.3.2.3;17.2.3 For Two-Layer Ranking;216
9.3.3;17.3 Algorithm-Dependent Generalization Bound;217
9.3.3.1;17.3.1 For Document Ranking;218
9.3.3.2;17.3.2 For Subset Ranking;219
9.3.3.3;17.3.3 For Two-Layer Ranking;220
9.3.4;17.4 Summary;220
9.3.5;17.5 Exercises;221
9.3.6; References;221
9.4;Chapter 18: Statistical Consistency for Ranking;223
9.4.1;18.1 Overview;223
9.4.2;18.2 Consistency Analysis for Document Ranking;224
9.4.2.1;18.2.1 Regarding Pairwise 0-1 Loss;224
9.4.3;18.3 Consistency Analysis for Subset Ranking;224
9.4.3.1;18.3.1 Regarding DCG-Based Ranking Error;225
9.4.3.2;18.3.2 Regarding Permutation-Level 0-1 Loss;225
9.4.3.3;18.3.3 Regarding Top-k True Loss;226
9.4.3.4;18.3.4 Regarding Weighted Kendall's tau;227
9.4.4;18.4 Consistency Analysis for Two-Layer Ranking;229
9.4.5;18.5 Summary;229
9.4.6;18.6 Exercises;230
9.4.7; References;230
10;Part VII: Summary and Outlook;232
10.1;Chapter 19: Summary;233
10.1.1; References;236
10.2;Chapter 20: Future Work;239
10.2.1;20.1 Sample Selection Bias;239
10.2.2;20.2 Direct Learning from Logs;240
10.2.3;20.3 Feature Engineering;241
10.2.4;20.4 Advanced Ranking Models;241
10.2.5;20.5 Large-Scale Learning to Rank;242
10.2.6;20.6 Online Complexity Versus Accuracy;243
10.2.7;20.7 Robust Learning to Rank;243
10.2.8;20.8 Online Learning to Rank;244
10.2.9;20.9 Beyond Ranking;245
10.2.10; References;245
11;Part VIII: Appendix;247
11.1;Chapter 21: Mathematical Background;248
11.1.1;21.1 Probability Theory;248
11.1.1.1;21.1.1 Probability Space and Random Variables;248
11.1.1.2;21.1.2 Probability Distributions;249
11.1.1.2.1;21.1.2.1 Discrete Distribution;249
11.1.1.2.2;21.1.2.2 Continuous Distribution;250
11.1.1.2.3;21.1.2.3 Popular Distributions;251
11.1.1.3;21.1.3 Expectations and Variances;251
11.1.2;21.2 Linear Algebra and Matrix Computation;252
11.1.2.1;21.2.1 Notations;252
11.1.2.2;21.2.2 Basic Matrix Operations and Properties;253
11.1.2.2.1;21.2.2.1 Matrix Multiplication;253
11.1.2.2.2;21.2.2.2 Identity Matrix;254
11.1.2.2.3;21.2.2.3 Diagonal Matrix;254
11.1.2.2.4;21.2.2.4 Transpose;254
11.1.2.2.5;21.2.2.5 Symmetric Matrix;255
11.1.2.2.6;21.2.2.6 Trace;255
11.1.2.2.7;21.2.2.7 Norm;255
11.1.2.2.8;21.2.2.8 Inverse;256
11.1.2.2.9;21.2.2.9 Orthogonal Matrix;256
11.1.2.2.10;21.2.2.10 Determinant;257
11.1.2.2.11;21.2.2.11 Quadratic Form;257
11.1.2.3;21.2.3 Eigenvalues and Eigenvectors;258
11.1.3;21.3 Convex Optimization;259
11.1.3.1;21.3.1 Convex Set and Convex Function;259
11.1.3.2;21.3.2 Conditions for Convexity;260
11.1.3.2.1;21.3.2.1 First-Order Condition;260
11.1.3.2.2;21.3.2.2 Second-Order Condition;260
11.1.3.3;21.3.3 Convex Optimization Problem;260
11.1.3.4;21.3.4 Lagrangian Duality;261
11.1.3.5;21.3.5 KKT Conditions;262
11.1.4; References;263
11.2;Chapter 22: Machine Learning;264
11.2.1;22.1 Regression;264
11.2.1.1;22.1.1 Linear Regression;264
11.2.1.2;22.1.2 Probabilistic Explanation;265
11.2.2;22.2 Classification;266
11.2.2.1;22.2.1 Neural Networks;267
11.2.2.2;22.2.2 Support Vector Machines;268
11.2.2.3;22.2.3 Boosting;270
11.2.2.4;22.2.4 K Nearest Neighbor (KNN);271
11.2.3;22.3 Statistical Learning Theory;271
11.2.3.1;22.3.1 Formalization;272
11.2.3.2;22.3.2 Bounds for |R(g) - R(g)|;274
11.2.3.2.1;22.3.2.1 Hoeffding's Inequality;274
11.2.3.2.2;22.3.2.2 Uniform Bounds in Finite Case;275
11.2.3.2.3;22.3.2.3 Uniform Bounds in Infinite Case;276
11.2.3.2.4;22.3.2.4 Uniform Bounds Based on Covering Number;277
11.2.3.2.5;22.3.2.5 Uniform Bounds Based on Rademacher Average;278
11.2.4; References;279
12;Index;280