KwikSort Re-Ranking

Re-rank BM25 results with a majority vote of many axioms

This walkthrough shows how ir_axioms can re-rank a result set in PyTerrier using the KwikSort algorithm [Ailon et al., 2008] and manually combined axioms [Hagen et al., 2016]. We use the passage ranking task of the TREC 2020 Deep Learning track with BM25 as the baseline and evaluate nDCG@10, reciprocal rank, and average precision with PyTerrier's standard Experiment functionality.

Based on the notebook pyterrier_kwiksort.ipynb .

Setup

Follow the common setup to load the datasets, build the index, define the bm25 baseline, and connect ir_axioms to the index.

Combine Axioms

We combine many of the axioms implemented in ir_axioms in a majority vote. That is, we only keep preferences where at least 50 % of the axioms agree, and fall back to the original BM25 ranking otherwise. Because some axioms call external APIs (e.g., the argumentativeness axioms) or are computationally expensive, we cache the voting result on disk:

from ir_axioms.axiom import (
    ArgUC, QTArg, QTPArg, aSL,
    LNC1, TF_LNC, LB1,
    PROX1, PROX2, PROX3, PROX4, PROX5,
    REG, ANTI_REG, ASPECT_REG,
    AND, LEN_AND, M_AND, LEN_M_AND, DIV, LEN_DIV,
    TFC1, TFC3, M_TDC, LEN_M_TDC,
    STMC1, STMC2,
    ORIG, MajorityVoteAxiom,
)

axiom = MajorityVoteAxiom(
    axioms=[
        ArgUC(), QTArg(), QTPArg(), aSL(),
        LNC1(), TF_LNC(), LB1(),
        PROX1(), PROX2(), PROX3(), PROX4(), PROX5(),
        REG(), ANTI_REG(), ASPECT_REG(),
        AND(), LEN_AND(), M_AND(), LEN_M_AND(), DIV(), LEN_DIV(),
        TFC1(), TFC3(), M_TDC(), LEN_M_TDC(),
        STMC1(), STMC2(),
    ],
    minimum_votes=0.5,
).cached(cache_dir / "axioms" / "vote") | ORIG()

KwikSort Re-Ranking

With the combined axiom, we create a new PyTerrier pipeline that re-ranks the top-20 baseline results using KwikSort. KwikSort works similar to Quicksort, but instead of comparing items by their natural order, it compares them by axiom preferences. Here, we always choose the middle document as the pivot, to make the re-ranking deterministic:

from ir_axioms.integrations import KwikSortReranker
from ir_axioms.tools import MiddlePivotSelection

kwiksort = bm25 % 20 >> KwikSortReranker(
    axiom=axiom,
    pivot_selection=MiddlePivotSelection(),
    verbose=True,
)

Experimental Evaluation

Because the axiomatic re-ranker is a PyTerrier transformer, we can use PyTerrier's Experiment to compare the re-ranked pipeline to the BM25 baseline. Refer to the PyTerrier documentation to learn more about running experiments. We append the baseline results after the top-20 positions using the ^ operator:

from ir_measures import nDCG, MAP, RR
from pyterrier import Experiment

experiment = Experiment(
    [bm25, kwiksort ^ bm25],
    dataset_test.get_topics(),
    dataset_test.get_qrels(),
    [nDCG @ 10, RR, MAP],
    names=["BM25", "KwikSort"],
    verbose=True,
)
experiment.sort_values(by="nDCG@10", ascending=False)

Next Steps

Instead of weighting all axioms equally, learn how to combine them from relevance judgments.

References

Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55 (5) : 23:1–23:27, 2008. [bib] [doi]

@article{ailon2008aggregating,
  author       = {Nir Ailon and
                  Moses Charikar and
                  Alantha Newman},
  title        = {Aggregating inconsistent information: Ranking and clustering},
  journal      = {J. {ACM}},
  volume       = {55},
  number       = {5},
  pages        = {23:1--23:27},
  year         = {2008},
  url          = {https://doi.org/10.1145/1411509.1411513},
  doi          = {10.1145/1411509.1411513}
}

Matthias Hagen, Michael Völske, Steve Göring, and Benno Stein. Axiomatic Result Re-Ranking. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016, pages 721–730, 2016. ACM. [bib] [doi]

@inproceedings{hagen2016axiomatic,
  author       = {Matthias Hagen and
                  Michael V{\"{o}}lske and
                  Steve G{\"{o}}ring and
                  Benno Stein},
  title        = {Axiomatic Result Re-Ranking},
  booktitle    = {Proceedings of the 25th {ACM} International Conference on Information
                  and Knowledge Management, {CIKM} 2016, Indianapolis, IN, USA, October
                  24-28, 2016},
  pages        = {721--730},
  publisher    = {{ACM}},
  year         = {2016},
  url          = {https://doi.org/10.1145/2983323.2983704},
  doi          = {10.1145/2983323.2983704}
}