A systematic approach to normalization in probabilistic models

The development of retrieval models is one of the key aspects of research in information retrieval (IR). The IR models arise from experimental observations about the use of the language, predominantly on collections of documents primarily composed of news corpora. Today, with the almost total digitization of most text produced, it is clear that the textual documents are not just news and that different collections require different approaches (Hanbury and Lupu 2013). Consequently, the field has been driven to deal with different kinds of information types, demonstrated by the creation of new and more domain specific initiatives in the main IR evaluation campaigns: TREC, NTCIR, CLEF, and FIRE. Now, thanks to the observations made in the context of these evaluation campaigns, we are able to revisit some of the original assumptions and extend the models to integrate other collection statistics that reflect the different use of the language in different domains.

Every IR model boils down to a scoring function in which we can distinguish a component that increases with the number of occurrences of a term in a document (a term frequency component, \({\text {TF}}\)) and a component that decreases with the commonality of a term (an inverse document frequency component, \({\text {IDF}}\)). In this paper we focus on the \({\text {TF}}\) component. Its normalization, first introduced by Robertson et al. (1994) for BM25, and then generalized by Singhal et al. (1996) for a generic model, consists in adjusting the within-document term frequency (\(\textit{tf}_d\)) based on the ratio between the document length (\(l_d\)) and its expectation (\(\mathrm {E}_{\mathcal {D}}[l_d]\)), called pivoted document length normalization. The work of Singhal et al. is motivated by the experimental observation that the length pattern of the retrieved documents should match the pattern of the relevant documents. Robertson et al. justify this normalization, later declared as ‘soft’ for the mitigation effect provided by the division by the mean, by introducing two contrasting hypotheses (Robertson and Zaragoza 2009), named verboseness and multi-topicality: (a) the verboseness hypothesis states that some authors need more words to explain something that could have been explained with fewer; (b) the multi-topicality hypothesis states that the reason why more words are required is because the author has covered more ground. While the first hypothesis suggests a document should be normalized by its length, the second suggests the contrary.

Recently, Lipani et al. (2015) have brought back to the attention of the IR community this discussion, pointing out that another collection statistic could be embedded in the \({\text {TF}}\) normalization of BM25. This new statistic measures a kind of verboseness, the repetitiveness of terms in a document, and leads to the achievement of performance better than the standard BM25.

In this paper we address this new observation from the perspective of the established models, and provide a new, general theory. Before doing that, a few general observations are in order.

Retrieval models combine various parameters into a score reflecting the degree to which a document implies a query. The common parameters and rationales are: where c is a collection of documents, d is a document, and t is a term. We claim that there are other properties of documents and terms that are important but under-represented, namely verboseness and the previously introduced burstiness (Roelleke 2013). In this paper we will focus primarily on verboseness, but we will also make some observations on burstiness and its relation with \({\text {IDF}}\). However, before starting, we introduce the notation used.

The discussion about the TF normalization was initiated by Robertson and Zaragoza (2009), introducing the two hypotheses: verboseness and multi-topicality and then followed by the work of Singhal et al. (1996) where the document length pivotization is justified experimentally. Not much work has been done on the multi-topicality hypothesis, but some for the verboseness hypothesis. However, the problem of how to weight terms dates back further, to the work of Salton and Buckley (1988). Na et al. (2008) introduce the concept of repetitiveness to derive a smoothing method for Language Modeling, showing an improvement with respect to other smoothing methods.

Following other work on the TF normalization issues, He and Ounis (2005a) apply the Dirichlet priors to the TF normalization following the idea of Amati and Van Rijsbergen (2002), and test it on different test collections (He and Ounis 2003, 2005b). Lv and Zhai pointed out that the TF quantification based on document length excessively penalizes very long documents due to its lower bound, a problem mitigated by leveraging the TF normalization by adding a constant (Lv and Zhai 2011b). They also pointed out that in case of BM25 it can be mitigated by adding a constant to the TF normalization (Lv and Zhai 2011c). Rousseau and Vazirgiannis (2013) generalized the previously mentioned TF normalizations through functional composition. Lv and Zhai (2011a) estimate dynamically the parameter \(k_1\) of BM25, based on a proposed information gain measure.

