11institutetext: FEEC, UNICAMP, Brazil 22institutetext: NeuralMind, Brazil

#  ExaRanker:
Explanation-Augmented Neural Ranker

Fernando Ferraretto 11 Thiago Laitz 1122 Roberto Lotufo 1122
Rodrigo Nogueira 1122

###### Abstract

Recent work has shown that inducing a large language model (LLM) to generate
explanations prior to outputting an answer is an effective strategy to improve
performance on a wide range of reasoning tasks. In this work, we show that
neural rankers also benefit from explanations. We use LLMs such as GPT-3.5 to
augment retrieval datasets with explanations and train a sequence-to-sequence
ranking model to output a relevance label and an explanation for a given
query-document pair. Our model, dubbed ExaRanker, finetuned on a few thousand
examples with synthetic explanations performs on par with models finetuned on
3x more examples without explanations. Furthermore, the ExaRanker model incurs
no additional computational cost during ranking, and allows explanations to be
requested on demand. Code and data are available at
https://github.com/unicamp-dl/ExaRanker

##  1 Introduction

Pretrained transformers such as BERT [9] and T5 [34] finetuned on hundreds of
thousands of examples brought significant gains to information retrieval (IR)
tasks [23, 30, 26, 22, 14, 58, 60, 17, 12, 25, 43, 16, 50, 64]. When queries
and documents from a task of interest are similar to the ones in the
finetuning data, it is likely that a model will have an effectiveness better
than that of unsupervised models. For example, a monoT5 [31] reranker
finetuned on 400k positive query-passage pairs from MS MARCO [1] outperforms
BM25 [38] in 15 of 18 datasets of the BEIR benchmark [40, 39].

However, when the number of labeled examples is limited, the effectiveness of
the model decreases significantly. For example, a BERT reranker finetuned on a
mere 10k query-relevant passage pairs performs only slightly better than BM25
on the MS MARCO passage ranking benchmark [31]. Increasing the model size [40]
or pretraining it on IR-specific objectives [19, 13] alleviate the need for
more finetuning data, at the expense of increased computational resources.

We argue that one reason neural retrievers need extensive amounts of training
examples is that they are finetuned with categorical labels (e.g.,
true/false). These labels provide limited information about the task to be
learned, making it more challenging for the model to grasp the nuances of the
task. For example, imagine attempting to teach a human to evaluate the
relevance of passages to queries, but only being able to communicate the words
“true” or “false” per query-passage pair. The learning process would be more
efficient if explanations in natural language were provided to explain why a
passage is relevant or not to a given query.

In this work, we propose a method for training retrieval models using natural
language explanations as additional labels, which reduces the need for
training examples. Furthermore, we show that few-shot LLMs such as GPT-3.5
[33] can be effectively employed to automatically augment training examples
with explanations, enabling IR practitioners to apply our method to other
datasets without the need for manual annotation. Our findings indicate that
the utility of incorporating explanations decreases as the number of training
examples increases. Furthermore, our experimental results demonstrate that
finetuning a model to generate a label prior to an explanation leads to
superior performance in comparison to generating an explanation before the
target label. This outcome may be counterintuitive and contradicts previous
findings in chain-of-thought works[27].

##  2 Related Work

Recent research has shown that inducing a large language model to generate
step-by-step rationales in natural language improves performance in various
tasks that require reasoning [36, 10, 59, 62, 32, 21, 63, 18, 5]. However,
experiments using induced explanations are typically carried out on models
with billions of parameters, which are impractical to use in information
retrieval tasks. For example, reranking 100 passages for one query using a
model with 175B parameters would take at least one minute on four A100 GPUs.
In this work, we propose a method to distill the knowledge from these large
models and effectively use it to improve the quality of results in a ranking
task.

Our method is related to InPars [3, 20], Promptagator [8] and UPR [42], with
the distinction that we augment existing target labels from training datasets
with additional information relevant to the task at hand, rather than
generating queries from documents. We view InPars and Promptagator as
complementary to our method, and anticipate potential integration of these
approaches in future research.

A large body of work addresses the task of generating explanations for a
ranked list of results [45, 46, 55, 52, 41, 47, 11, 44, 48, 35, 65, 56, 61,
29]. For example, GenEx [35] generates noun phrases (e.g., “impacts on
medicare tax”) for a given query-document pair. Snippet generation can also be
regarded as providing explanations for why certain results are being presented
to the user [53, 54, 2, 6]. A key distinction of these works in comparison to
ours is that our goal is to use explanations as a means to improve the
effectiveness of a retrieval model, rather than solely for the purpose of
explaining a list of results to users. We do not claim that our method makes a
retriever interpretable as we have not evaluated the correctness of the
generated explanations. Our goal here is orthogonal to that of building
interpretable retrievers: we show that explanations improve the effectiveness
of retrievers. Nevertheless, our method may help users to understand a ranked
list of results, but further examination of this aspect is left for future
research.

##  3 Methodology

The proposed method is illustrated in Figure 1. It starts by generating
explanations for query-passage-label triples using an LLM model with in-
context examples. These training triples are then augmented with the generated
explanations, and a sequence-to-sequence model is finetuned to produce the
target label followed by the explanation. In the inference phase, the
finetuned model is used to estimate the relevance of a query-passage pair,
based solely on the probability assigned to the label token.

Figure 1: Method overview.

