The recent years have been characterized by a strong democratization of news production on the web. In this scenario it is rare to find self-contained news articles that provide useful background and context information. The problem of finding information providing context to news articles has been tackled by the Background Linking task of the TREC News Track. In this paper, we propose a system to address the background linking task. Our system relies on LambdaMART learning to rank algorithm trained on classic textual features and on entity-based features. The idea is that the entities extracted from the documents as well as their relationships provide valuable context to the documents. We analyzed how this idea can be used to improve the effectiveness of (re-)ranking methods for the background linking task.
According to Pew Research studies carried out in 2018, the 93% of American
adults consume at least some of their news online, via social media
recommendations, web browsing or advertising recommendations [
In this paper, we present an IR system based on Learning to Rank methods to improve the ranking of documents for the Background Linking task context.
In the literature, several solutions were proposed to address this task. Most of
them treat background linking as an ad hoc search task and rely on approaches
based on keyword extraction [
We propose a retrieval system that relies on LambdaMART learning to rank
algorithm [
The rest of the article is organized as follows: in Section 2 we provide some background and related work, in Section 3 we describe the key components of the proposed solution and in Section 4 we present a use case. Section 5 describes the experimental setup and Section 6 reports about the evaluation results. 2
The TREC News Track aims to study how to provide contextual information
to users while reading news articles. To this end, two tasks are defined: Entity
Ranking and Background Linking. Background Linking Task concerns the
development of systems able to help users contextualize news articles as they are
reading them. Formally, given a source article (i.e., the query), the system should
retrieve a list of articles providing relevant background and context information
related to the source [
The reference collection for this task is the Washington Post Corpus ver.2.1 This collection contains about 590,000 news articles and blog posts published from 2012 to 2017 by the Washington Post2. Each document is characterized by a list of fields such as id, author, article URL, date of publication, title. The main content is organized in one or more paragraphs; they may include HTML tags, images and videos. Fifty topics have been provided for this task; each of them is identified by a number and by the id and the URL to the topic’s source document
Textual documents Bag of Entities
Initial Graph
Pruned Graph
Features Vectors
Re-rankings
of test documents
Final Run (or query ). Graded relevance judgments are ranging from 0 (not relevant) to 4 (recommended article).
In the proposed solution, we leverage document graph representation based
on the entities and their relationships that we automatically extract from the
documents. In the literature, several approaches take advantage of entity-oriented
representations. Xiong et al. in [
The main phases composing the proposed solution are reported in Figure 1. In the following, we describe every single phase.
Entity Linking. In this phase, we perform entity recognition on the textual
documents to extract a set of mentions to be linked with entities in a knowledge
repository (KR) [
Fusion. In this phase we experiment the fusion of multiple system’s runs to
analyze whether an increase in the number of merged runs corresponds to an
effectiveness improvement. Each run provided by the learning to rank phase
contains the same set of documents ranked differently. In order to create the
fusion runs we employ combSUM method [
To better illustrate how a graph of entities is created starting from a textual article, we employ a small portion of an article4 about tropical storms. Entity Linking. The mentions are detected and linked to Wikipedia entities. Below, we report the textual fragment where the mentions are marked in boldface.
Super Typhoon Vongfong explodes becomes most intense storm on Earth in 2014. Super Typhoon Vongfong has rapidly intensified over the past 24 hours from the equivalent of a category two hurricane to a monster typhoon [...] 4 Article available at: https://www.washingtonpost.com/news/capital-weathergang/wp/2014/10/07/super-typhoon-vongfong-explodes-becomes-most-intensestorm-on-earth-in-2014/
Storm
Tropical cyclone scales 0.483 0.514
In Table 2 we report the mentions and their linked entities. Giving a first look to the mention-entity associations, the largest part of entities are coherent with the tropical storms except for past tense and 24-hour clock which are very general or out of context. Graph Creation. The extracted entities are the nodes of the graph, while the edges are based on the semantic relatedness between the nodes. In Figure 2 we show the resulting graph. The two connected components are highly unbalanced because a component includes the largest part of entities while the second has only two entities. In the largest connected component lie the most meaningful entities, while the smallest one contains the two out of context entities, past tense and 24-hour clock.
Graph Pruning. Starting from the graph in Figure 2, we firstly remove the smallest connected component (right part in red). Then, we run the GirvanNewman algorithm that removes the Earth and Explosion entities. These entities are discarded because they have degree equal to one and they do not belong to the largest community. Nonetheless, if we consider these entities in the context of tropical storms, they do not bring any contribution for context identification, hence their removal increases the coherence of the graph with respect the topic. 5
In this section, we describe the experimental setup. In particular, we discuss some technical details, and we illustrate the tools used to implement each phase of the proposed solution.
Preprocessing. We preprocessed the Washington Post Corpus to remove from
each article all the fields without informative content. Then we indexed the
collection with Apache Solr5, an open-source search library based on Apache
Lucene set with the default English tokenizer, the English stop-words list and
no stemmer. Once indexed the collection, we used the default BM25 in Solr to
construct an initial ranking of 100 documents per topic: our baseline.
Entity Linking and Graph creation. Since it was unfeasible to analyze the entire
collection of documents in order to choose the most effective settings’ apporach,
we relied on a sample of thirty documents, both relevant and not relevant, and
we considered the setting the most effective on this sample. The linking system
we adopted is TagMe [
Features Extraction. To extract the set of textual-based features from each
document, we exploited Scikit-learn [
judgment of the document, the id of the query, the features extracted and the id of the document.
Learning to Rank. We relied on the implementation of LambdaMART provided by RankLib6, a library of learning to rank algorithms developed by the Lemur Project. We performed manual tuning, which allowed us to understand the best combinations of hyperparameters and analyze how each parameter interferes with the others. Table 3 summarizes the main features related to the training and test sets involved in our implementation. The test set comprises the vector representation of the documents belonging to the baseline. The training set, instead, combines two sets of topics belonging to different TREC tracks. We remark that even if both the training and test sets contain documents belonging to the Washington Post Corpus, they rely on disjointed sets of topics. Performing training depending on two different collections of documents allowed us to enrich the training set but, at the same time, it made our system suffer from the limitations induced by the transfer learning. In particular, what influenced our system the most was the lack of consistency between the relevance grades provided for the two tracks; indeed, we had to map the five possible relevance grades offered for the Background Linking task to the three grades provided for the Common Core Track of TREC 2017. The training set was finally split to derive a validation set. We trained the algorithm by choosing more than 200 different combinations of hyperparameters, and we selected the seventy models which maximized the nDCG@5 effectiveness on the validation set, and, at the same time, which were far from overfitting or underfitting conditions. In Table 4, the values of the five most effective models’ hyperparameters are described. We tested the seventy ranking models on the test set, and we obtained seventy final runs: each one contains a different re-ranking of the baseline documents. Fusion. To perform fusion we considered the ten most effective models and the related final runs. We fused k (with k = {2, 3, 5, 7, 10}) runs, and, for each k, we collected !10" runs – i.e. all the possible combinations of k distinct runs taken k from a set of ten runs.
Evaluation and metrics. Coherently with the guidelines of the task [
In this section we describe the results obtained by our system. We assess the retrieval effectiveness from both a quantitative and a qualitative viewpoint. 6.1
The quantitative evaluation has the intent to describe how our system performs on average. To this end, in Table 5 and Table 6 we illustrate the average results of the six selected runs and the baseline. We indicated the baseline as BM25, the best individual run as best run and the five best runs obtained with the fusion approach as fus followed by the number of runs fused. The top scores of each evaluation measure are highlighted in boldface.
In Table 5 we describe the performances of our system in terms of reciprocal rank, P@1 and nDCG@1: these metrics evaluate the effectiveness of one document per topic in a run. Our goal is to evaluate if our system can correctly recognize a relevant document and place it in the ranking’s highest positions. In general, all the generated runs show effectiveness slightly higher than the baseline both for reciprocal rank and nDCG@1. In P@1 instead, three runs equalled
the baseline (best run, fus2 and fus10 ) and three runs reported greater values (fus3, fus5 and fus7 ). The most effective run is fus5, obtained fusing five individual runs. It maximizes both reciprocal rank and P@1 evaluation measures. best run and fus7 instead, maximize the nDCG@1. Observing the reported results, we can notice that increasing the number of runs fused does not necessarily correspond to an effectiveness improvement. The effectiveness of fus5 and fus7 runs in fact, is usually higher than the effectiveness of fus2, fus3 and fus10 : this indicates that the fusion can improve the performances until a certain number of runs fused, after that, the fusion becomes disadvantageous and the effectiveness decreases. This is proved by fus10 which is the least effective run among the five fused runs. This behavior is verified in all the measures proposed in Table 5.
Table 6 reports the effectiveness of the proposed runs at different ranking depths. This analysis considers the nDCG evaluation measure at different cutoffs: 5, 10 and 100 (in this case, it is evaluated the entire ranking associated with each topic). In this analysis, we study our system’s ability to produce effective rankings. In particular, we are interested in how the effectiveness varies, increasing the cut-off. The results reported in terms of nDCG@5 highlight that the fus2, fus3, fus5 and fus7 runs have performances slightly above those of the baseline, while the best run approximates it very well. The least effective run in nDCG@5 is the fus10 which achieves the lowest result. If we consider more than five documents in the ranking, the BM25 model always reports the Fig. 3: This histogram represents the nDCG@5 effectiveness of the best run compared to the nDCG@5 of the baseline. Each column represents a topic and the column’s height is found computing the difference between the nDCG@5 of the best run and the nDCG@5 of the baseline for that topic. highest effectiveness. The highest results achieved by our system for nDCG@10 and nDCG@100 are those of fus5, while the lowest ones are attributed to the best run and fus10. As it has been already noticed in Table 5, this revealed that the fusion approach improves the system’s effectiveness, but it becomes disadvantageous if more than five runs are fused.
Discussion First, our hypothesis that fusing more runs leads to an effectiveness improvement does not seem to be supported. Both in Table 5 and Table 6 the fusion of all the available runs is the least effective run among the six proposed. We also see that there is no correlation between the number of runs fused and the effectiveness improvement. Despite this fact, the fusion approach has been revealed to be useful in our implementation, since among the selected runs, the fused ones achieve the highest results. Moreover, our system and the BM25 model show two opposite behaviors: the more documents we consider in the ranking, the more our system’s effectiveness decreases, and vice versa holds for the BM25 model. This contrast between our system and BM25 is primarily caused by the transfer learning. In fact, the effectiveness decrease detected after only five documents is strictly related to the inability of our system to distinguish among more than three relevance scores. 6.2
The qualitative evaluation describes the effectiveness of the particular topics belonging to a run. The histogram shown in Figure 3 describes the difference between the nDCG@5 score of the best run for a given topic and that one of the baseline. In particular, all the columns above the abscissa identify the topics where our system prevails over the baseline. Vice versa holds for the columns below the abscissa. It is possible to notice an equivalent number of topics laying above and below the abscissa; this means that the effectiveness improvement brought by the topics where our system prevails over the baseline is perfectly balanced by the effectiveness decrease caused by the topics where BM25 prevails over our system. This is the reason why, in the quantitative analysis, the nDCG@5 of the best run (0.4090) approximated the one of the baseline (0.4097). We conducted an analysis focused on the rankings associated with the best and the worst performing topics of the best run – this study aimed at finding a correlation between the documents’ feature vectors and our system’s effectiveness. The most compelling topics report in the first positions of their rankings documents whose relevance is identifiable both in the textual-based and in the entity-based graph features. This proves that relying on features that leverage the classic textual representation and the graph of entities can lead to an effectiveness improvement. Analyzing the rankings associated with the topics where the BM25 prevails, we identified three main reasons for our system’s poor effectiveness in some topics. These are: – The transfer learning: it prevented some topics from reaching a high level of effectiveness. – The graphs of entities: the documents may not present well-formed graphs; in this case, the learner attributes a score on the basis of the textual features only. This happens when the original article has not enough textual content to construct a consistent graph. – Errors in learning phase: this condition depends on the features in the vectors; we experimented that the value of a single feature may influence the entire ranking of a topic.
These conditions are unavoidable, and they represent the cases in which it is convenient to use the BM25 model. 7
This article presented a solution for the background linking task relying on LambdaMART to obtain a list of background articles. We leveraged the document’s textual and graph representations to extract a set of features used to perform training. Our goal was to study whether the combination of features belonging to different document representations can improve the system’s effectiveness; in particular, we were interested in exploring the impact related to the graphs of entities-based features. The analysis conducted on the single topics highlighted that there is a set of topics where our system outperformed the BM25 model. In these cases, the graphs of entities played a crucial role because the combination of textual-based features and graph-based ones allowed for an effectiveness improvement. This implied that our initial hypothesis is confirmed for this first set of topics. However, there was an equivalent number of topics where our system was not highly effective. Transfer learning has a high impact on negative performances. The balance between the effective and ineffective topics explained the similarity between the average nDCG@5 values obtained by our system and by the baseline. We finally introduced the fusion approach as a means to improve the overall effectiveness of our system. The results showed that, contrary to our initial belief, fusing too many runs makes the performances decrease; in particular, the optimal number of runs to merge, in the tested context, is five.