Term Dependence Models

Ranking beyond the bag of words. Why every model in the unit assumes that query terms occur independently and what that discards, shown on two documents with the same term counts; the Markov random field model of Metzler and Croft with its graph, its full independence, sequential dependence and full dependence variants, its potentials over single terms, ordered windows and unordered windows, and the ranking function derived from the joint distribution; the sequential dependence model computed by hand and run on all 225 Cranfield queries against query likelihood; proximity terms added to BM25; and the positional index that makes these features computable. Worked problems on cliques, window counts and feature values.

Cranfield abstracts 858 and 948 each contain panel eleven times and flutter seven times. In abstract 948 the word flutter follows panel directly four times. In abstract 858 it never does. Every ranking model in this unit so far reads the two abstracts as the same evidence about these two words, because each model sees only how often a word occurs and never where. Does the position of the words carry evidence that the counts do not? It can, and this article builds the standard model that uses it and measures what it adds on Cranfield.

A term dependence model is a ranking model in which the evidence from one query term depends on where the other query terms occur: next to it, near it, or anywhere. The models met so far, the Binary Independence Model, BM25 and query likelihood, are independence models. Each scores a document by a sum with one summand per query term, and a summand never looks at another term.

Here is the route. First we see why independence is assumed and what it throws away, on two small documents with identical counts. Then we build the Markov random field model of Metzler and Croft (2005): its graph, its three variants, its three kinds of feature, and its ranking function derived from the joint distribution. Next we compute the sequential dependence model by hand, on the small documents and on abstracts 858 and 948, and run it on all 225 Cranfield queries. Finally we look at proximity terms added to BM25 and at the index that makes any of this computable. The article assumes Dirichlet-smoothed query likelihood from language models for retrieval and the positional postings of phrase and proximity queries.

Why independence is assumed, and what it costs

Independence is assumed because the alternative cannot be estimated. The BIM needs, for a query of $n$ terms, the probability of each of the $2^n$ patterns of presence and absence among relevant documents, and no collection has enough judged documents to count them. Assuming that terms occur independently given relevance replaces those $2^n$ numbers by $n$. Query likelihood makes the matching assumption on its side: each query word is drawn from the document's model without regard to the others. Metzler and Croft (2005) put the general difficulty in one sentence: "estimating statistical models for general term dependencies is infeasible, due to data sparsity."

The assumption is false, and the unit has already measured how false. Panel occurs in 45 of Cranfield's 1,400 abstracts and flutter in 56. If the two occurred independently they would share $45 \times 56 / 1{,}400 = 1.8$ abstracts. They share 20, eleven times as many (probability for information retrieval works this example in full). A false assumption need not spoil a ranking, as long as it distorts every document's score in a similar way. That is the thread of this whole unit. But one kind of evidence is lost entirely, and no reweighting of term counts can bring it back.

Example (same counts, different documents). Two documents can have identical term counts and differ only in where the words stand, and an independence model must then score them equally. Take two documents of twelve analyzed terms each:

  • near: panel flutter measur wing model tunnel mach number pressur plate test result
  • far: panel measur wing model tunnel mach number pressur plate test result flutter

They contain the same twelve terms once each. For the query panel flutter, the BIM, BM25 and query likelihood each compute a function of the two term frequencies and the document length, which are the same for both documents. So each of the three models gives near and far exactly the same score. Under Dirichlet-smoothed query likelihood with Cranfield's statistics that score is $-10.1461$ for both; the computation is carried out below. A reader sees a difference at once: near mentions panel flutter, and far mentions panels and, eleven words later, flutter.

Earlier attempts to restore the lost evidence worked inside the BIM. The best known is van Rijsbergen's tree dependence model (1977), which lets each term depend on one other term. The pairs are chosen by building a maximum spanning tree over the terms, with the expected mutual information of each pair as the weight. The course text describes the model briefly (Manning, Raghavan, and Schütze, 2008, §11.4.2); the spanning-tree construction is van Rijsbergen's, as Metzler and Croft summarize it. Metzler and Croft review this line of work and report that the more complex models of this kind "have been shown to yield little or no improvements in effectiveness." They name two reasons. Models built on the BIM must estimate dependencies separately among relevant and nonrelevant documents, where there is little or no data. And the collections of the time were small, so most pairs of terms occurred together only a handful of times. Their model avoids the first problem by not modeling relevance as a separate variable at all.

