1 Introduction
Information Retrieval (IR) deals with the representation, storage, organisation and access to information itemsFootnote 1 (Baeza-Yates and Ribeiro-Neto Reference Baeza-Yates and Ribeiro-Neto1999). Given some query, formulated in natural language by a user, the IR system is suppose to retrieve and sort according to their relevance degree documents satisfying user's information needs (Grossman and Frieder Reference Grossman and Frieder2004).
The word relevant means that retrieved documents should be semantically related to the user information need. Hence, one main problem of IR is determining which documents are, and which are not relevant. In practice, this problem is usually regarded as a ranking problem, whose goal is to define an ordered list of documents such that documents similar to the query occur at the very first positions.
Over the past years, IR Models, such as: Boolean, Vectorial, Probabilistic and Language models have represented a document as a set of representative keywords (i.e. index terms) and defined a ranking function (or retrieval function) to associate a relevance degree for each document with its respective query (Baeza-Yates and Ribeiro-Neto Reference Baeza-Yates and Ribeiro-Neto1999; Grossman and Frieder Reference Grossman and Frieder2004). In general, these models have shown to be quite effective over several tasks in different evaluation forums (CLEFFootnote 2 and TRECFootnote 3). Nevertheless, these retrieval systems still fail at retrieving most of the relevant documents to a given query in the first positions. The latter is due to the fact that modelling user intentions from queries is, in general, a highly subjective and difficult task, hence, post-processing and ranking refinement strategies have been adopted (Yang, Ji and Tang 2006; Sarkar and Moore Reference Sarkar and Moore2009; Villatoro-Tello, Montes-y-Gómez and Villaseñor-Pineda Reference Villatoro-Tello, Montes-y-Gómez and Villaseñor-Pineda2009a, Reference Villatoro-Tello, Villaseñor-Pineda and Montes-y-Gómez2009b; Chávez, Sucar and Montes 2010; Zhou et al. Reference Zhou, Lawless, Min and Wade2010a, Reference Zhou, Lawless, Min and Wade2010b).
Post-retrieval techniques aim at refining retrieval results by feature re-weighting, query modification, document re-ranking and relevance feedback. The common idea is to interact with the user in order to learn or to improve a model of the underlying user's information need. Acceptable results have been obtained with such methods, however, they still have several limitations, including: (i) the need of extensive user interactionFootnote 4; (ii) multiple execution of retrieval models; (iii) the on-line construction of classification methods; (iv) the lack of contextual information in the post-retrieval processing, which may be helpful for better modelling users' information needs; and (v) the computational cost that involves processing the entire collection of documents each feedback iteration.
1.1 Our approach
This paper introduces an alternative post-retrieval technique that aims at improving the results provided by a document retrieval system and that overcomes some of the limitations of current post-retrieval methods. In particular, we face the problem of re-rankingFootnote 5 a list of documents retrieved by some IR system. This problem is motivated by the availability of retrieval systems that present high-recall and low-precision performance, which evidences that the corresponding retrieval system is in fact able to retrieve many relevant documents but has severe difficulties to generate a pertinent ranking of them. Hence, given a list of ranked documents, the problem we approach consists of moving relevant documents to the first positions and displacing irrelevant ones to the final positions in the list.
We propose a solution to the ranking refinement problem based on a Markov Random Field (MRF) (Kemeny, Snell and Kanpp 1976; Pearl Reference Pearl1988; Lauritzen Reference Lauritzen1996; Winkler Reference Winkler, Rozovskii and Yor2006) that aims at classifying the ranked documents as relevant or irrelevant. Each document in the retrieved list is associated to a binary random variable in the MRF (i.e. a node), the value of each random variable indicates whether a document is considered relevant (when its value is 1) or not (when its value is 0). The MRF considers several aspects: (1) the information provided by the base IR system, (2) similarities among retrieved documents in the list and (3) information obtained through a relevance feedback process. Accordingly, we reduce the problem of ranking refinement to that of minimising an energy function that represents a trade-off between document relevance and inter-document similarity. The information provided by the IR system is the base of our method, which is further enriched with contextual and relevance feedback information.
Our motivation for considering context information is that relevant documents to a query will be similar to each other and to its respective query, to some extent; whereas irrelevant documents will be different among them and not as similar to the query as the relevant documentsFootnote 6. Relevance feedback information has two main purposes: (i) to work as a seed generation mechanism for propagating the relevancy/irrelevancy status of nodes (documents) in the MRF, and (ii) to denote the users' search intention by working as example texts.
At this point, it is important to mention that, traditionally a relevance feedback process takes as input a set of n documents (tentatively relevant) and generates as output a set of k isolated terms (tentatively relevant to the query) which are further employed for a query expansion (QE) process. For our purposes, we will employ the complete documents (called example texts), since by doing this, we have showed (Villatoro-Tello et al. Reference Villatoro-Tello, Montes-y-Gómez and Villaseñor-Pineda2009a, Reference Villatoro-Tello, Villaseñor-Pineda and Montes-y-Gómez2009b) that it is possible to make a more accurate approximation of the users' search intention (i.e. to become into a more explicit representation the implicit information contained in the query).
The proposed MRF does not require of multiple executions of IR models, nor training classification methods, and it can work without user intervention; therefore, our MRF overcomes the main limitations of current post-processing techniques; see Section 2.
We report experimental results in four CLEF collections (Geo CLEF 2008, Ad Hoc CLEF 2005, Robust CLEF 2008, Image CLEF 2008) and one TREC collection (TREC-9 SDR) that show the pertinence of our method. Experimental results show that our method is able to improve the ranking provided by the IR system. Statistical tests were also performed to prove that obtained results were in fact significant, motivating us for further research.
1.2 Structure of the paper
The rest of this papers is organised as follows. The next section describes some of the recent work on ranking refinement in document retrieval. Section 3 presents some background concepts that will help the reader for a better understanding of the proposed method. Section 4 introduces the proposed MRF for ranking refinement in document retrieval. Section 5 describes the main characteristics of employed collections as well as our base IR system. In Section 6, experimental results are discussed, and in Section 7, some set of additional experiments are presented with the aim of comparing our proposed method against one of the most common re-ranking strategies, QE. Finally, Section 8 depicts the main conclusions derived from this work and outlines future work directions.
2 Related work
Document re-ranking or ranking refinement in IR has been a widely research topic during the last fifthteen years. There are two main approaches for this task: (i) indirect re-ranking via some QE strategy, and (ii) direct re-ranking on initial retrieved documents (Yang et al. Reference Yang, Ji, Zhou, Nie and Xiao2006). Normally, QE strategies assume that top ranked documents are more likely to be relevant, the terms contained within these documents can be used to augment the original query and then a better ranking can be expected via a second retrieval process. In contrast, direct re-ranking strategies try to improve the ranking of the initial set of retrieved documents by directly adjusting their positions without the need of performing a second retrieval process, normally, this type of strategy use the information contained within the retrieved documents (e.g. inter-document similarities) to generate a better ranking of them. The generated output (i.e. a list of ranked documents) by any of this two strategies would be of obvious benefit to users, for example, direct ranking refinement can be used to improve automatic QE since a better ranking in the top retrieved documents can be expected.
Our work, as we mention in Section 1.1, focuses on direct document ranking refinement. Depending on the employed information source, direct document ranking refinement can be classified into the following categories.
Based on inter-document relationships. As an example of this type of approaches, (Balinski and Danilowicz Reference Balinski and Danilowicz2005) generate a re-ranked list of documents by using documents distances to modify their relevance weight, while Lee, Park and Choi (Reference Lee, Park and Choi2001); Yang et al. (Reference Yang, Ji, Zhou, Nie and Xiao2006); Bendersky and Kurland (Reference Bendersky and Kurland2008) and Sarkar and Moore (Reference Sarkar and Moore2009) proposed a ranking refinement approach based on document clustering, where the key idea is that nodes relatively closer (in graph topology) to some set of presumable relevant nodes are more likely to be relevant.
Based on external resources. One of the main disadvantage of this approach is the high dependence on the availability of various external resources, such as manually built thesaurus (Qu, Xu and Wang Reference Qu, Xu and Wang2000) where the purpose of the thesaurus is to enrich queries and then a re-ranking process is performed by means of computing similarities of each retrieved document to its respective enhanced query. In (Zhou et al. Reference Zhou, Lawless, Min and Wade2010a, Reference Zhou, Lawless, Min and Wade2010b) they try to directly model the internal structure of topics by means of a weighted vector of knowledge-based concepts derived from external resources such as Wikipedia articles, hence, if a group of documents deal with the same enhanced topic, these documents will get allocated similar ranking as they are more likely to be relevant to the query. Other example of this type of approaches are (Bear et al. Reference Bear, Israel, Petit and Martin1997), which represents queries through manually crafted grammars; and (Kamps Reference Kamps2004; Yang et al. Reference Yang, Ji and Tang2004) that represent documents employing a set of key-phrases or key-terms, which are extracted from a controlled vocabulary, and try to re-rank the set of initially retrieved documents employing its respective type of representations by computing similarities among queries and documents.
Based on common characteristics found both in documents and queries. The main characteristic of this type of methods is the use of specific information extracted from documents or queries. For example, (Luk and Wong Reference Luk and Wong2004) used information in the document title; (Crouch et al. Reference Crouch, Crouch, Chen and Holtz2002) used stemmed words in the initial retrieval and augmented un-stemmed words in queries in document re-ranking; (Xu and Croft Reference Xu and Croft1996, Reference Xu and Croft2000) made use of global and local information to re-rank the documents via local context analysis; (Mitra, Singhal and Buckley Reference Mitra, Singhal and Buckley1998) used maximal marginal relevance to adjust the contribution of relevant terms; (Yang and Ji Reference Yang and Ji2005a, Reference Yang and Ji2005b) used query terms, which occur in both queries and top retrieved documents, to re-rank documents.
Based on graph structure. This type of methods represent retrieved documents in a graph topology in order to explore their intrinsic structure and then to produce a re-rank of them. (Kurland and Lee Reference Kurland and Lee2005) performed re-ranking based on measures of centrality in the graph formed by the generation of links induced by language model scores, through a weighted version of the PageRank algorithm and a HITS-style cluster based approach. In (Zhang et al. Reference Zhang, Hua, Yi, Lei, Wensi, Weiguo, Zheng and Wei-Ying2005), a similar method is employed to improve web search based on a linear combination of results from text search and authority ranking. The graph, which it is called “affinity graph”, shares strong similarities with (Kurland and Lee Reference Kurland and Lee2005) where the links are induced by a modified version of cosine similarity using the vector space model. (Diaz Reference Diaz2005) used score regularisation to adjust document retrieval ranking from an initial retrieval by a semi-supervised learning method. (Deng, Lyu and King Reference Deng, Lyu and King2009) further developed this method by building a latent space graph based on content and explicit link information, similar to this method, except that they model the explicit information in a direct form as proposed by (Zhou et al. Reference Zhou, Lawless, Min and Wade2010a, Reference Zhou, Lawless, Min and Wade2010b). Finally, the method proposed by (Yang et al. Reference Yang, Ji, Zhou, Nie and Xiao2006) adds to the graph structure of documents, the use of learning algorithms to perform a re-ranking considering the intrinsic information among top retrieved documents. (Yang et al. Reference Yang, Ji, Zhou, Nie and Xiao2006) employs a label propagation-based learning algorithm to integrate pseudo labeled data with unlabeled data. Their proposed algorithm first represents labeled and unlabeled examples as vertices in a connected graph, then propagates the label information from any vertex through weighted edges and finally infers the labels of unlabeled examples until the propagation process converges.
Whereas most of the above cited works have reported acceptable performance, they still have several limitations. Some of them require the execution of a retrieval model multiple times, the on-line constructions of classification methods or the need of external resources for acquiring terms semantically related to queries and/or documents; all of these formulations can be computationally expensive. Additionally, most of the described methods do not take into account all of the available information (e.g. initial ranking and contextual information) for refining the retrieval results of the base IR system, which can be helpful for improving the effectiveness of post-retrieval techniques.
In this work, we propose a direct ranking refinement strategy for improving the output generated by a document retrieval system. Our approach does not require the multiple execution of a retrieval model, the construction of a classifier nor the use of external resources such as thesaurus. For this purpose, we propose a variant of relevance feedback that aims at overcoming the limitations of current methods by considering full documents (called example texts) instead of a set of k isolated terms. By providing full example texts as feedback elements, it is possible to generate a more explicit approximation of the implicit information contained in a given query. The proposed method do not need to process the entire collection of documents in each feedback iteration, but it focuses on the top n retrieved documents. It is also important to mention that our method requires minimal user intervention and it can even work without the need of a user at all (e.g. under a blind relevance feedback formulation). Additionally, the proposed model takes advantage of all of the information available during a retrieval session, namely: initial ranking as provided by the base IR system, inter-document similarity among retrieved elements (i.e. context) and relevance feedback information. A notable benefit of our approach is that it is not restricted to a particular retrieval system or system architecture. Thus, our method offers advantages in terms of generality, as it can be used with any retrieval system, robustness, as it does not require an user-in-the-loop, as well as efficiency and effectiveness.
3 Background information
In this section, we provide some background concepts that will be helpful for understanding the rest of this paper.
3.1 Query expansion via relevance feedback
A QE via relevance feedback process is a controlled technique which main goal is to reformulate a query. In other words, a relevance feedback strategy is normally a previous step for a QE process. The basic idea is to select a set of k words which are related to a set of documents that have been previously retrieved and tagged as relevant by some user. Further, these words are added to the original query (Salton and Buckley Reference Salton and Buckley1990). In order to apply a relevance feedback process, it is necessary to perform a first search (i.e. a first retrieval process) which generates an ordered list of documents. Afterwards, the user selects from the first positioned documents those that he considers as relevant (i.e. the user establishes the documents' relevance). This relevance judgements that the user just gave to the documents are employed to compute a new set of values that indicate in a more accurate form the impact of each word in the original queryFootnote 7.
Commonly, the k most frequent words within the documents tagged as relevant are considered for its addition to the original query. One of the main advantages of the QE via relevance feedback process is that usually the IR systems are able to obtain better precision and recall levels as long as the added words are good terms, i.e. relevant words to the user's information need. Among the disadvantages is the computational cost implied, since it is necessary to perform a second retrieval process. Besides this, relevance feedback strategies have shown to be sensitive to the quality of the added words, since adding an irrelevant word could be very harmful for the IR system.
3.2 Markov random fields
MRF are a type of undirected probabilistic graphical models that aim at modeling dependencies among variables of the problem in turn (Kemeny et al. Reference Kemeny, Snell and Kanpp1976; Pearl Reference Pearl1988; Lauritzen Reference Lauritzen1996; Winkler Reference Winkler, Rozovskii and Yor2006). MRFs have a long history within image processing and computer vision (Li Reference Li1994, Reference Li2001). They were first proposed for denoising digital images (Kemeny et al. Reference Kemeny, Snell and Kanpp1976; Pearl Reference Pearl1988; Lauritzen Reference Lauritzen1996; Winkler Reference Winkler, Rozovskii and Yor2006) and since then a large number of applications and extensions have been proposed. Classical applications include image segmentation (Held et al. Reference Held, Kops, Krause, Wells, Kikinis and Müeller1997) and image filtering (Geman and Geman Reference Geman and Geman1984); although, recently they have been successfully applied for image annotation (Carbonetto, De Freitas, and Barnard Reference Carbonetto, De Freitas and Barnard2004), region labeling (Escalante, Montes and Sucar Reference Escalante, Montes and Sucar2007; Hernández and Sucar Reference Hernández and Sucar2007) and IR (Metzler and Croft Reference Metzler and Croft2005, Reference Metzler and Croft2007; Lease Reference Lease2009) with great success.
MRF modeling has appealing features for problems that involve the optimisation of a configuration of variables that have inter-dependencies among them. Accordingly, MRFs allow the incorporation of contextual information in a principled way. MRFs rely on a strict probabilistic modeling, yet they allow the incorporation of prior knowledge by means of potential functions. For those reasons, in this paper, we adopted an MRF model for refining the initial ranking of a set of documents retrieved by some IR system. The rest of this sections summarises the formalism of MRFs.
An MRF is a set of random variables F = {f 1,. . .,fN} indexed by sites or nodes where the following conditions hold:
where 
(fi) is the set of neighbours of fi according to the neighbouring system . Formula 1 is the so called positivity condition and avoids negative probability values, whereas expression 2 states that the value of a random variable depends only on the set of neighbours of that variable.
It has been shown that an MRF follows a Gibbs distribution (Geman and Geman Reference Geman and Geman1984), where a Gibbs distribution of the possible configurations of F with respect to has the following form:
where Z is a normalisation constant and the T is the so called temperature parameter (a common choice is T = 1) and E(F) is an energy function of the following form:
where “. . .” denotes possible potentials Vc defined over higher order neighbourhoods C 3, C 4. . . ., CK; each Ci defines a neighbourhood system of order i between the nodes of the MRF.
Often, the set F is considered the union of two subsets of random variables X ∪ Y; where X is the set of observed variables and Y is the set of output variables, which state that we would like to predict. Potentials Vc are problem dependent and commonly learned from data.
One of the main problems in MRFs is that of selecting the most probable configuration of F (i.e. an assignment of values to each variable fi of the field). Such configuration is determined by the configuration of F that minimises expression 4, for which a diversity of optimisation techniques have been adopted (Kemeny et al. Reference Kemeny, Snell and Kanpp1976; Pearl Reference Pearl1988; Lauritzen Reference Lauritzen1996; Winkler Reference Winkler, Rozovskii and Yor2006).
4 Proposed Markov random field for ranking refinement
As we previously mention, we focus on the problem of ranking refinement based on the fact that current IR methods are effective retrieving most of the relevant documents for different sets of queries, but they have severe difficulties generating a pertinent ranking of them. Our main hypothesis establishes that for any set of retrieved documents, obtained as a result from a common query, there must exist some degree of homogeneity among the relevant documents, whereas irrelevant documents tend to be relatively heterogeneous. Hence, our idea is to incorporate inter-document similarities, position (i.e. rank) of the documents in the original retrieved list, and similarities against a set of example texts in a MRF to generate the final re-ranked list of documents.
The MRF we propose takes as input a list of D-ranked documents, which are provided by an IR system, and attempts to re-rank the documents in the list in such a way that relevant documents are placed before irrelevant ones. The proposed method can be added as a post-processing stage for any IR system, as it does not rely on information from a particular system. The rest of this section describes the MRF we propose.
We consider an MRF in which each variable F = {f 1. . . .,fN} corresponds to a document di in the list D returned by the base IR system; each fi is a binary random variable such that when fi = 1 the ithdocument is considered to be relevant to the search intention and when fi = 0 the corresponding document is considered to be irrelevant. The main task of the MRF is to divide the documents in the list into relevant and irrelevant ones by varying the values of F = {f 1,. . .,fN}. Based on the final configuration of the MRF, we generate a new list of documents by placing in the first positions those documents i for which fi = 1, followed by the rest of the documents (i.e. documents with fi = 0). We define an energy function for the MRF that attempts to model the relevancy status of documents in terms of: (i) the rank information provided by the base IR system, (ii) the similarity against a set of example texts obtained through some relevance feedback strategy; and (iii) similarities among documents in the retrieved list.
4.1 Energy function
The energy function has two main parts, the interaction potential and the observation potential; it has the following form:
where Ni is the set of neighbours of node fi, Vc is the interaction potential and accounts for information of the association between surrounding documents, whereas Va is the observation potential and it accounts for information that is associated to a single document (see Figure 1). λ is a scalar that weights the importance of both Va and Vc.
Diagram of the proposed MRF for document re-ranking. Each document in the original retrieved list is associated to a node in the MRF. Single node information is incorporated through the Va(fi) potential (dashed lines), while contextual information is introduced via the Vc(fi, Ni) potential (solid lines).
The energy function of the MRF specifies how likely a configuration of the MRF (i.e. an assignment of values to each node fi) is the best ranking for documents in the list. We define an energy function that incorporates inter-document similarity, also the similarity against a set of example texts which are obtained through a relevance feedback process and rank information provided by the base retrieval system. The underlying idea is that a combination of these information sources is beneficial for characterising good ranks.
As final remark, observe that both elements of the energy function (Expression 5) are quadratic; i.e., O(Vc) = O(n 2) and O(Va) = O(n 2) being n the number of documents contained in the retrieved list. Hence, O(E) = O(n 2) + O(n 2) = O(max(n 2, n 2)) = O(n 2) and since λ is a constant, it is a depreciable element from the complexity calculation.
Next, we provide a general description on how the energy function is computed and in Section 4.2, we provide details on how does the dissimilarity between documents is estimated.
4.1.1 Interaction potential
Intuitively, Vc asses how much support provide the neighbouring same-valued variables to fi so it keep its current value, and also how much support give oppose-value variables to fi so it changes to the contrary value.
The interaction potential Vc is defined as:
where g(fi, NiI) is the average dissimilarity between the document associated with the node fi and its neighbours with irrelevant value NiI. Conversely, g(fi, NiR) represents the average dissimilarity between the associated document to fi and its neighbours with relevant value NiR. Thus, we divide the neighbours of node fi into two subsets: neighbours with relevant value (NiR), and neighbours with irrelevant value (NiI)Footnote 8.
Accordingly, we define the dissimilarity measure g(fi, NiX) for a subset of relevant (R) or irrelevant (I) nodes NiX (being X a place-holder for R or I) as:
where dist(di, dj) represents a distance function between di and dj, which is computed by means of comparing the textual features of the documents (see Section 4.2). Remember that documents di and dj are associated to nodes fi and fj respectively, accordingly, the dissimilarity measure (g) between a node fi and its neighbours NiX is defined as the normalised sum of the distance between the associated document di and all its surrounding documents.
It is important to mention that the idea of rewarding irrelevant documents comes from the fact that retrieved documents were obtained by means of the same query. Although we assume that irrelevant documents will be relatively heterogeneous, these documents will contain small similarities among them because of this fact, i.e. they may have a minor degree of homogeneity. Consequently, by rewarding these small similarities our MRF model tries to distinguish relevant from irrelevant documents in the list.
4.1.2 Example texts and the virtual document
As we mentioned in Section 1.1, the information obtained by the relevance feedback process is a set of example texts instead of a set of k isolated terms. In previous work (Villatoro-Tello et al. Reference Villatoro-Tello, Montes-y-Gómez and Villaseñor-Pineda2009a, Reference Villatoro-Tello, Villaseñor-Pineda and Montes-y-Gómez2009b), we have shown that by using example texts it is possible to generate a more explicit approximation of the users' information need.
In order to be able to process the information contained in the example texts, we define a virtual document v as the result of concatenating |S| example texts which were previously obtained by a relevance feedback strategy. Formally, having a set D = {d 1, d 2,. . ., d |D|} which is an ordered list of |D| retrieved documents by some IR system, we will select from D a total of |S| example texts by applying some relevance feedback strategy, generating the set of example texts S = {s 1, s 2,. . ., s|S|}.
Then, to define our virtual document v, we first concatenate all the example documents, and then we generate its representation using the traditional tf-idf weighting scheme (see Section 4.2).
4.1.3 Observation potential
The observation potential Va is based on the assumption that relevant documents are similar to the set of example texts and at the same time it is likely that they appear in the top positions; alternatively, it assumes that irrelevant documents are less similar to the set of example texts and it is very probably that they appear at the bottom positions of the list. The observation potential Va is defined as follows:
Va captures the affinity between the document di associated to node fi and the virtual document v, as measured by a distance term and by using the rank information of the original list. In the one hand, dist(di, v) indicates how distant is the document di to the virtual document v. On the other hand, δ is a function that transforms the position (rank(di)) of the document di in the original list into a real value (Chávez et al. Reference Chávez, Sucar and Montes2010).
The latter factor incorporates information from the initial retrieval system; however, notice that we only use the position of the documents in the list, which is an independent value of the retrieval system that was employed to obtain the initial list.
The transformation δ is defined as follows:
when fi = 1, δ(x) takes values proportional to the position of the document in the list; when fi = 0, δ(x) takes values proportional to the inverse of the position in the list. The position (inverse of the position) of documents is weighted exponentially because we want the position (inverse of the position) to have more influence for the top-ranked (bottom-ranked) documents. This function was inspired on the distance based probability model due to (Mallows Reference Mallows1975): 
.
In the one hand, constant c 1 in expression 9 represents the point from which we will start assigning a greater penalisation value. For our experiments c 1 was set to 300. On the other hand, constant c 1 reflex the scale of the penalisation values, i.e. to greater values of c 1 lower penalisation scores, and vice-versa. For performed experiments, c 1 was set to 5. Figure 2 resumes the behaviour of δ for the selected values.
Graphical behaviour of the transformation δ when c 1 = 300 and c 1 = 5. Observe that δ(x) will take a value proportional to the position of the document in the list.
4.1.4 Defining the MRF's initial configuration
As we previously mention, we employed the relevance feedback information for two main purposes: (i) to work as a seed generation mechanism for propagating the relevancy/irrelevancy status of nodes (documents) in the MRF, and (ii) to denote the users' search intention by working as example texts. The latter has been already explained in Section 4.1.2, in this section, we will explain the first one.
We use relevance feedback information as a seed for building the initial configuration of the MRF; that is, we set fi = 1 for relevance feedback documents (i.e. the example texts) and we set fj = 0 for the rest. In this way, the MRF starts the energy minimisation process knowing what documents are potentially relevant to the users' information need. Thus, the inference process consists of identifying further relevant documents in the list by propagating through the MRF the relevance feedback information. Since, we assume that example texts are indeed relevant to the users' information need, they are considered to be relevant during the whole energy minimisation process (i.e. the corresponding nodes are never set to 0).
4.1.5 Inference in the MRF
As stated before, the configuration that minimises expression 5 is used for generating the new rank of documents. Such configuration is obtained via stochastic simulation using the iterated conditioned modes (ICM) algorithm (Besag Reference Besag1986). In the future, we will explore the use of other strategies.
The ICM uses a deterministic “greedy” strategy to find a local minimum. It starts with an estimate of the labelling, which is given by the example texts (See Section 4.1.4), and then for each node, the label which gives the largest decrease of the energy function is chosen. This process is repeated until convergence, which is guaranteed to occur, and in practice is very fast (Besag Reference Besag1986).
It is important to mention that for this work, our purpose is that it was not to compare several optimisation process neither in terms of solution quality or running time efficiency. Rather than that, our goal was to provide some evidence of the pertinence of using MRF's for a ranking refinement process.
4.2 Estimation of similarities
In Section 4.1, we described the form of the energy function we use. In this section, we describe how the dissimilarity between documents is estimated. The proposed dissimilarity measure is basically a normalised number representing the overlap of words between documents that are compared.
4.2.1 Textual features
As textual features, we use a bag of words representation, where each document is represented by a weighted vector that indicates the presence and importance of words from the collection vocabulary in the document. This type of representation is known as the vectorial space model representation (VSM) (Salton, Yang and Wong Reference Salton, Yang and Wong1975), which basic idea establishes that the main meaning of a document is given by the words contained in it. This type of representation proposes to transform documents to a vectorial representation by employing the words contained in it.
In the VSM model, each document di is represented by a vector of length equal to the vocabulary size |V|. The collection vocabulary is the set of all different terms (i.e. words) that appear in the collection of documents. Each component k from the vector indicates the contribution of term k within the document represented by that vector. The set of vectors representing documents within the collection generate a vectorial space where documents can be compared through its vectorial representation. Then, the generated vectorial space is represented by the matrix (M TD)Footnote 9, also known as term-document (TD) matrix of size M × N, where M is equal to the size of the vocabulary (i.e. M = |V|), and N is the number of documents within the collection. Each entry MikTD represents the contribution of term tk within document di.
Several weighting schemes have been proposed, however the most employed is the term-frequency inverse-document-frequency (tf-idf) scheme. This strategy assigns to each value of MikTD the value determined by the following expression:
where tfik represents the number of times term k appears in document di. |D| is the total number of documents and dfk is the number of documents that contain term k.
4.2.2 Similarity of textual features
In order to compute the similarity between documents, we employed the following functions:
• The dissimilarity between two documents di and dj, which are associated to nodes fi and fj respectively is defined as follows:
(11)where sim(di, dj) represents a similarity function. For our experiments, we employed the well known dice coefficient, which is defined as follows:
(12)Hence, dik and djk represents the tf-idf value of the kth-term of di and dj respectively.• The dissimilarity between a document di associated to node fi and the virtual document v is defined in a similar form:
(13)where sim(di, v) is also computed employing the dice coefficient.
5 Experimental setup
In this section, we describe the experimental setup that we employed to analyse the feasibility of the proposed method. A brief description of the base IR system used is given as well as its configuration. Besides this, we describe the test collections and the different sets of queries used to evaluate the proposed ranking refinement method.
5.1 Base IR system
As we have mentioned before, our ranking refinement strategy does not depend on any particular IR system. However, in order to perform our experiments we employed as base IR system the wellknown IR system LEMUR-INDRI. This system is part of the Lemur ProjectFootnote 10 started in 2000 by the Center for Intelligent Information Retrieval (CIIR) at the University of Massachusetts, Amherst, and the Language Technologies Institute (LTI) at Carnegie Mellon University. Particularly, the LEMUR-INDRI toolkit is a search engine that provides state-of-the-art text search facilities, a rich structured query language for different text collections, and is considered as a robust system capable of producing comparable results to new IR schemes.
For all our experiments, the collections were indexed by this tool. For this purpose, collections were preprocessed by applying stop word elimination as well as a stemming process. For our experiments, we employed a list of 571 stop words available in the CLEF siteFootnote 11. Additionally, for the stemming process we employed the well known Porter algorithm (Porter Reference Porter1997).
As baseline results, we considered the performance obtained under this configuration employing the LEMUR-INDRI search engine.
5.2 Collections
For our experiments, we employed four different collections, two of them are news documents, one is of annotated images (images with textual descriptions of their content), and finally one collection that consists of automatically generated transcriptions from news broadcasting. The first three collections are part of the CLEF evaluation forum and are employed for different tasks, the last one is part of the TREC forum. Following we give a brief description of these collections.
LA Times 94 (LA94) News from year 1994 written in American English, contains 113005 news documents in a total of 425Mb Di Nunzio et al. Reference Di Nunzio, Ferro, Mandl and Peters2008).
Glasgow Herald 95 (GH95) News from year 1995 written in British English, contains 56472 news documents in a total of 154Mb Di Nunzio et al. Reference Di Nunzio, Ferro, Mandl and Peters2008).
IAPR TC-12 Photographic collection of images from around the world, it includes photos of sports, persons, animals, cities, etc. It contains 20,000 images, each with it respective textual description (Grubinger Reference Grubinger2007).
TREC-9 SDR A set of automatically generated audio transcriptions from several news broadcasting sites. Contains 21754 news transcriptions in a total of 91Mb (Garafolo, Auzanne and Voorhees Reference Garafolo, Auzanne and Voorhees2000).
5.3 Topics
Figure 3 shows the general structure of CLEF topics. The main query or title is between labels <EN-title> and </EN-title>. Also a brief description (<EN-desc>, </EN-desc>) and a narrative (<EN-narr>, </EN-narr>) are given. These last two fields usually contain more information about the requirements of the original query. It is worth mentioning that TREC-9 SDR topics are formed by only one sentence or title, i.e. they do not have any description or narrative fields.
General structure of CLEF topics.
For our experiments, we worked with topics from four different tasks from the CLEF forum and one task from the TREC forum. It is important to mention that for all our experiments, we used the title and description fields only. Table 1 shows some information about the considered topics and the search collections employed by each task.
Characteristics of the employed set of topics
The Supported column in Table 1 indicates how many topics have at least one relevant document within their respective collection. On the other hand, the short name column shows the form in how we will refer from here to each task. Another important aspect of topics is the number of relevant elements that they have within the collection. Commonly, if a topic has many relevant elements, it is said that this topic is well supported by its respective collection. Table 2 shows some information about the number of relevant elements for each set of topics we employed. Generally, topics with many relevant elements have higher probabilities of satisfying its information need. Hence, topics with very few relevant elements are considered more difficult.
Relevant elements contained in the search collections
5.4 Evaluation
The evaluation of results was carried out using a measure that has demonstrated its pertinence to compare IR systems, namely, the Mean Average Precision (MAP). MAP is defined as follows:
Where Pi(r) is the precision at the first r documents, reli(r) is a binary function which indicates if document at position r is relevant or not for the query i; n is the total number of relevant documents for the query i, m is the number of relevant documents retrieved and Q is the set of all queries.
Intuitively, this measure indicates how well the system puts into the first positions relevant documents. It is worth pointing out that since our IR system was configured to retrieve 1,000 documents per query, MAP values are measured at 1,000 documents.
6 Experimental results
We conducted several experiments for evaluating the performance of the MRF model described in Section 4. The goal of the experiments were to: (i) evaluate the proposed MRF performance under different parameter settings; (ii) compare the performance of the MRF to that of the base IR system; and (iii) analyse the results of the proposed MRF when different relevance feedback strategies are considered. The rest of this section describes the obtained results and highlights our main findings.
Each run of our experiments proceeds as follows. First, we provide the original list as input to our MRF model. Next, through some relevance feedback strategy, a set of k example documents are selected from the list. These k example documents are used as the initial configuration for the method under evaluation, and for the construction of our virtual document v. The ICM algorithm is run up to 500 iterations trying to minimise the corresponding energy function. The obtained configuration of the method is employed to generate a new list of ranked documents, and finally this new generated list is evaluated.
We considered two relevance feedback strategies for our experiments: (i) a blind scheme, where we took as example texts the first k retrieved documents by the base IR system; and (ii) a simulated scheme, where using ground truthFootnote 12 information, we simulate a manual relevance feedback session by identifying k example texts in the list. Section 6.1 describes the results obtained when a blind feedback scheme is adopted, and Section 6.2 the results when a simulated (i.e. manual) feedback is considered.
Experimental results are reported in terms of MAP values. Shown figures (Figures 4 and 5) summarise our results and expose only the best results obtained over the different configurations. In order to evaluate the statistical significance of the improvements that the MRF had over the baseline result, we performed the paired Student's t-test Footnote 13 with a confidence of 90 percent (i.e. α = 0.10).
Ranking Refinement results employing a blind feedback strategy. First, column represents the Base IR system performance; next, three columns show results obtained when 2, 5 and 10 example documents are automatically selected.
Ranking Refinement results employing a simulated feedback strategy. First column represents the Base IR system performance; next three columns show results obtained when two, five and ten example documents are manually selected.
6.1 Experiments using blind relevance feedback
In this section, we show results obtained when a blind relevance feedback strategy is employed to select documents that will be used for defining the initial configuration of the proposed MRF, and for constructing the virtual document v. Figure 4 show results obtained over the different considered tasks (See Section 5.3). The goal of this experiments was to quantify the improvement offered by the MRF for document re-ranking over an initial list of retrieved documents when there is no user intervention.
For the Geo08 task, it can be noticed that significant results are obtained when λ has values of 0.7 and 0.5. The best result occurs when two documents are selected as feedback and when λ has a value of 0.7. This means that for this collection the information provided by the neighbours has more benefit than the one provided by the observations. This configuration improves the base IR system up to a 3.71 per cent.
Similarly, to the Geo08 task, the best result for the AdHoc05 task is obtained when we employ two feedback elements and the scalar λ is equal to 0.7. However, this configuration does not represent a significant improvement; this means that even though it was possible to obtain the highest MAP value under this configuration, the improvement over all the queries was not consistent, which is also the case of λ equal to 0.0 and considering 10 documents as feedback. Nevertheless, when λ is equal to 0.0 considering five documents as feedback, our method is able to provide a ranking that is in fact a significant improvement.
It is worth mentioning that Robust08 task is considered a difficult task (See Table 2). However, better results are obtained when the scalar λ assigns equal importance to the interaction and observation potentials. Under this configuration and considering two example documents as feedback elements it is possible to improve the MAP in a 0.72 percent, showing all these cases significant improvements.
In the case of the Image08 task, observe that one main difference of these results compared with previous experiments is that our MRF reach its best performance when 10 documents are considered as feedback, and similarly to previous experiments this happens when λ is 0.7, i.e. when more importance is given to the information provided by the neighbours. This configuration is able to significantly improve the base IR system by up to a 5.97 per cent in terms of the MAP measure.
Finally, for the SDR09 task, obtained results have a very similar behaviour than those obtained with the Image08 task. The best performance occurs when ten documents are considered as feedback and when the scalar λ = 0.7. In terms of the MAP measure, our MRF is able to significantly improve the base IR system by up to a 3.11 per cent.
In general, experiments showed that if a blind relevance feedback strategy is employed, it is recommended to use few feedback elements, since adding more feedback elements results in a degradation of the order assigned to the retrieved documents, which was the case for the “difficult” tasks (Geo08, AdHoc05 and Robust08). It is also important to mention that better results are obtained when the scalar λ get values between 0.3 and 0.7, indicating that the information provided by the neighbours and by the observation potential are both important to generate a better ordering of the documents.
If we know some characteristics of each of the evaluated tasks, it is also possible to assure that if our sets of queries are considered difficult (i.e. there are no many relevant elements within the document collection), it is recommended to use few feedback elements and to assign less importance to the interaction potential, and more relevance to the observation potential. On the other hand, if our set of queries are some how easier (i.e. are better supported by the collection), we can use more relevance feedback elements and trust more in the information provided by the neighbours (i.e. the interaction potential).
6.2 Experiments using simulated relevance feedback
In this section, we exhibit results obtained when a simulated relevance feedback is considered. As we previously mentioned, a simulated relevance feedback process consist of taking as feedback those documents that we know are true relevant elements (i.e. they are part of the ground truth). Similarly, to the experiments from previous section, we used these documents to initialise the MRF configuration, and to construct the virtual document v which will be part of the observation potential.
Figure 5 summarises obtained results for the tasks defined in Section 5.3. The main goal of this set of experiments is: (a) illustrate the possible reachable improvement of a base IR system if minimal user intervention is considered. It is worth mentioning that all results obtained under this feedback configuration were statistically significant with a confidence level of 99 per cent (i.e. α = 0.01) in accordance with the paired Student's t-test.
Notice that for the Geo08 task, the best result considering either two or ten feedback elements is obtained when λ = 0.7. This is an indicator that both the interaction potential and the observation potential are being complementary to each other. However, there still is a tendency to prefer higher values of λ (i.e. λ → 1), which indicates that relevant neighbours have some homogeneity that allows the MRF to differentiate them from the irrelevant ones.
Similarly, in the case of the AdHoc05 task, better results with few feedback elements are reached when λ = 0.7. This configuration allows our MRF model to improve the MAP measure by up to a 34.59 per cent when only two documents are given as feedback.
Observe that for the Robust08 task, when only two documents are given as feedback elements, the best performance is obtained when λ = 0.5, which means that it is necessary for the MRF to complement information provided by the interaction potential (Vc) with the observation potential (Va) information. However, if more elements are given as feedback it is possible to trust only in the information provided by the neighbours (i.e. the interaction potential).
Finally, for the case of the Image08 and SDR09 tasks, it is important to notice that both experiments reach their best performance when λ has values between 0.7 and 0.5. This indicates that for these particular collections, even if several documents are given as feedback elements, it is not possible to trust only in the information provided by the neighbours, which has been the case of the others tasks (Geo08, AdHoc05 and Robust08). In other words, the homogeneity among relevant documents within these collections (Image08 and SDR09) is not that evident, and as a consequence the MRF model needs of the information provided by the observations (i.e. the observation potential).
In general, performed experiments show that it is possible to outperform (consistently) results obtained by the base IR system. As expected, improvements are larger for higher values of k, nevertheless there are important improvements when k = 2, which is a very positive result since providing only two documents as examples (or feedback) is not an overwhelming task for the user.
Additionally, is was possible to observe that the proposed MRF behaves different depending on the characteristics of the document collection. For instance, Geo08, AdHoc05 and Robust08 use the same documents collection (See Table 1), which in general are news reports, and for this cases the MRF performs better when there is a tendency to prefer the information provided by the neighbours (i.e. λ → 1). However, for Image08 and SDR09 which contain shorter documents, the MRF needs additional knowledge, i.e., the information provided by the observations in order to be able to provide a better ranking.
6.3 Performance analysis
6.3.1 On the selection of the parameters values
Previous experiments showed that the efficacy of the proposed MRF varies depending on the values for the parameter λ; which is a scalar that assigns more or less importance to our defined potentials (see expresion 5); and parameter k; which represents the number of example documents. In order to provide a deeper understanding of the impact of these parameters on the methods performance, Figure 6 plots the statistical significance of the improvements that the MRF – using a blind relevance feedback strategy – had over the baseline on the different collections, in accordance to the paired Student's t-test with a confidence of 90 per cent In these figures, a black dot indicates that the achieved improvement was statistically significant, a gray dot indicates that the MRF was able to obtain a better performance in terms of the MAP measure but without being significant, whereas a white dot indicates that our method did not improve the results obtained by the base IR machine.
Analysis of the statistical significance of results for several combinations of the configuration parameters of the proposed MRF employing a blind relevance feedback strategy.
As can be observed, our method is able to generate a better ranking of the set of retrieved documents when both the interaction potential (Vc) and the observational potential (Va) are considered in the energy function of the proposed MRF. Notice that in general, when the scalar λ is set to 1, it is not possible to obtain good results, indicating that the information provided by the neighbours is not enough to adequately find the best configuration of the MRF.
On the contrary, when λ goes from 0.0 to 0.7 it is possible to obtain results that represent a statistically significant improvement, particularly for λ set to 0.3. Also notice that by using few documents as example texts (two documents) is possible to obtain significant results. In general, we can conclude that the performance of our method was very robust across all evaluated tasks, suggesting that if a blind relevance feedback strategy is followed, it is recommendable to use few example texts and a scalar λ equal to 0.3.
For the experiments employing a simulated feedback process (Section 6.2), all configurations produce significant results, i.e. if we draw a similar graphs as the one shown in Figure 6 it will result in totally black graphs. Therefore, considering this fact and the results shown in Figure 5, we can conclude that by including only two example texts and considering an equilibrated weight between our potentials (Vc and Va) it is possible to obtain significant improvements over the base system.
6.3.2 Running time efficiency
Although our goal was not to prove if the optimisation algorithm (ICM) produce better results in terms of solution quality and running time efficiency, we performed some experiments to measure the running time efficiency where the main variation was the number of documents that are taken into account for the construction of the fully connected MRF. For this experiments, we first consider a set of one hundred documents until we reach the 1,000 documents (considering increments of one hundred documents)Footnote 14.
Figure 7 presents the time efficiency of the proposed MRF when example texts are selected via a blind feedback strategy. As can be noticed, the greater the number of documents considered in the graph of the MRF, the greater the time required to converge to an optimal configuration.
Average time consumption for the blind feedback configurations with its respective standard deviations.
Similarly, Figure 8 show the time efficiency of our method when the example texts are selected via simulated feedback. Notice that when example texts are provided by some user, the proposed MRF takes more time than its homologue experiment using blind feedback (Figure 7) to converge to the optimal configuration. The reason for this behaviour is because when a simulated feedback process is performed, we are some how compelling the MRF to find documents with certain degree of homogeneity to the provided example texts that are in fact relevant documents, which is not always the case when a blind feedback process is performed.
Average time consumption for the simulated feedback configurations with its respective standard deviations.
6.3.3 Comparison with other approaches
Finally, Figure 9 depicts a comparison of the performance obtained by the teams that participate in the most recent track for each task. Symbol × represents the average performance of all participant teams. Upper line (-) indicates the maximum performance obtained in each track, while the lower line (-) indicates the minimum performanceFootnote 15. Symbol ◇ represents the performance obtained by our proposed method using the blind feedback configuration (See Figure 4 for reference).
Performance of the proposed method against the best obtained results in the bibliography. × represents the average performance of all participant teams. Upper line (-) indicates the maximum result obtained in each track, while the lower line (-) indicates the minimum performance. ◇ represents the performance obtained by our MRF using the blind feedback configuration (See Figure 4 for reference).
It is worth mentioning that the teams that participated in each track applied a great variety of methods and some times employed a great diversity of resources to solve the problem, which is the reason, we can not think in a direct comparison of our proposed method against them. However, Figure 9 demonstrates that our proposed method is able to reach a state-of-the-art performance except in the SDR09 task. It is also important to mention that when simulated feedback is used, our method significantly outperformed the best results reported in the CLEF and TREC evaluation forums.
7 Additional experiments
In order to compare our findings against one of the most employed indirect ranking refinement strategies, i.e. QE via relevance feedback (QE), we conducted the following set of experiments, where the main goal was to: (i) compare our best results obtained with the proposed MRF model against QE results, (ii) to show the lack of sensitivity of our proposed MRF model to the quality of the information provided by the relevance feedback.
Each run of this set of experiments proceeds as follows. We took from the retrieved list by the base IR system k example texts, and all the information contained within these documents is employed to augment their respective query, and then a second retrieval process is performed using the expanded query. The new list of retrieved documents is then compared against the base IR system performance.
For the experiments presented in this section, we considered only a blind relevance feedback strategy since as we previously mention, we were interested in showing the robustness of our MRF method against the QE process when there is no user intervention.
7.1 QE via blind relevance feedback
In Figure 10, we present the MAP performance obtained for both the QE strategy and our ranking refinement (RR) method. For each evaluated task (i.e. Geo08, AdHoc05, Robust08, Image08 and SDR09), the first three bars represent results obtained with the QE process considering two, five and ten example texts respectively; and the following set of three bars represent the best results obtained employing our proposed ranking refinement strategy also considering two, five and ten example texts.
Query Expansion versus Ranking Refinement using a MRF considering a blind feedback strategy. First three columns show the MAP performance of the QE technique using two, five and ten documents respectively. Last three columns indicate the MAP performance of the proposed MRF using two, five and ten example documents respectively.
As it is possible to observe in Figure 10, QE technique is much more sensitive to the quality and to the quantity of added information to the original query, which is not the case of our proposed MRF method. Particularly, we can observe this behaviour for difficult tasks, which are Geo08 and Robust08. On the contrary, for better supported tasks (i.e. Image08 and SDR09), it can be sometimes preferable to perform a QE process.
In Figure 11, we exhibit the recall levels obtained by the QE process and the one of the base IR system, which is the same recall value maintained by our MRF method since as we have mentioned, we do not perform a second retrieval process. The first three columns correspond to the recall obtained using different configurations for the QE process, and the fourth column represents the recall value obtained by the base IR system.
Query Expansion versus Ranking Refinement using a MRF considering a blind feedback strategy. First three columns show recall levels obtained by the QE process considering two, five and ten documents respectively. Last column show the recall value obtained by the base IR system, which is the same recall value maintained by our MRF.
Noticed that the QE process in general affects negatively the recall (see Figure 11). Hence, we can conclude that our MRF method for document ranking refinement is less sensible to the quality and to the quantity of added feedback elements, in other words, the proposed MRF is a more robust method for this particular feedback situation where added information is partially correct.
8 Conclusions
We have introduced a MRF for improving the order of a list of initially retrieved documents. The proposed model incorporates similarity between documents in the list, similarity between documents and a set of example texts, and information obtained from the original order assigned to the documents. The ranking refinement problem is faced as one of separating relevant from irrelevant documents in the list. Our work included: (i) the inclusion of full texts (i.e. example texts) as feedback instead of a set of isolated terms, and (ii) the development of potentials and energy functions based on textual features that allow us to differentiate relevant from irrelevant documents.
Experimental results proved the effectiveness of our method. In particular, results showed that the proposed method is able to improve the base IR system. We studied the performance of the proposed model under different parameter settings and over several standard IR tasks from the CLEF and TREC forums. Experiments showed that under a blind relevance feedback scheme was possible to significantly improve results from a base IR system. These results also showed that few feedback elements are needed to reach a good performance. Additionally, we compare our method against one of the most employed ranking refinement strategies, i.e. QE. Obtained results showed that our MRF model is less sensitive to the quality and to the quantity of the feedback information than the QE technique.
The contributions of this work are as follows. We proposed a novel ranking refinement technique that faces the problem as one of combinatorial optimisation. The proposed model was able to improve the ranking of the base IR system as well as the performance of one of the most commonly used re-ranking strategies, i.e. a QE process. Our approach incorporates: (i) initial rank information provided by the base IR system; (ii) contextual information, which is often dismissed in usual post-retrieval techniques; and (iii) example texts information, which is obtained through a relevance feedback process. As observed in our experiments, our MRF model is capable of working with either automatic or manual relevance feedback strategies. Additionally, our MRF does not depend on any specific IR system, nor on a particular architecture or document collection.
As future work, we would like to include multimodal information to our MRF. For instance, in the Geo CLEF tasks besides considering textual features, we believe that it could be helpful to consider also geographical features. In the Image CLEF, this can be done by considering some visual features which can be obtained from the image provided as query, whereas for the SDR task this can be done by considering phonetic features. Additionally, we would like to consider in the energy function more context information such as an user profile, or information of previous performed queries, which it will help to the MRF on determining potential relevant elements. Furthermore, we plan to implement and test our proposed method with a more recent and efficient energy minimisation algorithm, such as loopy belief propagation algorithm.