We begin by randomly selecting 15k pairs of (query, relevant passage) and
another 15k pairs of (query, non-relevant passage) from the training set of MS
MARCO passage ranking dataset, and then generate explanations for these 30k
pairs. Manually generating explanations for such a large volume of text would
be cost-prohibitive, so we use text-davinci-002111beta.openai.com with a few-
shot prompt to infer explanations for query-passage-label triples. We use
greedy decoding, and the output is limited to 256 tokens. The few-shot prompt,
illustrated in Figure 2, contains 7 examples that were selected from the MS
MARCO training dataset, and has an average of 1400 tokens, including the 256
tokens of the explanation to be generated. As of January 2023, generating an
explanation for each query-passage-label triple costs 0.028 USD using the
OpenAI API. Due to cost constraints, the dataset was limited to 30k examples,
which amounts to 840 USD.

Figure 2: Prompt used to generate explanations for a query-passage-label
triple (presented in Python’s f-string notation).

Note that we also use the label (relevant or not relevant) in the prompt and
request only the explanation for the triple query-passage-label. In
preliminary experiments, we noticed that the model generates better
explanations when the label is provided, as it is not confounded by the
classification task and can focus specifically on the explanation.

Once the 30k explanations are generated, a sequence-to-sequence model is
finetuned with the following input/output templates (shown using Python’s
f-string notation):

Input:
Is the question {query} answered by the {passage}? Give an explanation.

Output:
{label}. Explanation: {explanation}

The terms {query} and {passage} are the query-passage pair extracted from the
MS MARCO dataset. The {label} is true if the passage is relevant to the query
and false otherwise. Finally, {explanation} is the one generated by the LLM as
explained above. Figure 3 illustrates examples of input and output generated
by the model.

Figure 3: Illustration of input and generated outputs of a relevant (green)
and non-relevant (red) query-passage pair.

The T5-base model was used as the starting point for the finetuning phase. The
model was finetuned for 30 epochs using the AdamW optimizer [24] with a
learning rate of 3e-5, weight decay of 0.01, and batch size of 128 examples
(64 positives and 64 negatives). The maximum number of input and output tokens
were each limited to 512. Sequences exceeding these values were truncated
during both training and inference. For comparison purposes, a T5-base model
was also finetuned using the same hyperparameters and dataset, but without the
inclusion of explanations in the target text.

After finetuning, we evaluate the models on a passage ranking task. The input
to the model is the same as presented before, and, as a consequence, it
generates the same output pattern.222In our experiments the model always
generates an output that matches the target template. The probability of the
first output token is used as the relevance score $s$ for the query-passage
pair:

$s=\begin{cases}1+p_{0},&\text{if }t_{0}=\text{true}\\\ 1-p_{0},&\text{if
}t_{0}=\text{false}\\\ 0,&\text{otherwise}\end{cases}$

where $t_{0}$ is the token generated in the first decoding step and $p_{0}$ is
the probability assigned by the model to that token, i.e., the probability
from the softmax after the logits.

We limit the model to generate only the label for the query-passage pair
(i.e., the first token) and omit the full explanation text to save processing
time. Since the model was trained with causal mask, that is, only tokens
generated so far influence the prediction of the next token, the relevance
scores are the same had the model generated an explanation. Alternatively,
explanations can generated by decoding more tokens until the termination token
(e.g., <EOS>) is generated.

To evaluate the real benefits of explanation in a more realistic scenario in
which training data is not available, we evaluate the model in a zero-shot
manner on 6 datasets from the BEIR benchmark [51]: Robust04 [57], TREC-COVID
[37], DBPedia [15], FiQA [28], TREC-NEWS [49] and NFCorpus [4]. TREC-DL 2020
[7] is used as a validation set to select the best checkpoint and
hyperparameters.

##  4 Results

Main results are presented in Table 1. The first two rows are the BM25
baseline and the monoT5-base model finetuned on 400k positive query-passage
pairs from the MS MARCO dataset for one
epoch333https://huggingface.co/castorini/monot5-base-msmarco-10k. We focus our
analysis on the number of positive query-passage pairs as these need to be
manually annotated. Thus they are an expensive component when developing a
search engine. Negative query-passage pairs can be automatically selected
using a retriever once queries are gathered. We also need to generate
explanations for negative query-passage pairs, but we assume this cost will
decrease over time with the increased availability of open-sourced LLMs.

In the third and fourth rows, we compare models finetuned using the same
hyperparameters and examples, but without explanations (monoT5) and with
explanations (ExaRanker). The ExaRanker model outperforms the model without
explanations in all 7 datasets. On average, it improves the score by 0.8
nDCG@10 points in the zero-shot evaluation.

Compared to the BM25 baseline, the finetuned models have a much higher nDCG@10
scores. Also, ExaRanker finetuned on 15k and 10k positive examples are on
average 1.7 nDCG@10 points behind monoT5-400k, which has been finetuned on
400k positive examples. This result shows the benefits of using the
explanation to provide more data and reasoning during the training phase, and
enable the model to succeed with much less training data.