Lipani et al. (2015) introduce a new variant of BM25, called BM25VA that explicitly incorporates verboseness. This is the main work that motivates this paper. The verboseness is defined as in Eq. (1), and pivoted as \(v_d/\mathrm {E}_{\mathcal {D}}[v_d]\). Verboseness is then added to the \(\text {TF}_{\text {BM25}}\), linearly combining the two contributions through the parameter b, as follows:In this work, it is heuristically shown that the parameter b is inversely proportional to a statistic of the collection, the average collection verboseness \(\mathrm {E}_{\mathcal {D}}[v_d]\), and that it can be predicted without statistically damaging the performance of the trained BM25.

Another way of approaching the length normalization issue is to consider retrieval of the the individual passages (Robertson and Walker 1999). However, this use of passages to address length normalization is theoretically unjustified and introduces a series of decision points (size and nature of passages) that are not the focus of this current study.

Before getting into the details of the duality between document verboseness and length, it is necessary to formally define the current pivotization of document length and introduce the pivotization of verboseness. To do this we start from the foundation of every IR model: the document-term matrix \(A \in \mathbb {N}^{|\mathcal {D}| \times |\mathcal {T}|}\), in which each element is a \(\textit{tf}_d\) indicated here by \(a_{d,t}\) for convenience of the notation. For any given matrix, we can define two ways to sum the elements of this matrix; one that fixes a column (a term t) and sums over the rows (the \(|\mathcal {D}|\) documents) and one that fixes a row (a document d) and sums over the columns (the \(|\mathcal {T}|\) terms). Doing this we calculate two lengths: the length of a term¹ and the length of a document, as follows:Now, if we want to compute the average of the values on each row or column, we have to divide the sums obtained above by a value. For this value we actually have two options: the number of columns or rows, and the number of non-zero elements in the columns or rows. The first is what we would call the average, and the second the elite average. To give an intuition, think of the question “What is the average number of Ferraris owned by a person?”. This question has two answers: we can divide the total number of Ferraris (the sum of the elements on a row/column) by the total number of people on the planet (the number of columns/rows); or, we can consider only those people that have at least one Ferrari and then divide the number of Ferraris by the size of this set of people. The first one is the common average, while the second, obviously, is the elite average.

Returning to our document-term matrix, we will denote by a bar (\(\bar{a}\)) a common average and by a breve \((\breve{a}\)) an elite average:in which we observe that the two elite averages just defined \(\breve{a}_t\) and \(\breve{a}_d\) correspond to the burstiness \(b_t\) as defined in Eq. (2) and the verboseness \(v_d\) as defined in Eq. (1).

Considering the remaining elements, \(\bar{a}_t\), \(\breve{a}_t\), \(\bar{a}_d\) and \(\breve{a}_d\), we can think of them as defining an average document \(\bar{d} = [\bar{a}_{t_1}\,\ldots \,\bar{a}_{t_{|\mathcal {T}|}}]\), an elite average document \(\breve{d} = [\breve{a}_{t_1}\,\ldots \,\breve{a}_{t_{|\mathcal {T}|}}]\), an average term \(\bar{t} = [\bar{a}_{d_1}\,\ldots \,\bar{a}_{d_{|\mathcal {D}|}}]\), and an elite average term \(\breve{t} = [\breve{a}_{d_1}\,\ldots \,\breve{a}_{d_{|\mathcal {D}|}}]\). Moreover, we observe also that the elite average document is equal to \(\breve{d} = [b_{t_1}\,\ldots \,b_{t_{|\mathcal {T}|}}]\) and the elite average term is equal to \(\breve{t} = [v_{d_1}\,\ldots \,v_{d_{|\mathcal {D}|}}]\).