The Markov random field model

Here is the idea in one sentence: draw a graph whose nodes are the document and the query terms, join the terms that are assumed to depend on one another, and score a document by adding one weighted feature for every fully connected group of nodes that includes the document.

The graph

A Markov random field is a way of writing a joint probability distribution from an undirected graph. Each node is a random variable. An edge says that two variables interact directly; a variable is independent of its non-neighbors given the values of its neighbors. A clique is a set of nodes in which every two are joined by an edge.

In the retrieval model, the graph $G$ has one node $D$ for the document and one node $q_i$ for each of the $n$ query terms, $Q = q_1 \dots q_n$. Every query node is joined to $D$. The edges among the query nodes are the modeling choice, and they are what makes the three variants.

Three variants

Metzler and Croft describe three ways of joining the query nodes. For a query of three terms:

Variant Edges among query terms Cliques that contain $D$ and a query term
Full independence (FI) none $\{q_1, D\}$, $\{q_2, D\}$, $\{q_3, D\}$
Sequential dependence (SD) $q_1$–$q_2$, $q_2$–$q_3$ the three above, and $\{q_1, q_2, D\}$, $\{q_2, q_3, D\}$
Full dependence (FD) every pair the five above, and $\{q_1, q_3, D\}$, $\{q_1, q_2, q_3, D\}$
  • Full independence assumes that the query terms are independent of one another given the document. This is the assumption of every model above.
  • Sequential dependence "assumes a dependence between neighboring query terms." The set $\{q_1, q_3, D\}$ is not a clique here, because $q_1$ and $q_3$ are not joined.
  • Full dependence assumes that "all query terms are in some way dependent on each other." Every subset of the query terms forms a clique with $D$. The paper notes the cost: "The number of cliques is exponential in the number of query terms."

A query of $n$ terms has $n$ single-term cliques under each variant. Sequential dependence adds $n - 1$ pairs. Full dependence adds every subset of two or more terms, $2^n - n - 1$ of them. For the twelve terms of a typical Cranfield query that is 11 pairs against 4,083 subsets, which is why the experiments below use sequential dependence.

From the joint distribution to a ranking function

Here is the plan of the derivation. The joint probability of a query and a document is a product over cliques. Ranking needs only the part of its logarithm that changes from document to document, and with exponential potentials that part is a weighted sum of features.

The formal version. The model defines the joint distribution of the query and the document as

$$P_\Lambda(Q, D) = \frac{1}{Z_\Lambda} \prod_{c \in C(G)} \psi(c; \Lambda),$$

where:

  • $C(G)$ is the set of cliques of the graph;
  • $\psi(c; \Lambda)$ is a potential function, a non-negative number that says how compatible the values of the variables in clique $c$ are with one another;
  • $\Lambda$ stands for the parameters of the potentials;
  • $Z_\Lambda$ is the constant that makes the probabilities sum to 1 over all queries and documents.

The steps follow the paper's section 2.1.

  1. Rank by the posterior. For a fixed query, documents are ranked by $P_\Lambda(D \mid Q) = P_\Lambda(Q, D) / P_\Lambda(Q)$.
  2. Take the logarithm. The logarithm is increasing, so it preserves the order: $\log P_\Lambda(D \mid Q) = \log P_\Lambda(Q, D) - \log P_\Lambda(Q)$.
  3. Drop what does not depend on the document. $P_\Lambda(Q)$ is the same for every document, so it shifts all scores equally. Substituting the product, $\log P_\Lambda(Q, D) = -\log Z_\Lambda + \sum_{c \in C(G)} \log \psi(c; \Lambda)$, and $Z_\Lambda$ is also the same for every document. This matters in practice: $Z_\Lambda$ is a sum over every possible query and document and cannot be computed, and the ranking never needs it. What remains is

$$P_\Lambda(D \mid Q) \;\stackrel{\mathrm{rank}}{=}\; \sum_{c \in C(G)} \log \psi(c; \Lambda).$$

  1. Choose exponential potentials. A potential must be non-negative. The usual form is $\psi(c; \Lambda) = \exp\left[\lambda_c\, f(c)\right]$, where $f(c)$ is a real-valued feature function of the clique's values and $\lambda_c$ is its weight. Then $\log \psi(c; \Lambda) = \lambda_c\, f(c)$, and the ranking function is

