Bayesian Inference Networks

The Binary Independence Model and BM25 estimate the probability of relevance from the query terms a document contains, treating the terms as independent and the query as a flat list. Real information needs have structure. A searcher may want documents about heat transfer or heat flux, and about turbine blades. They may count a phrase as more important than its separate words, or one concept as twice as important as another. Bayesian inference networks, introduced to retrieval by Howard Turtle and W. Bruce Croft (1990, 1991), represent such structure explicitly. Documents, terms, query concepts, and the information need become nodes in a network, and ranking becomes probabilistic inference: for each document, compute the belief that observing it satisfies the information need.

The model was implemented in the INQUERY system (Callan, Croft, and Harding, 1992), which performed strongly in early TREC evaluations, and its query language survives in the Indri search engine.

Bayesian networks in brief

A Bayesian network is a directed acyclic graph whose nodes are random variables and whose edges express direct dependence. Each node has a conditional probability distribution given its parents. The joint distribution of all the variables factorizes into these local distributions, which makes it possible to represent a complicated distribution compactly and to compute the probability of one variable given evidence about others. In general, inference in such networks is computationally hard. The retrieval network is structured so that the computation needed for ranking is simple.

The retrieval network

The Turtle-Croft network has two parts (Turtle and Croft, 1991).

The document network is built once, at indexing time:

• document nodes $d_j$, one per document, representing the event that the document is observed;
• representation nodes $r_k$, one per index term or concept, representing the event that the concept is present.

An edge from $d_j$ to $r_k$ carries the probability that the concept is present given the document, the term's belief in that document. The original network also has text representation nodes between the two layers, one for each form of a document's text, such as an abstract or a full text. With one text form per document, as assumed here, they can be left out.

The query network is built for each query:

• query concept nodes, which combine representation nodes according to the query's operators;
• query nodes, one for each query, when several formulations of the same need are combined;
• a single information need node $I$ at the top.

To rank documents, each document node in turn is set to true, meaning that this document is observed, with all others false. The beliefs are then propagated up through the network to compute $P(I \mid d_j)$. Documents are ranked by that belief. Since only one document is observed at a time and each representation node depends only on that document, propagation reduces to evaluating the query's operators on the term beliefs, which is fast.

Estimating term beliefs

The belief that concept $r_k$ is present in document $d_j$ is estimated from term statistics, in the spirit of TF-IDF. INQUERY's default form combined a normalized term frequency and a normalized IDF with a default belief:

$$\mathrm{bel}(r_k \mid d_j) = \alpha + (1 - \alpha) \cdot \mathit{ntf}_{k,j} \cdot \mathit{nidf}_k,$$

with $\alpha = 0.4$. Here $\mathit{ntf}$ is a saturating, length-normalized term frequency between 0 and 1, and $\mathit{nidf}$ is IDF scaled to lie between 0 and 1. The default belief means that a term absent from a document still has belief 0.4 rather than 0. Absence of a word is weak evidence that the concept is absent, since the document may express it in other words. This choice makes a strict conjunction partly satisfiable by a document that lacks one term, softening the AND operator in the way the worked examples below show.

The exact normalizations changed between versions. The one the INQUERY group published for its TREC-8 runs (Allan, Callan, Feng, and Malin, 2000, §1.1) is

$$\mathit{ntf}_{t,d} = \frac{\mathit{tf}_{t,d}}{\mathit{tf}_{t,d} + 0.5 + 1.5\, \frac{L_d}{L_{\mathrm{avg}}}}, \qquad \mathit{nidf}_t = \frac{\log \frac{N + 0.5}{\mathrm{df}_t}}{\log (N + 1)},$$

where $L_d$ is the length of document $d$ in words, $L_{\mathrm{avg}}$ the average length, $N$ the number of documents and $\mathrm{df}_t$ the number containing $t$. Both parts are recognizable. $\mathit{ntf}$ is the saturating curve of BM25, $\mathit{tf}/(\mathit{tf} + K)$, with $K = 0.5 + 1.5\, L_d / L_{\mathrm{avg}}$: 2 for a document of average length, more for longer ones. $\mathit{nidf}$ is IDF divided by $\log(N + 1)$, slightly more than the largest IDF any term can have, $\log(N + 0.5)$ for a term in a single document, so that it stays below 1. Two consequences follow. Every belief lies between 0.4 and $0.4 + 0.6\, \mathit{nidf}_t$, so a common term can never contribute a high belief however often it occurs. And because the ceiling is set by IDF, the formula is a TF-IDF weight rescaled into a probability-like range, as Turtle and Croft (1990, §3.4) showed a weighted-sum link matrix produces.

