Skip to content

Latest commit

 

History

History
403 lines (317 loc) · 29.3 KB

experiments-msmarco-passage.md

File metadata and controls

403 lines (317 loc) · 29.3 KB
Raw

Anserini: BM25 Baselines for MS MARCO Passage Ranking

This page contains instructions for running BM25 baselines on the MS MARCO passage ranking task. Note that there is a separate MS MARCO document ranking task.

This exercise will require a machine with >8 GB RAM and at least 15 GB free disk space .

If you're a Waterloo undergraduate going through this guide as the screening exercise of joining my research group, try to understand what you're actually doing, instead of simply cargo culting (i.e., blinding copying and pasting commands into a shell). In particular, you'll want to pay attention to the "What's going on here?" sections.

What's going on here?

As a really high level summary: in the MS MARCO passage ranking task, you're given a bunch of passages to search and a bunch of queries. The system's task is to return the best passages for each query (i.e., passages that are relevant).

Note that "the things you're searching" are called documents (in the generic sense), even though they're actually passages (extracted from web pages) in this case. You could be search web pages, PDFs, Excel spreadsheets, and even podcasts. Information retrieval researchers refer to these all as "documents".

Data Prep

We're going to use the repository's root directory as the working directory. First, we need to download and extract the MS MARCO passage dataset:

mkdir collections/msmarco-passage

wget https://msmarco.blob.core.windows.net/msmarcoranking/collectionandqueries.tar.gz -P collections/msmarco-passage

# Alternative mirror:
# wget https://rgw.cs.uwaterloo.ca/JIMMYLIN-bucket0/data/collectionandqueries.tar.gz -P collections/msmarco-passage

tar xvfz collections/msmarco-passage/collectionandqueries.tar.gz -C collections/msmarco-passage

To confirm, collectionandqueries.tar.gz should have MD5 checksum of 31644046b18952c1386cd4564ba2ae69.

What's going on here?

If you peak inside the collection:

head collections/msmarco-passage/collection.tsv

You'll see that collection.tsv contains the passages that we're searching. Each line represents a passage: the first column contains a unique identifier for the passage (called the docid) and the second column contains the text of the passage itself.

Next, we need to convert the MS MARCO tsv collection into Anserini's jsonl files (which have one json object per line):

python tools/scripts/msmarco/convert_collection_to_jsonl.py \
  --collection-path collections/msmarco-passage/collection.tsv \
  --output-folder collections/msmarco-passage/collection_jsonl

The above script should generate 9 jsonl files in collections/msmarco-passage/collection_jsonl, each with 1M lines (except for the last one, which should have 841,823 lines).

Indexing

We can now index these docs as a JsonCollection using Anserini:

target/appassembler/bin/IndexCollection \
  -collection JsonCollection \
  -input collections/msmarco-passage/collection_jsonl \
  -index indexes/msmarco-passage/lucene-index-msmarco \
  -generator DefaultLuceneDocumentGenerator \
  -threads 9 -storePositions -storeDocvectors -storeRaw

Upon completion, we should have an index with 8,841,823 documents. The indexing speed may vary; on a modern desktop with an SSD, indexing takes a couple of minutes.

Retrieval

Since queries of the set are too many (+100k), it would take a long time to retrieve all of them. To speed this up, we use only the queries that are in the qrels file:

python tools/scripts/msmarco/filter_queries.py \
  --qrels collections/msmarco-passage/qrels.dev.small.tsv \
  --queries collections/msmarco-passage/queries.dev.tsv \
  --output collections/msmarco-passage/queries.dev.small.tsv

The output queries file should contain 6980 lines.

What's going on here?

Check out the contents of the queries file:

$ head collections/msmarco-passage/queries.dev.small.tsv
1048585	what is paula deen's brother
2	 Androgen receptor define
524332	treating tension headaches without medication
1048642	what is paranoid sc
524447	treatment of varicose veins in legs
786674	what is prime rate in canada
1048876	who plays young dr mallard on ncis
1048917	what is operating system misconfiguration
786786	what is priority pass
524699	tricare service number

These are the queries we're going to feed to the search engine. The first field is a unique identifier for the query (called the qid) and the second column is the query itself. These queries are taken from Bing search logs, so they're "realistic" web queries in that they may be ambiguous, contain typos, etc.

We can now perform a retrieval run using this smaller set of queries:

target/appassembler/bin/SearchCollection \
  -index indexes/msmarco-passage/lucene-index-msmarco \
  -topics collections/msmarco-passage/queries.dev.small.tsv \
  -topicreader TsvInt \
  -output runs/run.msmarco-passage.dev.small.tsv -format msmarco \
  -parallelism 4 \
  -bm25 -bm25.k1 0.82 -bm25.b 0.68 -hits 1000

The above command uses BM25 with tuned parameters k1=0.82, b=0.68. The option -hits specifies the number of documents per query to be retrieved. Thus, the output file should have approximately 6980 × 1000 = 6.9M lines.

Retrieval speed will vary by machine: On a reasonably modern desktop with an SSD, with four threads (as specified above), the run takes a couple of minutes. Adjust the parallelism by changing the -parallelism argument.

What's going on here?

Congratulations, you've performed your first retrieval run!

You feed a search engine a bunch of queries, and the retrieval run is the output of the search engine. For each query, the search engine gives back a ranked list of results (i.e., a list of hits).

Let's take a look:

$ head runs/run.msmarco-passage.dev.small.tsv
1048585	7187158	1
1048585	7187157	2
1048585	7187163	3
1048585	7546327	4
1048585	7187160	5
1048585	8227279	6
1048585	7617404	7
1048585	7187156	8
1048585	2298838	9
1048585	7187155	10