$$P_\Lambda(D \mid Q) \;\stackrel{\mathrm{rank}}{=}\; \sum_{c \in C(G)} \lambda_c\, f(c),$$

the paper's equation 1. A clique that does not contain $D$ is given the potential 1, whose logarithm is 0. The clique $\{D\}$ alone could carry a document prior. Like the paper's experiments, we give it the potential 1 as well, which amounts to a uniform prior over documents. So only cliques that contain the document and at least one query term contribute.

The symbol $\stackrel{\mathrm{rank}}{=}$ means "gives the same ordering of documents as". The result is a linear function of features. A clique may carry more than one feature. The paper gives a clique of contiguous query terms the product of two potentials, $\psi_O(c)\,\psi_U(c)$, which is again non-negative and so is a valid potential. Its logarithm is the sum $\lambda_O f_O(c) + \lambda_U f_U(c)$. Everything specific to retrieval is in the choice of features.

The three potential functions

The paper uses three kinds of feature, one for each way a clique can be formed. Each is the logarithm of a smoothed probability. Its form is that of the Dirichlet-smoothed term probability of query likelihood:

$$f(\text{event}, D) = \log \frac{\mathit{tf}_{\text{event}, D} + \mu\, \mathit{cf}_{\text{event}} / \lvert C \rvert}{\lvert D \rvert + \mu},$$

where $\mathit{tf}_{\text{event}, D}$ counts the event's occurrences in the document, $\mathit{cf}_{\text{event}}$ counts them in the whole collection, $\lvert D \rvert$ is the document's length, $\lvert C \rvert$ the number of tokens in the collection, and $\mu$ the smoothing parameter. The paper writes the same quantity as $(1 - \alpha_D)\,\mathit{tf}/\lvert D \rvert + \alpha_D\,\mathit{cf}/\lvert C \rvert$ with $\alpha_D = \mu / (\mu + \lvert D \rvert)$; putting the two terms over the common denominator $\lvert D \rvert + \mu$ gives the form above. The three events are:

Feature Clique Event counted Written in the paper's query language
Term, $f_T$ one query term and $D$ the term $q_i$ q_i
Ordered window, $f_O$ contiguous query terms and $D$ the exact phrase $q_i \dots q_{i+k}$, in order and adjacent #1(q_i ... q_i+k)
Unordered window, $f_U$ two or more query terms and $D$ all the terms inside a window of $N$ tokens, in any order #uwN(q_i ... q_j)

The ordered window rewards a document for containing part of the query as a phrase. The unordered window rewards it for containing the terms near one another. A clique of contiguous query terms receives both features, through the product potential above, and a clique of terms that are not contiguous in the query receives only the unordered one. For the sequential dependence variant the paper compares windows of 2, 50 and unlimited size with a sentence-sized window, for which it takes $N = 8$ because "the average length of an English sentence is 8-15 terms". For full dependence it sets $N$ to four times the number of terms in the clique.

The ranking function and its weights

Giving every clique its own weight would leave far too many parameters. The paper ties them: all term cliques share $\lambda_T$, all ordered-window features $\lambda_O$, and all unordered-window features $\lambda_U$. For the sequential dependence variant, the ranking function is then

$$\mathrm{score}(Q, D) = \lambda_T \sum_{i=1}^{n} f_T(q_i, D) \;+\; \lambda_O \sum_{i=1}^{n-1} f_O(q_i, q_{i+1}, D) \;+\; \lambda_U \sum_{i=1}^{n-1} f_U(q_i, q_{i+1}, D).$$

Two properties can be read from it.

  • Full independence is query likelihood. With $\lambda_O = \lambda_U = 0$ the score is $\lambda_T \sum_i f_T(q_i, D)$, and $\sum_i f_T(q_i, D)$ is the logarithm of the Dirichlet-smoothed query likelihood. A positive factor $\lambda_T$ does not change the order. The reduction uses the uniform document prior stated above; the paper makes the same assumption. So the model contains the unigram language model as its simplest case, which is the baseline for the experiments below.
  • Only the proportions of the weights matter. Multiplying all three weights by the same positive constant multiplies every score by it and changes no ranking. The paper therefore fixes $\lambda_T + \lambda_O + \lambda_U = 1$.