So, now, for each row d and for each column t we have a sum, an average, and an elite average. To obtain a collection-level statistic, we have to aggregate again, calculating sums and averages (common and elite averages are identical now, because all rows and all columns have a non-zero aggregated value).

Doing so, we observe thati.e. the average document length \(\bar{l}_d\) is equal to the sum of the elements of the average document \(\bar{d}\).

However, the same observation is not valid for verboseness, because it is an elite average. Instead, we have two notations:

A graphical representation of the calculations performed in this section is shown in Fig. 1.

To discuss the justification of \({\text {TF}}\) quantifications, we consider the probabilistic derivation of IR models. Most IR models can be derived from measuring the dependence between document and query. Let d denote a document, q a query, and c a collection. The document-query independence (DQI Roelleke and Wang 2008) is the point-wise mutual information expressed as:

Document and query are considered as sequences of term events. The decomposition of d leads to TF-IDF (and, for particular assumptions, to BM25), and the decomposition of q leads to LM. In this section we review the decomposition of d. When decomposing d using \(P(d,q) = P(d|q)P(q)\) and then \(P(d) = \prod _{t \in \mathcal {T}_d} P(t)^{\textit{tf}_d}\) and \(P(d|q) = \prod _{t \in \mathcal {T}_d} P(t|q)^{\textit{tf}_d}\), we obtain:Here, P(t|q) is the query term probability, and P(t) is the background model (collection-wide) term probability. The equation makes two independence assumptions: different terms are independent, and also, the multiple occurrences of the same term are independent. The first assumption is reflected in applying the sum over different terms, and the second assumption is reflected by the total term frequency count, \(\textit{tf}_d\).

To provide a justification for TF-IDF, one is looking for the bridges to close the gap between the probabilistic roots (assuming independence) and the TF-IDF. Expressed as an equation, we are looking for justifications to transform components of Eq. (25) to TF-IDF.where \({\text {TF}}\) and \({\text {IDF}}\) are the two components, term frequency and inverse document frequency.

In this section, we first present the material, then the experimental setup. Finally we discuss the results.

Finally we make some observations across the experimental results about the behavior of the parameter a. Before that however, let us make an observation on the nature of the data at our disposal. Figure 3 shows the distribution of the document verboseness versus document length for the elite and non-elite pivotizations. In both cases we see that verboseness brings additional information compared to document length: the plotted distributions are well spread, away from the first diagonal.

The a parameter controls the contribution of elite pivoted verboseness and elite pivoted document length. When \(a<0.5\), the contribution of the document verboseness is higher than the contribution of the document length, and vice versa when \(a>0.5\). Looking at the distribution for the elite pivotizations of the documents, redefining the origin to the point (1, 1) we split the distributions in four quadrants.⁴ We know that whatever a we fix, the documents in the I quadrant will be always demoted to some degree, and in the III quadrant the documents will be always promoted to some degree. So here the question is what happens to the documents in the IV and II quadrant. When to be preferred is the contribution of document verboseness (\(a>0.5\)) more documents with low verboseness (\(\hat{v}_d<1\)) and high length (\(\hat{l}_d>1\)) will be promoted against the documents of the IV quadrant, and when preferred is the contribution of the document length (\(a<0.5\)) the contrary happens. Therefore, the a values, previously listed, should anti-correlate with the ratio of the number of relevant documents between the II quadrant and the IV quadrant. Here the two lists of values sorted by test collection, of a extracted from Tables 3, 4, 5, and 6, for the standard BM25 case with trained a: 0.8, 0.6, 0.4, and 0.0 and ratios: 0.63, 0.86, 1.16 and 4.20, where we observe that they anti-correlate. Therefore if we think that all the documents of the collection should be relevant we should find the a value that mostly balance the proportion of non verbose but long documents with the short but verbose documents. All the test collections but Disks 4&5 have been crawled from the Web. For all of them we can observe that the plots manifest a visible noise. In particular we observe the presence of black dots that are most probably caused by the existance of duplicated documents in the collections. For example, the existance of duplicated documents in the e-Health’14 test collection is a known issue to the e-Health IR community.