The first column is the qid (corresponding to the query). From above, we can see that qid 1048585 is the query "what is paula deen's brother". The second column is the docid of the retrieved result (i.e., the hit), and the third column is the rank position. That is, in a search interface, docid 7187158 would be shown in the top position, docid 7187157 would be shown in the second position, etc.

You can grep through the collection to see what that actual passage is:

$ grep 7187158 collections/msmarco-passage/collection.tsv
7187158	Paula Deen and her brother Earl W. Bubba Hiers are being sued by a former general manager at Uncle Bubba'sâ�¦ Paula Deen and her brother Earl W. Bubba Hiers are being sued by a former general manager at Uncle Bubba'sâ�

In this case, the hit seems relevant. That is, it answers the query. So here, the search engine did well.

Note that this particular passage is a bit dirty (garbage characters, dups, etc.)... but that's pretty much a fact of life when you're dealing with the web.

Finally, we can evaluate the retrieved documents using this the official MS MARCO evaluation script:

python tools/scripts/msmarco/msmarco_passage_eval.py \
 collections/msmarco-passage/qrels.dev.small.tsv runs/run.msmarco-passage.dev.small.tsv

And the output should be like this:

#####################
MRR @10: 0.18741227770955546
QueriesRanked: 6980
#####################
What's going on here?

So how do we know if a search engine is any good? One method is manual examination, which is what we did above. That is, we actually looked at the results by hand.

Obviously, this isn't scalable if we want to evaluate lots of queries... If only someone told us which documents were relevant to which queries...

Well, someone has! (Specifically, human editors hired by Microsoft Bing in this case.) These are captured in what are known as relevance judgments. Take a look:

$ grep 1048585 collections/msmarco-passage/qrels.dev.small.tsv
1048585	0	7187158	1

This says that docid 7187158 is relevant to qid 1048585, which confirms our intuition above. The file is in what is known as the qrels format. You can ignore the second column. The fourth column "1", says that the docid is relevant. In some cases (though not here), that column might say "0", i.e., that the docid is not relevant.

With relevance judgments (qrels), we can now automatically evaluate the search engine output (i.e., the run). The final ingredient we need is a metric (i.e., how to score).

Here, we're using a metric called MRR, or mean reciprocal rank. The idea is quite simple: We look at where the relevant docid appears. If it appears at rank 1, the system gets a score of one. If it appears at rank 2, the system gets a score of 1/2. If it appears at rank 3, the system gets a score of 1/3. And so on. MRR@10 means that we only go down to rank 10. If the relevant docid doesn't appear in the top 10, then the system gets a score of zero.

That's the score of a query. We take the average of the scores across all queries (6980 in this case), and we arrive at the score for the entire run.

You can find this run on the MS MARCO Passage Ranking Leaderboard as the entry named "BM25 (Lucene8, tuned)", dated 2019/06/26. So you've just reproduced (part of) a leaderboard submission!

We can also use the official TREC evaluation tool, trec_eval, to compute other metrics than MRR@10. For that we first need to convert runs and qrels files to the TREC format:

python tools/scripts/msmarco/convert_msmarco_to_trec_run.py \
  --input runs/run.msmarco-passage.dev.small.tsv \
  --output runs/run.msmarco-passage.dev.small.trec

python tools/scripts/msmarco/convert_msmarco_to_trec_qrels.py \
  --input collections/msmarco-passage/qrels.dev.small.tsv \
  --output collections/msmarco-passage/qrels.dev.small.trec

And run the trec_eval tool:

tools/eval/trec_eval.9.0.4/trec_eval -c -mrecall.1000 -mmap \
  collections/msmarco-passage/qrels.dev.small.trec runs/run.msmarco-passage.dev.small.trec

The output should be:

map                   	all	0.1957
recall_1000           	all	0.8573

Average precision and recall@1000 are the two metrics we care about the most.

What's going on here?

Don't worry so much about the details here for now. The tl;dr is that there are different formats for run files and lots of different metrics you can compute. trec_eval is a standard tool used by information retrieval researchers.

In fact, researchers have been trying to answer the question "how do we know if a search result is good and how do we measure it" for over half a century... and the question still has not been fully resolved. In short, it's complicated.

BM25 Tuning

Note that this figure differs slightly from the value reported in Document Expansion by Query Prediction, which uses the Anserini (system-wide) default of k1=0.9, b=0.4.

Tuning was accomplished with tools/scripts/msmarco/tune_bm25.py, using the queries found here; the basic approach is grid search of parameter values in tenth increments. There are five different sets of 10k samples (using the shuf command). We tuned on each individual set and then averaged parameter values across all five sets (this has the effect of regularization). In separate trials, we optimized for:

  • recall@1000, since Anserini output serves as input to downstream rerankers (e.g., based on BERT), and we want to maximize the number of relevant documents the rerankers have to work with;
  • MRR@10, for the case where Anserini output is directly presented to users (i.e., no downstream reranking).

It turns out that optimizing for MRR@10 and MAP yields the same settings.

Here's the comparison between the Anserini default and optimized parameters:

Setting MRR@10 MAP Recall@1000
Default (k1=0.9, b=0.4) 0.1840 0.1926 0.8526
Optimized for recall@1000 (k1=0.82, b=0.68) 0.1874 0.1957 0.8573
Optimized for MRR@10/MAP (k1=0.60, b=0.62) 0.1892 0.1972 0.8555

As mentioned above, the BM25 run with k1=0.82, b=0.68 corresponds to the entry "BM25 (Lucene8, tuned)" dated 2019/06/26 on the MS MARCO Passage Ranking Leaderboard. The BM25 run with default parameters k1=0.9, b=0.4 roughly corresponds to the entry "BM25 (Anserini)" dated 2019/04/10 (but Anserini was using Lucene 7.6 at the time).

Reproduction Log*