The weights are not estimated by maximum likelihood, since that would need $Z_\Lambda$. The paper trains them "by directly maximizing mean average precision", starting from full independence and climbing one coordinate at a time. Its Table 6 gives suggested values for each variant: $(\lambda_T, \lambda_O, \lambda_U) = (0.85, 0.10, 0.05)$ for sequential dependence and $(0.80, 0.10, 0.10)$ for full dependence. These are the weights commonly quoted for the sequential dependence model, and they come from that table. The same table reports results with the parameters set to their best values on each collection. Sequential dependence raised mean average precision over full independence on all four of the paper's TREC collections:

  • by 5.2 percent on the Associated Press collection;
  • by 7.1 percent on the Wall Street Journal;
  • by 6.6 percent on the WT10g web collection;
  • by 13.2 percent on GOV2, a crawl of 25 million pages.

The model by hand

Back to the two twelve-term documents. The collection statistics are Cranfield's, with the unit's analysis (stop words removed, then stemmed) and $\mu = 200$, the value chosen for Cranfield in language models for retrieval. The collection has $\lvert C \rvert = 156{,}309$ tokens. Panel occurs 231 times in it and flutter 282 times. The pair panel flutter, adjacent and in that order, occurs 32 times in 12 abstracts. The two words occur within a window of 8 tokens 82 times in 19 abstracts.

The term features are the same for both documents. Each word occurs once in 12 tokens:

$$f_T(\textit{panel}) = \ln \frac{1 + 200 \times 231 / 156{,}309}{12 + 200} = \ln \frac{1.2956}{212} = -5.0976, \qquad f_T(\textit{flutter}) = \ln \frac{1.3608}{212} = -5.0485.$$

Their sum, $-10.1461$, is the query likelihood score of both documents.

The window features differ. The background mass of the ordered window is $200 \times 32 / 156{,}309 = 0.0409$, and that of the unordered window is $200 \times 82 / 156{,}309 = 0.1049$.

Document #1 count $f_O$ #uw8 count $f_U$
near 1 $\ln \frac{1.0409}{212} = -5.3165$ 1 $\ln \frac{1.1049}{212} = -5.2568$
far 0 $\ln \frac{0.0409}{212} = -8.5521$ 0 $\ln \frac{0.1049}{212} = -7.6111$

In far the two words are eleven positions apart, outside a window of 8, so both counts are zero and both features fall back to the background.

The scores, with weights $(0.85, 0.10, 0.05)$:

  • near: $0.85 \times (-10.1461) + 0.10 \times (-5.3165) + 0.05 \times (-5.2568) = -8.6242 - 0.5317 - 0.2628 = -9.4187$;
  • far: $0.85 \times (-10.1461) + 0.10 \times (-8.5521) + 0.05 \times (-7.6111) = -8.6242 - 0.8552 - 0.3806 = -9.8600$.

The sequential dependence model separates the two documents by 0.4413, where the unigram model gave both the same score. The gap is $0.10 \times 3.2357 + 0.05 \times 2.3543$: the ordered feature of near exceeds that of far by $\ln(1.0409/0.0409) = 3.2357$ and the unordered feature by $\ln(1.1049/0.1049) = 2.3543$. For scale, a second occurrence of flutter in a document of the same length would add $0.85 \times \ln(2.3608/1.3608) = 0.468$ to the score. One adjacent occurrence of the pair is worth about as much as one more occurrence of a query word.

Abstracts 858 and 948

The opening pair is the same situation in real text. For the two-term query panel flutter:

Abstract 858 Abstract 948
Length 149 142
panel, flutter counts 11, 7 11, 7
#1(panel flutter) 0 4
#uw8(panel flutter) 7 6
Sum of term features $-7.2896$ $-7.2490$
$f_O$ $\ln \frac{0.0409}{349} = -9.0506$ $\ln \frac{4.0409}{342} = -4.4383$
$f_U$ $\ln \frac{7.1049}{349} = -3.8943$ $\ln \frac{6.1049}{342} = -4.0257$
Sequential dependence score $-7.2959$ $-6.8068$

The term features differ by 0.0405, only because 948 is seven tokens shorter. The sequential dependence scores differ by 0.4891, and 0.4612 of that is the ordered window. Abstract 858 has one more unordered window than 948: seven times it has the two words within eight tokens of each other, never as panel followed directly by flutter. That recovers a little, 0.05 times the difference of the two unordered features. (The window counts in this section are by this page's scan; with Indri's overlapping windows they would be 9 and 7.)

