The parameter plane has few answers

The matrix a corpus wrote found that changing two entries of a fitted substitution matrix by a bit each moved three alignments in ten. That is a statement about sensitivity, and it has an unexpected implication about the shape of the space of cost models. If a small change moves many alignments completely — not nudges them — then as costs vary continuously, each pair’s optimal alignment must jump between discrete answers and hold still in between.

This page draws that directly. It takes one pair of strings and one cost model with two free parameters, computes the optimal alignment at every setting of a grid of hundreds, and colours each setting by which alignment won. The picture is the parameter plane, and the question it answers is how many different answers the plane contains.

The model and the grid #

Two models are swept.

Affine. A substitution costs one. A gap of length $L$ costs $o + L \cdot e$, where $o$ is the cost of opening it and $e$ the cost of each character. The two parameters are $o$ and $e$, each swept from 0.25 to 6 in steps of 0.25 — 576 settings.

Linear. A substitution costs $s$ and every gap character costs $g$, with no opening charge. The two parameters are $s$ and $g$, over the same grid.

At each setting the optimal global alignment is computed with the site’s affine table, ties broken the way every traceback on this site breaks them, and the alignment’s two rows are recorded as its identity. Two settings belong to the same region if their alignments are character-for-character the same.

Five hundred and seventy-six settings, four answers #

The plane is almost entirely one colour. The two words have the same length, nine letters, and aligning them without gaps costs five substitutions. Any alignment with gaps must put them in pairs — one in each string, to keep the lengths equal — so it pays at least two openings and two extensions, at least $2o + 2e$, and it must save more than that in substitutions. On most of this grid no gap pair saves enough, so the gapless alignment wins almost everywhere.

The other three regions are small and all near the origin. That is where gaps are nearly free, and there the aligner can buy substitutions away by shifting: “inte-ntion” against “-execution” lines up $e$ with $e$ and $tion$ with $tion$ at the price of two single-character gaps, and wins when two openings and two extensions cost less than the two substitutions they remove.

The count is the finding: four alignments across 576 settings. Every other number on the plate is how the settings are divided among them.

Why the regions are polygons #

The shape of every region on these plates follows from one observation, and it is worth making because it turns the pictures from measurements into predictions.

Fix a single alignment — a particular path through the table — and ask what it costs as the parameters vary. Its cost is its number of substitutions, times the substitution cost, plus its number of gap runs times $o$, plus its number of gap characters times $e$. Every one of those counts is a property of the path, fixed once the path is fixed. So under the affine model each alignment’s cost is a linear function of $(o, e)$: a plane over the parameter plane, with a slope set by how many gaps the alignment opens and how long they are.

The optimal alignment at a setting is the one whose plane is lowest there. The lowest of a collection of planes is their lower envelope, and the region where any one plane is lowest is an intersection of half-planes — a convex polygon, bounded by straight lines where two alignments’ costs are equal. For this pair the gapless alignment costs 5 everywhere; “inte-ntion” against “-execution” costs $3 + 2o + 2e$, so the boundary between them is the line $o + e = 1$; and “inte—ntion” against “—execution”, with one substitution and two runs of three, costs $1 + 2o + 6e$, meeting the gapless alignment along $o + 3e = 2$. Every boundary on the first plate is a segment of a line like these.

That also explains why regions are few. A path through a table of nine by nine has a great many possible shapes, but its cost depends on it only through three counts, and many paths share the same three counts. Among paths with the same counts, the lowest-cost one is the same everywhere in the plane. So the number of regions is bounded by the number of distinct count triples that can ever be lowest — which is far smaller than the number of paths — and a distance that is a path through a grid is the reminder that it is paths, not scores, that the table is choosing among.

A finer grid finds one more #

Refining the grid found exactly one new alignment, and found it where one would look: in the corner closest to the origin, where gap costs below the coarse grid’s smallest value make a long shift affordable. Every region from the coarse grid is still present, a little larger in settings because there are four times as many settings, and nothing new appeared anywhere else.

