The DBpedia-Entity v2 test collection contains the query brooklyn bridge, and its judges graded two entities as highly relevant: the bridge itself, and a painting of it by Albert Gleizes. Run BM25 over the entities' names and abstracts together, and the bridge comes fourth, behind Brooklyn Bridge Park, a later bridge proposal and an album. Give the name its own field, with a high weight and its own length normalization, as BM25F can, and the bridge comes first. How should a search engine rank entities rather than documents, and how much does the structure of an entity's description help?
Entity-oriented search is search in which entities are the unit of retrieval, the unit of meaning, or both. Its central task is ad hoc entity retrieval: given a keyword query $q$ and an entity catalog $\mathcal{E}$, return a ranked list of entities by their relevance to $q$, inferred from unstructured or structured data about them (Balog, 2018, Definition 3.1). Balog's working definition of an entity is "a uniquely identifiable 'thing,' a typed object, with name(s), attributes, and relationships to other entities". Entities also serve document retrieval, by giving a machine a representation of what a query or a document is about, and they shape the result page, through entity cards.
Here is the route. First we turn entities into fielded documents built from a knowledge base. Then we rank them with the fielded models, and prove how FSDM reduces to the models it generalizes. Next we add what is special about entities: their types and their relationships in a knowledge graph. After that we turn to the reverse use, entities in the service of document retrieval, and to entity cards. Then we run BM25 and BM25F over the 4.6 million entities of DBpedia-Entity v2 and set the results beside the published baselines. Finally we look at this site's own search box, which is an entity search over pages. The article assumes BM25F and Term Dependence Models, and it follows Entity Linking, which maps text to entities, and Knowledge Graphs, which describes the knowledge bases entities come from; the numbers are computed by tools/experiments/knowledge-stores/entity-oriented-search.py.
What kinds of query ask for entities
Entity-bearing queries come in several shapes. Pound, Mika and Zaragoza (2010) classified the queries of a web search log into entity queries, type queries, attribute queries, relation queries and others, and, as Zhiltsov, Kotov and Nikolaev (2015, §1) report, found that such information needs make up more than half of the queries. DBpedia-Entity v2 (Hasibi et al., 2017) assembled 467 queries from earlier evaluation campaigns into four categories, with these examples from the paper (§2.2):
- SemSearch ES: short and ambiguous queries for one particular entity, such as brooklyn bridge or 08 toyota tundra (113 queries);
- INEX-LD: keyword queries in the style of IR test collections, such as electronic music genres (99);
- ListSearch: queries that seek a list of entities, such as Professional sports teams in Philadelphia (115);
- QALD-2: natural language questions answerable from DBpedia, such as Who is the mayor of Berlin? (140).
The categories differ in what they need. A named-entity query is close to a known-item search: the answer's name is in the query. A list query names a type and a constraint. A question may need a relationship between entities that no single description states.
Entities as documents
Here is the idea in one sentence: write a "profile" document for each entity, containing everything known about it, and rank those documents with the models we already have (Balog, 2018, §3.1). The design question is what goes into the profile and how to keep its structure.
From triples to fields
A knowledge base such as DBpedia stores facts as subject-predicate-object triples; Knowledge Graphs describes the model. An entity's neighborhood can contain hundreds of distinct predicates, too many to give each its own field with its own weight. The common remedy is predicate folding: group the predicates into a handful of fields (Balog, 2018, §3.2.3.1). The groups Balog lists are these.
- Name: the entity's names, from predicates such as
foaf:nameandrdfs:label. - Name variants: aliases, collected from redirects, disambiguation pages and link anchor texts. These are the alias dictionary of Entity Linking seen from the entity's side.
- Attributes: literal values, such as an abstract or a founding date, sometimes with the predicate's name in front ("founding date 1964").
- Types: the classes and categories the entity belongs to.
- Outgoing and incoming relations: the names of the entities it links to and of those that link to it.
- Catch-all: everything together.
A reference to another entity, a URI, is replaced by that entity's name, so that it can match query words (Balog, 2018, §3.2.3.2). The price, which Balog points out (§4.2.2), is that the unambiguous identifier becomes an ambiguous string again. Zhiltsov et al. (2015, Table 1) used five such fields for DBpedia: names, attributes, categories, similar entity names and related entity names. Their Table 2 shows the entity Barack Obama, whose related entity names field contains "spouse michelle obama" and "predecessor george walker bush".
How many fields are needed? Balog (2018, §3.2.3.1) notes that with as few as two, name and content, "it is possible to achieve solid performance", citing Neumayer, Balog and Nørvåg (2012), and that this "title+content" setting is a common baseline. The BEIR copy of DBpedia-Entity used in the experiment below is exactly that setting.
Ranking fielded entity descriptions
Once entities are fielded documents, the fielded models of document retrieval apply. Four are standard in this literature, and they differ in where the field weights act and whether word order counts.
BM25F
BM25F combines each field's length-normalized term frequency into one pseudo frequency before BM25's saturation. In Balog's notation (2018, eq. 3.14 and the following equation),
$$\mathrm{score}(e; q) = \sum_{t \in q} c(t; q)\, \frac{(k_1 + 1)\, \tilde{c}(t; e)}{k_1 + \tilde{c}(t; e)}\, \mathrm{IEF}(t), \qquad \tilde{c}(t; e) = \sum_{f} \alpha_f\, \frac{c(t; f_e)}{1 - b_f + b_f\, l_{f_e} / \bar{l}_f} ,$$
where $c(t; q)$ counts $t$ in the query, $c(t; f_e)$ counts it in field $f$ of entity $e$, $\alpha_f$ is the field's weight, $l_{f_e}$ the field's length and $\bar{l}_f$ its mean length over the catalog, and $\mathrm{IEF}(t)$ is the inverse entity frequency, the IDF computed over entities, without field information. The BM25F article derives why the fields are combined before the saturation and proves that, when the field scores share one saturation, no reweighting of their sum reproduces it.
The mixture of language models and PRMS
The mixture of language models (MLM) of Ogilvie and Callan (2003) estimates a smoothed language model for each field and mixes them with fixed weights,
$$P(t \mid \theta_e) = \sum_{f} \alpha_f\, P(t \mid \theta_{f_e}), \qquad \sum_f \alpha_f = 1 ,$$
and ranks entities by query likelihood under the mixture (Balog, 2018, eq. 3.12), with each $P(t \mid \theta_{f_e})$ a Dirichlet-smoothed field model.
The probabilistic retrieval model for semistructured data (PRMS) of Kim, Xue and Croft (2009) replaces the fixed weight $\alpha_f$ by a weight that depends on the term: the probability $P(f \mid t)$ that term $t$ belongs in field $f$. By Bayes' rule and the law of total probability,
$$P(f \mid t) = \frac{P(t \mid f)\, P(f)}{\sum_{f'} P(t \mid f')\, P(f')} ,$$
where $P(t \mid f)$ is estimated from the collection-wide language model of field $f$, the field's total count of $t$ divided by the field's total length, and the prior $P(f)$ is usually uniform (Balog, 2018, eq. 3.13). Balog's example, from IMDb, maps Meg to the cast field with probability 0.407 and redemption to the title field with 0.983. A term that is typical of titles is matched mainly against titles. PRMS has no free parameters, and it assumes that the fields have distinct term distributions; Balog notes that it works well only when they do. Worked problem 2 computes the mapping probabilities of brooklyn and bridge in DBpedia's two fields.
The fielded sequential dependence model
The sequential dependence model (SDM) of Metzler and Croft scores a document by a weighted sum of three kinds of feature: single terms, ordered pairs of adjacent query terms (exact bigrams) and unordered pairs within a window. Each feature is the logarithm of a Dirichlet-smoothed probability over the whole document. Zhiltsov et al. (2015) observed that this treats a match in the name exactly like a match deep in the attributes. Their fielded sequential dependence model (FSDM) replaces each single-document probability by a mixture over fields. For a query of terms $q_1, \dots, q_n$ and an entity document $D$ with fields $j = 1, \dots, F$, the unigram feature is (their §3.1)
$$\tilde{f}_T(q_i, D) = \log \sum_{j=1}^{F} w^T_j\, \frac{\mathit{tf}_{q_i, D_j} + \mu_j\, \mathit{cf}^{\,j}_{q_i} / \lvert C_j \rvert}{\lvert D_j \rvert + \mu_j} ,$$
where $\mathit{tf}_{q_i, D_j}$ is the term's frequency in field $j$ of $D$, $\lvert D_j \rvert$ the field's length, $\mathit{cf}^{\,j}_{q_i}$ and $\lvert C_j \rvert$ the term's count and the total length of field $j$ over the collection, $\mu_j$ a Dirichlet prior for the field, and the weights $w^T_j \ge 0$ sum to 1. The ordered and unordered bigram features $\tilde{f}_O$ and $\tilde{f}_U$ have the same form, with the frequency of the exact phrase $q_i q_{i+1}$, or of the two terms within a window of 8 positions, in place of $\mathit{tf}$, and each with its own field weights $w^O_j$ and $w^U_j$. The ranking function is their equation (1):
$$P_\Lambda(D \mid Q) \stackrel{\mathrm{rank}}{=} \lambda_T \sum_{i=1}^{n} \tilde{f}_T(q_i, D) + \lambda_O \sum_{i=1}^{n-1} \tilde{f}_O(q_i, q_{i+1}, D) + \lambda_U \sum_{i=1}^{n-1} \tilde{f}_U(q_i, q_{i+1}, D) .$$
Separate field weights for unigrams and bigrams let the model weight, for example, an exact phrase in the name field heavily for a named-entity query while matching the words of a list query loosely in the descriptive fields; the paper gives that reasoning with the query apollo astronauts who walked on the moon. The model has $3F + 3$ free parameters. Zhiltsov et al. train them in two stages by coordinate ascent on mean average precision: first the field weights of each feature type separately, then the $\lambda$ (their Algorithm 1).
FSDM generalizes the two models it combines, and both reductions can be checked directly from the definitions.
Reduction to MLM. Set $\lambda = (1, 0, 0)$. The score becomes $\sum_i \tilde{f}_T(q_i, D) = \sum_i \log \sum_j w^T_j P(q_i \mid \theta^j_D) = \log \prod_i P(q_i \mid \theta_D)$, where $P(q_i \mid \theta_D) = \sum_j w^T_j P(q_i \mid \theta^j_D)$ is the mixture of field models. That is the logarithm of the query likelihood under MLM with weights $\alpha_j = w^T_j$, and the logarithm is increasing, so the ranking is MLM's. Zhiltsov et al. (2015, §3.1) state this special case.
Reduction to SDM. Take a single field, $F = 1$. The constraint $\sum_j w_j = 1$ forces $w^T_1 = w^O_1 = w^U_1 = 1$, each mixture has one term, and each feature becomes the logarithm of one Dirichlet-smoothed probability over the whole document, which is SDM's feature, $\log \frac{\mathit{tf} + \mu\, \mathit{cf} / \lvert C \rvert}{\lvert D \rvert + \mu}$, with the same window of 8 for unordered pairs. The ranking function is then SDM's, term for term. $\blacksquare$
The two reductions say different things. The first means that FSDM over a given set of fields contains MLM over the same fields: tuned on the training queries, it can always match MLM's score on those queries, provided the optimizer reaches its optimum, which coordinate ascent does not guarantee, and nothing guarantees the same on unseen queries. The second is a statement about the model family, not about a fixed index: SDM is FSDM over an index with one field. Over an index with several fields, no choice of weights gives SDM over the whole document. A weight of 1 on one field gives SDM over that field alone, and any other choice is a fixed mixture of field models, whereas the Dirichlet model of the concatenated document weights each field by its share of that document's length, which varies from document to document. With few training queries, the extra $3F$ parameters can also be fitted to noise, which is why Hasibi et al. (2017, §3.2) trained such models by cross-validation.
What the published comparison shows
Hasibi et al. (2017) ran all these models, and others, on DBpedia-Entity v2 over a five-field index of DBpedia 2015-10 built the way Zhiltsov et al. built theirs. Their Table 2 reports nDCG@10 on the 467 queries, for untrained methods with default settings and for trained methods whose parameters were fitted on the older v1 judgments: BM25 over the flattened fields with default parameters ($k_1 = 1.2$, $b = 0.8$) scored 0.2558, PRMS 0.3905, MLM with equal field weights 0.4021, unigram language modeling 0.4182, SDM 0.4185, FSDM 0.4267 and BM25F trained by coordinate ascent 0.4378. The collection's repository reports the same methods trained on the v2 judgments by cross-validation, with BM25F 0.4605 and FSDM 0.4524 in total, and per category (BM25F) 0.6281 on SemSearch ES, 0.4394 on INEX-LD, 0.4252 on ListSearch and 0.3689 on QALD-2 (Hasibi et al., 2017, repository table).
The paper points out one lesson in its own numbers: "default parameter settings may be unfitting for entity retrieval", since BM25 with trained parameters (BM25-CA, 0.4231 in Table 2) is far above BM25 with defaults, and the trained values were $b \approx 0.05$ and $k_1$ between 2 and 6, depending on the query category. Balog's (2018, §3.6) summary of the same benchmark is that fielded representations with supervised learning give "a moderate, around 10%, relative improvement over unstructured and unsupervised models", and that models that handle queries for a particular entity well "perform 25–40% worse on more complex queries", such as relationship queries or natural language questions.
Types: what kind of entity is wanted
The query Professional sports teams in Philadelphia asks for entities of one type. If the target type is known, from the user or from a classifier, results can be filtered or re-ranked by how well each entity's types match it (Balog, 2018, §4.3). The usual form is a linear mixture of the term-based score and a type-based score,
$$\mathrm{score}(e; \tilde{q}) = \lambda\, \mathrm{score}_t(e; q) + (1 - \lambda)\, \mathrm{score}_T(e; T_q) ,$$
where $T_q$ is the set of target types and $\lambda$ is chosen empirically. Balog describes four ways to compute $\mathrm{score}_T$:
- Term-based: put the labels of an entity's types in a field and match the type labels against it.
- Set-based: the share of target types that the entity has, $\lvert T_e \cap T_q \rvert / \lvert T_q \rvert$, possibly after expanding both sets with ancestors and descendants in the taxonomy.
- Distance in the taxonomy: $e^{-\alpha\, d(T_q, T_e)}$, where $d$ is zero if the sets share a type and otherwise the shortest path between a target type and an entity type, capped at a maximum ($\alpha = 3$ and a cap of 5 in the setting Balog reports).
- Probability distributions: type models smoothed like language models, compared by Kullback-Leibler divergence.
Type systems are imperfect: types are missing or wrong, and taxonomies are uneven in depth. DBpedia's 2015-10 ontology has 739 classes, by the release's announcement and by Hasibi et al. (2017, §2.1); Balog's (2018, Table 4.3) overview of the same release counts 713 types in a hierarchy 7 levels deep, with 2.8 types per entity on average. Wikipedia's categories number over 1.3 million and do not form a proper is-a hierarchy. Balog's conclusion is that in most applications with more than a handful of types, "target type information should be treated as 'hints' rather than as strict filters." Identifying the target types of a query automatically is its own task, for which Balog and Neumayer (2012) is a standard reference.
Entity retrieval from a knowledge graph
An entity description folds the graph into text. Some methods use the graph directly. Tonon, Demartini and Cudré-Mauroux (2012), as Balog (2018, §4.4.1) describes them, first retrieve a few seed entities with a term-based model and then follow the graph's edges from those seeds to find more candidates. The best of their variants followed same-as links, redirects and disambiguation links from the top 3 seeds, and scored each candidate by an even mixture ($\lambda = 0.5$) of its own term-based score and the scores of the seeds that led to it.
A second approach keeps entity identifiers on both sides of the match. Hasibi, Balog and Bratsberg (2016) link the entities mentioned in the query (by the methods of Entity Linking) and represent each candidate by its related entities as well as its terms. Their ELR model adds to the SDM ranking function a fourth sum, $\lambda_E \sum_i f_E(e_i; e)$, over the query's linked entities $e_i$ (Balog, 2018, §4.2.2). In Hasibi et al.'s (2017) Table 2, adding ELR to SDM moved nDCG@10 from 0.4185 to 0.4200.
A third needs no entity descriptions at all. Rank documents for the query, and give each entity the sum of the scores of the retrieved documents that mention it, weighted by how strongly it is associated with each:
$$\mathrm{score}(e; q) = \sum_{d \in D_q} \mathrm{score}(d; q)\, w(e, d)$$
(Balog, 2018, §3.4). This document-based ranking can be built on any search engine whose documents have been annotated with entities.
Ranking entities by their position in the graph, independent of the query, is the subject of PageRank; Balog (2018, §4.6) treats it as a query-independent prior for entities. Knowledge Graph Embeddings covers the learned alternative, in which each entity and relation becomes a vector.
Entities in the service of document retrieval
Entities also help retrieve documents. Balog (2018, ch. 8) groups the methods into three families, in the order they appeared.
- Expansion. The query's entities supply expansion terms. Meij et al. (2010) formulate it as two translations, from the query to entities and from entities to terms: $P(t \mid \hat{\theta}_q) \propto \sum_{e \in E_q} P(t \mid e, q)\, P(e \mid q)$ (Balog, 2018, eq. 8.5), so that the expanded query model mixes the vocabularies of the query's entities, each weighted by how strongly it is related to the query. This is query expansion with a knowledge base as the external resource. Dalton, Dietz and Allan (2014) combined entity annotations of documents with expansion by entities' names, types and categories.
- Projection. The latent entity space model of Liu and Fang (2015) scores a document by passing through entities, $\alpha \sum_{e} P(q \mid e)\, P(e \mid d) + (1 - \alpha)\, P(q \mid d)$, mixed with the ordinary query likelihood (Balog, 2018, eq. 8.7), with $\alpha$ between 0.5 and 0.7 suggested in the absence of training data (Liu and Fang, 2015, §5.5). $P(e \mid d)$ projects the document onto an entity, from the cross-entropy of their language models, and $P(q \mid e)$ projects the query, best estimated, Liu and Fang found, from the similarity of $e$ to the query's own entities (their §5.4.2).
- Entity-based representations. Documents and queries are represented as bags of entities alongside their bags of words, and the two are matched together. Balog (2018, §8.7) reports that this family, at the time of writing, beat a language-modeling baseline by over 80% and a learning-to-rank baseline by over 20% in nDCG@20 on ClueWeb09-B.
All three are run as re-rankers of a first-stage result list, usually its top 100 (Balog, 2018, §8.5), which is the cascade of multi-stage ranking. The test collections are TREC's web and Robust tracks; of the 200 TREC 2009-2012 Web track queries, 94 contain an explicitly mentioned entity, and the manual annotations of Dalton et al. raise that to 191 (Balog, 2018, §8.6).
Entity cards
When a query names an entity, many search engines show an entity card: a panel with images, the entity's name and type, a short description, a few facts and related entities (Balog, 2018, §9.2.1). Balog calls cards the counterpart of document snippets for entities, and reports studies in which cards attracted users' attention, and relevant cards let users issue significantly fewer queries and finish tasks faster. The main retrieval problem inside a card is choosing which of an entity's hundreds of facts to show. Hasibi, Balog and Bratsberg (2017) rank facts by their utility, an even mixture of a fact's general importance and its relevance to the query, $\mathrm{utility}(f, q) = \alpha\, \mathrm{importance}(f) + (1 - \alpha)\, \mathrm{relevance}(f, q)$ with $\alpha = 1/2$ (Balog, 2018, eq. 9.3), learned from crowdsourced labels with features such as how many triples in the knowledge base share a fact's object value. A card is therefore query-biased in the same sense as a query-biased summary of a document.
An experiment: BM25 and BM25F over 4.6 million entities
Hasibi et al.'s five-field index cannot be rebuilt here: it needs the full DBpedia 2015-10 dump and their preprocessing. What can be run is the two-field version that the BEIR benchmark distributes (Thakur et al., 2021). Each entity has its title and its DBpedia abstract, the 467 queries are those of DBpedia-Entity v2, and the judgments are the same three-grade judgments, divided by BEIR into 67 development queries drawn at random and 400 test queries (Thakur et al., 2021, appendix D.7). The question is how far ranking the two fields separately, with BM25F, improves on running them together, and how close two fields come to the published five-field results.
Setup
The data are fixed: the BEIR corpus file at a pinned revision of its Hugging Face repository, 4,635,922 entities, checked by SHA-256 on every run, with the test judgments from the companion repository. Text is analyzed almost as this site's search engine analyzes it: lowercase alphanumeric tokens, accents removed, the site's stop list of 33 words, and the Porter stemmer, but without the site's stripping of possessives and its naming of Greek letters. After analysis an entity's title averages 2.754 terms and its abstract 33.161. The 400 test queries have 43,515 judgments: 28,229 at grade 0, 8,785 at grade 1 and 6,501 at grade 2.
Every ranker scores all 4.6 million entities exhaustively, with the IDF of the site's engine, $\ln\!\left(1 + \frac{N - \mathit{df} + 0.5}{\mathit{df} + 0.5}\right)$, over entities. Four rankers are compared.
- BM25, BEIR's parameters: title and abstract run together, $k_1 = 0.9$, $b = 0.4$, the Anserini defaults that BEIR used (Thakur et al., 2021, §4, call them "the default Lucene parameters"; Lucene's own BM25 defaults are $k_1 = 1.2$, $b = 0.75$).
- BM25, tuned: the same, with $k_1$ and $b$ chosen by coordinate ascent on nDCG@10 over the 67 development queries. The search settled on $k_1 = 0.6$, $b = 0.4$.
- BM25F, tuned: two fields, the abstract's weight fixed at 1, the title's weight, $b_{\text{title}}$, $b_{\text{abstract}}$ and $k_1$ tuned the same way. The search settled on a title weight of 12, $b_{\text{title}} = 0.9$, $b_{\text{abstract}} = 0$ and $k_1 = 0.9$.
- Title only: BM25 on the title field alone, with the tuned BM25 parameters, to show what the name carries by itself.
nDCG@10 uses the grade as the gain and the logarithmic discount, counts unjudged entities as grade 0, and takes the ideal from all the judged grades of the query, which is what trec_eval computes and what BEIR and Hasibi et al. report. Differences are tested with the paired two-sided randomization test of Comparing Systems with Significance Tests: 20,000 random sign flips of the 400 per-query differences, $p = (b + 1)/20{,}001$, and the median $p$ over 30 seeds (0 to 29).
Results
| Ranker | All 400 | SemSearch ES (86) | INEX-LD (84) | ListSearch (105) | QALD-2 (125) |
|---|---|---|---|---|---|
| BM25, BEIR's parameters | 0.324 | 0.551 | 0.317 | 0.283 | 0.207 |
| BM25, tuned | 0.324 | 0.550 | 0.316 | 0.290 | 0.202 |
| BM25F, tuned | 0.343 | 0.620 | 0.342 | 0.270 | 0.213 |
| Title only | 0.275 | 0.574 | 0.242 | 0.199 | 0.155 |
The numbers in parentheses are the test queries of each category.
BM25F is ahead of BM25. Over the 400 test queries the mean difference in nDCG@10, BM25F minus tuned BM25, is 0.0188, with a standard deviation of 0.1207 per query, $t = 3.12$ and a randomization $p$ of 0.002. BM25F is better on 171 queries, worse on 136 and tied on 93. Tuning BM25 itself changed nothing measurable: against BEIR's parameters the mean difference is $-0.0005$ ($p = 0.83$).
The clear gain is on queries that name things. The same paired randomization test, run within each category, gives this:
| Category | Queries | BM25F minus BM25 | $t$ | $p$ |
|---|---|---|---|---|
| SemSearch ES | 86 | +0.0705 | 4.93 | < 0.001 |
| INEX-LD | 84 | +0.0264 | 2.27 | 0.025 |
| ListSearch | 105 | −0.0203 | −1.79 | 0.077 |
| QALD-2 | 125 | +0.0110 | 1.09 | 0.28 |
On the named-entity queries of SemSearch ES, BM25F scores 0.620 against 0.550, and the difference is far beyond chance; it accounts for 0.015 of the overall difference of 0.019. On the INEX-LD keyword queries the gain, 0.342 against 0.316, is marginal at the 5% level. On list queries BM25F is lower, 0.270 against 0.290, though not significantly ($p = 0.077$), and on questions the small gain, 0.213 against 0.202, could be chance. Four tests on subsets of one comparison also invite the multiple-comparison caution of the course's article; only the SemSearch result would survive it. A title weight of 12 makes a match in the name count like a dozen matches in the abstract. That plausibly helps when the query is a name and can hurt when the query's words describe a class of entities, whose members' names do not contain them; the list-query result points that way without establishing it. The title alone carries a great deal for named-entity queries, 0.574, more than BM25 over both fields, and little for the others.
The opening query, explained. For brooklyn bridge, BM25 over both fields ranks Brooklyn Bridge Park, The Second Brooklyn Bridge and the album Brooklyn Bridge above the bridge, which is fourth; its nDCG@10 for the query is 0.708. BM25F ranks the bridge first and the Gleizes painting third, for 0.825. Two settings work together: the title's weight of 12, and the title field's own length normalization. With $b_{\text{title}} = 0.9$ and a mean title of 2.754 terms, a two-term title gets a normalizer of $1 - 0.9 + 0.9 \times 2/2.754 = 0.754$ and a three-term title 1.080, so the same title match adds 43% more to the pseudo frequency in Brooklyn Bridge than in Brooklyn Bridge Park. With $b_{\text{title}} = 0$ the two titles' matches would count the same. After the saturation, with pseudo frequencies near 18, the difference in score is much smaller than 43%, but it is enough to reorder near-identical names. Worked problem 1 traces the bridge's score term by term.
Beside the published numbers. BEIR's BM25 on the same corpus and test queries is 0.313 (Thakur et al., 2021, Table 2), and our BM25 with the same parameters is 0.324. The two are not the same implementation: BEIR's indexed title and passage as separate Lucene fields in Anserini, with Lucene's analysis, and ours runs them together with the site's analyzer. Hasibi et al.'s numbers are on a different footing again: five fields from the full knowledge base, a different index and analyzer, all 467 queries in place of BEIR's 400, and parameters trained separately for each query category by cross-validation (their §3.2), where ours were tuned once on 67 mixed queries. The comparison is therefore only of orders of magnitude, not a finding. With that caveat, the pattern is suggestive. On named-entity queries our two-field BM25F (0.620) is in the neighborhood of their five-field one (0.6281). On list queries and questions it is far below (0.270 against 0.4252, and 0.213 against 0.3689). A likely reason, which this experiment does not test, is that the answers to list queries and questions are described in the categories and related entities that the BEIR copy leaves out. The pattern matches Balog's summary: queries for a particular entity are handled well, and complex queries much less so.
What the experiment can and cannot show
- Small tuning set. The parameters were tuned on 67 queries, and a title weight of 12 with $b_{\text{abstract}} = 0$ is a choice the development queries made. On the test queries the tuned BM25 was no better than BEIR's defaults, which suggests the dev set is too small to tune BM25's two parameters usefully; BM25F's advantage held on the test queries, which were not used in tuning.
- Two fields. The experiment says nothing about FSDM, PRMS or types, which need the fields the BEIR copy lacks.
- One query set, pooled judgments. The judgments were pooled from the runs of the systems Hasibi et al. describe (their §2.3.1: 37 earlier runs and 13 new ones, to depth 20), and none of our rankers contributed to the pool. An unjudged entity counts as irrelevant, which can understate any system that retrieves entities the pooled systems did not; Relevance Judgments describes the bias.
This site's search as entity search
This site's own search box is an entity search in all but name. Its pages are entities with identifiers (their slugs), and each is indexed as a fielded description, as How This Search Works describes: a title with weight 12, the summary followed by the tags with weight 1, the section headings with weight 4, the body with weight 1, and the names of the Greek letters in the page's mathematics with weight 0.1, ranked by BM25F. The correspondence with the fields of an entity description is close:
- the title is the name field;
- the summary is the short description, the role DBpedia's abstract plays;
- the tags are soft type labels, deliberately not a hierarchy;
- the
[[links]]between pages are relations, which the ranker does not use, though they are the data of the unit's knowledge graph and of the entity linking experiment.
A title weight of 12 is what the DBpedia tuning also chose, from a different grid and for a different collection, and its purpose is the one the site's own title test checks: a query that names a page should put that page first. The site's tests require exactly that, for every article: each must be the top result for its own title, which is a named-entity query in SemSearch's sense. The full results page now fuses BM25F with a dense ranking (Hybrid Retrieval), while the instant results remain BM25F. Bibliography entries are served as pages of their own but kept out of the search index, so works and authors are entities the site describes and does not rank. This section reports no measurement of the site's search; its evaluation is the subject of the pages it links.
What is proved here, what is cited, and what the experiment shows
Derived on the page. The reductions of FSDM to the mixture of language models (with $\lambda = (1, 0, 0)$) and to SDM (with one field). PRMS's mapping probability from Bayes' rule. The arithmetic of the experiment's example and of the worked problems.
Cited. The task and the entity-description methods (Balog, 2018, chs. 3, 4, 8 and 9). The query classes (Pound et al., 2010, as Zhiltsov et al. report them). BM25F (Robertson and Zaragoza, 2009), MLM (Ogilvie and Callan, 2003), PRMS (Kim et al., 2009), FSDM (Zhiltsov et al., 2015), ELR (Hasibi et al., 2016) and the type, graph and document-retrieval methods, from Balog's account; the papers on MLM, ELR and the latent entity space were also read. The test collection and its baselines (Hasibi et al., 2017, and its repository); BEIR's version and BM25 result (Thakur et al., 2021).
Shown by the experiment. On BEIR's two-field DBpedia-Entity v2, over all 4.6 million entities and the 400 test queries: BM25F with a title weight of 12, tuned on 67 development queries, beats BM25 by 0.019 in nDCG@10 (0.343 against 0.324, $p = 0.002$). Within categories, the gain is clear on named-entity queries ($p < 0.001$) and marginal on keyword queries ($p = 0.025$); the lower score on list queries ($p = 0.077$) and the gain on questions ($p = 0.28$) are not significant. These are observations of one collection, one analyzer and one tuning set. The comparison with the published five-field baselines is not part of what the experiment shows, since those were measured on a different query set with different training.
Worked problems
These problems are posed on the DBpedia-Entity v2 experiment and on the models of the article; the unit has no course assignments. The script recomputes every number.
Problem 1 (a BM25F entity score by hand). The entity Brooklyn Bridge has a title of 2 analyzed terms and an abstract of 40. The query's two stems are brooklyn, which occurs once in the title and twice in the abstract, and bridg, once in the title and 4 times in the abstract. Their IDFs are 6.2791 and 5.3714. With the tuned parameters (title weight 12, $b_{\text{title}} = 0.9$, $b_{\text{abstract}} = 0$, $k_1 = 0.9$) and mean title length 2.754, compute the entity's BM25F score.
Solution. The title normalizer is $1 - 0.9 + 0.9 \times 2 / 2.754 = 0.7535$, and with $b_{\text{abstract}} = 0$ the abstract's normalizer is 1 whatever its length. The pseudo frequencies are
$$\tilde{c}(\textit{brooklyn}) = 12 \times \frac{1}{0.7535} + 2 = 17.925, \qquad \tilde{c}(\textit{bridg}) = 12 \times \frac{1}{0.7535} + 4 = 19.925 ,$$
computed from the unrounded mean title length (from the rounded 0.7535 they come to 17.926 and 19.926, which changes nothing below at the precision shown).
Each term contributes $\mathrm{IEF} \times \frac{(k_1 + 1)\,\tilde{c}}{k_1 + \tilde{c}}$: for brooklyn, $6.2791 \times \frac{1.9 \times 17.925}{18.825} = 11.360$, and for bridg, $5.3714 \times \frac{1.9 \times 19.925}{20.825} = 9.765$. The score is 21.125. Each term is close to its ceiling of $1.9 \times \mathrm{IEF}$ (11.930 and 10.206): one title occurrence, worth about 16 abstract occurrences here, nearly saturates the term on its own, as the BM25F article found for this site's title weight.
Problem 2 (PRMS field mapping). Over the whole catalog the title field holds 12,768,550 analyzed terms and the abstract field 153,733,381. Brooklyn occurs 736 times in titles and 10,181 times in abstracts; bridg 7,747 and 42,576 times. With a uniform prior over the two fields, compute $P(\text{title} \mid t)$ for each.
Solution. For brooklyn, $P(t \mid \text{title}) = 736 / 12{,}768{,}550 = 5.764 \times 10^{-5}$ and $P(t \mid \text{abstract}) = 10{,}181 / 153{,}733{,}381 = 6.623 \times 10^{-5}$. With equal priors the priors cancel, and $P(\text{title} \mid t) = 5.764 / (5.764 + 6.623) = 0.465$. For bridg, $P(t \mid \text{title}) = 7{,}747 / 12{,}768{,}550 = 6.067 \times 10^{-4}$ and $P(t \mid \text{abstract}) = 42{,}576 / 153{,}733{,}381 = 2.769 \times 10^{-4}$, so $P(\text{title} \mid t) = 6.067 / (6.067 + 2.769) = 0.687$. A bridge is named in titles relatively more often than Brooklyn is: PRMS would weight the title field 0.687 for bridg and only 0.465 for brooklyn, the opposite of what a fixed title weight does for this query, where the bridge's name is the whole point.
Problem 3 (the two reductions of FSDM). Show that FSDM with $\lambda = (1, 0, 0)$ ranks as MLM with field weights $w^T_j$, and that FSDM with one field ranks as SDM.
Solution. With $\lambda = (1, 0, 0)$ the ranking function is $\sum_{i=1}^{n} \log \sum_j w^T_j P(q_i \mid \theta^j_D)$. The inner sum is MLM's mixture probability $P(q_i \mid \theta_D)$ with $\alpha_j = w^T_j$, and a sum of logarithms is the logarithm of the product, so the score is $\log \prod_i P(q_i \mid \theta_D)$, the log query likelihood under MLM. Since the logarithm is strictly increasing, the two rank every pair of documents the same way. With $F = 1$, the constraint that each weight vector sums to 1 gives $w^T_1 = w^O_1 = w^U_1 = 1$. Each feature is then $\log$ of one Dirichlet-smoothed probability over the single field, the whole document: for unigrams $\log \frac{\mathit{tf}_{q_i, D} + \mu\, \mathit{cf}_{q_i}/\lvert C \rvert}{\lvert D \rvert + \mu}$, and the same with phrase and window counts for the bigram features. These are SDM's three features, and the ranking function has SDM's form with the same $\lambda$, so the rankings coincide.
Problem 4 (nDCG@10 for one query). For brooklyn bridge, the grades of BM25F's top ten are $2, 1, 2, 1, 1, 1, 0, 0, 0, 1$, and the query's ten best judged grades are $2, 2, 1, 1, 1, 1, 1, 1, 1, 1$ (it has 2 entities at grade 2 and 12 at grade 1). Compute nDCG@10.
Solution. DCG@10 is $\sum_{r=1}^{10} g_r / \log_2(r + 1)$:
$$\frac{2}{1} + \frac{1}{1.585} + \frac{2}{2} + \frac{1}{2.322} + \frac{1}{2.585} + \frac{1}{2.807} + \frac{1}{3.459} = 2 + 0.631 + 1 + 0.431 + 0.387 + 0.356 + 0.289 = 5.094 .$$
The ideal list gives $\frac{2}{1} + \frac{2}{1.585} + \sum_{r=3}^{10} \frac{1}{\log_2(r+1)} = 2 + 1.262 + 2.913 = 6.174$ (the terms are rounded; the total is summed before rounding). So nDCG@10 is $5.094 / 6.174 = 0.825$, the value in the article. BM25's list for the same query, with the bridge fourth, scores 0.708.
Problem 5 (the paired t statistic). Over the 400 test queries, the per-query differences in nDCG@10, BM25F minus tuned BM25, have mean 0.0188 and standard deviation 0.1207. Compute the standard error and $t$, and say what the test assumes that the randomization test does not.
Solution. The standard error is $0.1207 / \sqrt{400} = 0.1207 / 20 = 0.00604$, and $t = 0.0188 / 0.00604 = 3.11$ on 399 degrees of freedom; from the unrounded mean and standard deviation it is 3.12, the value in the article. The t-test treats the mean of the 400 differences as approximately normal, which with 400 queries the central limit theorem supports; the randomization test assumes only that, if the two rankers were interchangeable, each difference would be as likely to have either sign. Both put the difference well beyond chance here ($p$ of 0.002 from the randomization test). The standard deviation is more than six times the mean: BM25F is better on 171 queries and worse on 136, so the gain is a shift of the balance over many queries, not an improvement on each.
What we have learned
An entity can be searched like a document once its knowledge-base neighborhood is folded into a few fields, and the fielded models of document retrieval then apply: BM25F and the mixture of language models with fixed field weights, PRMS with weights that follow each term, and FSDM, which adds the proximity of SDM and contains both MLM and SDM as special cases. Types and graph links add evidence that no description holds, and entities in turn sharpen document retrieval and give the result page its cards. On DBpedia-Entity v2 with two fields, BM25F's heavy title weight helped clearly where the query names its answer and not detectably where it describes a class, and the published five-field results, though measured on a different footing, suggest that much of the remaining gap lies in the categories and relationships that only a knowledge base supplies.
Entity descriptions fold a knowledge graph into text. The unit's next article, Knowledge Graph Embeddings, keeps the graph and represents each entity and relation as a vector learned from its triples. Both keep knowledge outside the language model; Generative Retrieval then asks what happens when the index itself is stored in a model's parameters.
References
- Balog, K. (2018). Entity-Oriented Search. The Information Retrieval Series 39. Springer, Cham. Open access. doi:10.1007/978-3-319-93935-3. record · 2 pages
- Balog, K., and Neumayer, R. (2012). Hierarchical target type identification for entity-oriented queries. In Proceedings of CIKM 2012, 2391–2394. doi:10.1145/2396761.2398648. record
- Dalton, J., Dietz, L., and Allan, J. (2014). Entity query feature expansion using knowledge base links. In Proceedings of SIGIR 2014, 365–374. doi:10.1145/2600428.2609628. record
- Hasibi, F., Balog, K., and Bratsberg, S. E. (2016). Exploiting entity linking in queries for entity retrieval. In Proceedings of ICTIR 2016, 209–218. doi:10.1145/2970398.2970406. record
- Hasibi, F., Balog, K., and Bratsberg, S. E. (2017). Dynamic factual summaries for entity cards. In Proceedings of SIGIR 2017, 773–782. doi:10.1145/3077136.3080810. record
- Hasibi, F., Nikolaev, F., Xiong, C., Balog, K., Bratsberg, S. E., Kotov, A., and Callan, J. (2017). DBpedia-Entity v2: A test collection for entity search. In Proceedings of SIGIR 2017, 1265–1268. doi:10.1145/3077136.3080751. Collection, runs and results table: https://github.com/iai-group/DBpedia-Entity (accessed 22 November 2026). record
- Kim, J., Xue, X., and Croft, W. B. (2009). A probabilistic retrieval model for semistructured data. In Advances in Information Retrieval (ECIR 2009), 228–239. doi:10.1007/978-3-642-00958-7_22. record
- Liu, X., and Fang, H. (2015). Latent entity space: A novel retrieval approach for entity-bearing queries. Information Retrieval Journal, 18(6), 473–503. doi:10.1007/s10791-015-9267-x. record
- Meij, E., Trieschnigg, D., de Rijke, M., and Kraaij, W. (2010). Conceptual language models for domain-specific retrieval. Information Processing & Management, 46(4), 448–469. doi:10.1016/j.ipm.2009.09.005. record
- Metzler, D., and Croft, W. B. (2005). A Markov random field model for term dependencies. In Proceedings of SIGIR 2005, 472–479. record · 3 pages
- Neumayer, R., Balog, K., and Nørvåg, K. (2012). When simple is (more than) good enough: Effective semantic search with (almost) no semantics. In Advances in Information Retrieval (ECIR 2012), 540–543. doi:10.1007/978-3-642-28997-2_59. record
- Ogilvie, P., and Callan, J. (2003). Combining document representations for known-item search. In Proceedings of SIGIR 2003, 143–150. doi:10.1145/860435.860463. record
- Pound, J., Mika, P., and Zaragoza, H. (2010). Ad-hoc object retrieval in the web of data. In Proceedings of WWW 2010, 771–780. doi:10.1145/1772690.1772769. record
- Robertson, S., and Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389. record · 8 pages
- Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., and Gurevych, I. (2021). BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track. arXiv:2104.08663. record · 8 pages
- Tonon, A., Demartini, G., and Cudré-Mauroux, P. (2012). Combining inverted indices and structured search for ad-hoc object retrieval. In Proceedings of SIGIR 2012, 125–134. doi:10.1145/2348283.2348304. record
- Zhiltsov, N., Kotov, A., and Nikolaev, F. (2015). Fielded sequential dependence model for ad-hoc entity retrieval in the web of data. In Proceedings of SIGIR 2015, 253–262. doi:10.1145/2766462.2767756. record