Model | Ft Pos. | DL 20 | Robust | Covid | Dbp | FiQA | News | NFC | Avg ZS
---|---|---|---|---|---|---|---|---|---
BM25 | - | 0.478 | 0.407 | 0.594 | 0.318 | 0.236 | 0.395 | 0.321 | 0.379
monoT5 | 400k | 0.652 | 0.536 | 0.777 | 0.419 | 0.413 | 0.447 | 0.357 | 0.491
monoT5 | 15k | 0.656 | 0.523 | 0.746 | 0.392 | 0.382 | 0.409 | 0.344 | 0.466
ExaRanker | 15k | 0.680 | 0.531 | 0.747 | 0.394 | 0.403 | 0.417 | 0.351 | 0.474
monoT5 | 10k | 0.643 | 0.510 | 0.749 | 0.379 | 0.374 | 0.426 | 0.341 | 0.463
ExaRanker | 10k | 0.667 | 0.527 | 0.752 | 0.409 | 0.393 | 0.418 | 0.347 | 0.474
monoT5 | 5k | 0.625 | 0.488 | 0.693 | 0.364 | 0.337 | 0.417 | 0.328 | 0.438
ExaRanker | 5k | 0.665 | 0.505 | 0.750 | 0.389 | 0.380 | 0.414 | 0.345 | 0.464
monoT5 | 2.5k | 0.611 | 0.486 | 0.666 | 0.334 | 0.328 | 0.370 | 0.325 | 0.418
ExaRanker | 2.5k | 0.650 | 0.496 | 0.686 | 0.393 | 0.306 | 0.398 | 0.335 | 0.436
Table 1: Main results (nDCG@10), including average zero-shot (all except DL
20). The column “Ft Pos.” is the number of positive training examples on which
the model was finetuned.

To better understand the benefits of using explanations, we have reproduced
the training methodology with smaller datasets: 20k, 10k and 5k examples. All
datasets have an equal number of positive and negative query-passage pairs.

The ExaRanker model outperforms the model finetuned without explanations in
all cases. It reinforces the evidence of the benefits of using explanations
and indicates that the model benefits more when datasets are smaller. When
finetuning on 15k positive examples, ExaRanker performs 0.8 points better than
monoT5. When finetuned on 10k examples, the improvement is 1.1 points and
increases to 2.6 when finetuned on 5k positive examples.

Figure 4 provides a visualization of this trend. We see that the improvement
in using explanations decreases as the number of samples increases. However,
we see a performance increase when explanations are used to augment labels
compared to finetuning without explanations. Comparing the monoT5 results
finetuned using 15k positive pairs with ExaRanker using 5k positive pairs, we
see that the average scores are very close but ExaRanker uses 3x less data for
finetuning. These results suggest that data augmentation through explanations
is an effective way to transfer knowledge from larger models.

Figure 4: Average zero-shot results on 6 datasets of the BEIR benchmark when
varying the number of training examples. monoT5-400k is finetuned on the 400k
relevant query-passage pairs from MS MARCO without explanations.

###  4.1 Qualitative Analysis

Table 2 presents some sample outputs for a qualitative comparison of the
correct and incorrect predictions made by ExaRanker on the TREC-DL 2020
dataset. The model is able to generate reasonable explanations: in the second
example, it was able to understand the context, correctly predicting the
relevance of the passage, even though it only mentions specific terms from the
query, such as “early pregnancy”. However, it may struggle with more fine-
grained relationships, such as correctly identifying the relationship between
electromagnetic waves and radio waves, as shown in the third example. Overall,
explanations appear to support a better understanding of the relationship
between the query and the passage, both quantitatively and qualitatively.

In summary, the purpose of this method is to use the explanations to provide
more information on how to perform the ranking task. However, the models do
not necessarily rely on reasoning to arrive at an answer. The explanations are
used to expedite the learning process, but the most relevant score for ranking
the relationship between sequences is concentrated in the label score,
specifically the true or false label indicating the relevance relation, rather
than in the entire explanation generated.

Input |  Output |  Target
---|---|---
Is the question: "average salary for dental hygienist in nebraska" answered by the document: "Dental Hygienist Salaries by Area. According to the Bureau of Labor Statistics, Dental Hygienists in the state of Nebraska can expect to earn an average of $65,236 annually or $31.36 per hour."? Give an explanation. |  true. Explanation: The question is about average salary for dental hygienist in nebraska. The passage describes the average salary for dental hygienist in Nebraska. |  true
Is the question: "can fever cause miscarriage early pregnancy?" answered by the document: "Pregnancy Early symptoms of pregnancy include a missed period, morning sickness, breast swelling, fatigue, and more. Chickenpox (varicella) Chickenpox is an illness that causes a red, itchy rash, fever, headache, sore throat, and body aches"? Give an explanation. |  false. Explanation: The question is about if fever can cause miscarriage early pregnancy. The passage is about early symptoms of pregnancy and chickenpox. |  false
Is the question: "what medium do radio waves travel through" answered by the document: "An electromagnetic wave (this includes light) does not require a physical medium - it can travel through empty space."? Give an explanation. |  false. Explanation: The question is about what medium do radio waves travel through. The passage is about electromagnetic waves and how they travel through empty space. |  true
Is the question: "do google docs auto save" answered by the document: "Inter-sheet formulas in Google Docs are similar to those used in Microsoft Excel. Using this ability, you can post a value automatically in a cell on one tab that is calculate or posted in a cell on another tab."? Give an explanation. |  true. Explanation: The question is about if google docs auto save. The passage describes how google docs auto save. |  false
Table 2: Outputs generated by the ExaRanker model.

###  4.2 Ablation Experiments

Two additional experiments were conducted to better understand the
contribution of adding explanations as target sequences in a ranking task.

First we finetuned another ExaRanker model for 30 epochs, with the same
hyperparameters but inverting the order in which label and explanations are
generated: first an explanation is generated, then a relevance label. It is
reasonable to expect that this order would lead to better results, as it
induces the model to elaborate on the relationship between query and passage
prior to predicting a label. However, as shown in Table 3, the nDCG@10 score
dropped 9.6 points compared to generating a relevance label followed by an
explanation. We believe that this behavior is due to the difficulty of using a
ranking score from multiple tokens. We tried different approaches, such as
using the average token probabilities of the entire sequence or using only the
probability of the final token (true or false). In all cases, nDCG@10 was
lower than the method described in Section 3.