That is what a plane with few answers looks like under refinement. A plane with many answers would gain new regions all over as the grid tightened; this one gains them only at its edge, where the model’s parameters approach a degenerate value. The published analysis of parametric alignment bounds the number of regions for two parameters by a power of the strings’ length smaller than one — for global alignment of two strings of length $n$, a bound that grows like $n^{2/3}$ — which says the same thing in the limit: the number of answers grows far more slowly than the length of the strings.

The linear model’s regions are wedges #

The linear model’s picture is geometrically different, and the difference has a one-line explanation. If every cost — every substitution and every gap character — is multiplied by the same positive factor, every alignment’s total cost is multiplied by that factor, and the cheapest alignment stays cheapest. So the optimal alignment at $(s, g)$ is the same as at $(2s, 2g)$, and at every point on the ray from the origin through $(s, g)$. Regions are unions of rays. They are wedges.

That means the linear model has one real parameter, not two: the ratio $g/s$. Everything a two-dimensional sweep of the linear model can find, a one-dimensional sweep of the ratio finds too, and the site’s check verifies this directly — it scales every setting on the grid by two and requires the alignment not to change — so the claim is enforced rather than argued.

With a single ratio the boundaries can be computed by hand. The gapless alignment costs five substitutions, $5s$. The alignment “inte-ntion” against “-execution” has two single-character gaps and three substitutions, $3s + 2g$. The four-gap alignment has eight gap characters and no substitutions, $8g$. Setting them equal pairwise: the gapless alignment beats the two-gap one exactly when $g \ge s$, the two-gap one beats the four-gap one when $g \ge s/2$, and so the plane divides along the lines $g = s$ and $g = s/2$. On the 24-by-24 grid the settings with $g \ge s$ number $24 \times 25 / 2 = 300$ — which is the gapless region’s count on the plate, exactly.

The affine model does not have this property, because the opening charge is not proportional to anything: scaling $o$ and $e$ together while holding the substitution at one changes the ratio of gap cost to substitution cost. Its regions are genuine polygons. But even there, the count on the first plate says the extra parameter bought one additional alignment over the linear model’s three.

Other pairs #

Strings of different lengths change the picture, because gaps are no longer optional: a 21-character string aligned against a 17-character one needs at least four gap characters in the shorter string whatever the costs. The parameters now decide not whether to open gaps but how to group them — one long gap, or several short ones — and the plane divides into three large regions of comparable size rather than one dominant one.

That is the regime where tuning matters. It is also where the affine model’s second parameter earns its place: with the lengths unequal, the trade between one long gap and several short ones is precisely a trade between openings and extensions, and a model with only a per-character cost could not express a preference either way. The model has parameters is the theme, and this plate is a case where both parameters are doing work rather than one of them being redundant. Along the boundary between the 312-setting region and the 167-setting region, a small change in the ratio of opening to extension cost regroups the gaps, and the two alignments claim different correspondences for several characters. A practitioner sweeping gap parameters on a benchmark of such pairs would see the benchmark score change at those boundaries and not between them.

The single-setting region on this plate is worth a sentence of its own. One alignment wins at exactly one of the 576 settings, at the corner where both gap costs are smallest, and nowhere else on the grid. It is a real optimum — at that setting its cost is strictly lowest — and it would be found by an exhaustive search of this grid and missed by any search that sampled a coarser one. Regions that small are the reason a reported optimum should be read with its neighbourhood: an alignment that is optimal at a point and nowhere around it is an answer that one step of estimation error will take away.

The second pair has different lengths too and yet is nearly all one region. Its dominant alignment puts all four forced gaps in one run at the end, where one opening pays for all of them; alternatives that scatter the gaps to line up more letters pay three extra openings, and three openings of at least 0.25 each cost more than the substitutions they remove everywhere except the very corner.

So whether a pair’s plane is dominated by one region depends on the pair — on how many substitutions a rearrangement of gaps can buy, set against how many openings it costs. What does not depend on the pair is that the number of regions is small.

Different models give different answers to the same pair #

