A variance that had seen one hash

A budget split before the question arrives gave two sets one budget of state, 40,960 bits each, and split it between a HyperLogLog and a bottom-k sample before anyone knew what intersection would be asked. The two estimate an intersection in different ways. Inclusion–exclusion adds the two sets’ HyperLogLog estimates — a count read off the leading zeros — and subtracts their union’s, and the error of a difference showed why that is good when the sets overlap a lot and hopeless when they overlap a little: three errors that are a per cent of a hundred thousand arrive as a multiple of an intersection of a hundred. The sample keeps the smallest hashes of each set and estimates the intersection as the share of the union’s smallest hashes that both sets hold, times the union’s size, which is good at small overlaps as long as some shared hash is seen at all.

The covariance the registers already hold found the best way to use both. Weight them by the inverse of their variances, with inclusion–exclusion’s variance read from thirty-two groups of its own registers, so that the covariance between a set’s estimate and the union’s is measured rather than dropped, and the sample’s taken as a binomial proportion. Against an oracle that knew the overlap before spending a bit, the weighting’s worst regret over overlaps from 0.98 to 0.001 was 1.70 at an even split, the best any rule had reached. At seven eighths of the budget in registers it was 4.46, worse than any rule there, and all of it at the smallest overlap.

That essay’s closing section explained the corner. A sample of 160 hashes asked about two sets sharing one key in a thousand expects a sixth of a shared hash, usually sees none, and its estimated overlap of nought makes its binomial variance nought, so the weighting believes the sample completely at the one overlap where it knows least. It proposed the correction a proportion with no successes needs: half a shared hash added to the count, and the variance taken at that estimate. The prediction was that the worst regret at seven eighths would fall from 4.46 to under 2.5, while the even split stayed at 1.70, leaving a regret curve under two from two eighths to seven.

What the variance had been #

The study is the earlier essays’: two sets of 100,000 keys at ten overlaps, 64 draws each, every split of the budget in eighths, the same hashes, the same thirty-two groups of registers. The mean relative error of each rule at each overlap — an error measured, as an error measured against the answer insisted, against the true intersection rather than the union — is divided by the oracle’s best at that overlap, any split and either method, and a rule’s worst regret at a split is the largest of those ratios.

Reading the rule before changing it turned up the first finding. The sample’s binomial variance is computed at an overlap $J = \max(\hat J, 1/k)$: a sample that saw no shared hash is given the variance it would have had if it had seen one. That floor was always there. So the variance in the corner was never nought, and the account of the corner was wrong about the direction of the error. The question for the half hash is then which way it moves a variance that was taken at one hash.

It moves it down. Half a hash, $(\text{shared} + \tfrac12)/(k + 1)$, is about half the floor’s $1/k$, and the variance at a small share scales with the share. So the correction the proposal described as making the sample admit its ignorance makes the sample claim more certainty, not less, wherever it saw nothing. Two versions were run: the variance taken at half a hash with the estimate left as it was, and the estimate’s share taken at half a hash as well — which is what adding half a hash to the count says. To see what the corner actually wants, the floor itself was swept, from a tenth of a hash to two.

Lower, but not under two and a half #

Half a shared hash in the sample’s variance cuts the weighting’s worst regret at seven eighths from 4.46 to 3.08, not under the 2.5 predicted; put into the estimate as well it gives 3.74 there, but 1.61 at five eighths — the lowest worst regret of any split and rule measured, under the 1.70 the register weighting reached at an even split. The even split does not move, as predicted: its sample holds 640 hashes and sees a shared one at every overlap except the smallest, where it sees none in 41 of 64 draws and its inclusion–exclusion is useless anyway. From one eighth to four, the three register weightings agree to the hundredth.