Query operators

The query network combines beliefs with operators, each a canonical form of conditional probability that avoids specifying an exponentially large table. For parent beliefs $p_1, \dots, p_n$, the main INQUERY operators are:

With beliefs restricted to 0 and 1, #and, #or, and #not reduce to Boolean logic. With graded beliefs they give graded scores. #sum and #wsum behave like the vector space model's weighted sums. One network thus contains the Boolean, vector space, and probabilistic approaches as special cases, which was one of the model's main theoretical attractions. Turtle and Croft (1991) showed that combining several formulations of the same query, such as a natural language and a Boolean version, in one network improved effectiveness over any one alone.

Where the operator formulas come from

The formulas in the table are not chosen for convenience; they follow from writing down a node's conditional probability table, which Turtle and Croft (1990, §3.4) call a link matrix, and summing over the states of its parents (Croft, Metzler, and Strohman, 2010, §7.4.1, derive #and the same way). Take a query node $q$ with two parents $a$ and $b$, believed present with probabilities $p_a = 0.55$ and $p_b = 0.48$, and treat the parents as independent. Each of the four combinations of parent states has a probability, and the link matrix says how likely $q$ is to be true in each:

The belief in $q$ is the sum over states of the state's probability times $P(q \mid a, b)$. For #and only the last row counts, giving $0.264 = p_a p_b$. For #or every row but the first counts, giving $0.216 + 0.286 + 0.264 = 0.766 = 1 - (1 - p_a)(1 - p_b)$. With $n$ parents the table has $2^n$ rows, but for these canonical matrices the sum always collapses to the closed forms in the operator table, so the network never has to store or sum the table. A weighted-sum matrix, in which $q$'s probability in each state is the share of the total parent weight held by the parents that are true, collapses in the same way to #wsum. The independence of the parents is an assumption, the same one the BIM makes.

A worked example

A document has beliefs 0.62 for heat, 0.55 for transfer, and 0.48 for flux. For the query structure heat and (transfer or flux):

A second document contains heat with belief 0.62 but neither transfer nor flux. Both get the default belief 0.4, so #or gives $1 - 0.6 \times 0.6 = 0.64$, and #and gives $0.62 \times 0.64 = 0.397$. The document ranks below the first, which matched more of the query, but it is not excluded, as it would be by a Boolean AND.

A real query through the network

The beliefs in the example above were chosen for illustration. With the belief formula, a real collection supplies them. Cranfield query 185, experimental studies on panel flutter, has four terms after stemming and stopping, and two natural formulations:

• $q_1$ = #sum(experiment studi panel flutter), the natural-language form, which averages the evidence;
• $q_2$ = #and(experiment panel flutter), a structured form for a searcher who insists on experiments and drops the vague studies;
• $I$ = #sum(q1 q2), the information need, combining both formulations, the kind of combination Turtle and Croft (1991) found effective.

The numbers below are computed by tools/experiments/cranfield/infnet_example.py over the 1,400 Cranfield abstracts, with lengths in tokens after stopping ($L_{\mathrm{avg}} = 111.65$) and natural logarithms, rounded to three decimals. The normalized IDFs are 0.196 for experiment, 0.244 for studi, 0.474 for panel, and 0.444 for flutter.

One belief by hand. Abstract 856 has 172 tokens and contains panel 16 times. Then $\mathit{ntf} = 16 / (16 + 0.5 + 1.5 \times 172/111.65) = 16 / 18.811 = 0.851$, $\mathit{nidf} = \ln(1400.5/45) / \ln 1401 = 3.438 / 7.245 = 0.474$, and the belief is $0.4 + 0.6 \times 0.851 \times 0.474 = 0.642$.

