Newest-Vertex Bisection
Every face of the triangle mesh is a right triangle, and it can be split only one way: at the midpoint of its longest edge. Both halves are right triangles again, and each half’s longest edge is one of the old triangle’s short edges.
A vertex asked for in the middle of a short edge forces the triangle to split its long edge first, and that split can force a neighbour in turn. This chain is the conformity closure: it keeps every vertex at a corner of each triangle around it, never in the middle of an edge. The run starts from the square cut along one diagonal and split evenly to … faces. The drawing then asks for five splits near the run’s deepest vertex, with the engine’s rule computed on this page; the orange vertices are the ones the closure added, … in all. A vertex added this way sits exactly at the average of its two parents, so it does not change the surface.
Parents, Surplus and Tents
The surface is stored as corrections. A vertex that splits a segment has two parents, the segment’s ends. Its height is the average of its parents’ heights plus a number of its own, its surplus.
Changing one surplus moves that vertex and everything finer built on it. The surface changes by the surplus times a tent: a function that is 1 at the vertex and falls linearly to 0 at the neighbouring vertices of its level. Level by level, the tents add up to the whole surface, and on a smooth surface the deep surpluses are small. That is why a prior can pull each surplus toward zero. This drawing is a one-dimensional sketch.
The Same Sum in Two Dimensions
In two dimensions a tent covers the faces around its vertex. In the triangle mesh it is a pyramid over the two triangles that share the split edge; in the rectangle mesh it is a bilinear bump over the cells beside it.
The drawing rebuilds the rectangle run’s surface from its surpluses, adding one depth at a time. A vertex’s depth is the level of the segment it splits: the shorter the segment, the deeper the vertex. Rebuilt this way, the heights agree with the engine’s to within … logits. Only free vertices carry a surplus; every other vertex sits at its parents’ average.
Where the Score Comes From
A candidate is a vertex whose surplus is still held at zero. Its score says which way the fit would like that surplus to move: it is the slope of the log-likelihood as the surplus leaves zero.
For a site with n flips, k heads and fitted probability p, the slope is the tent’s height at the site times k − np, summed over the sites under the tent. Each term has variance tent² × np(1 − p): the site’s Fisher information, which measures how sharply its flips pin down its odds, weighted by the tent. The candidate drawn is the one with the largest round-0 |z| among the centres of the starting squares. Its sites are drawn against the final fit with the surface flattened across the square. With coin effects the engine replaces k − np by the site’s residual after its coin effect is estimated, centred on its expected value, and np(1 − p) by that residual’s information, which is smaller. A candidate with fewer than 10 sites under its tent is not scored.
Taking Out What the Parents Can Fit
Part of any tent can be made by coefficients already in the fit. If the data only need a steeper slope between the parents, the candidate should not get credit for it.
Write each coefficient’s tent, evaluated at the sites, as a column. The candidate’s column x splits into the closest combination Xa of the existing columns, measured with the sites’ weights and the prior, and a remainder x − Xa. The remainder’s weighted squared length, h, is the information left for the candidate alone. For the square in the last step, the tents at its four corners could absorb … of its tent, computed here with weights np(1 − p) on the sites inside the square. The engine uses every site, its own weights and the prior. The vector picture is a sketch.
Shrinkage Bias and the z
The prior pulls every surplus toward zero, so the fit falls a little short where the data want more. A candidate nearby picks up that shortfall in its score even when no new vertex is needed.
The engine estimates that part of the score as c′J−1Pθ, with θ the fitted coefficients and P the prior’s precision, and subtracts it. Because the fit sets X′s = Pθ, the corrected score is the score of the remainder, (x − Xa)′s. Dividing by its standard deviation, built from each site’s variance the same way, gives the candidate’s z. The surplus it proposes is S/(h + λ), with S the score and λ the prior’s precision at its depth. The top of the drawing is a one-dimensional sketch; the numbers below it are the engine’s.
Fitting the Null
If none of a round’s candidates mattered, their z’s would follow one bell curve, the null. The gate estimates that curve from the round’s own scores, by Lindsey’s method.
The scores are counted into 72 bins, each score split between its two nearest bins. A Poisson regression of the counts on a degree-6 polynomial in z gives a smooth log-density. A normal’s log-density is a parabola, and near zero the null dominates, so a parabola is fitted to the log-density over |z| ≤ 2 (central matching). Its peak gives the null’s centre, its curvature the spread, and its height π0, the share of candidates that are noise. Recomputed on this page from round 0’s scores: …. The engine’s: …. The spread is held between 0.35 and 6 (3 in the rectangle engine).
Three Ways to Pick
A candidate’s local false discovery rate, lfdr, is the chance it is noise given its z: π0 times the null’s density at z, divided by the fitted density. The gate sorts by lfdr and takes the longest run from the top whose average lfdr stays at or below 10%.
That average estimates the share of noise among those taken. On round 0’s scores the gate takes …. Benjamini–Hochberg at the same 10%, against the textbook null N(0, 1), would take …, and |z| > 1.96 would take …. The gate falls back to Benjamini–Hochberg only when a round has fewer than 50 candidates, or when the fitted density has no peak near zero to match.
Admitting One at a Time
Tents at neighbouring vertices overlap. If two candidates sit on the same bump in the data, both score well, but once one is admitted the other has less left to explain.
So the selected candidates are admitted one at a time, best first, and each is scored again against the surface the earlier admissions left. The surplus committed is the one from the new score. In this one-dimensional sketch, admitting A leaves B with … of its score.
Overlapping Tents in the Run
Round 0 of the run selected … candidates. Their tents are outlined here, numbered in the order they were admitted.
… A candidate is turned back only when its new score no longer promises a gain, which in practice means its score is exactly zero or fewer than 10 sites remain under its tent. Over the whole run the engine scored … candidates again at admission and turned back …. Admission first adds the candidate’s closure at zero surplus; those vertices stay even if the candidate is turned back.
Two Variances
The coin variance v is the spread of the coin effects around the surface. It is estimated again at the start of every round, by matching the squared residuals to what v predicts once the fit is allowed for.
As the mesh takes up the pattern in the odds, v falls toward the true …. The depth variance τ² sets the prior on the surpluses at one depth, with precision λ = 1/τ². It is estimated by EM: the average, over that depth’s admitted vertices, of the surplus squared plus its posterior variance. A depth needs three admitted vertices; with fewer it borrows from the nearest depth that has them. τ starts at 1 logit and never goes below 0.005.
Stopping
The rounds stop after three in a row select nothing, when no candidate can be scored, or when the mesh passes its face budget: … faces here, the larger of 600 and one face per 24 sites.
The whole surface is refitted at the start of every round and after every third round. After the last round comes one more refit. Then any coefficient whose tent covers no training site is retired, fixed at zero surplus: … here. Last comes a final refit with a tighter tolerance and more accurate variance calculations. This run took … rounds.
The Rectangle Engine
The rectangle engine runs the same gate on different cells. Each cell is a rectangle with a bilinear surface, and it can be cut along either axis, so each cell offers both cuts as candidates and the gate picks.
It starts from an 8 × 8 grid with the corners and the two midlines free. Cutting a cell leaves its neighbour with a vertex in the middle of an edge, a hanging vertex (orange). Its parents are the ends of that edge, so it sits on the edge’s line and the surface stays continuous without a closure. … Its null’s spread is capped at 3, and a round counts toward the three that stop the fit whenever it admits nothing, not only when it selects nothing. On the held-out half the mean deviance per site is … for the rectangles and … for the triangles. A site’s deviance is twice the log of how much likelier its flips are under its own share of heads than under the fit.