Lecture 8: Learning to rank
Background reading: Zhai - Learning to rank
ML in IR only became prominent in the last 10 years, pushed by large companies such as Google. Why didn't we have machine learning in IR earlier?
- Poorer ML techniques
- Not enough features for ML to show it's strength
- Limited training data
- Manual test collection creation was hard
Why is ML needed now in IR?
- Classic IR handle very few features
- Only things like TF, doc length, DF
- Way more features are available now after the advance of the Web
- Tuning weights without ML is no longer possible (e.g. Google uses 200+ features)
LTR Framework
Offline:
- Pooling: acquire queries, documents and human relevance judgments using pooling
- Top-K retrieval (train): Generate sample of documents for training queries
- Feature extraction: extract feature vector for each query-document pair
- Learning: learn a model
- Test: re-apply step 2 and 3 for a test set.
- Learned model application: apply on every document in the test sample.
N.B. features are not just extracted from document, but from query-document pairs. This makes sense, because some features may for example be a BM25 score which requires a query as input.
Linear combination of features
This is the setup from Zhai-Learning_to_rank.md .
We want to learn P(R=1|q,d).
We assume that the log odds can be expressed by some weighted linear combination of features.
$$ log \frac{ P(R=1|q,d)}{1-P(R=1|q,d)} = \beta_0 + \sum_{i=1}^n \beta_i X_i$$
It is common to express the probability of relevance in terms of this logistic function so it is clamped between 0 and 1. This way we can connect arbitrary combinations of feature scores.
Q: Why do we use the logistic function when expressing the probability of relevance in terms of a linear combination of (positively valued) features?
Categories of learning algorithms
- Pointwise
- Pairwise
- Listwise
Q: What are three categories of learning to rank algorithms?
Pointwise LTR
This is the typical way all classification and regression algorithms work.
- Input: feature vector of each single document
- Output: relevance degree for each document
- Ground truth: relevance degree per document
- Loss function: prediction error of per document, given true label
Pairwise LTR
Given a pair of documents, which one is more relevant?
- Input: Feature vectors of pair of documents
- Output: Pairwise preference {1,-1} between document pairs
- Ground truth labels: $y_{u,v}=1$ if relevance degree $l_u > l_v$; -1 otherwise.
- Loss function: measure inconsistency of the pairwise preference $h(x_u, x_v) \in {1,-1}$ and ground truth $y_{u,v}$.
Examples: RankSVM, RankNet, LambdaMART
Listwise LTR
- Input: All documents associated with query q
- Output:
- Relevance degrees of all documents associated with q (similar to pointwise); OR
- Ranked list of documents
- Ground truth labels:
- Similar to pointwise; OR
- TODO what? "judgment total order and based on the concept of equivalent permutation set"
- Loss function:
- Optimizes a common IR evaluation measure; OR
- Measures difference between ranked list and ground truth ranking
Examples: Coordinate Ascent, AdaRank, ListNet
Listwise LTR seems to be closest to the way we usually evaluate IR ranking functions, since they output a ranked list (or equivalent; relevance ordering).
Pro:
- Considers positions of documents in the ranked list (like normal IR applications)
- We want to prioritize correctly ordering the most relevant documents (not only just finding the top-k most relevant);
- unlike the other approaches this approach directly optimizes on the optimal ranking order by optimizing NDCG or MAP
Con:
- These models are complexity and have issues with scalability
Feature extraction
- Query features
- Query length
- Number of entities in query
- Sum of IDF of query terms
- Document features
- number of in links
- nr of out links
- Page rank
- Length of document
- Query-document features
- Depend on both query and document
- BM25 scores for various fields as feature
- Nr. of matching query terms
- LM scores for various fields
- etc.
Practical considerations
- Some queries have many relevant documents and others few
- Queries with may results may dominate learning if we take a pairwise approach; there are more query-document pairs for these queries.
- A huge imbalance between non-relevant and relevant instances are often a problem for most models
- Under- or oversampling from each class may address the imbalance.
On LTR hyperparameters:
- The choice of a particular LTR algorithm is itself an LTR parameter
- What sample size to use?
- What IR measure to optimize? Which cut-off to use?
- Negative sampling
Ranklib and Terrier are platforms for IR LTR.