Output template | nDCG@10
---|---
{label}. Explanation: {explanation}. | 0.680
Explanation: {explanation}. {label}. | 0.584
Table 3: Ablation of the output template. Results are on TREC DL 2020 and the
models were finetuned on 15k positive + 15k negative examples.

In a second ablation study, we tested if explanations would improve a model
already finetuned on a large ranking dataset. For that, we further finetuned
on 15k positive + 15k negative examples with explanations a monoT5-base model
already finetuned on 400k positive pairs from MS MARCO. Results in Table 4
show a negligible difference of 0.2 nDCG@10 points compared to the model
finetuned only on labels. As explained before, we expect the benefits of
explanations to be reduced when large training data is available. This
experiment demonstrated, however, that finetuning on explanations does not
negatively affect a ranker’s effectiveness while equipping it with the
capability of generating explanations for its relevance predictions.

Model | DL 20 | Robust | Covid | Dbp | FiQA | News | NFC | Avg
---|---|---|---|---|---|---|---|---
monoT5 (ft on 400k pos) | 0.652 | 0.536 | 0.777 | 0.419 | 0.413 | 0.447 | 0.357 | 0.514
ExaRanker (from monoT5) | 0.701 | 0.528 | 0.756 | 0.398 | 0.406 | 0.442 | 0.352 | 0.512
Table 4: Results on finetuning Exaranker from a monoT5-base model finetuned on
400k positive examples from MS MARCO.

##  5 Conclusion

We have proposed a method for training information retrieval (IR) models using
natural language explanations as additional labels, which reduces the need for
a large number of training examples. Our results demonstrate that the use of
explanations can significantly improve the performance of IR models,
particularly when fewer labeled examples are available.

Finally, we showed that large language models can be used to effectively
generate these explanations, thus allowing our method to be applied to other
IR domains and tasks. Importantly, our method does not significantly increase
the time required to rerank passages as only the true/false token is used
during inference. The source code and datasets used in this study are
available for public use in the accompanying repository for future research
and advancements of the ExaRanker method.

## Acknowledgments

This research was partially funded by grant 2022/01640-2 from Fundação de
Amparo à Pesquisa do Estado de São Paulo (FAPESP).

