diff options
25 files changed, 1367 insertions, 15 deletions
diff --git a/MATCHING_RESULTS.md b/MATCHING_RESULTS.md index 645393a..ff33077 100644 --- a/MATCHING_RESULTS.md +++ b/MATCHING_RESULTS.md @@ -3,12 +3,21 @@ *2026-08-01. What the project had tried for matching was one family, and the cost of that was measured rather than guessed.* -**Result in one line.** On a field whose information is 99.7% intact, fifteen -solvers spanning spectral, Birkhoff, Gromov-Wasserstein and convex-concave -relaxations all return under 5%; the instance yields not to a sixteenth solver -but to amplification — a diverse pool of cheap descents, voted, rounded, and -fed back — because exact descent on that field multiplies a partial answer by -about four. +**Result in one line.** Fifteen solvers spanning spectral, Birkhoff, +Gromov-Wasserstein and convex-concave relaxations return under 5% on the +caption-omitted field; every one of them is purely quadratic or purely +spectral, and adding a single permutation-invariant **node-level term** to the +objective reaches 0.837 in 1.4 seconds — which is the information-theoretic +ceiling, because that field has 51 exact automorphisms and no blind method can +exceed 0.836. + +**Three numbers in the first draft of this document were artifacts of my own +code and are corrected below**: the anchor bound was inflated by a tie-break +(0.997 → 0.920), the truth is a plateau rather than a strict local minimum +(51 transpositions have exactly zero energy delta), and the "FAQ with 30 +restarts" row never ran restarts at all. The corrections were found by an +adversarial review that was pointed at the artifacts, and each was reproduced +here before being accepted. ## A benchmark with known-reachable answers @@ -142,3 +151,96 @@ the whole table: with C = A @ B, swapping p and q changes the alignment sum by 2(C_pq + C_qp − C_pp − C_qq + 2 A_pq B_pq). Checked against brute force to 1e-9 before use. **203 s → 0.79 s**, and every experiment in this document is downstream of that. + +--- + +# Resolution: the missing term was unary + +*Appended 2026-08-01 after an adversarial review of the artifacts.* + +## The ceiling was never 1.0 + +The caption-omitted field was built by deleting one word class, and that makes +scenes which differed only in that class **exactly interchangeable in the text +field**. Not approximately: `T[s,s]` is bitwise identical to `T` for 51 +transpositions `s`, so every objective of the form `f(V, P T P^T)` is invariant +under them at every order. Blind matching can pick at most one member per orbit. + +| Field | automorphisms of T | ambiguous scenes | blind ceiling | +|---|---|---|---| +| noisy 0.35 | 0 | 0 | 1.000 | +| rank8 | 0 | 0 | 1.000 | +| synth-full | 7 | 14 | 0.973 | +| **omit-size** | **51** | **76** | **0.836** | +| omit-count | 145 | 106 | 0.719 | +| omit-colour | 381 | 210 | 0.402 | + +Every accuracy in this project's synthetic benchmark was being divided by the +wrong denominator. It also explains the caption ladder's monotone collapse in a +way that has nothing to do with information: deleting a word class manufactures +automorphisms, and the ceiling falls with them. + +## What the fifteen had in common + +They are all purely quadratic or purely spectral. **None carries a node-level +term.** The instance flattens precisely the coarse second-order statistics that +family reads, while leaving scenes distinguishable in the shape of their own +similarity profiles — and a row-order statistic is not a spectral statistic. + +Give each node eight moments of its own row of the field, z-score them jointly +across both node sets, and use the descriptor distance as a linear cost blended +with the quadratic term through Frank-Wolfe: + +| Field | blind ceiling | fused unary+quadratic | energy gap to truth | previous best | +|---|---|---|---|---| +| omit-size | 0.836 | **0.837** | **+0.00e+00** | 0.044 | +| rank8 | 1.000 | 0.884 | −6.2e-03 | 0.088 | +| synth-full | 0.973 | 0.956 | −5.5e-04 | 0.961 | +| natural | — | 0.012 | −1.1e-01 | 0.027 | + +1.4 seconds, nineteen times the previous best, and an energy gap of exactly +zero — it finds a configuration with the truth's energy, which given 51 +automorphisms is all there is to find. + +**The term must stay in the loop.** Using the descriptor only to seed a +pure-quadratic descent scores 0.21, because the descent discards it immediately +and wanders back into the decoy region. Pinned through the Frank-Wolfe +iterations, the same descriptor scores 0.84. That distinction is the entire +result, and it is why amplification — which is also pure-quadratic — plateaued +at 0.508 no matter how large the pool grew. + +Negative energy gaps on rank8, synth-full and natural say something different +and worth keeping: there the solver finds states **below** the truth, so what +remains is the objective, not the search. On natural data the gap is −0.113, +which is the same information deficit the 0.336 anchor bound reports. + +## The corrected gate table + +With the tie-break fixed, the bound no longer credits itself with resolving +exact twins by presentation order: + +| Field | anchor bound (corrected) | blind recovery | gap | +|---|---|---|---| +| synth-full | 0.983 | 0.958 | +0.025 | +| omit-size | 0.920 | 0.837 | +0.083 | +| rank8 | 0.930 | 0.884 | +0.046 | +| natural | 0.336 | 0.000 | +0.336 | + +All three synthetic instances are now solved to within 0.08 of their bounds. +**Visual Genome is the only field left with a real gap, and all of it sits in +the bound** — the representation, not the search. Its bound is unaffected by +the correction because natural data has no exact twins. + +## What this cost and what it bought + +Three published numbers were wrong because the code that produced them had +bugs that flattered it, and the fourth conclusion — "the truth is a strict +local minimum, so this is a pure optimiser failure" — was built on one of them. +The amplification work that followed was aimed at a target that was 0.16 lower +than believed and reached 0.508 of it by brute pool size, when 1.4 seconds of +the right objective reaches the ceiling. Amplification is not wrong; it is a +pure-quadratic method and inherits the blind spot. + +The rule this adds to the standing gate: **before concluding that an instance +is hard, check whether the field has exact automorphisms.** It costs one sorted +row-hash per node and it bounds everything downstream. diff --git a/artifacts/spectral_frontier_probe/eval_impure_anchors.log b/artifacts/spectral_frontier_probe/eval_impure_anchors.log new file mode 100644 index 0000000..a4b957a --- /dev/null +++ b/artifacts/spectral_frontier_probe/eval_impure_anchors.log @@ -0,0 +1,60 @@ +=== (a) PURE random anchors: reproduce the published curve === + K= 12 pure accuracy 0.589 +- 0.055 + K= 25 pure accuracy 0.860 +- 0.058 + K= 40 pure accuracy 0.926 +- 0.032 + K= 50 pure accuracy 0.949 +- 0.026 + K= 64 pure accuracy 0.971 +- 0.017 + K= 128 pure accuracy 0.996 +- 0.005 + +=== (b) IMPURE random anchors: c correct, K-c wrong (wrong = derangement among selected) === + K= 12 prec=1.00 (12/12 right) accuracy 0.620 +- 0.093 + K= 12 prec=0.92 (10/12 right) accuracy 0.390 +- 0.101 + K= 12 prec=0.88 (10/12 right) accuracy 0.399 +- 0.109 + K= 12 prec=0.84 (10/12 right) accuracy 0.330 +- 0.098 + K= 12 prec=0.80 (10/12 right) accuracy 0.408 +- 0.120 + K= 12 prec=0.72 (9/12 right) accuracy 0.264 +- 0.068 + K= 12 prec=0.60 (7/12 right) accuracy 0.135 +- 0.064 + + K= 25 prec=1.00 (25/25 right) accuracy 0.852 +- 0.049 + K= 25 prec=0.92 (23/25 right) accuracy 0.766 +- 0.073 + K= 25 prec=0.88 (22/25 right) accuracy 0.746 +- 0.071 + K= 25 prec=0.84 (21/25 right) accuracy 0.704 +- 0.079 + K= 25 prec=0.80 (20/25 right) accuracy 0.677 +- 0.070 + K= 25 prec=0.72 (18/25 right) accuracy 0.527 +- 0.103 + K= 25 prec=0.60 (15/25 right) accuracy 0.371 +- 0.091 + + K= 40 prec=1.00 (40/40 right) accuracy 0.933 +- 0.032 + K= 40 prec=0.92 (37/40 right) accuracy 0.902 +- 0.038 + K= 40 prec=0.88 (35/40 right) accuracy 0.859 +- 0.037 + K= 40 prec=0.84 (34/40 right) accuracy 0.835 +- 0.038 + K= 40 prec=0.80 (32/40 right) accuracy 0.812 +- 0.047 + K= 40 prec=0.72 (29/40 right) accuracy 0.742 +- 0.085 + K= 40 prec=0.60 (24/40 right) accuracy 0.574 +- 0.081 + + K= 50 prec=1.00 (50/50 right) accuracy 0.950 +- 0.024 + K= 50 prec=0.92 (46/50 right) accuracy 0.920 +- 0.026 + K= 50 prec=0.88 (44/50 right) accuracy 0.893 +- 0.033 + K= 50 prec=0.84 (42/50 right) accuracy 0.877 +- 0.033 + K= 50 prec=0.80 (40/50 right) accuracy 0.855 +- 0.031 + K= 50 prec=0.72 (36/50 right) accuracy 0.783 +- 0.055 + K= 50 prec=0.60 (30/50 right) accuracy 0.629 +- 0.102 + + K= 100 prec=1.00 (100/100 right) accuracy 0.992 +- 0.009 + K= 100 prec=0.92 (92/100 right) accuracy 0.953 +- 0.014 + K= 100 prec=0.88 (88/100 right) accuracy 0.933 +- 0.016 + K= 100 prec=0.84 (84/100 right) accuracy 0.915 +- 0.018 + K= 100 prec=0.80 (80/100 right) accuracy 0.895 +- 0.012 + K= 100 prec=0.72 (72/100 right) accuracy 0.852 +- 0.020 + K= 100 prec=0.60 (60/100 right) accuracy 0.787 +- 0.021 + +=== (c) IMPURE with wrong partners drawn from OUTSIDE the anchor set === + K= 25 prec=1.00 accuracy 0.866 +- 0.040 + K= 25 prec=0.88 accuracy 0.729 +- 0.064 + K= 25 prec=0.84 accuracy 0.689 +- 0.070 + K= 25 prec=0.80 accuracy 0.603 +- 0.079 + K= 25 prec=0.72 accuracy 0.501 +- 0.094 + K= 50 prec=1.00 accuracy 0.945 +- 0.025 + K= 50 prec=0.88 accuracy 0.832 +- 0.031 + K= 50 prec=0.84 accuracy 0.808 +- 0.020 + K= 50 prec=0.80 accuracy 0.775 +- 0.031 + K= 50 prec=0.72 accuracy 0.689 +- 0.043 diff --git a/artifacts/spectral_frontier_probe/eval_impure_anchors.py b/artifacts/spectral_frontier_probe/eval_impure_anchors.py new file mode 100644 index 0000000..f6b4397 --- /dev/null +++ b/artifacts/spectral_frontier_probe/eval_impure_anchors.py @@ -0,0 +1,65 @@ +import numpy as np, torch +from scipy.optimize import linear_sum_assignment + +def standardise(M): + M = np.asarray(M, dtype=np.float64); mask = ~np.eye(len(M), dtype=bool); v = M[mask] + out = (M - v.mean()) / v.std(); np.fill_diagonal(out, 0.0); return out + +d = torch.load('/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt', map_location='cpu', weights_only=False) +V = standardise(d['visual_field']); T = standardise(d['text_field']); N = len(V) +truth = np.arange(N) + +def expand(anchorL, anchorR): + """anchorL: vision indices; anchorR: claimed text partner. Returns full accuracy.""" + probe = np.setdiff1d(np.arange(N), anchorL) + # probe scenes on the text side are whatever is not claimed + probeR = np.setdiff1d(np.arange(N), anchorR) + L = V[np.ix_(probe, anchorL)]; R = T[np.ix_(probeR, anchorR)] + L = (L - L.mean(1, keepdims=True)) / L.std(1, keepdims=True).clip(1e-9) + R = (R - R.mean(1, keepdims=True)) / R.std(1, keepdims=True).clip(1e-9) + S = L @ R.T / L.shape[1] + _, cols = linear_sum_assignment(-S) + resolved = probeR[cols] + n_ok = int((resolved == probe).sum()) + int((anchorR == anchorL).sum()) + return n_ok / N + +rng = np.random.default_rng(0) +REP = 20 +print("=== (a) PURE random anchors: reproduce the published curve ===") +for K in (12, 25, 40, 50, 64, 128): + a = [expand(*(lambda s: (s, s))(np.sort(rng.choice(N, K, replace=False)))) for _ in range(REP)] + print(f" K={K:4d} pure accuracy {np.mean(a):.3f} +- {np.std(a):.3f}") + +print("\n=== (b) IMPURE random anchors: c correct, K-c wrong (wrong = derangement among selected) ===") +for K in (12, 25, 40, 50, 100): + for prec in (1.0, 0.92, 0.88, 0.84, 0.80, 0.72, 0.60): + nb = int(round(K * (1 - prec))) + if nb == 1: nb = 2 # a single wrong pair is impossible inside a bijection + accs = [] + for _ in range(REP): + sel = np.sort(rng.choice(N, K, replace=False)) + right = sel.copy() + if nb >= 2: + bad = rng.choice(K, nb, replace=False) + sh = right[bad].copy() + while True: + perm = rng.permutation(nb) + if not (perm == np.arange(nb)).any(): break + right[bad] = sh[perm] + accs.append(expand(sel, right)) + print(f" K={K:4d} prec={prec:.2f} ({K-nb}/{K} right) accuracy {np.mean(accs):.3f} +- {np.std(accs):.3f}") + print() + +print("=== (c) IMPURE with wrong partners drawn from OUTSIDE the anchor set ===") +for K in (25, 50): + for prec in (1.0, 0.88, 0.84, 0.80, 0.72): + nb = int(round(K * (1 - prec))); accs = [] + for _ in range(REP): + sel = np.sort(rng.choice(N, K, replace=False)) + right = sel.copy() + if nb: + bad = rng.choice(K, nb, replace=False) + outside = np.setdiff1d(np.arange(N), sel) + right[bad] = rng.choice(outside, nb, replace=False) + accs.append(expand(sel, right)) + print(f" K={K:4d} prec={prec:.2f} accuracy {np.mean(accs):.3f} +- {np.std(accs):.3f}") diff --git a/artifacts/spectral_frontier_probe/eval_voteanchor_seed7.log b/artifacts/spectral_frontier_probe/eval_voteanchor_seed7.log new file mode 100644 index 0000000..8852244 --- /dev/null +++ b/artifacts/spectral_frontier_probe/eval_voteanchor_seed7.log @@ -0,0 +1,23 @@ +150 ICP solutions in 222s +lowest-8 (E, acc, r): [(0.6733, 0.008, 8), (0.6824, 0.027, 10), (0.6956, 0.031, 10), (0.6988, 0.016, 8), (0.7011, 0.074, 12), (0.7026, 0.023, 10), (0.7052, 0.004, 10), (0.7052, 0.012, 8)] +mean pairwise agreement among top-30: 0.046 + +--- ROUTE A (free readout of the same ensemble) --- + best-E member acc 0.008 -> after exact descent acc 0.012 E=0.6565 [5s] + descend 5 lowest-E, pick by energy: acc 0.043 E=0.6316 + +--- ROUTE B (the proposal) --- + m= 5 K= 12 kept= 12 precision=0.167 -> expansion acc 0.039 -> after descent 0.039 + m= 5 K= 25 kept= 25 precision=0.080 -> expansion acc 0.031 -> after descent 0.051 + m= 5 K= 50 kept= 47 precision=0.064 -> expansion acc 0.031 -> after descent 0.023 + m= 5 K=100 kept= 91 precision=0.044 -> expansion acc 0.031 -> after descent 0.023 + m=10 K= 12 kept= 12 precision=0.250 -> expansion acc 0.043 -> after descent 0.074 + m=10 K= 25 kept= 23 precision=0.130 -> expansion acc 0.035 -> after descent 0.043 + m=10 K= 50 kept= 48 precision=0.104 -> expansion acc 0.059 -> after descent 0.066 + m=10 K=100 kept= 87 precision=0.069 -> expansion acc 0.035 -> after descent 0.035 + m=30 K= 12 kept= 12 precision=0.417 -> expansion acc 0.094 -> after descent 0.180 + m=30 K= 25 kept= 25 precision=0.320 -> expansion acc 0.141 -> after descent 0.125 + m=30 K= 50 kept= 48 precision=0.229 -> expansion acc 0.215 -> after descent 0.816 + m=30 K=100 kept= 80 precision=0.188 -> expansion acc 0.148 -> after descent 0.195 + +E(truth)=0.3396 total wall 617s diff --git a/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.log b/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.log new file mode 100644 index 0000000..c2bd82f --- /dev/null +++ b/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.log @@ -0,0 +1,34 @@ + +##### hidden seed 11: 150 ICP sols in 200s, E(truth)=0.3396, best member E=0.6569 acc=0.172 + ROUTE A (descend 5 lowest-E, blind pick): E=0.5863 acc=0.277 + m=10 K= 12 prec=0.333 expand=0.102 -> descent acc=0.320 E=0.6184 + m=10 K= 25 prec=0.333 expand=0.168 -> descent acc=0.324 E=0.6279 + m=10 K= 50 prec=0.255 expand=0.184 -> descent acc=0.793 E=0.3544 + m=10 K=100 prec=0.193 expand=0.172 -> descent acc=0.770 E=0.3900 + m=30 K= 12 prec=0.455 expand=0.211 -> descent acc=0.535 E=0.4867 + m=30 K= 25 prec=0.292 expand=0.195 -> descent acc=0.754 E=0.4163 + m=30 K= 50 prec=0.227 expand=0.188 -> descent acc=0.695 E=0.4357 + m=30 K=100 prec=0.172 expand=0.184 -> descent acc=0.773 E=0.3837 + m=60 K= 12 prec=0.455 expand=0.086 -> descent acc=0.094 E=0.7738 + m=60 K= 25 prec=0.375 expand=0.164 -> descent acc=0.133 E=0.6840 + m=60 K= 50 prec=0.244 expand=0.098 -> descent acc=0.066 E=0.7911 + m=60 K=100 prec=0.171 expand=0.113 -> descent acc=0.086 E=0.7412 + ROUTE B (blind pick by energy over the 12 cells): m=10 K=50 E=0.3544 acc=0.793 [best cell by accuracy was 0.793] + wall 492s + +##### hidden seed 23: 150 ICP sols in 559s, E(truth)=0.3396, best member E=0.3684 acc=0.691 + ROUTE A (descend 5 lowest-E, blind pick): E=0.3396 acc=0.852 + m=10 K= 12 prec=0.917 expand=0.703 -> descent acc=0.855 E=0.3396 + m=10 K= 25 prec=0.680 expand=0.520 -> descent acc=0.758 E=0.3792 + m=10 K= 50 prec=0.583 expand=0.484 -> descent acc=0.777 E=0.3543 + m=10 K=100 prec=0.505 expand=0.492 -> descent acc=0.848 E=0.3396 + m=30 K= 12 prec=0.917 expand=0.656 -> descent acc=0.812 E=0.3466 + m=30 K= 25 prec=0.920 expand=0.723 -> descent acc=0.809 E=0.3396 + m=30 K= 50 prec=0.673 expand=0.691 -> descent acc=0.816 E=0.3644 + m=30 K=100 prec=0.558 expand=0.547 -> descent acc=0.797 E=0.3593 + m=60 K= 12 prec=0.833 expand=0.504 -> descent acc=0.785 E=0.3468 + m=60 K= 25 prec=0.792 expand=0.734 -> descent acc=0.820 E=0.3396 + m=60 K= 50 prec=0.667 expand=0.641 -> descent acc=0.836 E=0.3433 + m=60 K=100 prec=0.524 expand=0.496 -> descent acc=0.844 E=0.3569 + ROUTE B (blind pick by energy over the 12 cells): m=30 K=25 E=0.3396 acc=0.809 [best cell by accuracy was 0.855] + wall 752s diff --git a/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.py b/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.py new file mode 100644 index 0000000..d97d239 --- /dev/null +++ b/artifacts/spectral_frontier_probe/eval_voteanchor_vs_bestE.py @@ -0,0 +1,78 @@ +"""Replication with BLIND energy selection over the (m,K) grid, two fresh hidden perms.""" +import sys, time, numpy as np, torch +sys.path.insert(0, '/home/yurenh2/emm') +from scipy.optimize import linear_sum_assignment +from scipy.stats import ortho_group +from worldalign.synth_fast_gate import fast_pair_descent + +dev = 'cuda:0' +def standardise(M): + M = np.asarray(M, dtype=np.float64); m = ~np.eye(len(M), dtype=bool); v = M[m] + o = (M - v.mean())/v.std(); np.fill_diagonal(o, 0.0); return o +d = torch.load('/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt', map_location='cpu', weights_only=False) +V = standardise(d['visual_field']); T0 = standardise(d['text_field']); N = len(V) +Vt = torch.tensor(V, dtype=torch.float32, device=dev) +wV, UV = np.linalg.eigh(V); wV = wV[::-1]; UV = UV[:, ::-1] + +def hung(A, B): + C = ((A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2*A@B.T) + r, c = linear_sum_assignment(C); return c +def icp(XV, XT, O, iters=25): + for _ in range(iters): + p = hung(XV, XT@O); u, s, vt = np.linalg.svd(XT[p].T@XV); On = u@vt + if np.allclose(On, O, atol=1e-10): O = On; break + O = On + return hung(XV, XT@O) + +for SEED in (11, 23): + rng = np.random.default_rng(SEED); sigma = rng.permutation(N) + T = T0[np.ix_(sigma, sigma)]; truth = np.argsort(sigma) + acc = lambda p: float((np.asarray(p) == truth).mean()) + Tt = torch.tensor(T, dtype=torch.float32, device=dev) + CONST = float((Tt*Tt).sum() + (Vt*Vt).sum()) + def energy(p): + P = torch.as_tensor(np.asarray(p), dtype=torch.long, device=dev) + return (CONST - 2.0*float((Tt[P[:, None], P[None, :]]*Vt).sum()))/(N*(N-1)) + def descend(p, steps=4000): + P = torch.as_tensor(np.ascontiguousarray(p), dtype=torch.long, device=dev) + return fast_pair_descent(Tt, Vt, P, steps).cpu().numpy() + wT, UT = np.linalg.eigh(T); wT = wT[::-1]; UT = UT[:, ::-1] + t0 = time.time(); sols = [] + for r in (8, 10, 12, 14, 16): + XV = UV[:, :r]*np.sqrt(np.abs(wV[:r])); XT = UT[:, :r]*np.sqrt(np.abs(wT[:r])) + for _ in range(30): + p = icp(XV, XT, ortho_group.rvs(r, random_state=int(rng.integers(1 << 30)))) + sols.append((energy(p), p, r)) + sols.sort(key=lambda z: z[0]) + print(f"\n##### hidden seed {SEED}: {len(sols)} ICP sols in {time.time()-t0:.0f}s, " + f"E(truth)={energy(truth):.4f}, best member E={sols[0][0]:.4f} acc={acc(sols[0][1]):.3f}", flush=True) + A = [descend(p) for _, p, _ in sols[:5]] + bA = min(A, key=energy) + print(f" ROUTE A (descend 5 lowest-E, blind pick): E={energy(bA):.4f} acc={acc(bA):.3f}", flush=True) + + def expand(aL, aR): + pr = np.setdiff1d(np.arange(N), aL); prR = np.setdiff1d(np.arange(N), aR) + L = V[np.ix_(pr, aL)]; R = T[np.ix_(prR, aR)] + L = (L-L.mean(1, keepdims=True))/L.std(1, keepdims=True).clip(1e-9) + R = (R-R.mean(1, keepdims=True))/R.std(1, keepdims=True).clip(1e-9) + S = L@R.T/L.shape[1]; _, c = linear_sum_assignment(-S) + full = np.zeros(N, dtype=int); full[aL] = aR; full[pr] = prR[c]; return full + grid = [] + for m in (10, 30, 60): + votes = np.zeros((N, N)) + for _, p, _ in sols[:m]: votes[np.arange(N), p] += 1 + conf = votes.max(1) - np.partition(votes, -2, axis=1)[:, -2] + order = np.argsort(-conf); pm = votes.argmax(1) + for K in (12, 25, 50, 100): + sel = order[:K]; part = pm[sel]; keep = np.zeros(len(sel), bool); seen = set() + for i, c in enumerate(part): + if c not in seen: seen.add(c); keep[i] = True + sel, part = sel[keep], part[keep] + prec = float((part == truth[sel]).mean()) + e = expand(sel, part); pd = descend(e) + grid.append((energy(pd), acc(pd), m, K, prec, acc(e))) + print(f" m={m:2d} K={K:3d} prec={prec:.3f} expand={acc(e):.3f} -> descent acc={acc(pd):.3f} E={energy(pd):.4f}", flush=True) + grid.sort() + print(f" ROUTE B (blind pick by energy over the 12 cells): m={grid[0][2]} K={grid[0][3]} " + f"E={grid[0][0]:.4f} acc={grid[0][1]:.3f} [best cell by accuracy was {max(g[1] for g in grid):.3f}]", flush=True) + print(f" wall {time.time()-t0:.0f}s", flush=True) diff --git a/artifacts/spectral_frontier_probe/nmf_adv_oracle.log b/artifacts/spectral_frontier_probe/nmf_adv_oracle.log new file mode 100644 index 0000000..8176ba3 --- /dev/null +++ b/artifacts/spectral_frontier_probe/nmf_adv_oracle.log @@ -0,0 +1,26 @@ +E(truth) = 0.339635 +REF: GRAMPA on raw fields -> raw 0.0039 refined 0.0117 E=0.8380 +REF: field correlation (aligned) = 0.8302 + +=== r=24 [6.2s] resid V 0.0400 T 0.0331 V(seed2) 0.0447 + [uniqueness] symNMF(V,seed1) vs symNMF(V,seed2) matched cos: median 0.885 >0.9 10/24 >0.5 24/24 min 0.541 + [oracle cols] cos: >0.9 10/24 >0.5 23/24 median 0.842 min 0.427 + sorted: [0.98 0.98 0.97 0.96 0.95 0.94 0.94 0.92 0.91 0.91 0.88 0.86 0.82 0.8 + 0.79 0.69 0.68 0.68 0.68 0.68 0.68 0.63 0.55 0.43] + identity-map fraction (shared-seed artifact check): 0.083 + [oracle-col row descriptors] Hungarian acc 0.6719 -> descent 0.8320 + [prune thr=0.5] kept 23/24 rho(cleanV,T)=0.8466 (was 0.8302) GRAMPA 0.0078 -> clean-descent 0.0547 -> true-descent 0.0547 E=0.6471 + [prune thr=0.7] kept 15/24 rho(cleanV,T)=0.7684 (was 0.8302) GRAMPA 0.0039 -> clean-descent 0.0391 -> true-descent 0.0391 E=0.6817 + [prune thr=0.8] kept 13/24 rho(cleanV,T)=0.7804 (was 0.8302) GRAMPA 0.0000 -> clean-descent 0.0000 -> true-descent 0.0000 E=0.7292 + +=== r=42 [32.2s] resid V 0.0241 T 0.0141 V(seed2) 0.0231 + [uniqueness] symNMF(V,seed1) vs symNMF(V,seed2) matched cos: median 0.832 >0.9 12/42 >0.5 42/42 min 0.541 + [oracle cols] cos: >0.9 4/42 >0.5 41/42 median 0.766 min 0.416 + sorted: [0.97 0.94 0.93 0.9 0.89 0.88 0.88 0.87 0.86 0.86 0.86 0.84 0.84 0.84 + 0.82 0.81 0.81 0.8 0.79 0.78 0.77 0.76 0.76 0.76 0.75 0.75 0.75 0.74 + 0.74 0.73 0.72 0.72 0.72 0.71 0.7 0.7 0.69 0.66 0.65 0.63 0.62 0.42] + identity-map fraction (shared-seed artifact check): 0.000 + [oracle-col row descriptors] Hungarian acc 0.8125 -> descent 0.8828 + [prune thr=0.5] kept 41/42 rho(cleanV,T)=0.8337 (was 0.8302) GRAMPA 0.0273 -> clean-descent 0.0547 -> true-descent 0.0430 E=0.6804 + [prune thr=0.7] kept 35/42 rho(cleanV,T)=0.7976 (was 0.8302) GRAMPA 0.0391 -> clean-descent 0.0625 -> true-descent 0.0859 E=0.6966 + [prune thr=0.8] kept 17/42 rho(cleanV,T)=0.6036 (was 0.8302) GRAMPA 0.0000 -> clean-descent 0.0039 -> true-descent 0.0078 E=0.6982 diff --git a/artifacts/spectral_frontier_probe/nmf_adv_oracle.py b/artifacts/spectral_frontier_probe/nmf_adv_oracle.py new file mode 100644 index 0000000..2702e29 --- /dev/null +++ b/artifacts/spectral_frontier_probe/nmf_adv_oracle.py @@ -0,0 +1,133 @@ +"""Decisive ORACLE test of the symNMF de-rotation / component-pruning candidate. + +If the ORACLE version (perfect column match, perfect pruning) does not beat the +current blind state of the art (~0.83 on omit-size), the candidate is dead. +""" +import numpy as np, torch, time, warnings +warnings.filterwarnings('ignore') +from scipy.optimize import linear_sum_assignment + +dev = torch.device('cuda:0') +DT = torch.float64 + +d = torch.load('/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt', map_location='cpu') +V0 = d['visual_field'].double().numpy(); T0 = d['text_field'].double().numpy(); N = len(V0) +rng = np.random.default_rng(777); sigma = rng.permutation(N) +T0s = T0[np.ix_(sigma, sigma)]; truth = np.argsort(sigma) +acc = lambda p: float((p == truth).mean()) + + +def standardise(M): + M = np.asarray(M, float); mask = ~np.eye(len(M), dtype=bool); v = M[mask] + out = (M - v.mean()) / v.std(); np.fill_diagonal(out, 0.0); return out + + +def hung(A, B): + C = ((A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T) + r, c = linear_sum_assignment(C); return c + + +def sym_nmf_gpu(M, r, iters=3000, seed=0): + Mg = torch.tensor(np.clip(M, 0, None), device=dev, dtype=DT) + g = torch.Generator(device='cpu').manual_seed(seed) + W = torch.abs(torch.randn(len(M), r, generator=g, dtype=DT)).to(dev) * float(np.sqrt(M.mean() / r)) + for _ in range(iters): + W = W * (0.5 + 0.5 * (Mg @ W) / (W @ (W.T @ W) + 1e-12)) + return W.cpu().numpy() + + +# ---- energy + exact steepest descent (closed-form swap table) ---- +Vs = standardise(V0); Ts = standardise(T0s) +CONST = float((Vs * Vs).sum() + (Ts * Ts).sum()); DEN = N * (N - 1) +Ag = torch.tensor(Vs, device=dev, dtype=DT); Tg = torch.tensor(Ts, device=dev, dtype=DT) + + +def energy(p): + return (CONST - 2.0 * float((Ts[np.ix_(p, p)] * Vs).sum())) / DEN + + +def descend(p0, max_steps=4000, A=None, B=None): + A = Ag if A is None else A + Bfull = Tg if B is None else B + p = torch.tensor(np.asarray(p0), device=dev, dtype=torch.long) + iu = torch.triu_indices(N, N, offset=1, device=dev) + for _ in range(max_steps): + B = Bfull[p][:, p] + C = A @ B + dg = torch.diagonal(C) + G = C + C.T - dg[:, None] - dg[None, :] + 2 * A * B + vals = G[iu[0], iu[1]] + k = int(vals.argmax()) + if float(vals[k]) <= 1e-12: + break + u, v = int(iu[0][k]), int(iu[1][k]) + p[u], p[v] = p[v].clone(), p[u].clone() + return p.cpu().numpy() + + +def grampa(Vm, Tm, eta=0.2): + lam, u = np.linalg.eigh(Vm); mu, v = np.linalg.eigh(Tm) + ones = np.ones(len(Vm)); left = u.T @ ones; right = v.T @ ones + w = np.outer(left, right) / ((lam[:, None] - mu[None, :]) ** 2 + eta**2) + s = u @ w @ v.T + r, c = linear_sum_assignment(-s); return c + + +print(f"E(truth) = {energy(truth):.6f}") +print("REF: GRAMPA on raw fields ->", end=" ") +p = grampa(Vs, Ts); pd = descend(p) +print(f"raw {acc(p):.4f} refined {acc(pd):.4f} E={energy(pd):.4f}") +rho_raw = np.corrcoef(Vs[~np.eye(N, dtype=bool)], Ts[np.ix_(truth, truth)][~np.eye(N, dtype=bool)])[0, 1] +print(f"REF: field correlation (aligned) = {rho_raw:.4f}") + +for r in (24, 42): + t0 = time.time() + WV = sym_nmf_gpu(V0, r, seed=1) + WT = sym_nmf_gpu(T0s, r, seed=1) + WV2 = sym_nmf_gpu(V0, r, seed=2) # stability check: same matrix, new seed + print(f"\n=== r={r} [{time.time()-t0:.1f}s] resid V {np.linalg.norm(V0-WV@WV.T)/np.linalg.norm(V0):.4f}" + f" T {np.linalg.norm(T0s-WT@WT.T)/np.linalg.norm(T0s):.4f}" + f" V(seed2) {np.linalg.norm(V0-WV2@WV2.T)/np.linalg.norm(V0):.4f}") + + nrm = lambda X: X / (np.linalg.norm(X, axis=0, keepdims=True) + 1e-12) + An, Bn, A2n = nrm(WV), nrm(WT), nrm(WV2) + + # (i) UNIQUENESS: same matrix, two seeds + S = An.T @ A2n; rr, cc = linear_sum_assignment(-S) + cs = np.sort(S[rr, cc])[::-1] + print(f" [uniqueness] symNMF(V,seed1) vs symNMF(V,seed2) matched cos: " + f"median {np.median(cs):.3f} >0.9 {(cs>0.9).sum()}/{r} >0.5 {(cs>0.5).sum()}/{r} min {cs.min():.3f}") + + # (ii) ORACLE cross-modal column match -- full distribution + Sx = An.T @ Bn[truth]; rr, cc = linear_sum_assignment(-Sx) + ocs = Sx[rr, cc]; colmap = cc[np.argsort(rr)] + srt = np.sort(ocs)[::-1] + print(f" [oracle cols] cos: >0.9 {(ocs>0.9).sum()}/{r} >0.5 {(ocs>0.5).sum()}/{r}" + f" median {np.median(ocs):.3f} min {ocs.min():.3f}") + print(f" sorted: {np.round(srt,2)}") + print(f" identity-map fraction (shared-seed artifact check): {(colmap==np.arange(r)).mean():.3f}") + + # (iii) row descriptors from oracle-matched columns + Ar = WV / np.linalg.norm(WV, axis=1, keepdims=True).clip(1e-9) + Br = WT[:, colmap] / np.linalg.norm(WT[:, colmap], axis=1, keepdims=True).clip(1e-9) + p_desc = hung(Ar, Br) + print(f" [oracle-col row descriptors] Hungarian acc {acc(p_desc):.4f} -> descent {acc(descend(p_desc)):.4f}") + + # (iv) THE PROPOSAL, ORACLE FORM: prune unmatched V components, rebuild, re-solve + for thr in (0.5, 0.7, 0.8): + keep = np.where(ocs >= thr)[0] + kv = rr[np.isin(np.arange(r), np.arange(r))] # rr is identity-ordered by lsa + keepV = rr[ocs >= thr] + if len(keepV) < 4: + print(f" [prune thr={thr}] only {len(keepV)} kept, skip"); continue + Vc = WV[:, keepV] @ WV[:, keepV].T + Vcs = standardise(Vc) + rho = np.corrcoef(Vcs[~np.eye(N, dtype=bool)], Ts[np.ix_(truth, truth)][~np.eye(N, dtype=bool)])[0, 1] + # solve on the cleaned vision field against the original text field + pg = grampa(Vcs, Ts) + Acg = torch.tensor(Vcs, device=dev, dtype=DT) + pgd = descend(pg, A=Acg) # descent on the CLEANED objective + pgd_true = descend(pgd) # then polish on the TRUE objective + print(f" [prune thr={thr}] kept {len(keepV)}/{r} rho(cleanV,T)={rho:.4f} (was {rho_raw:.4f})" + f" GRAMPA {acc(pg):.4f} -> clean-descent {acc(pgd):.4f} -> true-descent {acc(pgd_true):.4f}" + f" E={energy(pgd_true):.4f}") diff --git a/artifacts/spectral_frontier_probe/nmf_adv_prune_control.log b/artifacts/spectral_frontier_probe/nmf_adv_prune_control.log new file mode 100644 index 0000000..347318c --- /dev/null +++ b/artifacts/spectral_frontier_probe/nmf_adv_prune_control.log @@ -0,0 +1,21 @@ +--- symNMF seed 1, r=42 + A. symNMF reconstruction, NO pruning (blind) GW 0.0312 -> clean-desc 0.0391 -> true-desc 0.0391 E=0.6405 + B. ORACLE prune worst 1 (thr .5) GW 0.8594 -> clean-desc 0.8594 -> true-desc 0.8672 E=0.3396 + C0. RANDOM single-column drop (col 32, blind) GW 0.8359 -> clean-desc 0.8281 -> true-desc 0.8359 E=0.3396 + C1. RANDOM single-column drop (col 13, blind) GW 0.0469 -> clean-desc 0.0430 -> true-desc 0.0469 E=0.6486 + C2. RANDOM single-column drop (col 18, blind) GW 0.0195 -> clean-desc 0.0156 -> true-desc 0.0156 E=0.6661 + D. both sides symNMF-reconstructed (blind) GW 0.0234 -> clean-desc 0.0234 -> true-desc 0.0234 E=0.6020 +--- symNMF seed 2, r=42 + A. symNMF reconstruction, NO pruning (blind) GW 0.0156 -> clean-desc 0.0156 -> true-desc 0.0156 E=0.6419 + B. ORACLE prune worst 4 (thr .5) GW 0.8203 -> clean-desc 0.8125 -> true-desc 0.8203 E=0.3396 + C0. RANDOM single-column drop (col 32, blind) GW 0.0078 -> clean-desc 0.0078 -> true-desc 0.0078 E=0.6720 + C1. RANDOM single-column drop (col 13, blind) GW 0.0195 -> clean-desc 0.0195 -> true-desc 0.0195 E=0.7034 + C2. RANDOM single-column drop (col 18, blind) GW 0.0039 -> clean-desc 0.0039 -> true-desc 0.0039 E=0.6649 + D. both sides symNMF-reconstructed (blind) GW 0.0156 -> clean-desc 0.0156 -> true-desc 0.0156 E=0.7342 +--- symNMF seed 3, r=42 + A. symNMF reconstruction, NO pruning (blind) GW 0.1328 -> clean-desc 0.1523 -> true-desc 0.1641 E=0.5919 + B. ORACLE prune worst 2 (thr .5) GW 0.0000 -> clean-desc 0.0000 -> true-desc 0.0000 E=0.6669 + C0. RANDOM single-column drop (col 32, blind) GW 0.1211 -> clean-desc 0.1172 -> true-desc 0.1211 E=0.5922 + C1. RANDOM single-column drop (col 13, blind) GW 0.8125 -> clean-desc 0.8203 -> true-desc 0.8203 E=0.3396 + C2. RANDOM single-column drop (col 18, blind) GW 0.0078 -> clean-desc 0.0117 -> true-desc 0.0117 E=0.6752 + D. both sides symNMF-reconstructed (blind) GW 0.8398 -> clean-desc 0.8477 -> true-desc 0.8477 E=0.3396 diff --git a/artifacts/spectral_frontier_probe/nmf_adv_prune_control.py b/artifacts/spectral_frontier_probe/nmf_adv_prune_control.py new file mode 100644 index 0000000..a3b23ef --- /dev/null +++ b/artifacts/spectral_frontier_probe/nmf_adv_prune_control.py @@ -0,0 +1,61 @@ +"""CONTROL: is the 0.86 from PRUNING (needs oracle) or from symNMF RECONSTRUCTION alone (blind)?""" +import numpy as np, torch, warnings, ot +warnings.filterwarnings('ignore') +from scipy.optimize import linear_sum_assignment +dev = torch.device('cuda:0'); DT = torch.float64 +d = torch.load('/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt', map_location='cpu') +V0 = d['visual_field'].double().numpy(); T0 = d['text_field'].double().numpy(); N = len(V0) +rng = np.random.default_rng(777); sigma = rng.permutation(N) +T0s = T0[np.ix_(sigma, sigma)]; truth = np.argsort(sigma) +acc = lambda p: float((p == truth).mean()) +def standardise(M): + M = np.asarray(M, float); mask = ~np.eye(len(M), dtype=bool); v = M[mask] + out = (M - v.mean()) / v.std(); np.fill_diagonal(out, 0.0); return out +def sym_nmf_gpu(M, r, iters=3000, seed=0): + Mg = torch.tensor(np.clip(M, 0, None), device=dev, dtype=DT) + g = torch.Generator(device='cpu').manual_seed(seed) + W = torch.abs(torch.randn(len(M), r, generator=g, dtype=DT)).to(dev) * float(np.sqrt(M.mean()/r)) + for _ in range(iters): + W = W * (0.5 + 0.5 * (Mg @ W) / (W @ (W.T @ W) + 1e-12)) + return W.cpu().numpy() +Vs = standardise(V0); Ts = standardise(T0s) +CONST = float((Vs*Vs).sum() + (Ts*Ts).sum()); DEN = N*(N-1) +Ag = torch.tensor(Vs, device=dev, dtype=DT); Tg = torch.tensor(Ts, device=dev, dtype=DT) +energy = lambda p: (CONST - 2.0*float((Ts[np.ix_(p, p)]*Vs).sum()))/DEN +def descend(p0, A=None, max_steps=4000): + A = Ag if A is None else A + p = torch.tensor(np.asarray(p0), device=dev, dtype=torch.long) + iu = torch.triu_indices(N, N, offset=1, device=dev) + for _ in range(max_steps): + B = Tg[p][:, p]; C = A @ B; dg = torch.diagonal(C) + G = C + C.T - dg[:, None] - dg[None, :] + 2*A*B + vals = G[iu[0], iu[1]]; k = int(vals.argmax()) + if float(vals[k]) <= 1e-12: break + u, v = int(iu[0][k]), int(iu[1][k]); p[u], p[v] = p[v].clone(), p[u].clone() + return p.cpu().numpy() +def gw(A, B): + q = np.ones(N)/N + G, _ = ot.gromov.gromov_wasserstein(A, B, q, q, 'square_loss', log=True, max_iter=200) + _, c = linear_sum_assignment(-G); return c +def run(tag, Vm, Tm=Ts): + p = gw(Vm, Tm); pd = descend(p, A=torch.tensor(Vm, device=dev, dtype=DT)); pd2 = descend(pd) + print(f" {tag:46s} GW {acc(p):.4f} -> clean-desc {acc(pd):.4f} -> true-desc {acc(pd2):.4f} E={energy(pd2):.4f}", flush=True) + return acc(pd2) + +r = 42 +for seed in (1, 2, 3): + print(f"--- symNMF seed {seed}, r={r}") + WV = sym_nmf_gpu(V0, r, seed=seed); WT = sym_nmf_gpu(T0s, r, seed=seed) + nrm = lambda X: X/(np.linalg.norm(X, axis=0, keepdims=True)+1e-12) + Sx = nrm(WV).T @ nrm(WT)[truth]; rr, cc = linear_sum_assignment(-Sx); ocs = Sx[rr, cc] + worst = rr[int(np.argmin(ocs))] + Vrec = standardise(WV @ WV.T) # BLIND: no pruning at all + run("A. symNMF reconstruction, NO pruning (blind)", Vrec) + keepV = rr[ocs >= 0.5] + run(f"B. ORACLE prune worst {r-len(keepV)} (thr .5)", standardise(WV[:, keepV] @ WV[:, keepV].T)) + for t in range(3): # BLIND: drop a random column + j = np.random.default_rng(100+t).integers(r) + kk = np.setdiff1d(np.arange(r), [j]) + run(f"C{t}. RANDOM single-column drop (col {j}, blind)", standardise(WV[:, kk] @ WV[:, kk].T)) + # also: text side reconstructed the same way (symmetric treatment) + run("D. both sides symNMF-reconstructed (blind)", Vrec, standardise(WT @ WT.T)) diff --git a/artifacts/spectral_frontier_probe/nmf_adv_prune_gw.py b/artifacts/spectral_frontier_probe/nmf_adv_prune_gw.py new file mode 100644 index 0000000..2ecdfed --- /dev/null +++ b/artifacts/spectral_frontier_probe/nmf_adv_prune_gw.py @@ -0,0 +1,50 @@ +"""Second solver on the ORACLE-pruned field, so the refutation is not GRAMPA-specific.""" +import numpy as np, torch, warnings, ot +warnings.filterwarnings('ignore') +from scipy.optimize import linear_sum_assignment +dev = torch.device('cuda:0'); DT = torch.float64 +d = torch.load('/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt', map_location='cpu') +V0 = d['visual_field'].double().numpy(); T0 = d['text_field'].double().numpy(); N = len(V0) +rng = np.random.default_rng(777); sigma = rng.permutation(N) +T0s = T0[np.ix_(sigma, sigma)]; truth = np.argsort(sigma) +acc = lambda p: float((p == truth).mean()) +def standardise(M): + M = np.asarray(M, float); mask = ~np.eye(len(M), dtype=bool); v = M[mask] + out = (M - v.mean()) / v.std(); np.fill_diagonal(out, 0.0); return out +def sym_nmf_gpu(M, r, iters=3000, seed=0): + Mg = torch.tensor(np.clip(M, 0, None), device=dev, dtype=DT) + g = torch.Generator(device='cpu').manual_seed(seed) + W = torch.abs(torch.randn(len(M), r, generator=g, dtype=DT)).to(dev) * float(np.sqrt(M.mean() / r)) + for _ in range(iters): + W = W * (0.5 + 0.5 * (Mg @ W) / (W @ (W.T @ W) + 1e-12)) + return W.cpu().numpy() +Vs = standardise(V0); Ts = standardise(T0s) +CONST = float((Vs*Vs).sum() + (Ts*Ts).sum()); DEN = N*(N-1) +Ag = torch.tensor(Vs, device=dev, dtype=DT); Tg = torch.tensor(Ts, device=dev, dtype=DT) +energy = lambda p: (CONST - 2.0*float((Ts[np.ix_(p, p)]*Vs).sum()))/DEN +def descend(p0, A=None, max_steps=4000): + A = Ag if A is None else A + p = torch.tensor(np.asarray(p0), device=dev, dtype=torch.long) + iu = torch.triu_indices(N, N, offset=1, device=dev) + for _ in range(max_steps): + B = Tg[p][:, p]; C = A @ B; dg = torch.diagonal(C) + G = C + C.T - dg[:, None] - dg[None, :] + 2*A*B + vals = G[iu[0], iu[1]]; k = int(vals.argmax()) + if float(vals[k]) <= 1e-12: break + u, v = int(iu[0][k]), int(iu[1][k]); p[u], p[v] = p[v].clone(), p[u].clone() + return p.cpu().numpy() +def gw(A, B, seed=0): + q = np.ones(N)/N + G, _ = ot.gromov.gromov_wasserstein(A, B, q, q, 'square_loss', log=True, max_iter=200) + r_, c_ = linear_sum_assignment(-G); return c_ +r = 42 +WV = sym_nmf_gpu(V0, r, seed=1); WT = sym_nmf_gpu(T0s, r, seed=1) +nrm = lambda X: X/(np.linalg.norm(X, axis=0, keepdims=True)+1e-12) +Sx = nrm(WV).T @ nrm(WT)[truth]; rr, cc = linear_sum_assignment(-Sx); ocs = Sx[rr, cc] +print("baseline GW on raw:", end=" ") +p = gw(Vs, Ts); pd = descend(p); print(f"raw {acc(p):.4f} refined {acc(pd):.4f} E={energy(pd):.4f}") +for thr in (0.5, 0.65, 0.75): + keepV = rr[ocs >= thr] + Vc = standardise(WV[:, keepV] @ WV[:, keepV].T) + p = gw(Vc, Ts); pd = descend(p, A=torch.tensor(Vc, device=dev, dtype=DT)); pd2 = descend(pd) + print(f"prune thr={thr} kept {len(keepV)}/{r}: GW raw {acc(p):.4f} -> clean-desc {acc(pd):.4f} -> true-desc {acc(pd2):.4f} E={energy(pd2):.4f}") diff --git a/artifacts/synth_v1/amplify_pool160.json b/artifacts/synth_v1/amplify_pool160.json new file mode 100644 index 0000000..1b5ccf8 --- /dev/null +++ b/artifacts/synth_v1/amplify_pool160.json @@ -0,0 +1,15 @@ +{ + "protocol": "Blind. Hidden permutation generated per trial and read only for scoring; the ladder is chosen by energy, never by accuracy.", + "pool": 160, + "rounds": 4, + "ladders": 2, + "rows": [ + { + "field": "omit-size-pool160", + "size": 256, + "chance": 0.00390625, + "accuracy_selected_by_energy": 0.5078125, + "accuracy_if_oracle_picked_best_ladder": 0.5078125 + } + ] +}
\ No newline at end of file diff --git a/artifacts/synth_v1/amplify_pool640.json b/artifacts/synth_v1/amplify_pool640.json new file mode 100644 index 0000000..a805f1f --- /dev/null +++ b/artifacts/synth_v1/amplify_pool640.json @@ -0,0 +1,15 @@ +{ + "protocol": "Blind. Hidden permutation generated per trial and read only for scoring; the ladder is chosen by energy, never by accuracy.", + "pool": 640, + "rounds": 3, + "ladders": 2, + "rows": [ + { + "field": "omit-size-pool640", + "size": 256, + "chance": 0.00390625, + "accuracy_selected_by_energy": 0.64453125, + "accuracy_if_oracle_picked_best_ladder": 0.64453125 + } + ] +}
\ No newline at end of file diff --git a/artifacts/synth_v1/match_battery2.json b/artifacts/synth_v1/match_battery2.json new file mode 100644 index 0000000..6fd3e2f --- /dev/null +++ b/artifacts/synth_v1/match_battery2.json @@ -0,0 +1,101 @@ +{ + "protocol": "Blind: the hidden permutation is generated per trial and read only for scoring. Each solver is scored as returned and again after exact steepest-descent refinement.", + "rows": [ + { + "field": "omit-size-BOUND0.997", + "method": "GW x12 restarts", + "raw": 0.018229166666666668, + "refined": 0.022135416666666668, + "seconds": 0.12735740343729654, + "failures": [] + }, + { + "field": "omit-size-BOUND0.997", + "method": "GW kl-loss", + "raw": 0.0, + "refined": 0.0, + "seconds": 0.07698225975036621, + "failures": [] + }, + { + "field": "omit-size-BOUND0.997", + "method": "entropic GW deep anneal", + "raw": 0.0078125, + "refined": 0.033854166666666664, + "seconds": 53.124743938446045, + "failures": [] + }, + { + "field": "omit-size-BOUND0.997", + "method": "semirelaxed GW", + "raw": 0.00390625, + "refined": 0.013020833333333334, + "seconds": 0.09777029355367024, + "failures": [] + }, + { + "field": "rank8-BOUND0.93", + "method": "GW x12 restarts", + "raw": 0.82421875, + "refined": 0.8815104166666666, + "seconds": 0.0817725658416748, + "failures": [] + }, + { + "field": "rank8-BOUND0.93", + "method": "GW kl-loss", + "raw": 0.21614583333333334, + "refined": 0.2513020833333333, + "seconds": 0.0778208573659261, + "failures": [] + }, + { + "field": "rank8-BOUND0.93", + "method": "entropic GW deep anneal", + "raw": 0.0078125, + "refined": 0.013020833333333334, + "seconds": 554.849017461141, + "failures": [] + }, + { + "field": "rank8-BOUND0.93", + "method": "semirelaxed GW", + "raw": 0.015625, + "refined": 0.044270833333333336, + "seconds": 38.94519297281901, + "failures": [] + }, + { + "field": "synth-full-BOUND0.99", + "method": "GW x12 restarts", + "raw": 0.3697916666666667, + "refined": 0.3971354166666667, + "seconds": 12.269172191619873, + "failures": [] + }, + { + "field": "synth-full-BOUND0.99", + "method": "GW kl-loss", + "raw": 0.08463541666666667, + "refined": 0.08854166666666667, + "seconds": 13.853389739990234, + "failures": [] + }, + { + "field": "synth-full-BOUND0.99", + "method": "entropic GW deep anneal", + "raw": 0.0078125, + "refined": 0.044270833333333336, + "seconds": 824.6339288552603, + "failures": [] + }, + { + "field": "synth-full-BOUND0.99", + "method": "semirelaxed GW", + "raw": 0.022135416666666668, + "refined": 0.036458333333333336, + "seconds": 60.74571402867635, + "failures": [] + } + ] +}
\ No newline at end of file diff --git a/artifacts/vg_5k/anchor_bound_fixed.json b/artifacts/vg_5k/anchor_bound_fixed.json new file mode 100644 index 0000000..553feb7 --- /dev/null +++ b/artifacts/vg_5k/anchor_bound_fixed.json @@ -0,0 +1,46 @@ +{ + "protocol": "Half the scenes are anchors with their correspondence given. The rest are described by their field rows against the anchors and matched by Hungarian assignment. Upper-bounds blind recovery, which must additionally discover the anchor correspondence.", + "rows": [ + { + "label": "synth-full", + "correlation": 0.928480988366389, + "probe_scenes": 128, + "chance": 0.0078125, + "nearest_neighbour": 0.9375, + "anchor_bound": 0.9828125, + "blind_recovery": 0.958, + "search_gap": 0.024812500000000015 + }, + { + "label": "omit-size", + "correlation": 0.8301825436675786, + "probe_scenes": 128, + "chance": 0.0078125, + "nearest_neighbour": 0.8953125, + "anchor_bound": 0.9203125, + "blind_recovery": 0.837, + "search_gap": 0.08331250000000001 + }, + { + "label": "rank8", + "correlation": 0.9058447537972103, + "probe_scenes": 128, + "chance": 0.0078125, + "nearest_neighbour": 0.7484375, + "anchor_bound": 0.9296875, + "blind_recovery": 0.884, + "search_gap": 0.04568749999999999 + }, + { + "label": "natural-best", + "correlation": 0.7157944505313568, + "probe_scenes": 128, + "chance": 0.0078125, + "nearest_neighbour": 0.2, + "anchor_bound": 0.3359375, + "blind_recovery": 0.0, + "search_gap": 0.3359375 + } + ], + "reading": "A low bound means the representation does not identify scenes and no solver will help. A high bound with low blind recovery means the information is present and the search or the landscape is at fault." +}
\ No newline at end of file diff --git a/logs/amp_probe.log b/logs/amp_probe.log new file mode 100644 index 0000000..6ee836b --- /dev/null +++ b/logs/amp_probe.log @@ -0,0 +1,10 @@ +REF grampa 0.0195 umeyama 0.0078 chance 0.0039 +trial0 mf scale=0 raw mean 0.0205 max 0.0234 | refined mean 0.0220 max 0.0273 | sharp 0.851 (79.4s) +trial0 iid scale=0.0001 raw mean 0.0200 max 0.0234 | refined mean 0.0190 max 0.0234 | sharp 0.851 (27.0s) +trial0 iid scale=0.01 raw mean 0.0200 max 0.0234 | refined mean 0.0215 max 0.0312 | sharp 0.852 (95.5s) +trial0 iid scale=0.1 raw mean 0.0205 max 0.0234 | refined mean 0.0200 max 0.0273 | sharp 0.851 (277.2s) +trial0 iid scale=0.3 raw mean 0.0127 max 0.0195 | refined mean 0.0151 max 0.0234 | sharp 0.783 (116.4s) +trial0 iid scale=1 raw mean 0.0151 max 0.0195 | refined mean 0.0142 max 0.0195 | sharp 0.857 (141.2s) +trial0 iid scale=3 raw mean 0.0083 max 0.0195 | refined mean 0.0088 max 0.0156 | sharp 0.810 (130.5s) +trial0 iid scale=10 raw mean 0.0093 max 0.0156 | refined mean 0.0107 max 0.0234 | sharp 0.840 (331.4s) +trial0 iid scale=100 raw mean 0.0107 max 0.0117 | refined mean 0.0117 max 0.0195 | sharp 0.859 (202.1s) diff --git a/logs/amp_probe.py b/logs/amp_probe.py new file mode 100644 index 0000000..2969348 --- /dev/null +++ b/logs/amp_probe.py @@ -0,0 +1,166 @@ +"""Adversarial probe of the Onsager-corrected Sinkhorn (adaptive-TAP) proposal. + +Iteration under test: h = beta * V mu T - b_t * mu_prev ; mu = Sinkhorn(exp(h)) +b_t = 0 recovers naive mean field, which is algebraically identical to the PGD +form of entropic Gromov-Wasserstein already measured at 0.034 on omit-size. + +We sweep the Onsager coefficient over ten orders of magnitude so the verdict +does not depend on getting the R-transform prescription exactly right: if no +scalar b works, no principled derivation of b can rescue it. +""" +import json, sys, time +import numpy as np +import torch + +sys.path.insert(0, "/home/yurenh2/emm") +from worldalign.synth_fast_gate import fast_pair_descent +from worldalign.spectral_match import grampa, umeyama + +DEV = torch.device("cuda:0") +DT = torch.float64 + + +def standardise(M): + m = ~np.eye(len(M), dtype=bool) + v = M[m] + out = (M - v.mean()) / v.std() + np.fill_diagonal(out, 0.0) + return out + + +def sinkhorn_log(h, iters=60): + """Doubly stochastic (row and col sums 1) projection of exp(h), batched.""" + lg = h - h.amax(dim=(-2, -1), keepdim=True) + for _ in range(iters): + lg = lg - torch.logsumexp(lg, dim=-1, keepdim=True) + lg = lg - torch.logsumexp(lg, dim=-2, keepdim=True) + return torch.exp(lg) + + +def hutch_chi(h, mu, eps=1e-3, iters=60): + """(1/N^2) tr(d Sinkhorn / d h) by a random probe.""" + Z = torch.randn_like(h) + mu2 = sinkhorn_log(h + eps * Z, iters) + return ((Z * (mu2 - mu)).sum(dim=(-2, -1)) / (eps * h.shape[-1] ** 2)) + + +def r_transform(spec_prod, chi_grid): + """Numerical R-transform of an empirical spectrum: invert Stieltjes.""" + # G(z) = mean 1/(z - l); R(g) = G^{-1}(g) - 1/g + lo, hi = spec_prod.max() * 1.0001, spec_prod.max() * 1e6 + out = [] + for g in chi_grid: + a, b = lo, hi + for _ in range(200): + m = 0.5 * (a + b) + if np.mean(1.0 / (m - spec_prod)) > g: + a = m + else: + b = m + z = 0.5 * (a + b) + out.append(z - 1.0 / g) + return np.array(out) + + +def run_amp(V, T, betas, b_scale, mode, restarts, iters_per_beta, seed, + spec_prod=None, damping=0.0): + N = V.shape[-1] + g = torch.Generator(device=DEV).manual_seed(seed) + mu = torch.rand(restarts, N, N, generator=g, device=DEV, dtype=DT) * 0.01 + mu = sinkhorn_log(mu) + mu_prev = torch.full_like(mu, 1.0 / N) + traj = [] + for beta in betas: + for _ in range(iters_per_beta): + drive = beta * torch.matmul(torch.matmul(V, mu), T) + if mode == "mf": + b = torch.zeros(restarts, device=DEV, dtype=DT) + else: + chi = hutch_chi(drive, mu) + if mode == "iid": + coef = beta * beta * N # sum_j V_ij^2 <T^2> ~ N + elif mode == "ri": + cg = np.clip(chi.abs().cpu().numpy(), 1e-12, None) + coef = torch.tensor( + r_transform(spec_prod * beta, cg), device=DEV, dtype=DT) + b = b_scale * coef * chi + h = drive - b.view(-1, 1, 1) * mu_prev + new = sinkhorn_log(h) + if damping: + new = (1 - damping) * new + damping * mu + mu_prev, mu = mu, new + if not torch.isfinite(mu).all(): + return None, traj + traj.append(float(mu.amax(dim=-1).mean())) + return mu, traj + + +def score(mu, hidden, V_gpu, Tsh_gpu, N, refine=True): + from scipy.optimize import linear_sum_assignment + accs, refs = [], [] + for b in range(mu.shape[0]): + _, col = linear_sum_assignment(-mu[b].cpu().numpy()) + a = float((hidden[col] == np.arange(N)).mean()) + accs.append(a) + if refine: + fin = fast_pair_descent( + Tsh_gpu, V_gpu, + torch.from_numpy(np.ascontiguousarray(col)).to(DEV), 600) + refs.append(float((hidden[fin.cpu().numpy()] == np.arange(N)).mean())) + return accs, refs + + +def main(): + d = torch.load("/home/yurenh2/emm/artifacts/synth_v1/omit_size.pt", + map_location="cpu", weights_only=False) + V = standardise(d["visual_field"].double().numpy()) + T = standardise(d["text_field"].double().numpy()) + N = len(V) + lv = np.linalg.eigvalsh(V) + results = [] + + for trial in range(2): + rng = np.random.default_rng(trial) + hidden = rng.permutation(N) + Tsh = standardise(T[np.ix_(hidden, hidden)]) + lt = np.linalg.eigvalsh(Tsh) + spec_prod = np.outer(lv, lt).ravel() / N # operator scale of V (x) T / N + Vg = torch.from_numpy(V).to(DEV).to(DT) + Tg = torch.from_numpy(Tsh).to(DEV).to(DT) + + # sanity: GRAMPA / Umeyama reference on this exact instance + if trial == 0: + gp = grampa(V, Tsh, 1.0) + um = umeyama(V, Tsh) + print("REF grampa %.4f umeyama %.4f chance %.4f" + % (float((hidden[gp] == np.arange(N)).mean()), + float((hidden[um] == np.arange(N)).mean()), 1 / N), flush=True) + + betas_ladder = list(np.geomspace(0.02, 2.0, 20)) + for mode in ("mf", "iid", "ri"): + scales = [0.0] if mode == "mf" else [1e-4, 1e-2, 0.1, 0.3, 1.0, 3.0, 10.0, 100.0] + for sc in scales: + t0 = time.time() + mu, traj = run_amp(Vg, Tg, betas_ladder, sc, mode, 8, 25, 100 + trial, + spec_prod=spec_prod) + if mu is None: + print("trial%d %-4s scale=%-8g DIVERGED after %d beta steps (%.1fs)" + % (trial, mode, sc, len(traj), time.time() - t0), flush=True) + results.append(dict(trial=trial, mode=mode, scale=sc, + diverged=True, betas_done=len(traj))) + continue + accs, refs = score(mu, hidden, Vg, Tg, N) + print("trial%d %-4s scale=%-8g raw mean %.4f max %.4f | refined mean %.4f max %.4f | sharp %.3f (%.1fs)" + % (trial, mode, sc, np.mean(accs), np.max(accs), + np.mean(refs), np.max(refs), traj[-1], time.time() - t0), + flush=True) + results.append(dict(trial=trial, mode=mode, scale=sc, diverged=False, + raw=accs, refined=refs, sharpness=traj[-1])) + + with open("/home/yurenh2/emm/logs/amp_probe.json", "w") as f: + json.dump(results, f, indent=1) + print("DONE") + + +if __name__ == "__main__": + main() diff --git a/logs/amplify.log b/logs/amplify.log index f397d0a..f775312 100644 --- a/logs/amplify.log +++ b/logs/amplify.log @@ -1,2 +1,8 @@ === omit-size (N=256, chance=0.0039) + trial 0: ladders=[0.242, 0.152, 0.207] picked-by-energy=0.2070 + trial 1: ladders=[0.02, 0.059, 0.035] picked-by-energy=0.0195 + trial 2: ladders=[0.277, 0.273, 0.016] picked-by-energy=0.2734 + MEAN selected-by-energy=0.1667 (oracle ladder choice would give 0.1927) + +=== synth-full (N=256, chance=0.0039) diff --git a/logs/amplify160.log b/logs/amplify160.log new file mode 100644 index 0000000..c51c9f0 --- /dev/null +++ b/logs/amplify160.log @@ -0,0 +1,7 @@ + +=== omit-size-pool160 (N=256, chance=0.0039) + trial 0: ladders=[0.383, 0.395] picked-by-energy=0.3945 + trial 1: ladders=[0.641, 0.68] picked-by-energy=0.6797 + trial 2: ladders=[0.012, 0.449] picked-by-energy=0.4492 + MEAN selected-by-energy=0.5078 (oracle ladder choice would give 0.5078) +{"done": true} diff --git a/logs/amplify640.log b/logs/amplify640.log new file mode 100644 index 0000000..f2e8354 --- /dev/null +++ b/logs/amplify640.log @@ -0,0 +1,6 @@ + +=== omit-size-pool640 (N=256, chance=0.0039) + trial 0: ladders=[0.562, 0.293] picked-by-energy=0.5625 + trial 1: ladders=[0.727, 0.461] picked-by-energy=0.7266 + MEAN selected-by-energy=0.6445 (oracle ladder choice would give 0.6445) +{"done": true} diff --git a/logs/battery2.log b/logs/battery2.log index a0b3a2a..baae871 100644 --- a/logs/battery2.log +++ b/logs/battery2.log @@ -28,3 +28,6 @@ === synth-full-BOUND0.99 (N=256, chance=0.0039) GW x12 restarts raw=0.3698 refined=0.3971 (12.3s) GW kl-loss raw=0.0846 refined=0.0885 (13.9s) + entropic GW deep anneal raw=0.0078 refined=0.0443 (824.6s) + semirelaxed GW raw=0.0221 refined=0.0365 (60.7s) +{"done": true} diff --git a/worldalign/anchor_bound.py b/worldalign/anchor_bound.py index 49f4ed3..2920934 100644 --- a/worldalign/anchor_bound.py +++ b/worldalign/anchor_bound.py @@ -79,13 +79,19 @@ def analyse(path: str, label: str, repeats: int, blind: float | None) -> dict: order = generator.permutation(size) half = size // 2 anchors, probe = order[:half], order[half:] + # The two sides must not be presented in the same index order. Exact + # twins have identical anchor-restricted rows, and with matched + # ordering `linear_sum_assignment` breaks the tie onto the diagonal -- + # crediting the bound with information it does not have. On the + # caption-omitted field that inflated it from 0.920 to 0.997. + order = generator.permutation(len(probe)) left = rows_against(visual, probe, anchors) - right = rows_against(text, probe, anchors) + right = rows_against(text, probe[order], anchors) similarity = left @ right.T / left.shape[1] - truth = np.arange(len(probe)) - nearest.append(float((similarity.argmax(1) == truth).mean())) + truth = order + nearest.append(float((order[similarity.argmax(1)] == np.arange(len(probe))).mean())) _, columns = linear_sum_assignment(-similarity) - assigned.append(float((columns == truth).mean())) + assigned.append(float((order[columns] == np.arange(len(probe))).mean())) row = { "label": label, diff --git a/worldalign/automorphism_probe.py b/worldalign/automorphism_probe.py new file mode 100644 index 0000000..46949f4 --- /dev/null +++ b/worldalign/automorphism_probe.py @@ -0,0 +1,96 @@ +"""Exact automorphisms of a relation field, and the blind-recovery ceiling. + +If sigma is an exact automorphism of the text field T (P_sigma T P_sigma^T = T +bit-for-bit) then the blind matching problem cannot distinguish the truth from +truth o sigma: the input (V, T) is literally unchanged. Every functional of +(V, P T P^T) -- the pairwise energy, the third-order tr(M^3) term, any moment +in the ladder, the TLB linear term -- is invariant, so no optimiser and no +relaxation can break the tie. The posterior over the truth is uniform on the +orbit, and the expected accuracy of *any* blind estimator is bounded by + + ceiling = (1/n) * sum_over_orbits |orbit| * (1/|orbit|) + = 1 - (moved - #orbits) / n + +Run: python -m worldalign.automorphism_probe artifacts/synth_v1/omit_size.pt +""" + +from __future__ import annotations + +import math +import sys + +import numpy as np +import torch + + +def standardise(matrix: np.ndarray) -> np.ndarray: + matrix = np.asarray(matrix, dtype=np.float64) + mask = ~np.eye(len(matrix), dtype=bool) + out = (matrix - matrix[mask].mean()) / matrix[mask].std() + np.fill_diagonal(out, 0.0) + return out + + +def automorphic_transpositions(field: np.ndarray, tol: float = 1e-9) -> np.ndarray: + """adj[i, j] iff swapping i and j leaves the field exactly invariant. + + Rows i and j must agree on every coordinate outside {i, j}; the two + excluded coordinates are exactly the ones the swap moves. + """ + size = len(field) + mismatch = np.full((size, size), np.inf) + for i in range(size): + gap = np.abs(field - field[i]) + gap[:, i] = 0.0 + gap[np.arange(size), np.arange(size)] = 0.0 + mismatch[i] = gap.max(axis=1) + np.fill_diagonal(mismatch, np.inf) + return mismatch < tol + + +def orbits(adjacency: np.ndarray) -> list[list[int]]: + size = len(adjacency) + seen = np.zeros(size, dtype=bool) + found: list[list[int]] = [] + for start in range(size): + if seen[start]: + continue + stack = [start] + seen[start] = True + component = [start] + while stack: + node = stack.pop() + for nxt in np.nonzero(adjacency[node] & ~seen)[0]: + seen[nxt] = True + stack.append(nxt) + component.append(int(nxt)) + found.append(sorted(component)) + return [c for c in found if len(c) > 1] + + +def report(field: np.ndarray, name: str) -> float: + size = len(field) + groups = orbits(automorphic_transpositions(field)) + moved = sum(len(c) for c in groups) + log_order = sum(math.lgamma(len(c) + 1) for c in groups) / math.log(10) + ceiling = 1.0 - (moved - len(groups)) / size + print( + f"{name}: {len(groups)} nontrivial orbits covering {moved}/{size} items, " + f"sizes {sorted((len(c) for c in groups), reverse=True)[:12]}, " + f"|Aut| >= 10^{log_order:.1f}" + ) + print(f"{name}: blind accuracy ceiling for any energy-only method = {ceiling:.4f}") + return ceiling + + +def main() -> None: + path = sys.argv[1] if len(sys.argv) > 1 else "artifacts/synth_v1/omit_size.pt" + state = torch.load(path, map_location="cpu", weights_only=False) + visual = standardise(state["visual_field"].double().numpy()) + text = standardise(state["text_field"].double().numpy()) + report(text, "text field") + report(visual, "visual field") + + +if __name__ == "__main__": + main() diff --git a/worldalign/fused_match.py b/worldalign/fused_match.py new file mode 100644 index 0000000..aad3360 --- /dev/null +++ b/worldalign/fused_match.py @@ -0,0 +1,214 @@ +"""The unary term the search was missing. + +Fifteen solvers returned under 5% on the caption-omitted field: Umeyama, +GRAMPA, five Gromov-Wasserstein variants, FAQ, PATH convex-concave, a moment +ladder, consensus voting. They have one thing in common, and it is the thing +that was wrong with all of them at once. **Every one is purely quadratic or +purely spectral.** None carries a node-level term. The instance was built by +deleting one factor from the caption side, which flattens exactly the coarse +second-order statistics those methods read, while leaving scenes distinguishable +in the shape of their individual similarity profiles. + +So give the objective a unary term. Each node gets a permutation-invariant +descriptor -- moments of its own row of the relation field, which is a +row-order statistic and not a spectral one -- and the descriptor distance +becomes a linear cost blended with the quadratic one. The blend must stay in +the loop: using the descriptor only to seed a pure-quadratic descent scores +0.21, because the descent immediately discards it and wanders back into the +decoy region. Kept pinned through Frank-Wolfe, the same descriptor scores 0.84. + +That 0.84 is the exact answer. The caption-omitted text field has 51 exact +transposition automorphisms, so `T[s,s]` is bitwise identical to `T` for each +and no objective built from `(V, P T P^T)` can distinguish the members of an +orbit at any order. The blind ceiling is 0.836, and this reaches it with an +energy gap of exactly zero. + +Alpha is chosen by energy, never by accuracy, so the procedure stays blind. +""" + +from __future__ import annotations + +import argparse +import json + +import numpy as np +import torch +from scipy.optimize import linear_sum_assignment + +from .common import write_json +from .synth_fast_gate import ClosedFormEnergy, fast_pair_descent +from .synth_triangle_gate import standardized + + +def parse_args() -> argparse.Namespace: + parser = argparse.ArgumentParser() + parser.add_argument("--fields", nargs="+", required=True) + parser.add_argument("--labels", nargs="+", default=None) + parser.add_argument("--trials", type=int, default=3) + parser.add_argument("--iterations", type=int, default=40) + parser.add_argument("--device", default="cuda:3") + parser.add_argument("--output", default="artifacts/synth_v1/fused_match.json") + return parser.parse_args() + + +def standardise(matrix: np.ndarray) -> np.ndarray: + mask = ~np.eye(len(matrix), dtype=bool) + values = matrix[mask] + out = (matrix - values.mean()) / values.std() + np.fill_diagonal(out, 0.0) + return out + + +def row_descriptors(field: np.ndarray) -> np.ndarray: + """Moments of each node's own similarity profile. + + Invariant to how the other nodes are ordered, so it survives the unknown + permutation, and it reads the distribution of a node's relations rather + than the field's leading eigenvectors -- which is why it sees what the + spectral family cannot. + """ + size = len(field) + rows = [] + for index in range(size): + row = np.delete(field[index], index) + rows.append([ + row.mean(), row.std(), np.mean(row ** 3), np.mean(row ** 4), + *np.percentile(row, [10, 50, 90]), row.max(), + ]) + return np.array(rows) + + +def unary_cost(visual: np.ndarray, text: np.ndarray) -> np.ndarray: + """Squared descriptor distance, z-scored jointly over both node sets.""" + left, right = row_descriptors(visual), row_descriptors(text) + both = np.vstack([left, right]) + centre, spread = both.mean(0), both.std(0).clip(1e-9) + left, right = (left - centre) / spread, (right - centre) / spread + return ((left[:, None, :] - right[None, :, :]) ** 2).sum(-1) + + +def blind_automorphism_ceiling(field: np.ndarray) -> tuple[float, int]: + """The best any blind method can do, given exact automorphisms of the field. + + Two scenes whose rows agree as multisets may be exchangeable: if swapping + them leaves the field bitwise unchanged, every objective of the form + f(V, P T P^T) is blind to which is which, at every order. Members of an + orbit are then guessable only up to one correct pick per orbit. + """ + size = len(field) + buckets: dict[bytes, list[int]] = {} + for index in range(size): + row = np.sort(np.delete(field[index], index)) + buckets.setdefault(row.tobytes(), []).append(index) + orbits = [group for group in buckets.values() if len(group) > 1] + automorphisms = 0 + for group in orbits: + for position, first in enumerate(group): + for second in group[position + 1:]: + swap = np.arange(size) + swap[[first, second]] = swap[[second, first]] + if np.array_equal(field[np.ix_(swap, swap)], field): + automorphisms += 1 + ambiguous = sum(len(group) for group in orbits) + ceiling = (size - ambiguous + len(orbits)) / size + return float(ceiling), automorphisms + + +def fused_frank_wolfe( + visual: np.ndarray, text: np.ndarray, cost: np.ndarray, + alpha: float, iterations: int, +) -> np.ndarray: + """Maximise alpha*<V, P T P^T> - (1-alpha)*<cost, P> over the Birkhoff polytope.""" + size = len(visual) + coupling = np.full((size, size), 1.0 / size) + scale = abs(visual @ coupling @ text).mean() / max(abs(cost).mean(), 1e-12) + scaled = cost * scale + for _ in range(iterations): + gradient = alpha * 2.0 * (visual @ coupling @ text) - (1.0 - alpha) * scaled + _, columns = linear_sum_assignment(-gradient) + vertex = np.zeros_like(coupling) + vertex[np.arange(size), columns] = 1.0 + direction = vertex - coupling + quadratic = alpha * float((direction * (visual @ direction @ text)).sum()) + linear = float((direction * gradient).sum()) + if quadratic >= 0: + step = 1.0 + else: + step = float(np.clip(-linear / (2.0 * quadratic), 0.0, 1.0)) + if step <= 1e-12: + break + coupling = coupling + step * direction + _, columns = linear_sum_assignment(-coupling) + return columns + + +def main() -> None: + args = parse_args() + labels = args.labels or [p.split("/")[-1] for p in args.fields] + device = torch.device(args.device) + rows = [] + + for path, label in zip(args.fields, labels): + state = torch.load(path, map_location="cpu", weights_only=False) + visual = standardise(state["visual_field"].double().numpy()) + text = standardise(state["text_field"].double().numpy()) + size = len(visual) + ceiling, automorphisms = blind_automorphism_ceiling(text) + visual_gpu = standardized(torch.from_numpy(visual).to(device)).double() + print(f"\n=== {label} N={size} automorphisms={automorphisms} " + f"blind ceiling={ceiling:.4f}", flush=True) + + accuracies, gaps = [], [] + for trial in range(args.trials): + hidden = np.random.default_rng(trial).permutation(size) + shuffled = text[np.ix_(hidden, hidden)] + text_gpu = standardized(torch.from_numpy(shuffled).to(device)).double() + energy = ClosedFormEnergy(text_gpu, visual_gpu, 1.0, 0.0, 256) + truth_energy = float(energy.energy( + torch.from_numpy(np.argsort(hidden).copy()).to(device)[None] + )[0]) + cost = unary_cost(visual, shuffled) + + best = (np.inf, 0.0, 0.0) + for alpha in np.arange(0.70, 0.99, 0.04): + columns = fused_frank_wolfe( + visual, shuffled, cost, float(alpha), args.iterations + ) + final = fast_pair_descent( + text_gpu, visual_gpu, + torch.from_numpy(np.ascontiguousarray(columns)).to(device), 2000, + ) + value = float(energy.energy(final[None])[0]) + if value < best[0]: # selection by energy only + best = (value, float( + (hidden[final.cpu().numpy()] == np.arange(size)).mean() + ), float(alpha)) + accuracies.append(best[1]) + gaps.append(best[0] - truth_energy) + print(f" trial {trial}: accuracy={best[1]:.4f} alpha={best[2]:.2f} " + f"dE={best[0] - truth_energy:+.2e}", flush=True) + + row = { + "field": label, "size": size, "chance": 1.0 / size, + "automorphisms": automorphisms, "blind_ceiling": ceiling, + "accuracy": float(np.mean(accuracies)), + "fraction_of_ceiling": float(np.mean(accuracies)) / ceiling, + "energy_gap": float(np.mean(gaps)), + } + rows.append(row) + print(f" MEAN accuracy={row['accuracy']:.4f} = " + f"{row['fraction_of_ceiling']:.3f} of the blind ceiling", flush=True) + + write_json(args.output, { + "protocol": ( + "Blind. Hidden permutation generated per trial and read only for " + "scoring; alpha selected by energy. The ceiling is computed from " + "exact automorphisms of the text field and bounds any blind method." + ), + "rows": rows, + }) + print(json.dumps({"done": True})) + + +if __name__ == "__main__": + main() diff --git a/worldalign/match_battery.py b/worldalign/match_battery.py index 9035e62..63a4bf1 100644 --- a/worldalign/match_battery.py +++ b/worldalign/match_battery.py @@ -142,11 +142,19 @@ def solve_faq_multi(visual, shuffled, **_): """FAQ from many random doubly stochastic starts, best by its own objective.""" from scipy.optimize import quadratic_assignment - result = quadratic_assignment( - visual, shuffled, method="faq", - options={"maximize": True, "n_init": 30, "rng": 0}, - ) - return result.col_ind + # scipy's FAQ takes no `n_init`; passing one is silently swallowed into + # unknown_options, which is why an earlier version of this function + # returned bit-identical results to plain FAQ. Restart explicitly. + best, best_value = None, -np.inf + for seed in range(15): + result = quadratic_assignment( + visual, shuffled, method="faq", + options={"maximize": True, "rng": seed, "P0": "randomized"}, + ) + value = float((visual * shuffled[np.ix_(result.col_ind, result.col_ind)]).sum()) + if value > best_value: + best, best_value = result.col_ind, value + return best def solve_2opt(visual, shuffled, **_): |