On these two words the model prefers 948. On the full query 185 the other terms keep 858 ahead, at rank 5 against rank 9, because 858 contains experiment three times and 948 does not contain it; the phrase has narrowed the gap between them by about 0.49. For the query this unit follows, the preference for 948 is the wrong one: 858 is one of the nine abstracts relevant to query 185, and 948 is not. The phrase panel flutter is strong evidence that an abstract is about panel flutter. It says nothing about whether the abstract reports experimental studies, which is what separates the relevant abstracts from the rest among those on the subject.

Query 185 in full

Query 185 analyzes to experiment studi panel flutter, so its adjacent pairs are (experiment, studi), (studi, panel) and (panel, flutter). In the collection the first pair occurs as a phrase 38 times in 24 abstracts, the second 3 times in one abstract, and the third 32 times in 12.

Example (the running query loses). Sequential dependence lowers query 185's average precision from 0.774 to 0.709. Under full independence the nine relevant abstracts stand at ranks 1, 2, 3, 4, 6, 9, 15, 16 and 18. Under sequential dependence they stand at 1, 2, 4, 5, 6, 13, 14, 15 and 18. The nonrelevant abstract 390 is a theoretical paper titled some panel-flutter studies using piston theory. It rises from rank 5 to rank 3 on three occurrences of the phrase. The relevant abstract 859 has panel 16 times and flutter 9 times and never the phrase, and it falls from 9 to 13. Of the 20 abstracts that contain both words, 12 contain the phrase, and only 5 of those 12 are relevant. On this query the phrase does not discriminate.

Example (a query that gains). Query 83, what is the present state of the theory of quasi-conical flows, gains: its average precision rises from 0.070 to 0.273. The pair (quasi, conic) occurs as a phrase once in the collection, in abstract 680, and (conic, flow) occurs 17 times in 11 abstracts, 680 among them. Abstract 680 is relevant. Full independence ranks it fifth, behind four nonrelevant abstracts. Sequential dependence ranks it first. Here the query contains a real technical phrase, and the phrase picks out the right abstract.

On all of Cranfield

The experiment runs both rankers on all 225 queries with the setup of comparing ranking models: title and text together, the unit's stop list and stemmer, $\mu = 200$, and the top 1,000 documents evaluated. Three details of the setup differ from the paper's, and one is a matter of counting.

  • Stop words and positions. Positions are assigned after stop words are removed, so flutter of panels counts as two adjacent terms. The paper kept stop words in the documents and removed them only from queries, so its windows count every word. Ours count analyzed terms, and our window of 8 spans more text.
  • Queries. The paper used the title fields of TREC topics, a few words each. The Cranfield queries are full questions, with 10.9 adjacent pairs on average after analysis, and their pairs include ones such as (what, present).
  • Pairs that never occur. A pair that never occurs in the collection is left out of the sum. Its smoothed probability would be zero in every document and its logarithm undefined, and leaving it out changes no document's score relative to another.
  • Counting unordered windows. The paper defines the unordered window as the terms appearing, in any order, within a window of $N$ terms, and it computed the counts with the #uwN operator of the Indri search engine. It does not say how overlapping matches are counted. Indri's implementation counts one window for every occurrence of either term that has the other term within the window after it, so windows may overlap and an occurrence may be used twice: the text a b a b holds three windows. This page counts by a rule of its own, a left-to-right scan that uses each position at most once (the worked problems trace it), which finds two windows in a b a b. The choice hardly matters here. The script runs both: with overlapping windows, sequential dependence reaches a MAP of 0.2906 (118 queries improved, 92 harmed), against 0.2907 (116 and 94) with the scan. The tables below use the scan.

The ranker is deterministic, so there are no random seeds to repeat. The comparison is per query, with the unit's paired randomization test, which is two-sided: the signs of the 225 per-query differences are flipped at random 20,000 times, and $p$ is the share of flips whose mean is at least as large in absolute value as the observed one (significance testing). The paper used a one-tailed paired t-test. On these data that test gives $t = 1.83$ and $p$ of about 0.033 for MAP (0.067 two-tailed), so whether the gain counts as significant at 0.05 depends on the choice of a two-sided test. With the paper's weights and $N = 8$:

Measure Query likelihood (FI) Sequential dependence Queries improved Harmed Unchanged $p$
MAP 0.2844 0.2907 116 94 15 0.069
nDCG at 10 0.3504 0.3587 81 54 90 0.057
Precision at 10 0.2169 0.2227 23 11 191 0.046

The full independence run reproduces the query likelihood numbers of the language model article exactly (MAP 0.284), which checks the implementation. Sequential dependence raises MAP by 0.006, about 2 percent. More queries improve than are harmed, but the difference in MAP is not significant at the 0.05 level. The largest changes run both ways: three queries lose between 0.19 and 0.25 in average precision, and three gain between 0.20 and 0.25. BM25 on the same queries has a MAP of 0.307, so adding dependence features does not close the gap between query likelihood and BM25 here.

Three further runs test the model's choices, each against the same baseline:

Setting MAP Improved Harmed $p$
Window $N = 2$ 0.2910 116 94 0.058
Window $N = 8$ (above) 0.2907 116 94 0.069
Window $N = 50$ 0.2887 114 94 0.18
Window unlimited 0.2893 111 98 0.12
Ordered only, weights $(0.85, 0.15, 0)$ 0.2912 116 94 0.059
Unordered only, weights $(0.85, 0, 0.15)$ 0.2869 106 106 0.48
  • The window size matters little, as the paper found on its collections ("very little difference across the various window sizes"). Narrow windows do slightly better here.
  • The ordered feature does the work. With all of the dependence weight on the ordered feature, MAP is 0.2912, as good as with both. With all of it on the unordered feature, MAP is 0.2869: more than half of the gain over 0.2844 is gone, and as many queries are harmed as improved.

To choose weights fairly, the queries were split as in the rest of the unit into 112 development and 113 test queries. A grid of $\lambda_O$ and $\lambda_U$ from 0 to 0.30 was evaluated on the development half. The best setting there was $(0.70, 0.20, 0.10)$, with a MAP of 0.2912 against 0.2845 for full independence. On the test queries it gave 0.2929 against 0.2843 ($p = 0.19$). The paper's weights, which were never tuned on Cranfield, gave 0.2937 on the same test queries ($p = 0.076$). Tuning on 112 queries found nothing better than the published values.

These are results on one small collection, and they should be read as that. The gain is positive and, by the two-sided test, not significant: about 2 percent, against the paper's 5 to 13 percent. The two are not measured alike. The paper's figures were obtained with the weights tuned on the very queries they are reported on, which the paper itself describes as an upper bound on performance; the run here uses the paper's weights untuned. That is the pattern the paper predicted. Its first hypothesis is that "dependence models will be more effective for larger collections than smaller collections". The reasoning is that a large, noisy collection holds many documents that match the query's words separately, and a phrase can filter them out. Cranfield has 1,400 abstracts on one subject. A pair of query words such as boundari layer occurs as a phrase 1,149 times, in 366 of the 370 abstracts that contain both words, so it filters almost nothing. The experiment here is consistent with the hypothesis and cannot test it, since it has only the small collection.

Proximity inside BM25

The same evidence can be added to BM25 without a new probabilistic model. Rasolofo and Savoy (2003) added a term-pair score to an Okapi system. They consider every pair of query terms and every occurrence of the two within five words of each other. Each such occurrence gets the weight $1/d^2$, where $d$ is the distance in words: 1.0 for adjacent words and 0.04 at a distance of five. The weights of a pair are summed over the document and passed through a saturating function of the same shape as BM25's term frequency component. Each pair's result is multiplied by the smaller of its two query term weights, the pairs are added up, and the total is added to the document's Okapi score, for the top 100 documents only. They report that on three TREC test collections the differences in average precision were small, and that the method tended to improve precision at the top ranks. Büttcher, Clarke, and Lushman (2006) added a proximity score to BM25 that they describe as very similar to Rasolofo and Savoy's. On TREC disks 4 and 5 without the Congressional Record (528,155 documents) it made no difference to precision at 10, which was 0.382 without it and 0.381 with it. On GOV2 (25.2 million web pages) it raised precision at 10 from 0.529 to 0.600, a significant gain. Their further experiments on subsets of GOV2 supported the hypothesis that proximity matters more as the collection grows, which is the direction of Metzler and Croft's first hypothesis.

