Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Overfitting — where it appears

Estimating a model so closely to one sample that it describes the sample's accidents rather than the process that produced it. A substitution matrix fitted to a few pairs, or a compressor's statistics fitted to a short text, predicts that sample well and new data poorly.

Named by 4 essays across 4 fields — each of them below, with the objects they name alongside it.

H0H1H2H3H4model order — symbols of contextbits per symbol0.02.14.2Uniform over 8 symbolsOrder-1 Markov chainWords from a fixed vocabulary32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen oncemodels: orders 0, 1, 2, 3, 42.06 bits found by one symbol of context

The model is the compressor

One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.

text · Bits stay 0.9, 400 pairsacgtacgt0525505225045240stay 0.5, 400 pairsacgtacgt0212202112022120cost of aligning the row letter with the column letterpseudocount 1

The matrix a corpus wrote

A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.

tables · Cost 12481632641282561executed queries the fit sawexpected regrettrusting the estimatefitted from the queriesthe best divisor, 1.5ρ = 4, σ = 1.5, 120 fits a pointlower is better

What a planner pays to find out what to pay

Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.

applied · Transfer 125102050100200100observed queries the selection sawcells expanded, meanon fresh querieson the sample it was chosen fromthe cornersfarthest-first8 maps × 150 fresh queriesflat lines read no queries

What the queries know that the map does not

A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

SamplingBreak-evenCost modelParameter choiceAdaptive codingAlignmentCardinality estimationConditional entropyContext modelCorpusDesign parameterDistribution

All concepts