## References

  * [1] P. Bajaj, D. Campos, N. Craswell, L. Deng, J. Gao, X. Liu, R. Majumder, A. McNamara, B. Mitra, T. Nguyen, M. Rosenberg, X. Song, A. Stoica, S. Tiwary, and T. Wang.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.  arXiv:1611.09268v3, 2018.
  * [2] H. Bast and M. Celikik.  Efficient index-based snippet generation.  ACM Transactions on Information Systems (TOIS), 32(2):1–24, 2014\.
  * [3] L. Bonifacio, H. Abonizio, M. Fadaee, and R. Nogueira.  Inpars: Unsupervised dataset generation for information retrieval.  In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2387–2392, 2022.
  * [4] V. Boteva, D. Gholipour, A. Sokolov, and S. Riezler.  A full-text learning to rank dataset for medical information retrieval.  In European Conference on Information Retrieval, pages 716–722. Springer, 2016.
  * [5] M. Bueno, C. Gemmel, J. Dalton, R. Lotufo, and R. Nogueira.  Induced natural language rationales and interleaved markup tokens enable extrapolation in large language models.  arXiv preprint arXiv:2208.11445, 2022.
  * [6] W.-F. Chen, S. Syed, B. Stein, M. Hagen, and M. Potthast.  Abstractive snippet generation.  In Proceedings of The Web Conference 2020, pages 1309–1319, 2020\.
  * [7] N. Craswell, B. Mitra, E. Yilmaz, and D. Campos.  Overview of the TREC 2020 deep learning track.  CoRR, abs/2102.07662, 2021.
  * [8] Z. Dai, V. Y. Zhao, J. Ma, Y. Luan, J. Ni, J. Lu, A. Bakalov, K. Guu, K. B. Hall, and M.-W. Chang.  Promptagator: Few-shot dense retrieval from 8 examples.  arXiv preprint arXiv:2209.11755, 2022.
  * [9] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
  * [10] P. Fernandes, M. Treviso, D. Pruthi, A. F. Martins, and G. Neubig.  Learning to scaffold: Optimizing model explanations for teaching.  arXiv preprint arXiv:2204.10810, 2022.
  * [11] Z. T. Fernando, J. Singh, and A. Anand.  A study on the interpretability of neural retrieval models using deepshap.  In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1005–1008, 2019.
  * [12] T. Formal, B. Piwowarski, and S. Clinchant.  Splade: Sparse lexical and expansion model for first stage ranking.  In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2288–2292, 2021.
  * [13] L. Gao and J. Callan.  Unsupervised corpus aware language model pre-training for dense passage retrieval.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2843–2853, Dublin, Ireland, May 2022. Association for Computational Linguistics.
  * [14] L. Gao, Z. Dai, and J. Callan.  Rethink training of bert rerankers in multi-stage retrieval pipeline.  arXiv preprint arXiv:2101.08751, 2021.
  * [15] F. Hasibi, F. Nikolaev, C. Xiong, K. Balog, S. E. Bratsberg, A. Kotov, and J. Callan.  Dbpedia-entity v2: a test collection for entity search.  In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1265–1268, 2017.
  * [16] S. Hofstätter, O. Khattab, S. Althammer, M. Sertkan, and A. Hanbury.  Introducing neural bag of whole-words with colberter: Contextualized late interactions using enhanced reduction.  arXiv preprint arXiv:2203.13088, 2022.
  * [17] S. Hofstätter, S.-C. Lin, J.-H. Yang, J. Lin, and A. Hanbury.  Efficiently teaching an effective dense retriever with balanced topic aware sampling.  In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 113–122, 2021.
  * [18] J. Huang, S. S. Gu, L. Hou, Y. Wu, X. Wang, H. Yu, and J. Han.  Large language models can self-improve.  arXiv preprint arXiv:2210.11610, 2022.
  * [19] G. Izacard, M. Caron, L. Hosseini, S. Riedel, P. Bojanowski, A. Joulin, and E. Grave.  Unsupervised dense information retrieval with contrastive learning, 2021\.
  * [20] V. Jeronymo, L. Bonifacio, H. Abonizio, M. Fadaee, R. Lotufo, J. Zavrel, and R. Nogueira.  Inpars-v2: Large language models as efficient dataset generators for information retrieval, 2023.
  * [21] U. Katz, M. Geva, and J. Berant.  Inferring implicit relations with language models.  arXiv preprint arXiv:2204.13778, 2022.
  * [22] C. Li, A. Yates, S. MacAvaney, B. He, and Y. Sun.  Parade: Passage representation aggregation for document reranking.  arXiv preprint arXiv:2008.09093, 2020.
  * [23] J. Lin, R. Nogueira, and A. Yates.  Pretrained transformers for text ranking: Bert and beyond.  Synthesis Lectures on Human Language Technologies, 14(4):1–325, 2021.
  * [24] I. Loshchilov and F. Hutter.  Decoupled weight decay regularization.  In International Conference on Learning Representations, 2019.
  * [25] S. Lu, D. He, C. Xiong, G. Ke, W. Malik, Z. Dou, P. Bennett, T.-Y. Liu, and A. Overwijk.  Less is more: Pretrain a strong Siamese encoder for dense text retrieval using a weak decoder.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2780–2791, Online and Punta Cana, Dominican Republic, Nov. 2021. Association for Computational Linguistics.
  * [26] S. MacAvaney, A. Yates, A. Cohan, and N. Goharian.  Cedr: Contextualized embeddings for document ranking.  In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1101–1104, 2019.
  * [27] L. C. Magister, J. Mallinson, J. Adamek, E. Malmi, and A. Severyn.  Teaching small language models to reason, 2023.
  * [28] M. Maia, S. Handschuh, A. Freitas, B. Davis, R. McDermott, M. Zarrouk, and A. Balahur.  Www’18 open challenge: Financial opinion mining and question answering.  In Companion Proceedings of the The Web Conference 2018, WWW ’18, page 1941–1942, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee.
  * [29] S. Mysore, A. Cohan, and T. Hope.  Multi-vector models with textual guidance for fine-grained scientific document similarity, 2022.
  * [30] R. Nogueira and K. Cho.  Passage re-ranking with bert.  arXiv preprint arXiv:1901.04085, 2019.
  * [31] R. Nogueira, Z. Jiang, R. Pradeep, and J. Lin.  Document ranking with a pretrained sequence-to-sequence model.  In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 708–718, 2020.
  * [32] M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, C. Sutton, and A. Odena.  Show your work: Scratchpads for intermediate computation with language models.  In Deep Learning for Code Workshop, 2022.
  * [33] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al.  Training language models to follow instructions with human feedback.  arXiv preprint arXiv:2203.02155, 2022.
  * [34] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, P. J. Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  J. Mach. Learn. Res., 21(140):1–67, 2020.
  * [35] R. Rahimi, Y. Kim, H. Zamani, and J. Allan.  Explaining documents’ relevance to search queries.  arXiv preprint arXiv:2111.01314, 2021.
  * [36] G. Recchia.  Teaching autoregressive language models complex tasks by demonstration.  arXiv preprint arXiv:2109.02102, 2021.
  * [37] K. Roberts, T. Alam, S. Bedrick, D. Demner-Fushman, K. Lo, I. Soboroff, E. Voorhees, L. L. Wang, and W. R. Hersh.  TREC-COVID: rationale and structure of an information retrieval shared task for COVID-19.  Journal of the American Medical Informatics Association, 27(9):1431–1436, 07 2020.
  * [38] S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, M. Gatford, et al.  Okapi at trec-3.  Nist Special Publication Sp, 109:109, 1995.
  * [39] G. Rosa, L. Bonifacio, V. Jeronymo, H. Abonizio, M. Fadaee, R. Lotufo, and R. Nogueira.  In defense of cross-encoders for zero-shot retrieval.  arXiv preprint arXiv:2212.06121, 2022.
  * [40] G. M. Rosa, L. Bonifacio, V. Jeronymo, H. Abonizio, M. Fadaee, R. Lotufo, and R. Nogueira.  No parameter left behind: How distillation and model size affect zero-shot retrieval.  arXiv preprint arXiv:2206.02873, 2022.
  * [41] D. Roy, S. Saha, M. Mitra, B. Sen, and D. Ganguly.  I-rex: a lucene plugin for explainable ir.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2949–2952, 2019.
  * [42] D. S. Sachan, M. Lewis, M. Joshi, A. Aghajanyan, W.-t. Yih, J. Pineau, and L. Zettlemoyer.  Improving passage retrieval with zero-shot question generation.  2022\.
  * [43] K. Santhanam, O. Khattab, J. Saad-Falcon, C. Potts, and M. Zaharia.  ColBERTv2: Effective and efficient retrieval via lightweight late interaction.  In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3715–3734, Seattle, United States, July 2022. Association for Computational Linguistics.
  * [44] P. Sen, D. Ganguly, M. Verma, and G. J. Jones.  The curious case of ir explainability: Explaining document scores within and across ranking models.  In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2069–2072, 2020.
  * [45] J. Singh and A. Anand.  Interpreting search result rankings through intent modeling.  arXiv preprint arXiv:1809.05190, 2018.
  * [46] J. Singh and A. Anand.  Posthoc interpretability of learning to rank models using secondary training data.  arXiv preprint arXiv:1806.11330, 2018.
  * [47] J. Singh and A. Anand.  Exs: Explainable search using local model agnostic interpretability.  In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 770–773, 2019.
  * [48] J. Singh, Z. Wang, M. Khosla, and A. Anand.  Valid explanations for learning to rank models.  arXiv preprint arXiv:2004.13972, 2020.
  * [49] I. Soboroff, S. Huang, and D. Harman.  Trec 2018 news track overview.
  * [50] N. Thakur, N. Reimers, and J. Lin.  Domain adaptation for memory-efficient dense retrieval.  arXiv preprint arXiv:2205.11498, 2022.
  * [51] N. Thakur, N. Reimers, A. Rücklé, A. Srivastava, and I. Gurevych.  Beir: A heterogeneous benchmark for zero-shot evaluation of information retrieval models.  In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
  * [52] P. Thomas, B. Billerbeck, N. Craswell, and R. W. White.  Investigating searchers’ mental models to inform search explanations.  ACM Transactions on Information Systems (TOIS), 38(1):1–25, 2019\.
  * [53] A. Tombros and M. Sanderson.  Advantages of query biased summaries in information retrieval.  In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 2–10, 1998.
  * [54] A. Turpin, Y. Tsegay, D. Hawking, and H. E. Williams.  Fast generation of result snippets in web search.  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 127–134, 2007.
  * [55] M. Verma and D. Ganguly.  Lirme: locally interpretable ranking model explanation.  In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1281–1284, 2019.
  * [56] M. Völske, A. Bondarenko, M. Fröbe, B. Stein, J. Singh, M. Hagen, and A. Anand.  Towards axiomatic explanations for neural ranking models.  In Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval, pages 13–22, 2021.
  * [57] E. Voorhees.  Overview of the trec 2004 robust retrieval track, 2005-08-01 2005.
  * [58] K. Wang, N. Thakur, N. Reimers, and I. Gurevych.  Gpl: Generative pseudo labeling for unsupervised domain adaptation of dense retrieval.  arXiv preprint arXiv:2112.07577, 2021.
  * [59] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou.  Self-consistency improves chain of thought reasoning in language models.  arXiv preprint arXiv:2203.11171, 2022.
  * [60] J. Xin, C. Xiong, A. Srinivasan, A. Sharma, D. Jose, and P. N. Bennett.  Zero-shot dense retrieval with momentum adversarial domain invariant representations.  arXiv preprint arXiv:2110.07581, 2021.
  * [61] P. Yu, R. Rahimi, and J. Allan.  Towards explainable search results: A listwise explanation generator.  In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 669–680, 2022.
  * [62] E. Zelikman, Y. Wu, and N. D. Goodman.  Star: Bootstrapping reasoning with reasoning.  arXiv preprint arXiv:2203.14465, 2022.
  * [63] D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, O. Bousquet, Q. Le, and E. Chi.  Least-to-most prompting enables complex reasoning in large language models.  arXiv preprint arXiv:2205.10625, 2022.
  * [64] H. Zhuang, Z. Qin, R. Jagerman, K. Hui, J. Ma, J. Lu, J. Ni, X. Wang, and M. Bendersky.  Rankt5: Fine-tuning t5 for text ranking with ranking losses.  arXiv preprint arXiv:2210.10634, 2022.
  * [65] H. Zhuang, X. Wang, M. Bendersky, A. Grushetsky, Y. Wu, P. Mitrichev, E. Sterling, N. Bell, W. Ravina, and H. Qian.  Interpretable ranking with generalized additive models.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 499–507, 2021.