Propagation for abstract 856 is three operator evaluations. $q_1 = (0.469 + 0.494 + 0.642 + 0.612)/4 = 0.554$. $q_2 = 0.469 \times 0.642 \times 0.612 = 0.184$. $I = (0.554 + 0.184)/2 = 0.369$. The same network, evaluated with each abstract observed in turn:

Abstract 390, some panel-flutter studies using piston theory, is a theoretical paper, and the same abstract that BM25 ranks fourth. Under the natural-language $q_1$ it ranks fifth, just above relevant abstract 1008: it lacks experiment, but its studi belief compensates in the average. Under $q_2$, which drops studi and multiplies, the missing experiment leaves 390 at the default belief 0.4 against 0.452 for the single mention in 1008, nothing makes up for it in a product, and it falls to eleventh while 1008 rises to fifth. Combining the formulations puts it seventh. Across all 542 abstracts that contain a query term:

On this query, structure helps, and the combination lands between its two parts. The beliefs are also strikingly compressed: every belief in the table lies between 0.4 and 0.65, because the default belief sets the floor and the normalized IDF the ceiling. What decides the ranking is the small differences above 0.4, and the operators decide how those differences combine: an average lets a strong term make up for a missing one, while a product lets a missing term, stuck at 0.4, pull the whole score down.

As a flat ranking function, the belief formula holds its own. Over all 225 Cranfield queries, each turned into a #sum of its terms, it reaches a mean average precision of 0.311, against 0.307 for BM25 with default parameters. It is better on 136 queries and worse on 69, but the difference is not significant (randomization test, $p = 0.12$), so on this collection the two are equivalent.

Strengths and limits

The inference network gave retrieval a single probabilistic framework in which several kinds of evidence could be combined. These included multiple document representations, multiple query formulations, phrases, proximity operators, and field restrictions. Its structured query language let expert searchers state their needs precisely and still receive ranked results, a combination that suited professional search well.

Its limits are the usual ones for probabilistic models. The operators assume independence among their inputs, which is no more true here than in the BIM, so the network models the structure of the query rather than dependence between terms. Term beliefs come from heuristic formulas rather than estimated probabilities, with constants such as the default belief tuned by experiment, and the network's structure is fixed by the query language rather than learned.

Descendants

The model's query language and combination of evidence carried forward. Metzler and Croft (2004) combined inference networks with language models, keeping most of INQUERY's operators but estimating the beliefs at the representation nodes from smoothed language models instead of the TF-IDF formula. The combined model was implemented in the Indri search engine (Croft, Metzler, and Strohman, 2010, §7.4). Indri's structured queries, with operators for phrases, unordered windows, weighted combinations, and fields, were widely used in research. They form the basis of influential models of term dependence, which reward query terms that appear near one another, such as the Markov random field model of Metzler and Croft (2005). In that sense the inference network's main legacy is a language for expressing how evidence should be combined, which learning to rank later replaced with combinations learned from data.

References

• Allan, J., Callan, J., Feng, F.-F., and Malin, D. (2000). INQUERY and TREC-8. In Proceedings of the Eighth Text REtrieval Conference (TREC-8), NIST Special Publication 500-246, 637–643.
• Callan, J. P., Croft, W. B., and Harding, S. M. (1992). The INQUERY retrieval system. In Proceedings of the Third International Conference on Database and Expert Systems Applications (DEXA), 78–83.
• Croft, W. B., Metzler, D., and Strohman, T. (2010). Search Engines: Information Retrieval in Practice, section 7.4. Addison-Wesley.
• Metzler, D., and Croft, W. B. (2004). Combining the language model and inference network approaches to retrieval. Information Processing and Management, 40(5), 735–750.
• Metzler, D., and Croft, W. B. (2005). A Markov random field model for term dependencies. In Proceedings of SIGIR 2005, 472–479.
• Turtle, H., and Croft, W. B. (1990). Inference networks for document retrieval. In Proceedings of SIGIR 1990, 1–24.
• Turtle, H., and Croft, W. B. (1991). Evaluation of an inference network-based retrieval model. ACM Transactions on Information Systems, 9(3), 187–222.