The prediction is wrong where it was made and right somewhere it was not. At seven eighths the half hash helps, by 1.38, but a regret of 3.08 is still the worst of any split from two eighths to six, and the curve the proposal hoped for, under two from two eighths to seven, does not exist: seven eighths is at 3.08 at best and two eighths at 2.44 for every register weighting. At five and six eighths the half hash in the estimate is the only change that helps, 1.83 to 1.61 and 2.16 to 1.84. The textbook weighting, with no register variance at all, has the lowest regret at seven eighths, 2.63, which the earlier essay recorded and did not dwell on.

What 160 hashes see #

A sample of 160 hashes expects 0.16 shared hashes when the sets share one key in a thousand and sees none in 91% of draws; it sees none in 52% at an overlap of 0.005 and in 19% at 0.01 — the smallest overlaps, where the weighting’s regret is worst. These are the draws where the floor decides everything. A draw that sees no shared hash estimates the intersection as nought, which is wrong by exactly its whole size, a relative error of one. A draw that sees one shared hash estimates it as the union over 160, about 1,250 keys where the truth at 0.001 is 200 — a relative error of about five. Six of the 64 draws at that overlap see one, and they contribute most of the sample’s mean error of 1.49.

So the sample at that overlap has two answers, nought and six times the truth, and no variance computed from what it saw can tell it which is nearer. The weighting asks a different question, how far to trust the sample against inclusion–exclusion, and the plate shows why that question is hard here: inclusion–exclusion is worse still, a mean error of 7.87, and the right answer is nearly always “trust the sample”, whatever the sample says.

A weight that was too small #

The weighting never believed the sample completely: with its variance floored at one shared hash, it gave the sample 0.66 of the weight at an overlap of 0.001; half a hash lowers the sample’s variance and raises its weight to 0.77 — the opposite of the repair the proposal thought it was making, and the reason the repair helped. With a third of the weight on inclusion–exclusion, whose relative error there is nearly eight, most of the blend’s error of 2.89 is inherited from it. Moving a ninth of the weight back to the sample takes that inherited error from 2.89 to 2.00.

The plate also shows where the half hash costs something. At an overlap of 0.01, where the sample sees a shared hash in four draws of five and its estimate is informative, the weight barely changes, 0.54 to 0.52. At 0.005 it rises from 0.62 to 0.66, and there the half-variance rule’s error rises too, from 0.86 to 0.91: a draw that saw one hash is now given a little more credence when its answer is several times the truth. A correction to the variance of a draw that saw nothing also changes the variance of a draw that saw one, since the half is added to every count.

The floor the corner wants #

Swept, the floor under the sample’s shared hashes wants to be small at seven eighths — worst regret 2.80, 2.74, 3.09, 4.46 and 6.24 at floors of a tenth of a hash, a quarter, a half, one and two — and does not matter below a hash at five and six eighths; no floor brings seven eighths under 2.74. A floor of a quarter of a hash is the best measured and the half hash is a little worse; a floor of two, a rule more cautious than the earlier one, more than doubles the regret again. The direction is unambiguous. In this corner the sample’s variance should be smaller than any formula with a real count in it would give, because the competing estimate is so much worse that the sample should take nearly all the weight even when it has seen nothing.

That is not a statement about proportions. The textbook treatment of a proportion with no successes — add a half to the count, or bound the proportion by three over the sample size — is about how sure to be of the proportion itself. The weighting’s question is relative: how sure of this estimate compared with that one. At five and six eighths the sample is large enough that its variance is not the binding term, and every floor below a hash gives the same answer to the hundredth.

A corner set by the sample #

At an overlap of one key in a thousand no weighting measured does better than the sample alone, whose mean error of 1.49 is 2.30 times the oracle’s 0.649: the corner’s regret is set by 160 hashes expecting a sixth of a shared one, and the weightings’ mean errors of 2.89, 2.00 and 2.43 are what each lets in of inclusion–exclusion’s. The oracle’s 0.649 comes from a split with more of the budget in the sample: with none of it in registers, 1,280 hashes expect about 1.3 shared hashes at that overlap, enough for an estimate. A split that gives the sample 160 has decided, before any question is asked, that this overlap will be answered badly, and a weighting can only choose how much worse than badly.

