summaryrefslogtreecommitdiff
path: root/MATCHING_RESULTS.md
diff options
context:
space:
mode:
Diffstat (limited to 'MATCHING_RESULTS.md')
-rw-r--r--MATCHING_RESULTS.md114
1 files changed, 108 insertions, 6 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.