// Across-cluster constraint experiment. See PREREG.md.
//
// One process = one seed. Generates a planted-grammar corpus (gold classes + gold dependency trees),
// then for each training tier: learns a grouping (exchange algorithm), builds the arms, counts window
// pairs, gates them (PMI > 0, G > 10.83), parses the held-out set (Eisner, root edges score 0) and
// scores links against gold. Prints TSV rows to stdout.
//
// ac <seed> [--tiers 1000,3000,...] [--mut-drop] [--heldout N]
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define W 6
#define K 30
#define MAXN 128
#define NEG (-1e30)
#define ALPHA 0.1
#define GCRIT 10.83
// ---------------------------------------------------------------- rng
typedef struct { uint64_t s; } rng_t;
static uint64_t rnext (rng_t *r) {
uint64_t z = (r->s += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
static double runif (rng_t *r) { return (rnext(r) >> 11) * (1.0 / 9007199254740992.0); }
static int rpick (rng_t *r, int n) { return (int) (runif(r) * n); }
// ---------------------------------------------------------------- grammar
enum {
N_ANIM_SG, N_ANIM_PL, N_FOOD_SG, N_FOOD_PL, N_PLACE_SG, N_PLACE_PL, N_THING_SG, N_THING_PL,
DET_SG, DET_PL, DET_ANY, ADJ_SIZE, ADJ_COLOR, ADJ_MOOD, PRON_SG, PRON_PL,
V_I_SG, V_I_PL, V_EAT_SG, V_EAT_PL, V_GO_SG, V_GO_PL, V_SEE_SG, V_SEE_PL, V_SAY_SG, V_SAY_PL,
PREP_LOC, PREP_WITH, ADV, COMP, NCLS
};
enum { ANIM, FOOD, PLACE, THING };
enum { VI, VEAT, VGO, VSEE, VSAY };
static const int class_size[NCLS] = {
120, 120, 120, 120, 120, 120, 120, 120,
3, 3, 1, 60, 60, 60, 4, 4,
40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
8, 3, 40, 1
};
static int is_open (int c) { return c <= N_THING_PL || (c >= ADJ_SIZE && c <= ADJ_MOOD) || (c >= V_I_SG && c <= V_SAY_PL) || c == ADV; }
static int V; // vocabulary size
static int *primary; // word -> primary gold class
static int *cw[NCLS], ncw[NCLS]; // class -> member words (Zipf rank order)
static double *ccum[NCLS]; // class -> cumulative Zipf weights
static void build_world (void) {
rng_t r = { 12345 };
V = 0;
for (int c = 0; c < NCLS; c++) V += class_size[c];
primary = malloc(sizeof(int) * V);
int w = 0;
for (int c = 0; c < NCLS; c++) {
cw[c] = malloc(sizeof(int) * (class_size[c] + V));
ncw[c] = 0;
for (int k = 0; k < class_size[c]; k++) { primary[w] = c; cw[c][ncw[c]++] = w++; }
}
// Polysemy: 10% of open-class words also join a second open class, at the end of its rank list.
for (int x = 0; x < V; x++) {
if (!is_open(primary[x]) || runif(&r) >= 0.1) continue;
int c;
do c = rpick(&r, NCLS); while (!is_open(c) || c == primary[x]);
cw[c][ncw[c]++] = x;
}
for (int c = 0; c < NCLS; c++) {
ccum[c] = malloc(sizeof(double) * ncw[c]);
double s = 0;
for (int k = 0; k < ncw[c]; k++) ccum[c][k] = (s += 1.0 / (k + 1));
for (int k = 0; k < ncw[c]; k++) ccum[c][k] /= s;
}
}
static int sample_word (rng_t *r, int c) {
double u = runif(r);
int lo = 0, hi = ncw[c] - 1;
while (lo < hi) { int m = (lo + hi) / 2; if (ccum[c][m] < u) lo = m + 1; else hi = m; }
return cw[c][lo];
}
typedef struct { int n, w[MAXN], c[MAXN], h[MAXN]; } sent_t;
static int emit (rng_t *r, sent_t *s, int c) {
int i = s->n++;
if (i >= MAXN) { fprintf(stderr, "sentence overflow\n"); exit(1); }
s->w[i] = sample_word(r, c); s->c[i] = c; s->h[i] = -1;
return i;
}
static int gen_pp_with (rng_t *r, sent_t *s, int depth);
static int gen_np (rng_t *r, sent_t *s, int sem, int pl, int depth) {
int d = emit(r, s, runif(r) < 0.5 ? DET_ANY : (pl ? DET_PL : DET_SG));
int adj[2], na = 0;
if (runif(r) < 0.4) { na = 1; if (runif(r) < 0.25) na = 2; }
for (int k = 0; k < na; k++) adj[k] = emit(r, s, ADJ_SIZE + rpick(r, sem == ANIM ? 3 : 2));
int n = emit(r, s, N_ANIM_SG + 2 * sem + pl);
s->h[d] = n;
for (int k = 0; k < na; k++) s->h[adj[k]] = n;
if (depth < 2 && runif(r) < 0.1) { int p = gen_pp_with(r, s, depth + 1); s->h[p] = n; }
return n;
}
static int gen_pp_loc (rng_t *r, sent_t *s, int depth) {
int p = emit(r, s, PREP_LOC);
int n = gen_np(r, s, PLACE, rpick(r, 2), depth);
s->h[n] = p;
return p;
}
static int gen_pp_with (rng_t *r, sent_t *s, int depth) {
int p = emit(r, s, PREP_WITH);
int n = gen_np(r, s, runif(r) < 0.5 ? ANIM : THING, rpick(r, 2), depth);
s->h[n] = p;
return p;
}
static int gen_s (rng_t *r, sent_t *s, int depth) {
int pl = rpick(r, 2);
int subj = runif(r) < 0.2 ? emit(r, s, PRON_SG + pl) : gen_np(r, s, ANIM, pl, depth);
double wt[5] = { 0.2, 0.2, 0.2, 0.25, depth < 2 ? 0.15 : 0 }, tot = 0;
for (int k = 0; k < 5; k++) tot += wt[k];
double u = runif(r) * tot;
int vt = 0;
while (vt < 4 && u >= wt[vt]) u -= wt[vt++];
int v = emit(r, s, V_I_SG + 2 * vt + pl);
s->h[subj] = v;
int o;
switch (vt) {
case VI: if (runif(r) < 0.3) { o = emit(r, s, ADV); s->h[o] = v; } break;
case VEAT: o = gen_np(r, s, FOOD, rpick(r, 2), depth); s->h[o] = v; break;
case VGO: o = gen_pp_loc(r, s, depth); s->h[o] = v; break;
case VSEE:
o = gen_np(r, s, rpick(r, 4), rpick(r, 2), depth); s->h[o] = v;
if (runif(r) < 0.3) { o = gen_pp_with(r, s, depth); s->h[o] = v; }
break;
case VSAY: {
int c = emit(r, s, COMP); s->h[c] = v;
o = gen_s(r, s, depth + 1); s->h[o] = c;
break;
}
}
if (vt != VSAY && runif(r) < 0.15) { o = emit(r, s, ADV); s->h[o] = v; }
return v;
}
// ---------------------------------------------------------------- corpus
typedef struct { int ns, ntok, *off, *w, *c, *h; } corpus_t;
static corpus_t gen_corpus (uint64_t seed, int ns) {
rng_t r = { seed };
corpus_t C = { ns, 0 };
int cap = ns * 16;
C.off = malloc(sizeof(int) * (ns + 1));
C.w = malloc(sizeof(int) * cap); C.c = malloc(sizeof(int) * cap); C.h = malloc(sizeof(int) * cap);
sent_t s;
for (int i = 0; i < ns; i++) {
s.n = 0;
gen_s(&r, &s, 0);
if (C.ntok + s.n > cap) {
cap *= 2;
C.w = realloc(C.w, sizeof(int) * cap); C.c = realloc(C.c, sizeof(int) * cap); C.h = realloc(C.h, sizeof(int) * cap);
}
C.off[i] = C.ntok;
for (int k = 0; k < s.n; k++) {
C.w[C.ntok + k] = s.w[k]; C.c[C.ntok + k] = s.c[k];
C.h[C.ntok + k] = s.h[k] < 0 ? -1 : s.h[k]; // head as an offset within the sentence
}
C.ntok += s.n;
}
C.off[ns] = C.ntok;
return C;
}
static corpus_t prefix (corpus_t C, int ns) { C.ns = ns; C.ntok = C.off[ns]; return C; }
// N1 null: shuffle tokens across the whole corpus, keeping sentence lengths. Heads are meaningless.
static corpus_t shuffled (corpus_t C, uint64_t seed) {
rng_t r = { seed };
corpus_t S = C;
S.w = malloc(sizeof(int) * C.ntok); S.c = malloc(sizeof(int) * C.ntok);
memcpy(S.w, C.w, sizeof(int) * C.ntok); memcpy(S.c, C.c, sizeof(int) * C.ntok);
for (int i = C.ntok - 1; i > 0; i--) {
int j = rpick(&r, i + 1);
int t = S.w[i]; S.w[i] = S.w[j]; S.w[j] = t;
t = S.c[i]; S.c[i] = S.c[j]; S.c[j] = t;
}
return S;
}
// ---------------------------------------------------------------- arms: token -> symbol
typedef struct { const char *name; int A; int *map; int gold_tok; } arm_t; // gold_tok: symbol = token's gold class
static int sym (const arm_t *a, const corpus_t *C, int t) { return a->gold_tok ? C->c[t] : (a->map ? a->map[C->w[t]] : C->w[t]); }
// ---------------------------------------------------------------- exchange clustering (Martin/Liermann/Ney)
static double xlx (double x) { return x > 0 ? x * log(x) : 0; }
static double exch_F (const double *N, int A) {
double f = 0;
for (int a = 0; a < A; a++) {
double row = 0, col = 0;
for (int b = 0; b < A; b++) { f += xlx(N[a * A + b]); row += N[a * A + b]; col += N[b * A + a]; }
f -= xlx(row) + xlx(col);
}
return f;
}
// Words 0..V-1 plus boundary word V (fixed in class K). Returns word -> class in [0, K).
static int *exchange (const corpus_t *C, int *passes_out) {
int VB = V + 1, A = K + 1;
uint32_t *bg = calloc((size_t) VB * VB, sizeof(uint32_t));
long *cnt = calloc(VB, sizeof(long));
for (int i = 0; i < C->ns; i++) {
int prev = V;
for (int t = C->off[i]; t < C->off[i + 1]; t++) { bg[(size_t) prev * VB + C->w[t]]++; cnt[C->w[t]]++; prev = C->w[t]; }
bg[(size_t) prev * VB + V]++;
}
// successor / predecessor lists
int *sn = calloc(VB, sizeof(int)), *pn = calloc(VB, sizeof(int));
for (int a = 0; a < VB; a++) for (int b = 0; b < VB; b++) if (bg[(size_t) a * VB + b]) { sn[a]++; pn[b]++; }
int **sw = malloc(sizeof(int *) * VB), **pw = malloc(sizeof(int *) * VB);
uint32_t **sc = malloc(sizeof(uint32_t *) * VB), **pc = malloc(sizeof(uint32_t *) * VB);
for (int a = 0; a < VB; a++) {
sw[a] = malloc(sizeof(int) * (sn[a] + 1)); sc[a] = malloc(sizeof(uint32_t) * (sn[a] + 1));
pw[a] = malloc(sizeof(int) * (pn[a] + 1)); pc[a] = malloc(sizeof(uint32_t) * (pn[a] + 1));
sn[a] = pn[a] = 0;
}
for (int a = 0; a < VB; a++) for (int b = 0; b < VB; b++) {
uint32_t n = bg[(size_t) a * VB + b];
if (!n) continue;
sw[a][sn[a]] = b; sc[a][sn[a]++] = n;
pw[b][pn[b]] = a; pc[b][pn[b]++] = n;
}
free(bg);
// init: frequency rank mod K
int *order = malloc(sizeof(int) * V);
for (int x = 0; x < V; x++) order[x] = x;
for (int i = 1; i < V; i++) { // insertion sort by count desc (V is small)
int x = order[i], j = i;
while (j > 0 && cnt[order[j - 1]] < cnt[x]) { order[j] = order[j - 1]; j--; }
order[j] = x;
}
int *cls = malloc(sizeof(int) * VB);
for (int i = 0; i < V; i++) cls[order[i]] = i % K;
cls[V] = K;
double *N = calloc((size_t) A * A, sizeof(double));
for (int a = 0; a < VB; a++) for (int k = 0; k < sn[a]; k++) N[cls[a] * A + cls[sw[a][k]]] += sc[a][k];
double sv[K + 1], pv[K + 1];
int pass;
for (pass = 0; pass < 30; pass++) {
int moves = 0;
for (int i = 0; i < V; i++) {
int x = order[i];
if (!cnt[x]) continue;
int a = cls[x];
double self = 0;
memset(sv, 0, sizeof sv); memset(pv, 0, sizeof pv);
for (int k = 0; k < sn[x]; k++) { if (sw[x][k] == x) self += sc[x][k]; else sv[cls[sw[x][k]]] += sc[x][k]; }
for (int k = 0; k < pn[x]; k++) if (pw[x][k] != x) pv[cls[pw[x][k]]] += pc[x][k];
// remove x from a
for (int c = 0; c < A; c++) { N[a * A + c] -= sv[c]; N[c * A + a] -= pv[c]; }
N[a * A + a] -= self;
int best = a; double bestF = -1e300;
for (int b = 0; b < K; b++) {
for (int c = 0; c < A; c++) { N[b * A + c] += sv[c]; N[c * A + b] += pv[c]; }
N[b * A + b] += self;
double f = exch_F(N, A);
if (f > bestF + 1e-9 || (b == a && f >= bestF - 1e-9)) { bestF = f; best = b; }
for (int c = 0; c < A; c++) { N[b * A + c] -= sv[c]; N[c * A + b] -= pv[c]; }
N[b * A + b] -= self;
}
for (int c = 0; c < A; c++) { N[best * A + c] += sv[c]; N[c * A + best] += pv[c]; }
N[best * A + best] += self;
if (best != a) { cls[x] = best; moves++; }
}
if (!moves) break;
}
*passes_out = pass;
for (int a = 0; a < VB; a++) { free(sw[a]); free(sc[a]); free(pw[a]); free(pc[a]); }
free(sw); free(sc); free(pw); free(pc); free(sn); free(pn); free(cnt); free(order); free(N);
return cls;
}
// ---------------------------------------------------------------- part A: class-bigram held-out bits/word
static double bits_unigram (const corpus_t *tr, const corpus_t *ho) {
double *n = calloc(V + 1, sizeof(double)), tot = 0;
for (int t = 0; t < tr->ntok; t++) n[tr->w[t]]++;
n[V] = tr->ns; tot = tr->ntok + tr->ns;
double h = 0;
for (int t = 0; t < ho->ntok; t++) h -= log2((n[ho->w[t]] + ALPHA) / (tot + ALPHA * (V + 1)));
h -= ho->ns * log2((n[V] + ALPHA) / (tot + ALPHA * (V + 1)));
free(n);
return h / ho->ntok;
}
static double bits_class_bigram (const arm_t *a, const corpus_t *tr, const corpus_t *ho) {
int A = a->A, B = A + 1; // symbol A = boundary
double *T = calloc((size_t) B * B, sizeof(double)), *Tr = calloc(B, sizeof(double));
double *E = calloc((size_t) A * V, sizeof(double)), *Er = calloc(A, sizeof(double));
for (int i = 0; i < tr->ns; i++) {
int prev = A;
for (int t = tr->off[i]; t < tr->off[i + 1]; t++) {
int s = sym(a, tr, t);
T[(size_t) prev * B + s]++; Tr[prev]++;
E[(size_t) s * V + tr->w[t]]++; Er[s]++;
prev = s;
}
T[(size_t) prev * B + A]++; Tr[prev]++;
}
double h = 0;
for (int i = 0; i < ho->ns; i++) {
int prev = A;
for (int t = ho->off[i]; t < ho->off[i + 1]; t++) {
int s = sym(a, ho, t);
h -= log2((T[(size_t) prev * B + s] + ALPHA) / (Tr[prev] + ALPHA * B));
h -= log2((E[(size_t) s * V + ho->w[t]] + ALPHA) / (Er[s] + ALPHA * V));
prev = s;
}
h -= log2((T[(size_t) prev * B + A] + ALPHA) / (Tr[prev] + ALPHA * B));
}
free(T); free(Tr); free(E); free(Er);
return h / ho->ntok;
}
// ---------------------------------------------------------------- part B: window pairs, gate, parse
typedef struct { int A; uint32_t *M; double *R, *Cm, N; } pairs_t;
static int mut_drop = 0;
static pairs_t count_pairs (const arm_t *a, const corpus_t *C) {
pairs_t P = { a->A };
P.M = calloc((size_t) a->A * a->A, sizeof(uint32_t));
P.R = calloc(a->A, sizeof(double)); P.Cm = calloc(a->A, sizeof(double));
rng_t mr = { 777 };
long expect = 0, got = 0;
for (int i = 0; i < C->ns; i++) {
int o = C->off[i], n = C->off[i + 1] - o;
for (int x = 0; x < n; x++) for (int y = x + 1; y < n && y - x <= W; y++) {
expect++;
if (mut_drop && runif(&mr) < 0.01) continue;
int sa = sym(a, C, o + x), sb = sym(a, C, o + y);
P.M[(size_t) sa * a->A + sb]++; P.R[sa]++; P.Cm[sb]++; got++;
}
}
P.N = got;
// C2 count guard: total pair count == number of in-window token pairs.
double tot = 0;
for (size_t k = 0; k < (size_t) a->A * a->A; k++) tot += P.M[k];
if (tot != (double) expect) {
printf("GUARD\tC2\tFAIL\t%s\texpect=%ld\tgot=%.0f\n", a->name, expect, tot);
fflush(stdout);
exit(2);
}
return P;
}
static void free_pairs (pairs_t *P) { free(P->M); free(P->R); free(P->Cm); }
// Gated PMI of one pair type, or NEG if it fails the gate.
static double gated_pmi (const pairs_t *P, int a, int b) {
double n = P->M[(size_t) a * P->A + b];
if (n <= 0) return NEG;
double ra = P->R[a], cb = P->Cm[b], N = P->N;
double pmi = log2(n * N / (ra * cb));
if (pmi <= 0) return NEG;
double o[4] = { n, ra - n, cb - n, N - ra - cb + n };
double e[4] = { ra * cb / N, ra * (N - cb) / N, (N - ra) * cb / N, (N - ra) * (N - cb) / N };
double g = 0;
for (int k = 0; k < 4; k++) if (o[k] > 0) g += o[k] * log(o[k] / e[k]);
g *= 2;
return g > GCRIT ? pmi : NEG;
}
// Eisner, first order, projective. Index 0 = root. sc[h][d] = arc score. Fills head[1..n-1].
static double Cc[MAXN + 1][MAXN + 1][2], Ic[MAXN + 1][MAXN + 1][2];
static int Cb[MAXN + 1][MAXN + 1][2], Ib[MAXN + 1][MAXN + 1][2];
static double sc[MAXN + 1][MAXN + 1];
static void backtrack (int s, int t, int dir, int complete, int *head) {
if (s == t) return;
if (complete) {
int r = Cb[s][t][dir];
if (dir == 0) { backtrack(s, r, 0, 1, head); backtrack(r, t, 0, 0, head); }
else { backtrack(s, r, 1, 0, head); backtrack(r, t, 1, 1, head); }
} else {
int r = Ib[s][t][dir];
if (dir == 0) head[s] = t; else head[t] = s;
backtrack(s, r, 1, 1, head); backtrack(r + 1, t, 0, 1, head);
}
}
static void eisner (int n, int *head) {
for (int s = 0; s < n; s++) for (int d = 0; d < 2; d++) Cc[s][s][d] = 0;
for (int k = 1; k < n; k++) for (int s = 0; s + k < n; s++) {
int t = s + k;
double best = -1e300; int br = s;
for (int r = s; r < t; r++) { double v = Cc[s][r][1] + Cc[r + 1][t][0]; if (v > best) { best = v; br = r; } }
Ic[s][t][0] = best + sc[t][s]; Ib[s][t][0] = br; // arc t -> s
Ic[s][t][1] = best + sc[s][t]; Ib[s][t][1] = br; // arc s -> t
best = -1e300; br = s;
for (int r = s; r < t; r++) { double v = Cc[s][r][0] + Ic[r][t][0]; if (v > best) { best = v; br = r; } }
Cc[s][t][0] = best; Cb[s][t][0] = br;
best = -1e300; br = s + 1;
for (int r = s + 1; r <= t; r++) { double v = Ic[s][r][1] + Cc[r][t][1]; if (v > best) { best = v; br = r; } }
Cc[s][t][1] = best; Cb[s][t][1] = br;
}
for (int i = 0; i < n; i++) head[i] = -1;
backtrack(0, n - 1, 1, 1, head);
}
typedef struct { long tp, pred, gold, gold_in_w; } link_t;
// score(i, j) for token offsets i < j within a sentence -> edge weight or NEG.
typedef double (*edge_fn) (const corpus_t *C, int o, int i, int j, void *ctx, int window);
static link_t parse_eval (const corpus_t *C, edge_fn f, void *ctx, int window) {
link_t L = { 0 };
int head[MAXN + 1];
for (int s = 0; s < C->ns; s++) {
int o = C->off[s], n = C->off[s + 1] - o, m = n + 1;
for (int h = 0; h < m; h++) for (int d = 0; d < m; d++) sc[h][d] = NEG;
for (int d = 1; d < m; d++) sc[0][d] = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
if (window && j - i > W) continue;
double v = f(C, o, i, j, ctx, window);
sc[i + 1][j + 1] = sc[j + 1][i + 1] = v;
}
eisner(m, head);
for (int d = 1; d < m; d++) {
int g = C->h[o + d - 1];
if (g >= 0) { L.gold++; if (abs(g - (d - 1)) <= W) L.gold_in_w++; }
int h = head[d];
if (h > 0) {
L.pred++;
int a = h - 1, b = d - 1;
if (C->h[o + b] == a || C->h[o + a] == b) L.tp++;
}
}
}
return L;
}
static double edge_gold (const corpus_t *C, int o, int i, int j, void *ctx, int window) {
(void) ctx; (void) window;
return (C->h[o + i] == j || C->h[o + j] == i) ? 1 : NEG;
}
typedef struct { const arm_t *a; const double *S; } arm_edge_t;
static double edge_arm (const corpus_t *C, int o, int i, int j, void *ctx, int window) {
(void) window;
arm_edge_t *e = ctx;
return e->S[(size_t) sym(e->a, C, o + i) * e->a->A + sym(e->a, C, o + j)];
}
static void print_link (int seed, int tier, const char *arm, long budget, long evald, long acc, link_t L) {
double p = L.pred ? (double) L.tp / L.pred : 0, r = L.gold ? (double) L.tp / L.gold : 0;
double f = p + r > 0 ? 2 * p * r / (p + r) : 0;
printf("B\t%d\t%d\t%s\t%ld\t%ld\t%ld\t%.5f\t%.5f\t%.5f\t%.5f\n", seed, tier, arm, budget, evald, acc, f, p, r,
L.gold ? (double) L.gold_in_w / L.gold : 0);
}
// Hard arm: evaluate every observed pair type of the arm's alphabet.
static double *hard_scores (const pairs_t *P, long *evald, long *acc) {
size_t A2 = (size_t) P->A * P->A;
double *S = malloc(sizeof(double) * A2);
*evald = *acc = 0;
for (int a = 0; a < P->A; a++) for (int b = 0; b < P->A; b++) {
size_t k = (size_t) a * P->A + b;
S[k] = NEG;
if (!P->M[k]) continue;
(*evald)++;
S[k] = gated_pmi(P, a, b);
if (S[k] > NEG) (*acc)++;
}
return S;
}
// ---------------------------------------------------------------- budgeted orders over word pairs
typedef struct { uint32_t k; double key1, key2; } cand_t;
static int cand_cmp (const void *x, const void *y) {
const cand_t *a = x, *b = y;
if (a->key1 != b->key1) return a->key1 > b->key1 ? -1 : 1;
if (a->key2 != b->key2) return a->key2 > b->key2 ? -1 : 1;
return a->k < b->k ? -1 : a->k > b->k;
}
static const long budgets[] = { 300, 1000, 3000, 10000, 30000, 100000, 300000, -1 };
#define NBUDGET 8
// order: 0 = frequency (U-f); otherwise ordered by the class-pair score of grouping `g` with scores Sg.
static void run_budgets (int seed, int tier, const char *name, const pairs_t *PU, const arm_t *U, const int *g,
const double *Sg, const corpus_t *ho) {
int A = PU->A;
long nt = 0;
for (size_t k = 0; k < (size_t) A * A; k++) if (PU->M[k]) nt++;
cand_t *cv = malloc(sizeof(cand_t) * nt);
long i = 0;
for (int a = 0; a < A; a++) for (int b = 0; b < A; b++) {
size_t k = (size_t) a * A + b;
if (!PU->M[k]) continue;
cv[i].k = (uint32_t) k; cv[i].key2 = PU->M[k];
cv[i].key1 = g ? Sg[g[a] * K + g[b]] : PU->M[k];
i++;
}
qsort(cv, nt, sizeof(cand_t), cand_cmp);
double *S = malloc(sizeof(double) * (size_t) A * A);
for (int bi = 0; bi < NBUDGET; bi++) {
long B = budgets[bi] < 0 || budgets[bi] > nt ? nt : budgets[bi];
for (size_t k = 0; k < (size_t) A * A; k++) S[k] = NEG;
long acc = 0;
for (long c = 0; c < B; c++) {
int a = cv[c].k / A, b = cv[c].k % A;
S[cv[c].k] = gated_pmi(PU, a, b);
if (S[cv[c].k] > NEG) acc++;
}
arm_edge_t e = { U, S };
link_t L = parse_eval(ho, edge_arm, &e, 1);
print_link(seed, tier, name, budgets[bi], B, acc, L);
if (budgets[bi] < 0 || budgets[bi] >= nt) break;
}
free(S); free(cv);
}
// ---------------------------------------------------------------- main
int main (int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: ac <seed> [--tiers a,b,c] [--mut-drop] [--heldout N]\n"); return 1; }
int seed = atoi(argv[1]);
int tiers[16] = { 1000, 3000, 10000, 30000, 100000 }, ntier = 5, nho = 2000;
for (int i = 2; i < argc; i++) {
if (!strcmp(argv[i], "--mut-drop")) mut_drop = 1;
else if (!strcmp(argv[i], "--heldout") && i + 1 < argc) nho = atoi(argv[++i]);
else if (!strcmp(argv[i], "--tiers") && i + 1 < argc) {
ntier = 0;
for (char *p = strtok(argv[++i], ","); p && ntier < 16; p = strtok(NULL, ",")) tiers[ntier++] = atoi(p);
}
}
setvbuf(stdout, NULL, _IOLBF, 0);
build_world();
int maxt = 0;
for (int i = 0; i < ntier; i++) if (tiers[i] > maxt) maxt = tiers[i];
corpus_t full = gen_corpus(1000003ULL * seed + 1, maxt);
corpus_t ho = gen_corpus(1000003ULL * seed + 2, nho);
printf("#\tseed=%d\tV=%d\tK=%d\tW=%d\theldout_sents=%d\theldout_toks=%d\n", seed, V, K, W, ho.ns, ho.ntok);
// C1: parser + scorer with gold-only edges and no window -> P = R = 1.
{
link_t L = parse_eval(&ho, edge_gold, NULL, 0);
int ok = L.tp == L.gold && L.pred == L.gold;
printf("GUARD\tC1\t%s\ttp=%ld\tpred=%ld\tgold=%ld\n", ok ? "PASS" : "FAIL", L.tp, L.pred, L.gold);
if (!ok) return 2;
}
arm_t U = { "U", V, NULL, 0 };
for (int ti = 0; ti < ntier; ti++) {
int tier = tiers[ti];
corpus_t tr = prefix(full, tier);
int passes;
int *Lmap = exchange(&tr, &passes);
int *Rmap = malloc(sizeof(int) * V), *perm = malloc(sizeof(int) * V);
rng_t rr = { 99991ULL * seed + tier };
for (int x = 0; x < V; x++) perm[x] = x;
for (int x = V - 1; x > 0; x--) { int j = rpick(&rr, x + 1), t = perm[x]; perm[x] = perm[j]; perm[j] = t; }
for (int x = 0; x < V; x++) Rmap[x] = Lmap[perm[x]];
arm_t G = { "G", NCLS, NULL, 1 }, Gw = { "Gw", NCLS, primary, 0 }, L = { "L", K, Lmap, 0 }, R = { "R", K, Rmap, 0 };
printf("#\ttier=%d\ttrain_toks=%d\texchange_passes=%d\n", tier, tr.ntok, passes);
// Part A
double hu = bits_unigram(&tr, &ho);
arm_t *armsA[] = { &G, &Gw, &L, &R, &U };
for (int k = 0; k < 5; k++) printf("A\t%d\t%d\t%s\t%.5f\t%.5f\n", seed, tier, armsA[k]->name, hu, bits_class_bigram(armsA[k], &tr, &ho));
// C3 N1 null at this tier: learn on shuffled train, score on shuffled held-out.
if (tier == 10000 || tier == 100000 || ntier == 1) {
corpus_t ntr = shuffled(tr, 31337ULL * seed + tier), nho_c = shuffled(ho, 31337ULL * seed + 7);
int np;
int *Nmap = exchange(&ntr, &np);
arm_t NL = { "L", K, Nmap, 0 };
printf("N1\t%d\t%d\tL\t%.5f\t%.5f\n", seed, tier, bits_unigram(&ntr, &nho_c), bits_class_bigram(&NL, &ntr, &nho_c));
free(Nmap); free(ntr.w); free(ntr.c); free(nho_c.w); free(nho_c.c);
}
// Part B: hard arms
arm_t *armsB[] = { &G, &Gw, &L, &R, &U };
double *SL = NULL, *SR = NULL;
pairs_t PU = { 0 };
for (int k = 0; k < 5; k++) {
pairs_t P = count_pairs(armsB[k], &tr);
long ev, acc;
double *S = hard_scores(&P, &ev, &acc);
arm_edge_t e = { armsB[k], S };
print_link(seed, tier, armsB[k]->name, -1, ev, acc, parse_eval(&ho, edge_arm, &e, 1));
if (armsB[k] == &L) SL = S;
else if (armsB[k] == &R) SR = S;
else free(S);
if (armsB[k] == &U) PU = P; else free_pairs(&P);
}
// Soft / budgeted arms over word pairs
run_budgets(seed, tier, "U-f", &PU, &U, NULL, NULL, &ho);
run_budgets(seed, tier, "S-L", &PU, &U, Lmap, SL, &ho);
run_budgets(seed, tier, "S-R", &PU, &U, Rmap, SR, &ho);
free_pairs(&PU); free(SL); free(SR); free(Lmap); free(Rmap); free(perm);
}
return 0;
}