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:

  1. Pooling: acquire queries, documents and human relevance judgments using pooling
  2. Top-K retrieval (train): Generate sample of documents for training queries
  3. Feature extraction: extract feature vector for each query-document pair
  4. Learning: learn a model
  5. Test: re-apply step 2 and 3 for a test set.
  6. 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.