Scale the whole log-likelihood table with the window size
ca_ll() multiplied only its row total by the window size, leaving cells
that do not add up to one sample: the row was counted in window
positions, the column and the sample size in corpus tokens.
Following Evert (2004), which the function cites, the sample consists of
co-occurrence tokens rather than corpus tokens. With a window of
window_size positions, every occurrence of either word takes part in
that many pairs, so the sample size and both marginals scale with it.
The expected co-occurrence frequency comes out as window_size * f1 * f2
/ n either way, which is why pmi, md, lfmd and npmi never depended on
this, and why it stayed unnoticed: only llr needs the rest of the table.
There the values differ, by 0.1% for a frequent collocate up to well
over 100% for a frequent node in a wide window. Results with a window of
one position are unchanged, the two being identical there.
It also removes a pathology instead of guarding against it: n -
window_size * f1 could turn negative, at which point the score became
NaN. window_size * (n - f1) cannot. In this database the case was out of
reach anyway, needing a word covering more than a tenth of the corpus,
but the same table is used elsewhere with freely chosen window sizes.
Reported-by: Tim Feldmüller <https://github.com/feldmueller>
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Change-Id: Ic396d586da7f6a68b2c911d871ff58032b554d1f
diff --git a/README.md b/README.md
index fd4916f..43838e0 100644
--- a/README.md
+++ b/README.md
@@ -207,6 +207,17 @@
how concentrated a pair is and thus orders collocates well. It lives in
`ca_focus_score()` now, so that it no longer looks like a variant of
`logDice`, from which it is deliberately different and on another scale
+ * the log-likelihood table is scaled with the window size as a whole, an
+ inconsistency [Tim Feldmüller](https://github.com/feldmueller) spotted. It used
+ to multiply only its row total by it, leaving cells that do not add up to
+ one sample: the row was counted in window positions, the column and the
+ sample size in corpus tokens. Following Evert (2004), which `ca_ll()`
+ cites, the sample consists of co-occurrence tokens, so the sample size and
+ both marginals scale with the window. The expected co-occurrence frequency
+ is `window_size * f1 * f2 / n` either way, which is why `pmi`, `md`, `lfmd`
+ and `npmi` are unaffected, but `llr` values differ, by 0.1% up to well over
+ 100% depending on the frequencies and the window. It also removes the case
+ where `n - window_size * f1` turned negative and the score became `NaN`
* the first collocate of every query is scored with the right window size.
`true_window_size` counts the positions a pair was observed in, but started
at one while the first key of the iteration already incremented it, so that
@@ -258,6 +269,12 @@
* v1.3.1 (2024-11-14)
* fixed calculation of total token count
+## Authors
+
+* Marc Kupietz
+
+**Contributors**: [Tim Feldmüller](https://github.com/feldmueller)
+
## TODO
* extend API
diff --git a/src/collocatordb.cc b/src/collocatordb.cc
index 6eda410..63029c4 100644
--- a/src/collocatordb.cc
+++ b/src/collocatordb.cc
@@ -179,12 +179,21 @@
// Collocations. PhD dissertation, IMS, University of Stuttgart. Published in
// 2005, URN urn:nbn:de:bsz:93-opus-23714. Free PDF available from
// http://purl.org/stefan.evert/PUB/Evert2004phd.pdf
+// The table classifies co-occurrence tokens, not corpus tokens: with a window of
+// window_size positions, every occurrence of either word takes part in that many
+// pairs, so the sample size and both marginals scale with it. Scaling only the
+// row, as this did before, leaves cells that do not add up to one sample and lets
+// n - window_size * w1 turn negative for a frequent node in a wide window. The
+// expected co-occurrence frequency is window_size * w1 * w2 / n either way, which
+// is why the other measures do not depend on this.
static double ca_ll(uint64_t w1, uint64_t w2, uint64_t w12, uint64_t n,
uint64_t window_size) {
- double r1 = (double)w1 * window_size, r2 = (double)n - r1, c1 = w2,
- c2 = n - c1, o11 = w12, o12 = r1 - o11, o21 = c1 - w12, o22 = r2 - o21,
- e11 = r1 * c1 / n, e12 = r1 * c2 / n, e21 = r2 * c1 / n,
- e22 = r2 * c2 / n;
+ double total = (double)n * window_size,
+ r1 = (double)w1 * window_size, r2 = total - r1,
+ c1 = (double)w2 * window_size, c2 = total - c1,
+ o11 = w12, o12 = r1 - o11, o21 = c1 - o11, o22 = r2 - o21,
+ e11 = r1 * c1 / total, e12 = r1 * c2 / total, e21 = r2 * c1 / total,
+ e22 = r2 * c2 / total;
return (2 * ((o11 > 0 ? o11 * log(o11 / e11) : 0) +
(o12 > 0 ? o12 * log(o12 / e12) : 0) +
(o21 > 0 ? o21 * log(o21 / e21) : 0) +
diff --git a/tests/basic_test.c b/tests/basic_test.c
index d98aac4..f4a003f 100644
--- a/tests/basic_test.c
+++ b/tests/basic_test.c
@@ -40,7 +40,7 @@
COLLOCATORDB* cdb = open_collocatordb(dbpath);
TEST_ASSERT(cdb != NULL);
char *json = get_collocators_as_json(cdb, testword);
- char *needle = "\"word\":\"um\",\"f2\":264,\"f\":5,\"npmi\":-0.0556349,\"pmi\":-0.958074,\"llr\":2.87723,\"lfmd\":3.68578,\"md\":1.36385,\"md_nws\":0.363854,\"dice\":0.00720461,\"ld\":6.88314,\"ln_count\":0,\"rn_count\":1,\"ln_pmi\":-1,\"rn_pmi\":-1,\"ldaf\":4.79935,\"win\":668,\"afwin\":668";
+ char *needle = "\"word\":\"um\",\"f2\":264,\"f\":5,\"npmi\":-0.0556349,\"pmi\":-0.958074,\"llr\":2.80721,\"lfmd\":3.68578,\"md\":1.36385,\"md_nws\":0.363854,\"dice\":0.00720461,\"ld\":6.88314,\"ln_count\":0,\"rn_count\":1,\"ln_pmi\":-1,\"rn_pmi\":-1,\"ldaf\":4.79935,\"win\":668,\"afwin\":668";
TEST_CHECK(strstr(json, needle) > 0);
TEST_MSG("Expected to contain: %s", needle);
}