The regions on the plates above are regions within one model family. A cost that is not one is the neighbouring case — two different families aligning the same pair differently — and the parameter plane gives it a picture: a change of model is a jump to a different plane altogether, and the only reason the two alignments disagree is that the two planes put the pair’s settings in different regions. Neither alignment is better in any sense that does not name a model, which is the definition is not the algorithm applied to the word “optimal”. A distance divided by a length found a further move of the same kind: dividing a cost by an alignment’s length changes the objective from a linear function of the parameters to a ratio of two, and a ratio’s lower envelope is no longer made of planes — so even the polygon picture above belongs to a choice of objective.

What few answers means for choosing parameters #

The practical content of the page is about tuning, and it runs against a common picture of it.

The common picture is a landscape: parameters are dials, a benchmark score is a smooth function of them, and tuning is climbing to the peak. The plates say the landscape for a single pair is a set of flat terraces with cliffs between them. Every setting in a region produces the same alignment and therefore the same score; the score changes only when a boundary is crossed, and it changes by a whole alignment’s worth.

For a benchmark of many pairs, the terraces of the individual pairs overlap, and the total score is a sum of step functions — which is why tuning curves for aligners look flat over wide ranges and then move abruptly. The flat bottom of a shallow curve finds the same flatness around a tuning optimum in a different setting, and here it has a structural cause: most settings near an optimum are in the same regions for most pairs.

Two consequences follow. A reported setting — “gap open 10, extend 1” — names a region more than a point, and any setting in the same region for the same data is equivalent to it. The zero-cost end gaps of the zero that moves the answer are a setting on the boundary of this plane in a third direction, and they move alignments for the same reason crossing any boundary does. And the settings that matter are the ones near boundaries, because those are where a small error in a fitted parameter flips answers; the threshold somebody chose found shipped constants sitting at arbitrary points inside wide flat regions for sorting routines, which is harmless for the same reason and would be harmful for the same reason if the region were narrow.

What the plates leave out #

One pair at a time. A region is a property of a pair, and the plates draw one pair per plate. The picture that bears directly on tuning is the overlay of many pairs’ regions, whose cells are the settings between which no pair’s alignment changes, and that overlay has not been drawn.

Ties are broken one way. Exactly on a boundary two alignments cost the same, and which one the traceback reports is decided by its tie rule. The boundaries’ positions are properties of the model; which side of a boundary a setting lying exactly on it is assigned to is a property of the implementation.

A grid, not the true regions. A region smaller than a grid cell can be missed entirely, as the refinement showed. Exact parametric methods compute the true boundaries by solving for the settings where two alignments’ costs are equal, which is how the published bounds are proved; the grid here is a measurement that can undercount and cannot overcount.

The substitution cost is held at one. The affine plates fix one of three natural parameters and sweep the other two, and the linear plates fix none but have one redundant. A full affine model has substitution, opening and extension costs, and scaling all three together changes nothing — so it has two real parameters, and the affine plates above are one slice of its two-dimensional space of ratios, not the whole of it. A different slice, say with extension held fixed, would show the same regions cut at a different angle, since a region is a property of the ratios and not of which cost was chosen to be one.

Where this ladder goes next: how far an alignment is from a tie #

The plates suggest a quantity that the sensitivity result on the rung before this one needed and did not have: for a given pair and a given setting, how far the setting is from the nearest boundary. A setting deep inside a region has an alignment no small change of parameters can move. A setting close to a boundary has an alignment that a bit of estimation error will flip.

That distance is computable — it is the smallest change in the costs that makes some other alignment’s total equal to the optimal one’s — and it predicts something checkable. The 200 test pairs of the matrix a corpus wrote moved in 30 to 57 per cent of cases between matrices; if the account on this page is right, the pairs that moved should be the ones whose settings sat nearest a boundary, and the pairs deep inside their regions should not have moved at all. The next rung measures that margin for each test pair and asks how well it predicts which alignments a refitted matrix will change — which, if it works, is a way to report with each alignment how much the answer can be trusted.