That is the regret’s floor at seven eighths: about 2.3 at the smallest overlap, whatever the weighting. The floors measured come within half of it, 2.74 at a quarter of a hash, and their worst regret moves to the next overlap up, 0.0025, where the sample sees a shared hash in a quarter of draws and a lowered variance trusts those draws’ inflated answers. Getting the corner under 2.5 would need a rule that gave the sample all the weight when it saw nothing and much less when it saw one, which is a rule about the count’s value, not its variance.

Half a hash in the estimate #

Adding the half to the estimate as well changes what the sample reports when it saw nothing: not nought, but half a hash’s share of the union, about 620 keys at seven eighths where the truth at 0.001 is 200. That is a relative error of two instead of one, and it is why the half-estimate rule is worse in the corner, 3.74 against 3.08. At five and six eighths it is the better rule. There the sample holds 480 or 320 hashes, an overlap of 0.001 means 0.5 or 0.3 shared hashes expected, and an estimate pulled up by half a hash is pulled toward the truth rather than past it: the intersection’s true share is then between nought and the half hash’s share, and a draw that saw nothing is less wrong reporting the half than reporting nought.

So the same correction is a good estimator for a sample that expects about half a shared hash and a bad one for a sample that expects a sixth. The correction that makes it work found the same shape in the HyperLogLog’s own small-range correction: a fix tuned to one regime is a bias in the next. The minimax split moves accordingly. Under the register weighting it was the even split at 1.70; under the half-estimate rule it is five eighths at 1.61, a split with more registers and a sample just large enough for the half to be right.

What one study cannot settle #

Two sets of equal size. Every number is for sets of 100,000 keys each. The earlier essay ran sets of uneven size and the weighting did well there; the corrections here were not run on them, and an uneven pair changes how many shared hashes a sample of the smaller set expects.

Ten overlaps and 64 draws. The worst regret is a maximum over ten overlaps of means over 64 draws, and in the corner those means are of draws that mostly report one of two values. A different set of 64 seeds would move the corner’s numbers by more than the differences between the floors of a tenth and a quarter.

The oracle’s other split. Regret is against the best split at each overlap, so seven eighths is charged for being seven eighths. That is the right charge for a budget chosen in advance, which is the question the split asks, and it means no rule at seven eighths can escape the cost of having given the sample 160 hashes.

One correction family. A floor, or a half added to the count. A rule that weighted the sample by whether it had seen anything at all — all the weight on a draw that saw nothing, a little on a draw that saw one — was not run, and the corner plate suggests it is the shape of what the data want.

What a planner pays to find out what to pay and a planner that knows how sure it is both found that an estimate’s stated uncertainty is worth exactly as much as the decision it changes, and here the decision is a weight, which an uncertainty about the proportion was never designed to set.

Still open: a weight that reads the count #

The plates point at a rule that is about the count, not the variance. In the corner the sample has two answers, nought and several times the truth, and the right weight for each differs: a draw that saw nothing is the sample’s best answer at the smallest overlaps and should be believed almost entirely, while a draw that saw one shared hash at an expected sixth is mostly luck and should be pulled toward inclusion–exclusion’s, which is itself useless there. A weight can be read from the count directly: give the sample the weight its floor of a quarter hash gives when it saw no shared hash, and the weight of the register weighting when it saw two or more, and treat a single shared hash as half of each.

The measurement that follows runs that rule, and a version that shrinks the sample’s estimate after a single shared hash toward the half hash’s share, at every split on both the even and the uneven pairs. The prediction is that the corner at seven eighths falls under 2.5 at last, to about 2.4, because the draws that saw one hash stop dragging the mean, and that five eighths stays at 1.61. It could fail on the shrinkage: a single shared hash at an overlap of 0.01 is the sample’s honest evidence, and shrinking it there to protect the smaller overlaps may cost more than it saves. The question is whether a sample’s few hashes can be weighed by how many it saw, or whether below about one expected shared hash the budget’s split is the only decision that matters.