The two approaches use the same data and differ in what they claim. The Markov random field model derives its features from a stated joint distribution and learns three weights. The BM25 variants add a heuristic term whose form is chosen for its behavior. Both need to know where in each document every query term occurs.

The index that makes it computable

None of these features can be computed from the postings used so far in this unit, which hold a term frequency for each document and nothing else. The count of #1(panel flutter) in a document needs the positions of panel and of flutter in that document. A positional index stores them: each posting carries the list of token positions at which the term occurs. Phrase and proximity queries describes the structure, the merge that finds a phrase from two position lists, and the window algorithm for proximity operators. It also introduces the smallest window containing all the query terms as a proximity measure for ranking.

The features of this article are small computations over two position lists:

  • the ordered window count is the number of positions $p$ of the first term such that $p + 1$ is a position of the second;
  • the unordered window count comes from one pass over the two sorted lists.

The cost is the cost of the index itself. Positional postings hold one entry per occurrence instead of one per document, and scoring a pair means reading both terms' position lists in every document that contains both. For sequential dependence that is $n - 1$ pairs for a query of $n$ terms, which is why it is the variant used in practice. This site's own search index stores positions for each field of each page (app/search.py) and uses them to answer quoted phrase queries. Its ranking is BM25F over term counts. It is an independence model with the data for a dependence model already in its index.

Worked problems

These problems are posed on the article's own examples and on small constructed position lists; the course text has no exercises on term dependence models. The script tools/experiments/cranfield/term_dependence.py computes every number in this article from the collection and asserts it.

Problem 1 (counting cliques). For a query of four terms $q_1 q_2 q_3 q_4$, count the cliques that contain the document node and at least one query term under each variant. For full dependence, say how many of the multi-term cliques are contiguous in the query, and give the general counts for $n$ terms.

Solution. Full independence has the four cliques $\{q_i, D\}$. Sequential dependence adds the three adjacent pairs $\{q_1, q_2, D\}$, $\{q_2, q_3, D\}$, $\{q_3, q_4, D\}$, for seven. Under full dependence every non-empty subset of the four terms forms a clique with $D$: $2^4 - 1 = 15$, of which 4 have one term and 11 have two or more. A subset is contiguous when it is a run $q_i \dots q_j$ with $i < j$, and there are $\binom{4}{2} = 6$ ways to choose the two ends: three pairs, two triples and the whole query. The other $11 - 6 = 5$ are not contiguous: $\{q_1, q_3\}$, $\{q_1, q_4\}$, $\{q_2, q_4\}$, $\{q_1, q_2, q_4\}$ and $\{q_1, q_3, q_4\}$. The six contiguous cliques receive an ordered and an unordered feature each, and the five others an unordered feature only.

In general there are $n$ single-term cliques, $n - 1$ adjacent pairs, and $2^n - n - 1$ subsets of two or more terms, of which $n(n-1)/2$ are contiguous. For $n = 12$ the full dependence variant has 4,083 multi-term cliques, 66 of them contiguous, against 11 pairs for sequential dependence.

Problem 2 (two features by hand). Abstract 948 has 142 tokens and contains the phrase panel flutter four times; abstract 858 has 149 tokens and never contains it. The phrase occurs 32 times in the collection of 156,309 tokens, and $\mu = 200$. Compute $f_O$ for each abstract and the difference the ordered feature makes to their sequential dependence scores.

Solution. The background mass is $\mu\,\mathit{cf}/\lvert C \rvert = 200 \times 32 / 156{,}309 = 0.0409$. Then

$$f_O(948) = \ln \frac{4 + 0.0409}{142 + 200} = \ln \frac{4.0409}{342} = -4.4383, \qquad f_O(858) = \ln \frac{0 + 0.0409}{149 + 200} = \ln \frac{0.0409}{349} = -9.0506.$$

The features differ by 4.6123, and with $\lambda_O = 0.10$ the scores differ by 0.4612 on this account. Most of that difference is the step from zero occurrences to one: a document with no occurrence has only the background mass 0.0409 in the numerator, and the first occurrence multiplies the numerator by about 25. The fourth occurrence multiplies it by about $4/3$. Smoothed log probabilities saturate, as BM25's term frequency component does.

