Search the embedding space with vector expressions
"König - Mann + Frau" now looks for the neighbours of
vec(König) - vec(Mann) + vec(Frau) instead of the neighbours of a single
word. A '+' or '-' is an operator only at the beginning of a token, so
hyphenated words like "Nord-Süd-Dialog" stay searchable, and blank
separated words keep entering the query with a '+', as before.
_get_neighbours() already had the branch for it, but nothing ever filled
wl->sep: the wordlist came from malloc() and the signs were read out of
uninitialised memory, so a multi word query subtracted operands at
random. It is filled now, and its indexing corrected - sep[b] is the sign
of operand b, not sep[b-1].
The predictive collocators answer for the whole query as well.
getCollocators() read the input weights of wl->wordi[0], the first
operand, and nothing said so: "Haus Auto" answered with the collocators
of Haus, "Auto Haus" with those of Auto. The score of a candidate is
sigmoid(q . syn1neg[collocate, position]), linear in q before the
sigmoid, so q can be the signed combination the paradigmatic side
searches around rather than the vector of one word.
The terms are averaged rather than summed. The sigmoid is informative
over a narrow range only - the strongest collocates of a single word
reach 0.994 to 0.997 on dereko-2026-ii, against the 0.9975 that MAX_EXP
allows - so a plain sum would push them into saturation. Dividing by the
number of terms keeps every query in the range MIN_RESP and the auto
focus are calibrated for, and leaves one word exactly as it was, divisor
one. A balanced analogy is one term as well, +1 -1 +1.
Those tails now saturate instead of being dropped. Activations outside
±MAX_EXP used to skip the collocate entirely, removing the strongest ones
from the list and from the position and target sums.
The count based collocators cannot follow: they are looked up per node in
the co-occurrence database. They used to be fetched for the first
paradigmatic neighbour, i.e. for the word nearest to the query vector,
which for an expression is not what was asked for. The interface says so
in place of that table now, and get_neighbours() reports the number of
operands so it can tell the two cases apart.
Operands outside the vocabulary are named above the result instead of
being dropped in silence. The vocabulary lookup only recognised a miss at
the very end of the vocabulary, so in a merged model a missing word
resolved to whatever sits at the boundary between the two vocabularies;
it returns -1 in both halves now.
Two more things the tokeniser uncovered. The best array was sized for
10 * max(N, 200) entries but sorted over N * para_threads, which fits
only as long as the syntagmatic threads take half of them - it is sized
for num_threads slices now. And its unfilled slots kept wordi == 0 from
the memset, which the result loop emitted as vocab[-1 * max_w] once a
thread found fewer candidates than were asked for; slots start at -1 and
the loop stops there.
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Change-Id: Ia91727eb669d73fc055adf652500464b8a743795
diff --git a/lib/IDS/DeReKoVecs/derekovecs-server.c b/lib/IDS/DeReKoVecs/derekovecs-server.c
index b1aa341..5a08486 100644
--- a/lib/IDS/DeReKoVecs/derekovecs-server.c
+++ b/lib/IDS/DeReKoVecs/derekovecs-server.c
@@ -12,6 +12,7 @@
#define max_size 2000
#define max_w 50
#define MAX_NEIGHBOURS 1000
+#define MAX_TARGET_WORDS 100
#define MAX_WORDS -1
#define MAX_THREADS 100
#define MAX_CC 50
@@ -61,9 +62,13 @@
} knn;
typedef struct {
- long long wordi[MAX_NEIGHBOURS];
- char sep[MAX_NEIGHBOURS];
- int length;
+ long long wordi[MAX_TARGET_WORDS];
+ /* '+' or '-': the sign with which wordi[i] enters the query vector */
+ char sep[MAX_TARGET_WORDS];
+ /* blank separated tokens of the query that are not in the vocabulary */
+ char oov[max_size];
+ int length; /* number of tokens found in the vocabulary */
+ int subtractions; /* how many of them enter with a '-' */
} wordlist;
typedef struct {
@@ -405,21 +410,50 @@
free(nbs);
}
+/* Predicts the collocates of a query. The score of a collocate is
+ sigmoid(q . syn1neg[target, position]), which is linear in q before the
+ sigmoid, so the query does not have to be a single word: q can be the same
+ signed combination of input vectors that the paradigmatic side searches
+ around, and "König - Mann + Frau" asks for the contexts that König and Frau
+ predict but Mann does not.
+
+ The combination is the mean over the positive terms rather than their sum,
+ because the sigmoid is only informative over a narrow range of q . syn1neg
+ and the strongest collocates of a single word already sit at the top of it.
+ A plain sum would push them past MAX_EXP, where they all saturate to the
+ same value. Dividing by the number of terms keeps every query in the range
+ the threshold and the auto focus below are calibrated for, and leaves the
+ single word case exactly as it was: one term, divisor one. A balanced
+ analogy has one term as well, +1 -1 +1, and lands in the same range. */
void *getCollocators(void *args) {
knnpars *pars = args;
int N = pars->N;
- int cc = pars->wl->wordi[0];
+ wordlist *wl = pars->wl;
knn *nbs = NULL;
long window_layer_size = size * window * 2;
- long a, b, c, d, window_offset, target, max_target = 0, maxmax_target;
- float f, max_f, maxmax_f;
+ long a, b, c, d, op, window_offset, target, max_target = 0, maxmax_target;
+ float f, max_f, maxmax_f, scale;
+ float qvec[max_size];
+ int terms = 0;
float *target_sums = NULL, worstbest, wpos_sum;
collocator *best;
- if (M2 == NULL || cc == -1)
+ if (M2 == NULL || wl == NULL || wl->length < 1)
return NULL;
+ for (a = 0; a < wl->length; a++) terms += (wl->sep[a] == '-' ? -1 : 1);
+ scale = (terms > 1 ? 1.0f / terms : 1.0f);
+ for (c = 0; c < size; c++) qvec[c] = 0;
+ for (a = 0; a < wl->length; a++) {
+ long long off = wl->wordi[a] * size;
+ if (wl->sep[a] == '-')
+ for (c = 0; c < size; c++) qvec[c] -= M2[off + c];
+ else
+ for (c = 0; c < size; c++) qvec[c] += M2[off + c];
+ }
+ for (c = 0; c < size; c++) qvec[c] *= scale;
+
a = posix_memalign((void **)&target_sums, 128, pars->cutoff * sizeof(float));
memset(target_sums, 0, pars->cutoff * sizeof(float));
best = malloc((N > 200 ? N : 200) * sizeof(collocator));
@@ -434,7 +468,7 @@
best[b].activation = worstbest;
}
- d = cc;
+ d = wl->wordi[0];
maxmax_f = -1;
maxmax_target = 0;
@@ -450,17 +484,22 @@
window_offset -= size;
for (target = 0; target < pars->cutoff; target++) {
if (garbage && garbage[target]) continue;
- if (target == d)
+ /* an operand of the query is not a collocate of itself */
+ for (op = 0; op < wl->length && wl->wordi[op] != target; op++)
+ ;
+ if (op < wl->length)
continue;
f = 0;
for (c = 0; c < size; c++)
- f += M2[d * size + c] * syn1neg_window[target * window_layer_size + window_offset + c];
+ f += qvec[c] * syn1neg_window[target * window_layer_size + window_offset + c];
+ /* Saturate rather than drop. Skipping the tails used to lose exactly
+ the collocates the sigmoid can no longer tell apart, i.e. the
+ strongest ones, and left them out of wpos_sum and target_sums too. */
if (f < -MAX_EXP)
- continue;
+ f = -MAX_EXP;
else if (f > MAX_EXP)
- continue;
- else
- f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
+ f = MAX_EXP;
+ f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
wpos_sum += f;
target_sums[target] += f;
@@ -615,41 +654,74 @@
return res;
}
-wordlist *getTargetWords(char *st1, int search_backw) {
- wordlist *wl = malloc(sizeof(wordlist));
- char st[100][max_size];
- long a, b = 0, c = 0, cn = 0;
+/* Returns the position of a word in the vocabulary, or -1. In a merged model
+ the two vocabularies sit next to each other and search_backw selects which
+ of them is looked at. */
+static long long lookupWord(const char *word, int search_backw) {
+ long long b, lower = (merge_words ? merge_words : 0);
+ long long upper = (merge_words ? merge_words : words);
- while (1) {
- st[cn][b] = st1[c];
- b++;
- c++;
- st[cn][b] = 0;
- if (st1[c] == 0) break;
- if (st1[c] == ' ' /*|| st1[c] == '-'*/) {
- b = 0;
- c++;
- }
+ if (search_backw) {
+ for (b = words - 1; b >= lower && strcmp(&vocab[b * max_w], word) != 0; b--)
+ ;
+ if (b < lower) b = -1;
+ } else {
+ for (b = 0; b < upper && strcmp(&vocab[b * max_w], word) != 0; b++)
+ ;
+ if (b >= upper) b = -1;
}
- cn++;
- for (a = 0; a < cn; a++) {
- if (search_backw) {
- for (b = words - 1; b >= (merge_words ? merge_words : 0) && strcmp(&vocab[b * max_w], st[a]) != 0; b--)
- ;
- } else {
- for (b = 0; b < (merge_words ? merge_words : words) && strcmp(&vocab[b * max_w], st[a]) != 0; b++)
- ;
- }
- if (b == words) b = -1;
- wl->wordi[a] = b;
- if (b == -1) {
- DEBUG_EPRINTF("Out of dictionary word!\n");
- cn--;
- } else {
- DEBUG_EPRINTF("Word: \"%s\" Position in vocabulary: %lld\n", &vocab[wl->wordi[a] * max_w], wl->wordi[a]);
- }
+ return b;
+}
+
+/* Splits a query into the operands of a vector expression. Blanks separate
+ words as before, and a leading '+' or '-' decides with which sign a word
+ enters the query vector, so that "König - Mann + Frau" is answered with the
+ neighbours of vec(König) - vec(Mann) + vec(Frau) rather than with those of
+ any single word. A sign is only an operator at the beginning of a token,
+ which leaves hyphenated words such as "Nord-Süd-Dialog" searchable; a
+ free standing sign applies to the word that follows it.
+
+ Tokens that are not in the vocabulary are left out of the list and
+ collected in wl->oov, so that the caller can report them instead of
+ quietly answering a different question. */
+wordlist *getTargetWords(char *st1, int search_backw) {
+ wordlist *wl = calloc(1, sizeof(wordlist));
+ char *copy = strdup(st1), *tok, *saveptr = NULL;
+ size_t oov_len = 0;
+ int sign = '+';
+
+ if (wl == NULL || copy == NULL) {
+ free(wl);
+ free(copy);
+ return NULL;
}
- wl->length = cn;
+
+ for (tok = strtok_r(copy, " \t\r\n", &saveptr); tok != NULL; tok = strtok_r(NULL, " \t\r\n", &saveptr)) {
+ long long b;
+ if (*tok == '+' || *tok == '-') {
+ sign = *tok++;
+ if (*tok == 0) continue; /* " - Mann": the sign belongs to the next token */
+ }
+ if (wl->length >= MAX_TARGET_WORDS) break;
+ /* Counted before the lookup: what the query is asking for does not change
+ because one of its operands happens to be unknown. */
+ if (sign == '-') wl->subtractions++;
+ b = lookupWord(tok, search_backw);
+ if (b < 0) {
+ DEBUG_EPRINTF("Out of dictionary word: \"%s\"\n", tok);
+ if (oov_len + strlen(tok) + 2 <= sizeof(wl->oov)) {
+ if (oov_len > 0) wl->oov[oov_len++] = ' ';
+ strcpy(wl->oov + oov_len, tok);
+ oov_len += strlen(tok);
+ }
+ } else {
+ DEBUG_EPRINTF("Word: \"%s\" Sign: %c Position in vocabulary: %lld\n", &vocab[b * max_w], sign, b);
+ wl->sep[wl->length] = (char)sign;
+ wl->wordi[wl->length++] = b;
+ }
+ sign = '+';
+ }
+ free(copy);
return (wl);
}
@@ -763,19 +835,19 @@
float worstbest = -1;
- for (a = 0; a < N; a++) best[a].activation = 0;
- a = 0;
+ for (a = 0; a < N; a++) {
+ best[a].activation = -1;
+ best[a].wordi = -1;
+ }
bi = wl->wordi;
cn = wl->length;
sep = wl->sep;
- b = bi[0];
- if (b == -1) {
+ if (cn < 1) {
goto end;
}
for (a = 0; a < size; a++) vec[a] = 0;
for (b = 0; b < cn; b++) {
- if (bi[b] == -1) continue;
- if (b > 0 && sep[b - 1] == '-')
+ if (sep[b] == '-')
for (a = 0; a < size; a++) vec[a] -= M[a + bi[b] * size];
else
for (a = 0; a < size; a++) vec[a] += M[a + bi[b] * size];
@@ -783,8 +855,12 @@
len = 0;
for (a = 0; a < size; a++) len += vec[a] * vec[a];
len = sqrt(len);
+ /* An expression whose operands cancel each other out, "Haus - Haus", has no
+ position to search around. */
+ if (len == 0) {
+ goto end;
+ }
for (a = 0; a < size; a++) vec[a] /= len;
- for (a = 0; a < N; a++) best[a].activation = -1;
for (c = from; c < upto; c++) {
if (garbage && garbage[c]) continue;
a = 0;
@@ -841,7 +917,7 @@
cutoff = words;
wl = getTargetWords(word, search_backw);
- if (wl == NULL || wl->length < 1 || wl->wordi[0] < 0 || syn_threads < 1) {
+ if (wl == NULL || wl->length < 1 || syn_threads < 1) {
free(wl);
return newSVpv("", 0);
}
@@ -923,24 +999,57 @@
knnpars pars[MAX_THREADS];
pthread_t *pt = (pthread_t *)malloc((num_threads + 1) * sizeof(pthread_t));
wordlist *wl = NULL;
- int syn_threads = (M2 ? window * 2 : 0);
- int para_threads = (no_similar_profiles ? 0 : num_threads - syn_threads);
+ int syn_threads = 0;
+ int para_threads = 0;
for (a = 0; a < MAX_THREADS; a++) para_nbs[a] = syn_nbs[a] = NULL;
- collocator *best = NULL;
- posix_memalign((void **)&best, 128, 10 * (N >= 200 ? N : 200) * sizeof(collocator));
- memset(best, 0, (N >= 200 ? N : 200) * sizeof(collocator));
-
if (N > MAX_NEIGHBOURS) N = MAX_NEIGHBOURS;
+ if (N < 1) N = 1;
+
+ /* Every paradigmatic thread fills its own slice of N entries, and the
+ syntagmatic part below works on the first MAX_NEIGHBOURS of the same
+ array. How many paradigmatic threads there are is only known further
+ down, so the array is sized for the maximum. */
+ collocator *best = NULL;
+ long best_entries = (long)N * num_threads;
+ if (best_entries < MAX_NEIGHBOURS) best_entries = MAX_NEIGHBOURS;
+ posix_memalign((void **)&best, 128, best_entries * sizeof(collocator));
+ memset(best, 0, best_entries * sizeof(collocator));
if (cutoff < 1 || cutoff > words)
cutoff = words;
wl = getTargetWords(st1, search_backw);
- if (wl == NULL || wl->length < 1)
+ if (wl == NULL)
goto end;
+ /* Tell the caller which words the query vector was built from and which
+ tokens of the query are unknown, so that "König - Mannn + Frau" is not
+ silently answered as "König + Frau". */
+ {
+ SV *added = newSVpv("", 0);
+ SV *unknown = newSVpv(wl->oov, 0);
+ for (a = 0; a < wl->length; a++) {
+ if (wl->sep[a] == '-') continue;
+ if (SvCUR(added) > 0) sv_catpvn(added, " ", 1);
+ sv_catpv(added, &vocab[wl->wordi[a] * max_w]);
+ }
+ if (latin_enc == 0) {
+ SvUTF8_on(added);
+ SvUTF8_on(unknown);
+ }
+ hv_store(result, "added", strlen("added"), added, 0);
+ hv_store(result, "unknown", strlen("unknown"), unknown, 0);
+ hv_store(result, "operands", strlen("operands"), newSViv(wl->length), 0);
+ }
+
+ if (wl->length < 1)
+ goto end;
+
+ syn_threads = (M2 ? window * 2 : 0);
+ para_threads = (no_similar_profiles ? 0 : num_threads - syn_threads);
+
slice = (para_threads > 0 ? cutoff / para_threads : cutoff);
a = posix_memalign((void **)&target_sums, 128, cutoff * sizeof(float));
@@ -964,7 +1073,7 @@
DEBUG_PRINTF("From: %ld, Upto: %ld\n", pars[a].from, pars[a].upto);
pthread_create(&pt[a], NULL, _get_neighbours, (void *)&pars[a]);
}
- if (M2) {
+ if (syn_threads) {
window_sums = new_window_sums();
for (a = 0; a < syn_threads; a++) {
pars[a + para_threads].cutoff = cutoff;
@@ -999,6 +1108,8 @@
for (a = 0, i = 0; i < N && a < N * para_threads; a++) {
int filtered = 0;
long long c = best[a].wordi;
+ if (c < 0) /* the threads found fewer candidates than were asked for */
+ break;
if ((merge_words && dedupe && i > 1) || (!merge_words && dedupe && i > 0)) {
for (j = 0; j < i && !filtered; j++)
if (strcasestr(&vocab[c * max_w], &vocab[chosen[j] * max_w]) ||
@@ -1055,7 +1166,7 @@
float total_activation = 0;
- if (M2) {
+ if (syn_threads) {
DEBUG_PRINTF("Waiting for syn threads to join\n");
DEBUG_FFLUSH();
for (a = 0; a < syn_threads; a++) pthread_join(pt[a + para_threads], (void *)&syn_nbs[a]);