In Tables 3, 4, 5, and 6 we observe that the best performing configuration, for both \(\text {TF}_{\text {log}}\) and \(\text {TF}_{\text {total}}\), uses the trained parameters combined in disjunction, in particular in Table 4 these configurations also show statistical significance against both standard configuration and trained configuration when verboseness is not present (\(a=0\)). The elite pivotization performs generally better than the non-elite pivotization. In particular the best performing configurations are with elite pivotization and trained parameters in conjunction. We observe also that in general the elite pivotization weighting role is taken by the parameter a (\(b=1\) means that a full document verboseness and length normalization is applied).

In Fig. 4 we further analyze the best configuration on a per topic basis. Here, we show the difference in \(\text {AP}\) between the \(\text {AP}\) of the trained TF\(_\text {BM25}\)-IDF with verboseness combined in conjunction with elite pivots, and the trained classic TF\(_\text {BM25}\)-IDF. If the difference is positive the variant with verboseness is better than the classic version.

This paper presents an extensive study of \({\text {TF}}\) quantifications and normalizations. The quantifications are with respect to a well-defined spectrum comprising \(\text {TF}_{\text {total}}\), \(\text {TF}_{\text {log}}\), \(\text {TF}_{\text {BM25}}\), and \(\text {TF}_{\text {constant}}\). Each of these \({\text {TF}}\) quantifications reflects a dependence assumption. In particular, \(\text {TF}_{\text {total}}\) and \(\text {TF}_{\text {constant}}\) are the extremes of the quantification spectrum, assuming independence for the former and subsumption for the latter. \(\text {TF}_{\text {BM25}}\) is a relatively strong dependence assumption, and \(\text {TF}_{\text {log}}\) is in the middle between \(\text {TF}_{\text {total}}\) and \(\text {TF}_{\text {BM25}}\). Each of these quantifications incorporates a \({\text {TF}}\) normalization parameter, usually denoted as \(K_d\).

Whereas current approaches regarding \(K_d\) consider only the document length as parameter of \(K_d\), this paper makes the case for \(K_d\) to be a combination of document verboseness and length. There are many heuristic options for how to combine the parameters, and this paper contributes the theoretical foundations leading to a systematic combination of document verboseness and length.

The paper reports results of an experimental study investigating the effect of various settings of \(K_d\) for the four main \({\text {TF}}\) quantifications. The overall finding is that combining document verboseness with document length (either in a conjunctive or disjunctive way) improves retrieval quality when compared to results considering document length only.

We expand this in two directions, first by exploring a similar normalization in the context of LM and second a similar normalization in the context of TF-IDF. For the former, we include document verboseness into the Dirichlet smoothing where non-significant effect is observed, which signifies that document verboseness can be neglected. For the latter, in Sect. 4.3 we have observed the duality between document verboseness and document length on one side, and term burstiness and term length on the other side, and we observed the effect of these normalizations on the query side with respect to LM. Here, significant improvements are observed, however these improvements are obtained primarily by the use of term burstiness, while the term length can be neglected. In both directions improvements are observed given by the new parametrizations, and their results show a dual behavior, given by the exclusion of document verboseness in the former, and by the exclusion of term length in the latter.

In summary in this paper we have provided an exhaustive study of normalization factors in IR probabilistic models using 4 different test collections. Based on the observations made on these test collections, we have made the case that different domains, having different text statistics, can be directly factored into the existing probabilistic models. We have thus provided a quantification of the various document and term statistics into one factor that balances different prior probabilities that all these models, more or less explicitly, rely on.