# Benchmarking Named Entity Disambiguation approaches for Streaming Graphs

Sutanay Choudhury, Chase Dowling

##  1\. Introduction

Named Entity Disambiaguation (NED) is a central task for applications dealing
with natural language text. Assume that we have a graph based knowledge base
(subsequently referred as Knowledge Graph) where nodes represent various real
world entities such as people, location, organization and concepts. Given data
sources such as social media streams and web pages Entity Linking is the task
of mapping named entities that are extracted from the data to those present in
the Knowledge Graph. This is an inherently difficult task due to several
reasons. Almost all these data sources are generated without any formal
ontology; the unstructured nature of the input, limited context and the
ambiguity involved when multiple entities are mapped to the same name make
this a hard task.

Our exploration is motivated by the objective of incremental maintenance of
Knowledge Graphs, where we continuously monitor data streams and update the
Knowledge Graph with information from newer events. A good Entity
Linking/Named Entity Disambiguation solution needs to perform well on three
aspects for our target setting.

  1. (1)

Scalability The solution needs to support very large Knowledge Graphs. As the
graphs grow in size, the number of candidates for mapping an entity increases.

  2. (2)

Speed Throughput is an important factor in a streaming setting. We can not
afford to select algorithms that do not satisfy a runtime constraint.

  3. (3)

Accuracy For the same algorithm, its accuracy can vary depending on the nature
of the input. The same entity linking system can perform poorly as we go from
well structured wikipedia pages to short text excerpts from social media.

With the above in mind, we looked at two state of the art systems employing
two distinctive approaches: graph based Accurate Online Disambiguation of
Entities (AIDA) and Mined Evidence Named Entity Disambiguation (MENED), which
employs a statistical inference approach. We compare both approaches using the
data set and queries provided by the Knowledge Base Population (KBP) track at
2011 NIST Text Analytics Conference (TAC). This report begins with an overview
of the respective approaches, followed by detailed description of the
experimental setup. It concludes with our findings from the benchmarking
exercise.