Problem 3 (counting windows). In a document, term $a$ occurs at positions 3, 10 and 30 and term $b$ at positions 5, 6 and 40. Count the ordered windows #1(a b) and the unordered windows #uwN(a b) for $N$ = 2, 8, 50 and unlimited, using the left-to-right scan: compare the earliest unused position of each term; if they are fewer than $N$ positions apart, count a window and use both; otherwise pass over the earlier one.

Solution. For #1, a window needs $b$ at the position just after an $a$. Positions 4, 11 and 31 hold no $b$, so the count is 0.

For $N = 8$: compare 3 and 5; they are 2 apart, so count one window and move both on. Compare 10 and 6; they are 4 apart, so count a second. Compare 30 and 40; they are 10 apart, which is not less than 8, so pass over 30, and $a$ is exhausted. The count is 2.

For $N = 2$ the two positions must be adjacent. Compare 3 and 5 (2 apart, not less than 2): pass over 3. Compare 10 and 5: pass over 5. Compare 10 and 6: pass over 6. Compare 10 and 40: pass over 10. Compare 30 and 40: pass over 30. The count is 0.

For $N = 50$ every comparison succeeds: 3 with 5, 10 with 6, 30 with 40. The count is 3, and it is 3 for an unlimited window too. With no limit the scan pairs off occurrences until one term runs out, so the count is the smaller of the two term frequencies. That is the sense in which an unlimited window measures co-occurrence in the document and nothing about position.

Indri's operator, which lets windows overlap, counts 0, 3, 5 and 5 on these lists for $N$ = 2, 8, 50 and unlimited. For $N = 8$ its three windows start at 3 (reaching the $b$ at 5), at 5 (reaching the $a$ at 10) and at 6 (reaching the same $a$ at 10), so position 10 is used twice.

Problem 4 (the scale of the weights). Show that the weights $(17, 2, 1)$ rank every set of documents exactly as $(0.85, 0.10, 0.05)$ do, and compute the two scores of the documents near and far under them.

Solution. $(17, 2, 1) = 20 \times (0.85, 0.10, 0.05)$. The score is linear in the weights, so every document's score is multiplied by 20, and multiplying all scores by a positive constant preserves their order. For near the score is $17 \times (-10.1461) + 2 \times (-5.3165) + (-5.2568) = -188.374$, which is $20 \times (-9.4187)$. For far it is $17 \times (-10.1461) + 2 \times (-8.5521) + (-7.6111) = -197.200$, which is $20 \times (-9.8600)$. The script also checks that the two weight vectors give the same ranking of all the candidates of query 185. This is why the model has two free parameters, not three, and why the paper can report its weights as proportions that sum to 1.

What we have learned

Independence models score a document from term counts alone, so two documents with the same counts get the same score wherever the words stand. The Markov random field model puts the query terms and the document in a graph and scores a document by a weighted sum of features, one per clique: single terms, exact phrases and windows. Its simplest case is query likelihood, and its sequential dependence variant adds the adjacent pairs of the query with the weights $(0.85, 0.10, 0.05)$ suggested in the original paper. On two documents with identical counts the model separated them by 0.44, about the worth of one more occurrence of a query word. On Cranfield it raised query likelihood's MAP from 0.284 to 0.291, a gain that is not significant, with the ordered window doing the work. Query 83 gained from a technical phrase. Query 185 lost, because the phrase panel flutter marks the subject and not the experimental studies the query asks for.

The three sums of the ranking function are features, and their weights were set by maximizing an evaluation measure directly. Learning to rank takes both ideas further: many features of a query and a document, proximity among them, with weights fitted to judged queries.

References

  • Büttcher, S., Clarke, C. L. A., and Lushman, B. (2006). Term proximity scoring for ad-hoc retrieval on very large text collections. In Proceedings of SIGIR 2006, 621–622. record
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 2 and 11. Cambridge University Press. record · 93 pages
  • Metzler, D., and Croft, W. B. (2005). A Markov random field model for term dependencies. In Proceedings of SIGIR 2005, 472–479. record · 2 pages
  • Rasolofo, Y., and Savoy, J. (2003). Term proximity scoring for keyword-based retrieval systems. In Advances in Information Retrieval: Proceedings of ECIR 2003, Lecture Notes in Computer Science 2633, 207–218. Springer. record
  • van Rijsbergen, C. J. (1977). A theoretical basis for the use of co-occurrence data in information retrieval. Journal of Documentation, 33(2), 106–119. record