nx_wordclust.nx source
↩ module page · 363 lines · 15261 B
1// nx_wordclust.nx -- WORD CLUSTERS from the estate's own PPMI model, the sovereign stand-in for the Brown clusters every
2// SemEval-2014 winner fed its tagger (DLIREC's largest single gains were name lists and word clusters from in-domain text).
3// The estate has no external corpus licensed for that, but it has knowledge/index/semppmi_v1.bin (built by nx_semppmi_build
4// from its own corpus) and ONE loader and cosine for it, nx_ppmi_lib -- composed here, never re-implemented.
5// K-MEDOIDS over PPMI cosine at three granularities (32 / 128 / 256 clusters, the Brown prefix-length idea): medoids seeded
6// by the caller's word frequencies (the training split's vocabulary), a few deterministic assignment/recentre rounds, and a
7// word not seen at build time is assigned on demand to its nearest medoid (a cluster is a function of the word, never of
8// the split it came from). Integer arithmetic only. A word the model does not know reads -1 at every level.
9// license_tier: ORIGINAL No hw writes (Rule 26). LIB.
10import "nx_syscalls.nx"
11import "nx_reviewmine_lib.nx"
12import "nx_ppmi_lib.nx"
13
14const WC_G_BYTES: i64 = 1024 // the PPMI lib's g-block (its contract: a zeroed block of at least 632 bytes)
15const WC_VOCAB_CAP: i64 = 32768 // distinct words the clusterer holds
16const WC_WORD_MAX: i64 = 64
17const WC_ARENA: i64 = 1048576
18const WC_HASH_SLOTS: i64 = 131072 // open addressing, power of two, >= 4x the vocabulary cap
19const WC_HASH_MASK: i64 = 131071
20const WC_LEVELS: i64 = 3
21const WC_K0: i64 = 32
22const WC_K1: i64 = 128
23const WC_K2: i64 = 256
24const WC_KMAX: i64 = 256
25const WC_ITERS: i64 = 3
26const WC_MEDOID_SAMPLE: i64 = 48 // members considered when a cluster recentres (bounds the quadratic step)
27const WC_NONE: i64 = 0 - 1
28const WC_CH_ZERO: i64 = 48
29const WC_ID_RADIX: i64 = 64 // a cluster id is spelled as two bytes: id / 64 and id mod 64, offset from '0'
30// per-entry columns
31const WC_E_OFF: i64 = 0
32const WC_E_LEN: i64 = 1
33const WC_E_WID: i64 = 2
34const WC_E_FREQ: i64 = 3
35const WC_E_C0: i64 = 4
36const WC_E_C1: i64 = 5
37const WC_E_C2: i64 = 6
38const WC_E_N: i64 = 7
39// out[] of wc_build
40const WC_O_VOCAB: i64 = 0 // words added
41const WC_O_INMODEL: i64 = 1 // words the model knows (wid >= 0)
42const WC_O_K0: i64 = 2 // medoids actually used at each level
43const WC_O_K1: i64 = 3
44const WC_O_K2: i64 = 4
45const WC_O_N: i64 = 5
46// fixture model: NXPPMI1 header 32 B [magic, nv, nt], then vocab-hash[nv] (sorted), row-index[nv+1], norm2[nv], ctx[nt], val[nt]
47const WC_FX_HDR: i64 = 32
48const WC_FX_VAL: i64 = 1000
49const WC_MAGIC_N: i64 = 78
50const WC_MAGIC_X: i64 = 88
51const WC_MAGIC_P: i64 = 80
52const WC_MAGIC_M: i64 = 77
53const WC_MAGIC_I: i64 = 73
54const WC_MAGIC_1: i64 = 49
55
56static wc_g: *i64
57static wc_ent: *i64 // WC_VOCAB_CAP * WC_E_N
58static wc_arena: *u8
59static wc_used: i64
60static wc_n: i64
61static wc_hash: *i64 // slot -> entry index + 1 (0 = empty)
62static wc_med: *i64 // WC_LEVELS * WC_KMAX medoid entry indices
63static wc_kused: *i64 // medoids used per level
64static wc_loaded: i64
65static wc_built: i64
66static wc_order: *i64 // scratch: entry indices sorted by frequency
67static wc_ordertmp: *i64
68static wc_sum: *i64 // scratch: per-member cosine sums when recentring
69// the granularities in force (the defaults unless a caller sets them; a gate sets small ones for a planted vocabulary)
70static wc_k0: i64
71static wc_k1: i64
72static wc_k2: i64
73
74// choose the three granularities (each clamped to the in-model vocabulary at build time)
75func wc_set_k(k0: i64, k1: i64, k2: i64) -> i64 { wc_k0 = k0; wc_k1 = k1; wc_k2 = k2; return 0 }
76
77func wc_reset() -> i64 {
78 wc_k0 = WC_K0
79 wc_k1 = WC_K1
80 wc_k2 = WC_K2
81 if (wc_g as i64) == 0 {
82 wc_g = sys_mmap(WC_G_BYTES) as *i64
83 wc_ent = sys_mmap(WC_VOCAB_CAP * WC_E_N * RM_I64_BYTES) as *i64
84 wc_arena = sys_mmap(WC_ARENA)
85 wc_hash = sys_mmap(WC_HASH_SLOTS * RM_I64_BYTES) as *i64
86 wc_med = sys_mmap(WC_LEVELS * WC_KMAX * RM_I64_BYTES) as *i64
87 wc_kused = sys_mmap(WC_LEVELS * RM_I64_BYTES) as *i64
88 wc_order = sys_mmap(WC_VOCAB_CAP * RM_I64_BYTES) as *i64
89 wc_ordertmp = sys_mmap(WC_VOCAB_CAP * RM_I64_BYTES) as *i64
90 wc_sum = sys_mmap(WC_MEDOID_SAMPLE * RM_I64_BYTES) as *i64
91 }
92 var i: i64 = 0
93 while i < WC_HASH_SLOTS { wc_hash[i] = 0; i = i + 1 }
94 wc_used = 0
95 wc_n = 0
96 wc_built = 0
97 return 0
98}
99// load the PPMI model (the ONE loader); 1 on success, 0 fail-closed
100func wc_load_model(path: *u8) -> i64 {
101 wc_loaded = ppl_load(wc_g, path)
102 return wc_loaded
103}
104func wc_lc(c: i64) -> i64 { if c >= 65 { if c <= 90 { return c + 32 } } return c }
105// find the entry of a word (lowercased compare), or -1
106func wc_find(s: *u8, n: i64) -> i64 {
107 if n <= 0 { return WC_NONE }
108 if n > WC_WORD_MAX { return WC_NONE }
109 let lb: *u8 = sys_mmap(WC_WORD_MAX)
110 var i: i64 = 0
111 while i < n { lb[i] = wc_lc(s[i] as i64) as u8; i = i + 1 }
112 var slot: i64 = rm_hash(lb, n) & WC_HASH_MASK
113 var probes: i64 = 0
114 while probes < WC_HASH_SLOTS {
115 let e: i64 = wc_hash[slot] - 1
116 if e < 0 { return WC_NONE }
117 if wc_ent[e * WC_E_N + WC_E_LEN] == n {
118 var same: i64 = 1
119 var k: i64 = 0
120 let off: i64 = wc_ent[e * WC_E_N + WC_E_OFF]
121 while k < n { if wc_arena[off + k] != lb[k] { same = 0 } k = k + 1 }
122 if same == 1 { return e }
123 }
124 slot = (slot + 1) & WC_HASH_MASK
125 probes = probes + 1
126 }
127 return WC_NONE
128}
129// add a word occurrence (frequency counts) and resolve its PPMI id once; returns the entry index or -1 when full
130func wc_add(s: *u8, n: i64) -> i64 {
131 let found: i64 = wc_find(s, n)
132 if found >= 0 { wc_ent[found * WC_E_N + WC_E_FREQ] = wc_ent[found * WC_E_N + WC_E_FREQ] + 1; return found }
133 if n <= 0 { return WC_NONE }
134 if n > WC_WORD_MAX { return WC_NONE }
135 if wc_n >= WC_VOCAB_CAP { return WC_NONE }
136 if wc_used + n >= WC_ARENA { return WC_NONE }
137 var i: i64 = 0
138 while i < n { wc_arena[wc_used + i] = wc_lc(s[i] as i64) as u8; i = i + 1 }
139 let e: i64 = wc_n
140 wc_ent[e * WC_E_N + WC_E_OFF] = wc_used
141 wc_ent[e * WC_E_N + WC_E_LEN] = n
142 wc_ent[e * WC_E_N + WC_E_FREQ] = 1
143 var wid: i64 = WC_NONE
144 if wc_loaded == 1 { wid = ppl_wid_range(wc_g, wc_arena, wc_used, wc_used + n) }
145 wc_ent[e * WC_E_N + WC_E_WID] = wid
146 wc_ent[e * WC_E_N + WC_E_C0] = WC_NONE
147 wc_ent[e * WC_E_N + WC_E_C1] = WC_NONE
148 wc_ent[e * WC_E_N + WC_E_C2] = WC_NONE
149 var slot: i64 = rm_hash((wc_arena as i64 + wc_used) as *u8, n) & WC_HASH_MASK
150 while wc_hash[slot] != 0 { slot = (slot + 1) & WC_HASH_MASK }
151 wc_hash[slot] = e + 1
152 wc_used = wc_used + n
153 wc_n = wc_n + 1
154 return e
155}
156func wc_ecol(e: i64, col: i64) -> i64 { return wc_ent[e * WC_E_N + col] }
157func wc_cluster_col(level: i64) -> i64 { if level == 0 { return WC_E_C0 } if level == 1 { return WC_E_C1 } return WC_E_C2 }
158func wc_k_of(level: i64) -> i64 {
159 var k: i64 = wc_k2
160 if level == 0 { k = wc_k0 }
161 if level == 1 { k = wc_k1 }
162 if k > WC_KMAX { k = WC_KMAX }
163 if k < 1 { k = 1 }
164 return k
165}
166// nearest medoid of a PPMI id at one level (cosine argmax, ties to the first medoid); -1 when unknown
167func wc_nearest(level: i64, wid: i64) -> i64 {
168 if wid < 0 { return WC_NONE }
169 let k: i64 = wc_kused[level]
170 var best: i64 = WC_NONE
171 var bestv: i64 = WC_NONE
172 var m: i64 = 0
173 while m < k {
174 let mw: i64 = wc_ecol(wc_med[level * WC_KMAX + m], WC_E_WID)
175 let c: i64 = ppl_dcos(wc_g, wid, mw)
176 if c > bestv { bestv = c; best = m }
177 m = m + 1
178 }
179 return best
180}
181// order the in-model entries by frequency, descending, stable (a merge sort on indices)
182func wc_sort_by_freq() -> i64 {
183 var n: i64 = 0
184 var e: i64 = 0
185 while e < wc_n { if wc_ecol(e, WC_E_WID) >= 0 { wc_order[n] = e; n = n + 1 } e = e + 1 }
186 var width: i64 = 1
187 while width < n {
188 var lo: i64 = 0
189 while lo < n {
190 let mid: i64 = lo + width
191 var hi: i64 = lo + width * 2
192 if mid > n { } else {
193 if hi > n { hi = n }
194 var a: i64 = lo
195 var b: i64 = mid
196 var o: i64 = lo
197 while (a < mid) | (b < hi) {
198 var takea: i64 = 0
199 if b >= hi { takea = 1 } else { if a < mid { if wc_ecol(wc_order[a], WC_E_FREQ) >= wc_ecol(wc_order[b], WC_E_FREQ) { takea = 1 } } }
200 if takea == 1 { wc_ordertmp[o] = wc_order[a]; a = a + 1 } else { wc_ordertmp[o] = wc_order[b]; b = b + 1 }
201 o = o + 1
202 }
203 var c: i64 = lo
204 while c < hi { wc_order[c] = wc_ordertmp[c]; c = c + 1 }
205 }
206 lo = lo + width * 2
207 }
208 width = width * 2
209 }
210 return n
211}
212// k-medoids at one level: seed with the K most frequent in-model words, assign, recentre, repeat WC_ITERS times
213func wc_build_level(level: i64, ninmodel: i64) -> i64 {
214 var k: i64 = wc_k_of(level)
215 if k > ninmodel { k = ninmodel }
216 wc_kused[level] = k
217 var m: i64 = 0
218 while m < k { wc_med[level * WC_KMAX + m] = wc_order[m]; m = m + 1 }
219 let col: i64 = wc_cluster_col(level)
220 var it: i64 = 0
221 while it < WC_ITERS {
222 // assign every in-model word to its nearest medoid
223 var i: i64 = 0
224 while i < ninmodel {
225 let e: i64 = wc_order[i]
226 wc_ent[e * WC_E_N + col] = wc_nearest(level, wc_ecol(e, WC_E_WID))
227 i = i + 1
228 }
229 // recentre: for each cluster, the member (among the first WC_MEDOID_SAMPLE by frequency) with the largest
230 // cosine sum to those members becomes the medoid
231 var c: i64 = 0
232 while c < k {
233 let mem: *i64 = sys_mmap(WC_MEDOID_SAMPLE * RM_I64_BYTES) as *i64
234 var nm: i64 = 0
235 var j: i64 = 0
236 while (j < ninmodel) & (nm < WC_MEDOID_SAMPLE) {
237 let e2: i64 = wc_order[j]
238 if wc_ecol(e2, col) == c { mem[nm] = e2; nm = nm + 1 }
239 j = j + 1
240 }
241 if nm > 1 {
242 var a: i64 = 0
243 while a < nm {
244 var s: i64 = 0
245 var b: i64 = 0
246 while b < nm { if b != a { s = s + ppl_dcos(wc_g, wc_ecol(mem[a], WC_E_WID), wc_ecol(mem[b], WC_E_WID)) } b = b + 1 }
247 wc_sum[a] = s
248 a = a + 1
249 }
250 var bestm: i64 = 0
251 var bests: i64 = wc_sum[0]
252 a = 1
253 while a < nm { if wc_sum[a] > bests { bests = wc_sum[a]; bestm = a } a = a + 1 }
254 wc_med[level * WC_KMAX + c] = mem[bestm]
255 }
256 c = c + 1
257 }
258 it = it + 1
259 }
260 // final assignment against the settled medoids
261 var i2: i64 = 0
262 while i2 < ninmodel {
263 let e3: i64 = wc_order[i2]
264 wc_ent[e3 * WC_E_N + col] = wc_nearest(level, wc_ecol(e3, WC_E_WID))
265 i2 = i2 + 1
266 }
267 return k
268}
269// build all three levels from the words added so far; out is WC_O_N wide
270func wc_build(out: *i64) -> i64 {
271 var q: i64 = 0
272 while q < WC_O_N { out[q] = 0; q = q + 1 }
273 out[WC_O_VOCAB] = wc_n
274 if wc_loaded != 1 { return 0 }
275 let ninmodel: i64 = wc_sort_by_freq()
276 out[WC_O_INMODEL] = ninmodel
277 if ninmodel <= 0 { return 0 }
278 out[WC_O_K0] = wc_build_level(0, ninmodel)
279 out[WC_O_K1] = wc_build_level(1, ninmodel)
280 out[WC_O_K2] = wc_build_level(2, ninmodel)
281 wc_built = 1
282 return 1
283}
284// the cluster id of a word at a level, assigning an unseen word on demand (cached); -1 when unknown to the model
285func wc_cluster(s: *u8, n: i64, level: i64) -> i64 {
286 if wc_built != 1 { return WC_NONE }
287 var e: i64 = wc_find(s, n)
288 if e < 0 {
289 e = wc_add(s, n)
290 if e < 0 { return WC_NONE }
291 wc_ent[e * WC_E_N + WC_E_FREQ] = 0
292 let wid: i64 = wc_ecol(e, WC_E_WID)
293 wc_ent[e * WC_E_N + WC_E_C0] = wc_nearest(0, wid)
294 wc_ent[e * WC_E_N + WC_E_C1] = wc_nearest(1, wid)
295 wc_ent[e * WC_E_N + WC_E_C2] = wc_nearest(2, wid)
296 }
297 return wc_ecol(e, wc_cluster_col(level))
298}
299// spell a cluster id as two bytes into out (so a feature family can hash it); -1 spells as a single '@'
300func wc_spell(id: i64, out: *u8) -> i64 {
301 if id < 0 { out[0] = 64; return 1 }
302 out[0] = (WC_CH_ZERO + id / WC_ID_RADIX) as u8
303 out[1] = (WC_CH_ZERO + id % WC_ID_RADIX) as u8
304 return 2
305}
306// ---- FIXTURE: write a tiny NXPPMI1 model so a gate can drive the clusterer without the 43 MB estate model ----
307// words[i] (offsets/lens into one buffer) get the context vector ctx[i] (one context id each, value WC_FX_VAL): two words
308// sharing a context id are identical vectors (cosine 1000), different ids are orthogonal (cosine 0). Rows are written in
309// the model's sorted-hash order so the loader's binary search finds them.
310func wc_plant_model(path: *u8, buf: *u8, offs: *i64, lens: *i64, ctx: *i64, nw: i64) -> i64 {
311 let hashes: *i64 = sys_mmap(nw * RM_I64_BYTES) as *i64
312 let order: *i64 = sys_mmap(nw * RM_I64_BYTES) as *i64
313 var i: i64 = 0
314 while i < nw { hashes[i] = db_semhash(buf, offs[i], lens[i]); order[i] = i; i = i + 1 }
315 // selection sort of order[] by hash ascending (nw is tiny)
316 var a: i64 = 0
317 while a < nw {
318 var b: i64 = a + 1
319 while b < nw {
320 if hashes[order[b]] < hashes[order[a]] { let t: i64 = order[a]; order[a] = order[b]; order[b] = t }
321 b = b + 1
322 }
323 a = a + 1
324 }
325 let nv: i64 = nw
326 let nt: i64 = nw
327 let total: i64 = WC_FX_HDR + nv * 8 + (nv + 1) * 8 + nv * 8 + nt * 8 + nt * 8
328 let blob: *u8 = sys_mmap(total + 64)
329 var z: i64 = 0
330 while z < total { blob[z] = 0; z = z + 1 }
331 blob[0] = WC_MAGIC_N as u8; blob[1] = WC_MAGIC_X as u8; blob[2] = WC_MAGIC_P as u8; blob[3] = WC_MAGIC_P as u8
332 blob[4] = WC_MAGIC_M as u8; blob[5] = WC_MAGIC_I as u8; blob[6] = WC_MAGIC_1 as u8; blob[7] = 0
333 let hdr: *i64 = (blob as i64 + 8) as *i64
334 hdr[0] = nv
335 hdr[1] = nt
336 var off: i64 = WC_FX_HDR
337 let vh: *i64 = (blob as i64 + off) as *i64; off = off + nv * 8
338 let ridx: *i64 = (blob as i64 + off) as *i64; off = off + (nv + 1) * 8
339 let nrm: *i64 = (blob as i64 + off) as *i64; off = off + nv * 8
340 let tctx: *i64 = (blob as i64 + off) as *i64; off = off + nt * 8
341 let tval: *i64 = (blob as i64 + off) as *i64
342 var r: i64 = 0
343 while r < nv {
344 let w: i64 = order[r]
345 vh[r] = hashes[w]
346 ridx[r] = r
347 nrm[r] = WC_FX_VAL * WC_FX_VAL
348 tctx[r] = ctx[w]
349 tval[r] = WC_FX_VAL
350 r = r + 1
351 }
352 ridx[nv] = nv
353 let fd: i64 = sys_openat_wr(path, MODE_0644)
354 if fd < 0 { return 0 }
355 var wrote: i64 = 0
356 while wrote < total {
357 let n: i64 = sys_write(fd, (blob as i64 + wrote) as *u8, total - wrote)
358 if n <= 0 { sys_close(fd); return 0 }
359 wrote = wrote + n
360 }
361 sys_close(fd)
362 return 1
363}