##  2\. Background

Within in the broader field of named entity disambiguation, we focus on
Knowledge Base Population problem as introduced by the NIST Text Analytics
Conference (TAC) [5]. This competition uses a 2008 version of Wikipedia as the
Knowledge Base (KB). Given a string referring to a person, organization or
geo-political entity name and a background document providing contextual
information, the entity linking task requires a system to return the ID of an
entity in the knowledge base if it exists, else return NIL.

###  2.1. Problem Statement

We have a knowledge base $KB=(D,F,N)$ where $D$, $F$ and $N$ represent a
collection of documents, features and names. $C$ contains information about a
set of entities $E$. Each $d_{k}\in D$ corresponds to an entity $e_{i}\in E$,
and has a feature vector $F_{k}$ and a name $N_{k}$ associated with it. A
query is a three-tuple $Q=(Q_{t},Q_{n},Q_{d})$. $Q_{n}$ indicates the name of
the queried entity. $Q_{t}$ is the type of the queried entity, which is one of
the following: (a) person, (b) geo-political entity, (c) topic and (d)
unknown. The query contains a sample document describing the query context,
which is referred to as $Q_{d}$. As an example, a query may contain “John” as
the query name, ”person” as query type and a sample publication to provide the
contextual information.

Problem Definition Given a query $Q$, the goal of the entity disambiguation
system is to provide a query function $f(Q)$ that returns the most relevant
entity in the knowledge base if it exists, or NIL if it does not exist.

The entity linking process contains 3 steps: 1) pre-processing the query to
clean or expand into multiple forms using domain background 2) generating a
list of all candidate entities in the KB that are potential matches for the
query and 3) ranking the candidates in terms of match quality.

###  2.2. Graph-based approach

Given a query string name and a background document, a graph based approach
will extracts all potential entities from the background document. It builds a
query graph that includes the entity name, and other potential entities
connected via appropriate relations. Given this query graph, the algorithm
selects the entity in the Knowledge Graph whose neighborhood provides closest
mapping to the query graph. Finding the distances between two entities is a
critical step in the computation process for entity disambiguation solutions
that rely on a graph based approach. The distance computation can be performed
by considering multiple factors such as semantic association, specialization
of the semantic association, association length and rarity of associations [1,
3].

We evaluated the AIDA algorithm developed by Hoffart et al. [4]. AIDA
identifies all meaningful entities within a document (ignoring personal
pronouns, etc) and assigns them a label corresponding to a document within the
Knowledge Graph. By considering multiple entities within a document
simultaneously, the algorithm boils down to a graph matching problem finding
expected concurrent entities within the Knowledge Graph. Model parameters are
encoded in entity linking priors (probability that any two Knowledge Graph
entities are semantically related) and remained unchanged within the Knowledge
Graph. AIDA requires a trained and annotated graphical version of Wikipedia to
serve as a Knowledge Graph, however, no other preprocessing is required;

###  2.3. Statistical approach

This class of solutions exploit that fact that the context for any entity
(query or candidate) can be distinguished by a set of representative words.
The reason why context can help disambiguation is that each referent entity
candidate can be distinguished by a set of representative words. Those
representative words can be seen as the disambiguation evidences for those
entity candidates. Therefore it is natural to model each entity as a topic and
imagine those representative words are generated from such topics. Thus a
representative document for an entity such as a Wikipedia article can be
viewed as an unique topic composed of the words. Given a query entity such
algorithms will choose from candidates that is most topically coherent.

We implemented the MENED algorithm developed by Li et al. [6]. MENED is a
semi-supervised learning algorithm employing a generative version of Latent
Dirichlet Allocation [2]. MENED was designed for short text queries, using
word concurrence to search for candidate document labels before performing a
generative version of LDA on all candidate document labels to infer the
correct label for the query document.

##  3\. Comparison of disambiguation algorithms

Configuring AIDA AIDA is available via Github and version stability is ensured
by a web-based build/test server. The AIDA graph matching algorithm and
dependencies (e.g. Stanford NER) are combined into a single Java package and
can be run as a restful API. Because learned parameters are encoded in AIDA’s
knowledge base, multiple instances of AIDA can be run concurrently.

Configuring MENED Parameter and hyper-parameter selection is driven by small
samples of the query corpus. Publication parameters ($\alpha=0.001$,
$\alpha_{df}=0.01$, $\beta=0.001$, $\beta_{df}=0.01$, $\beta_{bg}=0.1$,
$\gamma_{1}=0.0003$, $\gamma_{2}=0.001$) were accurate to the order of
magnitude after sampling our query data set and were left unchanged.
Unprocessed TAC 2009 Wikipedia text data was used as the knowledge base for
experimental reproduction of the authors’ results. Data was stored in an
Elastic Search database, a restful API serving JSON objects built on Apache
Lucene for cloud databasing applications. Search results are scored using
Lucene’s built-in TF-IDF relevancy scoring. Query data and mined candidate
entity data were preprocessed by removing stop words and roughly tokenized
(removing punctuation and attempting to capture unrelated text such as URL’s).

###  3.1. Software Usability/Scaling

Figure 1 shows the runtimes for both AIDA and MENED running the TAC benchmark.
AIDA’s runtime appears to increase linearly as a function of entity mentions
and MENED’s appears to increase linearly as a function of document length
although we suspect polynomial complexity. Classical LDA is known to be NP-
Hard [7]. Neither publication provides explicit runtime complexities, however,
AIDA claims to be designed for online applications and empirical measurements
of runtime in seconds showed most disambiguation tasks taking less than 60
seconds. We restricted maximum runtimes to 600 seconds.

