Variants of TF-IDF weighting scored the four documents of this topic's running example under eight schemes, and judged each by whether the car-insurance headline $d_1$ and the auto-insurance page $d_3$ came out on top. Every component was chosen the same way on real collections: try it, measure it, keep what works. That leaves the weights without a reason. Is there anything a scoring function must do whatever the collection, which could be checked on paper before a single query is run?
There is. Fang, Tao, and Zhai (2004) wrote down six such requirements as formal constraints: precise statements of the form "if two documents differ in exactly this way, then this one must not score lower". Each captures one of the three heuristics behind the schemes of this topic: term frequency, term discrimination and length normalization. The approach is called axiomatic analysis. A scoring function can be tested against a constraint by algebra alone, and a failed constraint points at the part of the formula that misbehaves.
Here is the route. First we fix the notation and the five scoring functions of this topic that will be tested. Then we state the constraints, each with a small case built from the running example's headline. Next we report what the published analyses found for three well-known formulas. Finally we check this topic's own schemes against every constraint, with proofs and counterexamples, and solve four problems. The article assumes TF-IDF weighting, cosine similarity and the variants. The statements of the constraints and the results about pivoted normalization, Okapi and the Dirichlet prior are the papers'. The analysis of this topic's schemes is this article's own, and every claim in it is tested by a script.
The setting
A document $d$ is a bag of terms, with $c(t, d)$ the number of times term $t$ occurs in it. Its length $\lvert d \rvert$ is the total number of term occurrences, $\sum_t c(t, d)$. That is the length in tokens, not the length of a weight vector. A query $q$ is a set of terms, and $f(d, q)$ is the score a retrieval function gives $d$ for $q$. Each term has a discrimination value $\mathit{idf}(t)$, which may be any IDF-like measure.
A constraint compares two or three hypothetical documents for the same query in the same collection. The collection's statistics are therefore fixed, and only the counts in the documents vary. The examples below use the running example's vocabulary and its IDF values: 0.125 for best and car, 0.301 for insurance, auto and rate, and 0.602 for loan. Most start from the headline $d_1$, which is car insurance rate, one occurrence each.
Five scoring functions from this topic are tested. In each, a query term occurring once contributes its IDF once, on the query side or on the document side. Where the earlier articles normalized the query, that normalization divides every document's score by the same number and is left out here, so the cosine scores below are those of the earlier articles multiplied by the query's length.
| Name | SMART scheme | Score of $d$ for $q$ |
|---|---|---|
| raw sum | ntn.bnn | $\sum_{t \in q} c(t, d)\,\mathit{idf}(t)$ |
| log sum | ltn.bnn | $\sum_{t \in q} \big(1 + \log_{10} c(t, d)\big)\,\mathit{idf}(t)$ |
| ntc cosine | ntc.ntc | $\sum_{t \in q} \mathit{idf}(t)\, c(t, d)\,\mathit{idf}(t) \,/\, \lvert \vec{V}(d) \rvert$, with $\vec{V}(d)$ the vector of $c(t, d)\,\mathit{idf}(t)$ |
| lnc cosine | lnc.ltc | $\sum_{t \in q} \mathit{idf}(t)\,\big(1 + \log_{10} c(t, d)\big) \,/\, \lvert \vec{V}(d) \rvert$, with $\vec{V}(d)$ the vector of $1 + \log_{10} c(t, d)$ |
| pivoted lnc | pivoted cosine | the lnc numerator divided by $(1 - s)\,p + s\,\lvert \vec{V}(d) \rvert$ |
A term that does not occur contributes 0 to every sum. For the pivoted function the pivot is $p = 2.310$, the mean lnc length of the running example's four documents, and the slope is $s = 0.75$ unless stated. A term that occurs in every document has IDF 0 and adds nothing to any of these scores or to an ntc vector's length, so the analysis assumes that every term has a positive IDF.
Term frequency constraints
The first heuristic is that more occurrences of a query term should mean a higher score, with diminishing returns. Fang, Tao, and Zhai (2004, §2.1) state it as two constraints.
TFC1. Let $q = \{w\}$ be a query with one term. Assume $\lvert d_1 \rvert = \lvert d_2 \rvert$. If $c(w, d_1) > c(w, d_2)$, then $f(d_1, q) > f(d_2, q)$.
TFC2. Let $q = \{w\}$ be a query with one term. Assume $\lvert d_1 \rvert = \lvert d_2 \rvert = \lvert d_3 \rvert$ and $c(w, d_1) > 0$. If $c(w, d_2) - c(w, d_1) = 1$ and $c(w, d_3) - c(w, d_2) = 1$, then $f(d_2, q) - f(d_1, q) > f(d_3, q) - f(d_2, q)$.
In plain words, TFC1 says that of two documents equally long, the one that uses the query term more scores higher. TFC2 says that each further occurrence adds less than the one before: the step from 1 to 2 should count for more than the step from 100 to 101. The documents are held to equal length so that only the count of $w$ is being judged.
The paper then states a further property, which it says follows from TFC2 without printing the derivation. The later journal version (Fang, Tao, and Zhai, 2011, §2.1) makes it a constraint in its own right:
TFC3. Let $q$ be a query and $w_1, w_2 \in q$ two query terms. Assume $\lvert d_1 \rvert = \lvert d_2 \rvert$ and $\mathit{idf}(w_1) = \mathit{idf}(w_2)$. If $c(w_1, d_1) = c(w_1, d_2) + c(w_2, d_2)$ and $c(w_2, d_1) = 0$, $c(w_1, d_2) \ne 0$, $c(w_2, d_2) \ne 0$, then $f(d_1, q) < f(d_2, q)$.
That is: with the same number of query-term occurrences in all, a document that covers two query terms should beat one that repeats a single term.
Example (four tokens). For the query insurance, take three documents of four tokens each: insurance twice and rate twice, then insurance three times and rate once, then insurance four times. TFC1 asks for the scores to rise along the row, and TFC2 for the second rise to be smaller than the first.
| Function | 2 of 4 | 3 of 4 | 4 of 4 | First rise | Second rise |
|---|---|---|---|---|---|
| raw sum | 0.602 | 0.903 | 1.204 | 0.301 | 0.301 |
| log sum | 0.392 | 0.445 | 0.482 | 0.053 | 0.038 |
| lnc cosine | 0.213 | 0.249 | 0.301 | 0.036 | 0.052 |
| pivoted lnc | 0.200 | 0.232 | 0.271 | 0.032 | 0.039 |
All four satisfy TFC1 on this case. Only the log sum satisfies TFC2. The raw sum's rises are equal, and under either normalization the second rise is the larger one. The last section explains why.
The term discrimination constraint
The second heuristic is that a match on a rarer term should count for more. The 2004 paper (§2.2) states it as follows.
TDC (2004). Let $q$ be a query and $w_1, w_2 \in q$ two query terms. Assume $\lvert d_1 \rvert = \lvert d_2 \rvert$ and $c(w_1, d_1) + c(w_2, d_1) = c(w_1, d_2) + c(w_2, d_2)$. If $\mathit{idf}(w_1) \ge \mathit{idf}(w_2)$ and $c(w_1, d_1) \ge c(w_1, d_2)$, then $f(d_1, q) \ge f(d_2, q)$.
In plain words: with a fixed number of query-term occurrences to distribute, the document that puts more of them on the more discriminating term should not score lower.
The authors later judged this version too strong. In the 2011 article (§2.2) they give its consequence for the query "SVM tutorial": a document with 99 occurrences of SVM and one of tutorial would have to outscore a document with 50 of each, which they call counterintuitive. They replace it by a weaker constraint:
TDC (2011). Let $D$ be a document and $q = \{w_1, w_2\}$ a query. Let $D_1$ and $D_2$ be two documents of equal length, where $D_1$ contains only $w_1$ and $D_2$ contains only $w_2$. If $\mathit{idf}(w_1) > \mathit{idf}(w_2)$, then $f(D \cup D_1, q) > f(D \cup D_2, q)$.
Here $D \cup D_1$ is $D$ with the occurrences of $D_1$ appended. The 2011 article derives from this and TFC2 a form with one occurrence added: if $w_1$ and $w_2$ both occur in $D$, $\mathit{idf}(w_1) > \mathit{idf}(w_2)$ and $c(w_1, D) \le c(w_2, D)$, then adding one $w_1$ to $D$ must score higher than adding one $w_2$.
Example (TFC3 and the 2004 TDC cannot both hold). For the query best car, whose two terms have the same IDF, compare $d_1$ = car four times and rate once with $d_2$ = car twice, best twice and rate once. The pair meets the hypotheses of TFC3 with $w_1$ = car, which demands $f(d_1) < f(d_2)$. It also meets the hypotheses of the 2004 TDC, since the IDFs are equal and $c(\textit{car}, d_1) = 4 \ge 2 = c(\textit{car}, d_2)$, which demands $f(d_1) \ge f(d_2)$. No function can do both. This reading of the two printed statements is this article's, not the papers'. With equal IDFs the printed TDC applies in both directions: exchanging the roles of car and best, and of the two documents, it also demands $f(d_2) \ge f(d_1)$. So with equal IDFs it requires every redistribution of the query-term occurrences to tie, which is what the raw sum does and what TFC3 forbids. The conflict lies entirely in the case $\mathit{idf}(w_1) = \mathit{idf}(w_2)$. With a strict inequality between the IDFs the two constraints never apply to the same pair, and that is evidently the case the TDC was written for. The 2011 article replaced the constraint for a different reason, the "SVM tutorial" example.
Length constraints
The third heuristic is that a long document should not win merely by being long, nor lose merely by being long. The 2004 paper (§§2.3 and 2.4) gives three constraints.
LNC1. Let $q$ be a query and $d_1$, $d_2$ two documents. If for some word $w' \notin q$, $c(w', d_2) = c(w', d_1) + 1$, but for any query term $w$, $c(w, d_2) = c(w, d_1)$, then $f(d_1, q) \ge f(d_2, q)$.
LNC2. Let $q$ be a query. For every $k > 1$, if $d_1$ and $d_2$ are two documents such that $\lvert d_1 \rvert = k \cdot \lvert d_2 \rvert$ and for all terms $w$, $c(w, d_1) = k \cdot c(w, d_2)$, then $f(d_1, q) \ge f(d_2, q)$.
TF-LNC. Let $q = \{w\}$ be a query with one term. If $c(w, d_1) > c(w, d_2)$ and $\lvert d_1 \rvert = \lvert d_2 \rvert + c(w, d_1) - c(w, d_2)$, then $f(d_1, q) > f(d_2, q)$.
In plain words, LNC1 says that adding a word the query does not contain must not raise the score. LNC2 says that a document placed end to end with $k$ copies of itself must not score lower than the original, so the penalty for length must not outrun the gain from the larger counts. TF-LNC says that adding occurrences of the query term, and nothing else, must raise the score even though the document has grown. The 2011 article (§2.3) restates LNC1 with every other count held equal and restricts LNC2 to documents that contain a query term.
The opening of cosine similarity used LNC2's doubled document as its motivation, before the constraint had a name. From TF-LNC and LNC1 the paper derives one more statement: for a one-term query, if $c(w, d_3) > c(w, d_2)$ and $\lvert d_3 \rvert < \lvert d_2 \rvert + c(w, d_3) - c(w, d_2)$, then $f(d_3, q) > f(d_2, q)$. The argument is short. Let $d_1$ be $d_3$ with enough occurrences of non-query words added to reach the length $\lvert d_2 \rvert + c(w, d_3) - c(w, d_2)$. By LNC1, applied once for each added word, $f(d_3, q) \ge f(d_1, q)$, and by TF-LNC $f(d_1, q) > f(d_2, q)$.
Fang and Zhai (2005, §2.2) later recast four of the six in terms of adding one term to a document. Their Constraint 1 says that adding a query term must raise the score, which covers TFC1 and TF-LNC. Constraint 2 says that adding a non-query term must lower it, a strict form of LNC1. Constraint 3 says that the gain from adding a query term must shrink as more are added, a relative of TFC2 in which the document grows. They set LNC2 and TDC aside as not general enough for their framework.
What the papers found
The 2004 paper applies the six constraints to one formula from each of three families. All three measure a document's length in tokens, $\lvert d \rvert$, and the first two compare it with the collection's average, $\mathit{avdl}$.
- Pivoted normalization, the vector space formula, in the form $\sum_{w \in q \cap d} \frac{1 + \ln(1 + \ln c(w, d))}{(1 - s) + s\,\lvert d \rvert / \mathit{avdl}} \cdot c(w, q) \cdot \ln\frac{N + 1}{\mathit{df}(w)}$. Its length term is the pivoted form derived in variants of TF-IDF, applied to the token length, and its term frequency is dampened by two logarithms.
- Okapi, the probabilistic formula of Okapi BM25, with the IDF $\ln\frac{N - \mathit{df}(w) + 0.5}{\mathit{df}(w) + 0.5}$.
- The Dirichlet prior method of language models for retrieval.
Its summary (Fang, Tao, and Zhai, 2004, Table 5) is that none of the three satisfies all six constraints unconditionally:
| Formula | TFCs | TDC | LNC1 | LNC2 | TF-LNC |
|---|---|---|---|---|---|
| Pivoted | yes | conditional | yes | only for small $s$ | only for small $s$ |
| Dirichlet prior | yes | only for large $\mu$ | yes | conditional | yes |
| Okapi | only if IDF ≥ 0 | conditional | only if IDF ≥ 0 | only if IDF ≥ 0 | only if IDF ≥ 0 |
| Okapi, modified IDF | yes | conditional | yes | yes | yes |
Three of its findings bear on this topic.
A bound on the slope. For the pivoted formula, LNC2 holds only when the slope is below a bound. With $\lvert d_2 \rvert = \mathit{avdl}$, the paper (§3.1) derives $s \le \frac{1}{k - 1}\left(\frac{\mathit{tf}_1}{\mathit{tf}_2} - 1\right)$, where $\mathit{tf}_2 = 1 + \ln(1 + \ln c(w, d_2))$ is the term frequency part for the original document and $\mathit{tf}_1$ the same for the document repeated $k$ times. Evaluating the bound:
| $c(w, d_2)$ | 1 | 2 | 5 | 10 | 30 |
|---|---|---|---|---|---|
| $k = 2$ | 0.527 | 0.225 | 0.120 | 0.087 | 0.059 |
| $k = 3$ | 0.371 | 0.164 | 0.090 | 0.065 | 0.045 |
| $k = 4$ | 0.290 | 0.131 | 0.072 | 0.053 | 0.037 |
The bound tightens as the count or $k$ grows. The paper concludes that a reasonable slope should be small, below 0.4 even for small $k$, and predicts poor performance for large $s$. Its experiments on seven document sets agree: the slope that maximized average precision was between 0.01 and 0.3 in every case (its Table 7). The slopes of 0.75 and 0.70 that Singhal, Buckley, and Mitra (1996) found best were for pivoting the cosine factor, a different quantity from the token length pivoted here, so the two sets of numbers are not in conflict.
Negative IDF. Okapi's IDF is negative for a term in more than half the documents. An extra occurrence of such a term lowers the score, which violates the term frequency and length constraints at once. The paper predicts that Okapi should do worse on verbose queries, which contain common words, and that replacing its IDF by the always-positive $\ln\frac{N + 1}{\mathit{df}(w)}$ should repair it. Its experiments confirm both, with the modified formula significantly better on verbose queries. The clipped "probabilistic IDF" of the SMART notation and the variant IDF described in Okapi BM25 address the same problem.
The revision. With the relaxed TDC, the 2011 article (Table VI) reports that pivoted normalization, the Dirichlet prior and both forms of Okapi satisfy TDC, and that the modified Okapi satisfies every constraint. The article also adds a fourth family, PL2, which satisfies TDC only conditionally. Its appendix establishes TDC by showing that each score increases with the term's discrimination value.
This topic's schemes, checked
The papers analyze formulas normalized by token length. Four of this topic's five functions are different: two have no normalization at all, and two divide by the length of a weight vector. This section tests all five. Each verdict is proved below or refuted by a computed case. In addition tools/experiments/vsm/weighting_constraints.py tests every cell on 20,000 random instances drawn with a fixed seed, half of them short documents (up to four other terms) and half long ones (up to 60 other terms, with query-term counts up to 120). The search can refute a verdict but cannot prove one, so no cell rests on it alone.
One point of interpretation comes first. The constraints fix the token length $\lvert d \rvert$, but a cosine normalizer depends on how the tokens are spread over terms. Twenty tokens of one word give a short lnc vector, and twenty different words a long one. Taken literally, TFC1 can then be defeated by rearranging the words the constraint does not mention.
Example (TFC1 as stated fails under cosine normalization). For the query insurance, let $d_2$ have insurance once and one other word 19 times, and $d_1$ have insurance twice and 18 other words once each. Both have 20 tokens and $d_1$ has more occurrences of the query term. The lnc vector of $d_2$ has length $\sqrt{1 + 2.279^2} = 2.489$ and that of $d_1$ has length $\sqrt{1.301^2 + 18} = 4.438$. The lnc cosine scores are 0.121 for $d_2$ and 0.088 for $d_1$, and the pivoted scores 0.123 and 0.100. The document with fewer occurrences wins. (For ntc the roles reverse, because raw counts make the concentrated document's vector the long one: insurance twice with one other word 18 times scores 0.033, below insurance once with 19 other words once each, 0.067.)
That failure says something true about cosine normalization: it measures a different length from the one the constraints have in mind. The papers' own explanations describe the comparisons they intend. For TFC1, "the only difference between two documents is the occurrences of the query term". For TF-LNC, "$d_1$ is generated by adding more occurrences of the query term to $d_2$". For LNC1, the score should fall "if we add one extra occurrence" of a word not in the query (Fang, Tao, and Zhai, 2004, §§2.1, 2.3 and 2.4). The constraints that leave other counts free are therefore read below in that like-for-like form:
- TFC1 and TFC2. $d_1$ is $d_2$ with occurrences of non-query words replaced by occurrences of $w$, as in the four-token example.
- TFC3 and TDC. The two documents agree on every term other than $w_1$ and $w_2$.
- TF-LNC. $d_1$ is $d_2$ with occurrences of $w$ added and nothing else changed.
- LNC1. It is taken in its 2011 form, with every other count held equal.
Read as printed, TF-LNC and the 2004 LNC1 fail under cosine normalization by the same rearrangement as TFC1.
Example (TF-LNC and LNC1 as printed). For TF-LNC, let $d_2$ have insurance once and one other word 19 times, and $d_1$ have insurance twice and 19 other words once each. Then $d_1$ has one more occurrence of the query term and is one token longer, as the constraint asks, but the lnc score falls from 0.121 to 0.086 and the pivoted score from 0.123 to 0.098. (For ntc the arrangement is again the opposite one, and the score falls from 0.067 to 0.032.) For the 2004 LNC1, let $d_1$ have insurance once and 19 other words once each, and let $d_2$ have insurance once and the first of those words twice. One non-query word has one more occurrence in $d_2$ and the query term's count is equal, so the constraint demands $f(d_1) \ge f(d_2)$. The scores are 0.067 and 0.183 under lnc, 0.067 and 0.135 under ntc, and 0.077 and 0.166 pivoted.
The unnormalized sums are not affected by the distinction, since they involve no count other than those of the query terms. In the table, a verdict for a cosine or pivoted scheme is for the like-for-like form.
| Constraint | Raw sum | Log sum | ntc cosine | lnc cosine | Pivoted lnc |
|---|---|---|---|---|---|
| TFC1 | holds | holds | holds | holds | holds |
| TFC2 | fails (equal steps) | holds | fails | fails | fails |
| TFC3 | fails (tie) | holds | holds | holds | holds |
| TDC (2004) | holds | fails | fails | fails | fails |
| LNC1 (2011 form) | holds, as an equality | holds, as an equality | holds | holds | holds |
| LNC2 | holds | holds | holds, as an equality | fails | fails for every fixed $s > 0$; a given document satisfies it only below a slope bound of its own |
| TF-LNC | holds | holds | holds, except for a document that is only $w$ | holds, with the same exception | holds |
No column is clean. Two of the failures are weaknesses the running example has already shown. The raw sum's equal steps are what let the car review win on five occurrences of car, and the sums' indifference to added words is the missing length normalization.
The sums without normalization
Write $g(c)$ for the term frequency part, $g(c) = c$ for the raw sum and $g(c) = 1 + \log_{10} c$ (with $g(0) = 0$) for the log sum. The score is $\sum_{t \in q} g(c(t, d))\,\mathit{idf}(t)$. It involves no count other than those of the query terms, so the equal-length hypotheses play no part.
- TFC1 and TF-LNC. Both ask that a larger count of $w$ give a larger score. Both forms of $g$ are strictly increasing, with $g(0) = 0 < g(1) = 1$, and $\mathit{idf}(w) > 0$. Both constraints hold for both sums.
- TFC2. The raw sum's two steps are both $\mathit{idf}(w)$, so the strict inequality fails. For the log sum, the steps are $\mathit{idf}(w)\log_{10}\frac{c + 1}{c}$ and $\mathit{idf}(w)\log_{10}\frac{c + 2}{c + 1}$, and the first is larger because $(c + 1)^2 = c(c + 2) + 1 > c(c + 2)$.
- TFC3. With equal IDFs and counts $a, b \ge 1$, the raw sum gives both documents $(a + b)\,\mathit{idf}$, a tie. The log sum gives the concentrated document $1 + \log_{10}(a + b)$ and the spread one $2 + \log_{10}(ab)$, in units of the common IDF. The second is larger when $a + b < 10ab$, which always holds, since $a + b \le 2ab$ for $a, b \ge 1$.
- TDC (2004). For the raw sum, $f(d_1) - f(d_2) = \mathit{idf}(w_1)\big(c(w_1, d_1) - c(w_1, d_2)\big) + \mathit{idf}(w_2)\big(c(w_2, d_1) - c(w_2, d_2)\big)$. The totals are equal, so the second difference is minus the first, and $f(d_1) - f(d_2) = \big(c(w_1, d_1) - c(w_1, d_2)\big)\big(\mathit{idf}(w_1) - \mathit{idf}(w_2)\big) \ge 0$. The constraint holds. The log sum satisfies TFC3 and so, by the example above, cannot satisfy this one. It also fails where the IDFs differ. For
car insurance, take two documents that each contain rate once. The one with insurance three times scores 0.445, and the one with insurance twice and car once scores 0.517, although the first has more of the rarer term. (The raw sum gives them 0.903 and 0.727, as the constraint requires.) - LNC1. Adding a non-query word changes neither sum. The constraint holds as an equality, which means these scores do not penalize length at all. Both fail the strict form of Fang and Zhai (2005).
- LNC2. Repeating a document $k$ times multiplies the raw sum by $k$ and adds $\log_{10} k$ times the IDFs of the matched terms to the log sum. Neither goes down. For the raw sum this is the flaw of TF-IDF weighting seen from the other side: the constraint asks only that a longer document not be over-penalized, and says nothing against rewarding it $k$-fold.
The relaxed TDC of 2011 holds for the raw sum, since adding $k$ occurrences of $w_1$ and not $w_2$ changes the score by $k\big(\mathit{idf}(w_1) - \mathit{idf}(w_2)\big) > 0$. For the log sum it fails as printed, for an arbitrary $D$. If $D$ has insurance ten times and no car, adding one more insurance gives 0.615 and adding car gives 0.727: the first occurrence of the commoner term is worth more than the eleventh of the rarer one. It holds in the derived form, where $1 \le c(w_1, D) \le c(w_2, D)$. Then $\log_{10}\frac{c(w_1, D) + 1}{c(w_1, D)} \ge \log_{10}\frac{c(w_2, D) + 1}{c(w_2, D)}$, and multiplying the left side by the larger IDF and the right by the smaller keeps the inequality and makes it strict. The 2011 article reports that the pivoted formula satisfies its TDC, by the test described above, which examines how the score changes with the discrimination value. The same kind of case defeats the printed statement for that formula as well. Its term frequency part is 2.195 for a count of 10 and 2.223 for 11, a gain of 0.028 from unrounded values, against 1 for the first occurrence of a new term, and the two enlarged documents have the same length. Adding the commoner term therefore wins unless the rarer one's discrimination value is more than about 35 times larger. The appendix's test shows that the score increases with a term's discrimination value when the counts are fixed. Together with TFC2 that yields the derived form, where $c(w_1, D) \le c(w_2, D)$. It does not yield the statement for an arbitrary $D$, which the 2011 article prints. The derived form is evidently what the authors intend, and it is the form this article checks.
Cosine normalization
For a one-term query, write $x$ for the weight of $w$ in the document before normalization and $R$ for the sum of the squares of all the other weights. The cosine-normalized score is $\mathit{idf}(w)\,h(x, R)$ with
$$h(x, R) = \frac{x}{\sqrt{x^2 + R}}.$$
Here is the plan: three properties of $h$ settle five of the seven rows.
Lemma. For $x > 0$ and $R > 0$, $h$ is strictly increasing in $x$, strictly decreasing in $R$, and strictly concave in $x$. For $R = 0$, $h = 1$ whatever $x$ is.
Proof. Differentiating, $\partial h/\partial x = R\,(x^2 + R)^{-3/2} > 0$ and $\partial h/\partial R = -\tfrac{1}{2}x\,(x^2 + R)^{-3/2} < 0$. Differentiating the first again, $\partial^2 h/\partial x^2 = -3Rx\,(x^2 + R)^{-5/2} < 0$. If $R = 0$ then $h = x/\sqrt{x^2} = 1$.
- TFC1, by replacement. Replacing occurrences of other words by $w$ raises $x$ and lowers $R$. By the lemma the score rises. If the replacement leaves no other word, the score becomes $\mathit{idf}(w)$, its largest possible value.
- TF-LNC. In the like-for-like form, adding occurrences of $w$ raises $x$ and leaves $R$ alone, so the score rises when $R > 0$. If the document consists of $w$ only, the score is $\mathit{idf}(w)$ before and after, a tie.
- LNC1. In the 2011 form, adding a non-query word raises $R$ and leaves every query term's weight alone, so each term of the score falls. (This argument is per query term, with $x$ and $R$ taken for that term, and so covers queries of any size.)
- TFC3. With equal IDFs, let the unnormalized weights of the two terms in the spread document be $g_a$ and $g_b$ and that of the single term in the concentrated one be $g_{a+b}$, where $g_{a+b} \le g_a + g_b$ for both forms of $g$. Let $R$ be the squared weights of the remaining terms. The concentrated document scores $u\,g_{a+b}/\sqrt{g_{a+b}^2 + R}$ for a common factor $u$, and the spread one $u\,(g_a + g_b)/\sqrt{g_a^2 + g_b^2 + R}$. Since $g_a^2 + g_b^2 < (g_a + g_b)^2$, the second exceeds $u\,h(g_a + g_b, R)$, which is at least $u\,h(g_{a+b}, R)$ by the lemma. So the spread document scores strictly higher, even under ntc, where the two numerators are equal and the whole difference comes from the normalizer.
- TDC (2004). It fails, because TFC3 holds. With unequal IDFs the lnc scores of the two
car insurancedocuments above are 0.249 and 0.269, and the ntc scores 0.286 and 0.288, the wrong way round again. - TFC2. It fails even by replacement. In the four-token example the lnc steps are 0.036 and then 0.052: the last replacement removes the only other term, and the normalizer collapses. For ntc, take insurance once, rate once and loan 100 times, then replace rate, then one loan. The scores are 0.00151, 0.00301 and 0.00456, with steps of 0.00151 and 0.00155. What does hold, for a document that contains some term other than $w$, is the version in which the document grows, Constraint 3 of Fang and Zhai (2005): adding occurrences of $w$ with $R > 0$ fixed gives shrinking steps, because $h$ is concave in $x$ and $x$ grows by equal or shrinking amounts. A document consisting of $w$ alone scores $\mathit{idf}(w)$ at every count, so both steps are 0 and the strict constraint fails by a tie, the same exception as for TF-LNC.
- LNC2. Under ntc, repeating a document multiplies every weight by $k$ and the cosine does not change, which is the property the model was built for. Under lnc it adds $L = \log_{10} k$ to every nonzero weight, which changes the vector's direction. Write $g_i$ for the weights of the document's distinct terms, $x$ for that of $w$, and $\varphi(L) = (x + L)/\sqrt{\sum_i (g_i + L)^2}$. The derivative $\varphi'(L)$ has the sign of $\sum_i (g_i + L)^2 - (x + L)\sum_i (g_i + L) = \sum_i (g_i + L)(g_i - x)$. If $w$ is the document's most frequent term and not every term has the same count, every term of that sum is zero or negative and one is negative, so the score falls for every $k > 1$ and LNC2 fails. If $w$ is its least frequent term, the score rises. For insurance nine times and rate once, doubling lowers the score from 0.268 to 0.261. For the headline, whose counts are all equal, it stays at 0.174.
So the logarithm that repairs TFC2 for the unnormalized sum breaks LNC2 under cosine normalization. A document that is mostly about the query term is penalized for saying everything twice.
Pivoted normalization
The pivoted score for a one-term query is $\mathit{idf}(w)\,x / (a + s\sqrt{x^2 + R})$ with $a = (1 - s)\,p > 0$. Its derivative in $x$ is
$$\frac{a + sR/\sqrt{x^2 + R}}{\big(a + s\sqrt{x^2 + R}\big)^2},$$
which is positive even when $R = 0$. The numerator does not increase with $x$ and the denominator increases, so the derivative is decreasing and the score is strictly concave in $x$. It is decreasing in $R$, since $R$ appears only in the denominator. The arguments for TFC1, LNC1, TFC3 and the growing-document form of TFC2 therefore go through as for the cosine, with $a + s\sqrt{\cdot}$ in place of the square root. TF-LNC now holds without exception: a document consisting only of the query term scores 0.227 with one occurrence and 0.276 with five. The growing-document form needs no exception either. At $R = 0$ the derivative is $a/(a + sx)^2$, still strictly decreasing, and the document of insurance alone scores 0.227, 0.252 and 0.264 at counts 1, 2 and 3, with steps of 0.025 and 0.012. TFC2 by replacement still fails (the four-token example), and so does the 2004 TDC.
The one row that changes is LNC2. The constant $a$ in the divisor does not grow when the document is repeated, so the larger numerator can win. Whether it does depends on the slope and on the document.
Example (a bound on the slope). For insurance nine times and rate once, the weight of insurance is $x = 1.954$ and the vector's length is $n = 2.195$. Doubled, they are $x' = 2.255$ and $n' = 2.604$. The doubled document scores at least as high when $x'(a + sn) \ge x(a + sn')$, that is, when
$$\frac{(1 - s)\,p}{s} \ge \frac{x n' - x' n}{x' - x} = 0.456.$$
With $p = 2.310$ this is $s \le 0.835$. At $s = 0.75$ the score rises from 0.2645 to 0.2683. At $s = 1$, which is the lnc cosine, it falls from 0.2680 to 0.2608.
This is the same kind of result as the paper's bound for its own pivoted formula: LNC2 caps the slope, and the cap depends on the document. For this document the cap is high. It is not high in general, and no fixed slope above 0 satisfies LNC2 for every document.
Example (long documents lower the cap). A document with insurance ten times and 50 other words once each violates LNC2 at $s = 0.5$: its score for insurance is 0.1247, and 0.1175 when it is doubled. Its cap is $s \le 0.253$. A document with insurance 100 times and 100 other words once each violates it at $s = 0.25$: the score falls from 0.2080 to 0.1953, and the cap is $s \le 0.107$.
Proposition. For every slope $s$ with $0 < s \le 1$ there is a document that violates LNC2 under pivoted lnc normalization.
Proof. Take a one-term query $w$ and a document with $w$ occurring $c \ge 2$ times and $m$ other words once each, repeated $k$ times. Write $L = \log_{10} k$ and $x = 1 + \log_{10} c > 1$. Before repetition the weights are $x$ and $m$ ones, so the length is $n = \sqrt{x^2 + m}$. After it they are $x' = x + L$ and $m$ weights of $1 + L$, so $n' = \sqrt{(x + L)^2 + m(1 + L)^2}$. As in the example, the repeated document scores at least as high exactly when $(1 - s)\,p/s \ge (x n' - x' n)/(x' - x)$. For large $m$, $n = \sqrt{m} + O(1/\sqrt{m})$ and $n' = (1 + L)\sqrt{m} + O(1/\sqrt{m})$, so
$$x n' - x' n = \sqrt{m}\,\big[x(1 + L) - (x + L)\big] + O(1/\sqrt{m}) = \sqrt{m}\,L\,(x - 1) + O(1/\sqrt{m}).$$
Dividing by $x' - x = L$, the right-hand side of the condition is $\sqrt{m}\,(x - 1) + O(1/\sqrt{m})$, which grows without limit as $m$ does, while the left-hand side is fixed by $s$. So for $m$ large enough the condition fails. The cap on the slope is $p/(p + \text{right-hand side})$, and it tends to 0. For insurance ten times it is 0.190 with 100 other words, 0.023 with 10,000 and 0.002 with a million.
The condition $c \ge 2$ matters. A query term that occurs once among words that occur once has the same weight as all of them before and after repetition, and its score cannot fall.
So the contrast with the paper's formula is one of degree, not of kind. Both caps tend to 0, the paper's as the count of the query term grows and this one as the number of other words grows. On short documents the cosine factor's cap is high, because that factor grows only as the logarithm of $k$ under repetition. The seeded search shows the same dependence on document size. Restricted to short documents (at most six terms) it finds no violation in 20,000 cases at slopes 0.25 and 0.5 and 100 at 0.75. With long documents included it finds 504, 3,919 and 8,402 at the three slopes. A search over short documents alone would have suggested, wrongly, that small slopes are safe.
Worked problems
The four problems are posed on this topic's schemes and running example. Their numbers are computed by tools/experiments/vsm/weighting_constraints.py.
Problem 1 (Boolean term frequency). The scheme bnc gives every term that occurs the weight 1 before cosine normalization. Decide whether it satisfies TFC1 in the replacement form, using the query insurance and three-token documents.
Solution. It does not: the constraint's strict inequality fails with a tie. Take insurance once and rate twice, and replace one rate by insurance. Both documents have the same two distinct terms, so both have the vector $(1, 1)$ of length $\sqrt{2}$, and both score $0.301/\sqrt{2} = 0.213$. A weight that ignores counts cannot reward a count. This is the tie between $d_1$ and $d_3$ in the eight-scheme table of variants of TF-IDF, stated as a failed constraint.
Problem 2 (augmented term frequency). The augmented weight is $0.5 + 0.5\,c(t, d)/c_{\max}(d)$, with $c_{\max}(d)$ the largest count in the document. Without normalization, decide whether it satisfies TFC1 for the query insurance on five-token documents.
Solution. It fails whenever the query term is the most frequent term of both documents. With insurance three times and rate twice, the weight is $0.5 + 0.5 \times 3/3 = 1$ and the score 0.301. With insurance four times and rate once it is $0.5 + 0.5 \times 4/4 = 1$ and the score is again 0.301. The most frequent term always has weight 1, whatever its count. When the query term is not the most frequent, the constraint's conclusion does hold in these documents: insurance once of five scores $0.301 \times (0.5 + 0.5 \times 1/4) = 0.188$, and twice of five $0.301 \times (0.5 + 0.5 \times 2/3) = 0.251$.
Problem 3 (the car review doubled). Under lnc.ltc, decide whether the running example's car review $d_2$ (auto 1, best 2, car 5) satisfies LNC2 with $k = 2$ for the query best car insurance.
Solution. It violates it: the score falls from 0.455 to 0.449. The weights $1 + \log_{10} c$ are 1.000, 1.301 and 1.699, with length 2.362. Doubling the counts adds $\log_{10} 2 = 0.301$ to each, giving 1.301, 1.602 and 2.000, with length $\sqrt{1.693 + 2.567 + 4.000} = 2.874$. The document's matched terms are best and car, each with query weight 0.358 after the query's normalization:
- original: $0.358 \times (1.301 + 1.699)/2.362 = 0.358 \times 1.270 = 0.455$;
- doubled: $0.358 \times (1.602 + 2.000)/2.874 = 0.358 \times 1.253 = 0.449$.
The matched terms are the document's two most frequent, and the unmatched auto is its least frequent. Adding the same 0.301 to all three weights moves the vector toward auto, away from the query. The fall is small, but it is in the wrong direction, and it is on a document of the running example itself.
Problem 4 (the slope that repairs it). For the query car and the same doubled car review, find the slopes $s$ for which pivoted lnc normalization with $p = 2.310$ satisfies LNC2.
Solution. For this document it is satisfied for $s \le 0.814$. The weight of car is $x = 1.699$ with length $n = 2.362$, and after doubling $x' = 2.000$ with $n' = 2.874$. As in the example above, the doubled document scores at least as high when
$$\frac{(1 - s)\,p}{s} \ge \frac{x n' - x' n}{x' - x} = \frac{1.699 \times 2.874 - 2.000 \times 2.362}{0.301} = \frac{4.883 - 4.724}{0.301} = 0.527,$$
from unrounded values. Solving for $s$ gives $s \le p/(p + 0.527) = 0.814$. The slope of 0.75 used in this topic satisfies it, and the cosine, $s = 1$, does not.
What we have learned
Six constraints state what term frequency, term discrimination and length normalization should do: more occurrences help, with diminishing returns; rarer terms count for more; extra words do not help, and length alone does not hurt. The papers showed that pivoted normalization, Okapi and the Dirichlet prior each satisfy some of them only for restricted parameter values, and that the restrictions predict where each formula performs badly. For this topic's schemes, the raw sum fails the diminishing-returns constraints, the sums without normalization meet the length constraint only as an equality, cosine normalization with a logarithm over-penalizes a repeated document whose query term dominates it, and a pivoted slope below a document-dependent bound repairs that for the document in question, though no single slope does so for every document. Under cosine normalization the constraints have to be read like for like, since as printed they leave the other words free to be rearranged. The 2004 form of TDC cannot hold together with TFC3, and no scheme here satisfies everything.
The constraints are necessary conditions, as their authors stress: satisfying them all does not make a function good, and they do not replace evaluation. They do turn "this scheme ranked the headline first" into "this scheme fails here, for this reason". The next article, Finding Similar Documents, returns to the cosine and uses it to compare every document of a collection with every other.
Every number in this article is computed by tools/experiments/vsm/weighting_constraints.py in the site repository (random search with seed 790).
References
- Fang, H., Tao, T., and Zhai, C. (2004). A formal study of information retrieval heuristics. In Proceedings of SIGIR 2004, 49–56. record · 3 pages
- Fang, H., Tao, T., and Zhai, C. (2011). Diagnostic evaluation of information retrieval models. ACM Transactions on Information Systems, 29(2), Article 7. record
- Fang, H., and Zhai, C. (2005). An exploration of axiomatic approaches to information retrieval. In Proceedings of SIGIR 2005, 480–487. record
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 6.4. Cambridge University Press. record · 93 pages
- Singhal, A., Buckley, C., and Mitra, M. (1996). Pivoted document length normalization. In Proceedings of SIGIR 1996, 21–29. record · 3 pages