Figure 1. TAC Benchmark runtimes for AIDA and MENED

Nearly all of AIDA’s incorrect label assignments came from forcing a label on
a NIL or wildcard query document based on the TAC benchmark’s ground truth.
Although AIDA should exceed 80% for general queries, we were able to achieve
79% accuracy on TAC benchmark data. TAC benchmark data assigns a single label
to entire documents, while AIDA identifies labels for all named entities
within a document. As long as one of the disambiguated entities from within
the document corresponded with the document label, we counted the
disambiguation as correct. We did not attempt to set a minimum threshold of
certainty for which the NIL label would be selected as query document lengths
varied greatly.

We were unable to achieve MENED’s claimed accuracy of approximately 70-80% for
two reasons: 1) the MENED algorithm used the Google Search API combined with a
Wikipedia repository of 2012 as a knowledge base whereas we made use of the
TAC 2009 Wiki raw text dump only and 2) we were unable to specify the
conditions under which query documents were curated in the original test (e.g.
when original authors tested MENED on Twitter posts, tweets were hand selected
for disambiguation in order to create a set with ground truth available). At
best we achieve approximately 35% accuracy, correctly assigning NIL to all
wildcard query documents and in disambiguating hyper-specific queries.

In making use of the Google Search API, MENED acquires an implicit measure of
search relevance in entity candidate selection (e.g. searching Queen Elizabeth
invariably yields the current monarch as opposed to her predecessor).
Moreover, searches of our knowledge base were constrained to TF-IDF measures
of document relevancy. Queen Elizabeth happens to have the greatest weight in
the Wikipedia article about the monarchy of New Zealand, where the extremely
short summary mentions Queen Elizabeth II three times.

###  3.2. Example queries

We produce two example queries:

1: ”Einstein was born in Ulm.”

2: ”When Page played Kashmir at Knebworth, his Les Paul was uniquely tuned.”

AIDA produces the following annotated text for 1:
http://en.wikipedia.org/wiki/Albert_Einstein Einstein was born in
http://en.wikipedia.org/wiki/Ulm Ulm. and for 2: When Page played
http://en.wikipedia.org/wiki/Kashmir_(song) Kashmir at
http://en.wikipedia.org/wiki/Knebworth_Festival_1979 Knebworth, his
http://en.wikipedia.org/wiki/Gibson_Les_Paul Les Paul was uniquely tuned.

MENED incorrectly labels the first sentence with ”NIL” as the most likely
label, following by ”Mileva Mari”, a fellow student and Einsteins first wife.
The second setence is labeled with the top three results being
”Les_pauvres_riches”, ”Les_Contrebandi”, and ”Kashmir” the region. This
largely due to conflicting entity concurrence in the query and entity search
relavance (”Kashmir” the song, when searched directly using TF-IDF and without
the Google Search API, is the 5th most likely result).

##  4\. Conclusions and Future Research

We compare two, reportedly robust entity disambiguation algorithms using the
2011 TAC entity disambiguation benchmark dataset. Each system was evaluated
with a Cloud-based deployment in mind. The MENED algorithm was implemented
using a Cloud based database, while the AIDA algorithm was deployed and used
as a web service. Although the goal of each algorithm differs slightly, we
achieve high accuracy with AIDA, and moderate to low accuracy using MENED.
Although MENED attempts to apply a more flexible label to an entire document,
AIDA treats individually identified entities within a document with high
accuracy. We recommend AIDA for anyone seeking an out of the box solution. Its
high accuracy is also a testament to the relevance of graph based approaches
in Natural Language Processing.

One of MENED’s novel contributions is that with streaming data such as social
media text, it updates the knowledge base with newly inferred facts to improve
query processing accuracy. This ostensibly allows the knowledge base to handle
more vague, up to the minute queries and attribute black swan type events. We
propose integrating MENED’s machine learning approaches with AIDA’s graph
search based approach as a future research path. This will enable updating the
Knowledge Graph by adding new semantic relationships, allowing stale
relationships to fall off, and updating relationship probability priors as
inferences are made on streaming data.

## References

  * [1] B. Aleman-Meza, C. Halaschek-Weiner, I. B. Arpinar, C. Ramakrishnan, and A. P. Sheth.  Ranking complex relationships on the semantic web.  Internet Computing, IEEE, 9(3):37–44, 2005.
  * [2] D. M. Blei, A. Y. Ng, and M. I. Jordan.  Latent dirichlet allocation.  the Journal of machine Learning research, 3:993–1022, 2003.
  * [3] L. Fang, A. D. Sarma, C. Yu, and P. Bohannon.  Rex: Explaining relationships between entity pairs.  Proceedings of the VLDB Endowment, 5(3):241–252, 2011.
  * [4] J. Hoffart, M. A. Yosef, I. Bordino, H. Fürstenau, M. Pinkal, M. Spaniol, B. Taneva, S. Thater, and G. Weikum.  Robust disambiguation of named entities in text.  In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 782–792. Association for Computational Linguistics, 2011.
  * [5] H. Ji and R. Grishman.  Knowledge base population: Successful approaches and challenges.  In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 1148–1158. Association for Computational Linguistics, 2011.
  * [6] Y. Li, C. Wang, F. Han, J. Han, D. Roth, and X. Yan.  Mining evidences for named entity disambiguation.  In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1070–1078. ACM, 2013.
  * [7] D. Sontag and D. Roy.  Complexity of inference in latent dirichlet allocation.  In NIPS, pages 1008–1016, 2011.