Monotone regression splines keep a cumulative registration curve from going backwards

The pacing chart went out on Monday with a visible dip in week nine. Cumulative registrations at 4,505, then 4,210 the following week. Somebody asked whether three hundred people had cancelled.

Nobody had cancelled. A duplicate upload from a media partner had been cleaned up on the Thursday, and the cumulative count fell because the definition of a registration changed underneath the series. The smoother drew a curve straight through the dip, and because the chart also displayed a fitted trend, the forecast built on it briefly implied a negative arrival rate for a fortnight in the middle of the campaign.

Monotone regression splines exist for exactly this. Cumulative registrations cannot fall, so any fit that dips is wrong before you evaluate it against anything.

A cumulative series has a constraint built into it

The constraint is worth stating precisely, because half the value of imposing it is being clear about what it means.

A cumulative count at day t is the number of registrations received on or before day t. That number is non-decreasing in t as a matter of definition. It can stay flat, on a dead weekend or during a system outage, and it cannot go down. The derivative of the curve is the daily arrival rate, and a daily arrival rate below zero would be a day on which negative people registered.

A dip in the raw series therefore has exactly two possible causes. Either the data changed retrospectively, through a deduplication run, a cancellation batch or a correction, or the snapshots were taken from different sources and are not the same measurement. Both are worth investigating and neither is demand.

An unconstrained smoother has no way to know this. It sees a sequence of numbers, minimises squared error against them, and produces the best-fitting wiggle including the dip. Constraining the fit removes an entire class of wrong answers from the search space before evaluation starts, which is the cheapest kind of modelling improvement there is.

What does the pool adjacent violators algorithm actually do?

It solves the constrained least squares problem directly, and the mechanism is simple enough to do by hand.

de Leeuw, Hornik and Mair set the problem out in the Journal of Statistical Software in 2009, in the paper accompanying the isotone package for R. The monotone regression problem is to choose fitted values that minimise the weighted sum of squared differences from the observed values, subject to the fitted values being non-decreasing along the series. Their statement of the basic theorem behind the solution is the whole algorithm in one line: where an observed value is at least as large as the next one, the two fitted values are set equal.

So you walk the series. Wherever a value is smaller than the value before it, you merge the two into a block and give both the block's mean. Then you recheck backwards, because merging may have created a new violation with whatever came before. When no violations remain, you stop, and the result is provably the closest non-decreasing series to your data under squared error.

The history is longer than the algorithm. de Leeuw and colleagues trace it to Ayer and co-authors and to Brunk, both in the Annals of Mathematical Statistics in 1955, with van Eeden's 1958 Amsterdam dissertation the most general of the classical treatments. Their own contribution extends the standard implementation to observation weights, several approaches to tied predictor values, and loss functions other than squared error. That last extension has a practical reading for registration data, which I come back to below.

The worked pass over five snapshots

Five weekly cumulative snapshots from the show above: 4,120, then 4,505, then 4,210, then 4,300, then 4,900.

The weekly increments are plus 385, minus 295, plus 90 and plus 600. The second one is impossible, and the third is suspiciously small because it is still recovering from the correction.

Run the algorithm. The first violation is 4,505 followed by 4,210. Pool them: their mean is 4,357.5, so both become 4,357.5. Now recheck forwards. The next value is 4,300, which is below 4,357.5, so it joins the block. The block is now 4,505, 4,210 and 4,300, whose mean is 13,015 over 3, or 4,338.33. Recheck backwards against 4,120, which is lower, so that is fine. Recheck forwards against 4,900, which is higher, so that is fine too.

The fitted series is 4,120, then 4,338.33 three times, then 4,900. The implied increments are plus 218.33, zero, zero, then plus 561.67. Divided by seven days that is 31 registrations a day, then a flat fortnight, then 80 a day.

Read what the fit is telling you. It is not claiming that nobody registered for two weeks. It is saying that across those three snapshots the total moved by an amount consistent with 4,338 at every one of them, and that the data cannot distinguish between them. That is an honest summary of a period during which the definition of the count was being repaired.

One variation is worth knowing. The pooled value is a mean because the loss is squared error. de Leeuw and colleagues generalise the algorithm to absolute-deviation loss, where the pooled value becomes the weighted median instead. On the block above the median is 4,300 rather than 4,338.33, a difference of 38 registrations, and the median version is the one to prefer when the dip came from a single bad snapshot rather than from noise spread across several.

Where the smooth version comes in

The pooled fit is a staircase, and a staircase is an awkward thing to differentiate or to extrapolate from.

Ramsay published the smooth treatment in Statistical Science in 1988 under the title monotone regression splines in action. His argument for splines over polynomials is the one that applies here directly: piecewise polynomials give you flexibility, they localise the effect of a parameter change, and they allow useful constraints to be imposed on the estimated function, monotonicity among them. He works the idea through a set of statistical applications, including transformation of the response in nonlinear regression and dose-response modelling, and discusses the computational and inferential side of fitting them.

For a booking curve the appeal is concrete. A monotone spline gives you a differentiable curve whose derivative is guaranteed non-negative, so the daily arrival rate you read off it is always a real quantity, and the curve can be evaluated between snapshots. If your snapshots are weekly and someone wants the number at the early bird deadline on a Wednesday, a spline answers and a staircase shrugs.

The cost is the usual one for any smoother, which is choosing how smooth. That choice interacts with the constraint, since a heavily smoothed monotone fit will flatten a genuine late surge, and selecting the penalty by holding out whole editions is O6's subject.

Should you constrain the fit or repair the data?

Repair the data. Then constrain the fit anyway, because the two do different jobs.

Repairing means going back to the snapshot process and making it produce a series that cannot dip: append-only snapshot rows, a fixed definition of a countable registration, retrospective corrections recorded as adjustments with their own dates. That is the real fix and it prevents next year's dip.

Constraining the fit is what you do with the seven closed editions whose snapshots were taken under the old process and will never be re-collected. Those series have dips in them, they are the entire evidence base for your pacing model, and you have to fit something to them. Imposing monotonicity there is a statement about the world that you know to be true, which is the best kind of prior information to give a model.

There is a second argument. A parametric booking curve, of the kind O4 fits, is monotone automatically because the functional form is. Nonparametric smoothers give that up in exchange for flexibility, and monotone regression is how you buy it back without going all the way to a three parameter family. If you later stack the fitted curves across editions to look for common structure, as a principal components decomposition does in O7, every dip you left in is variance the decomposition will dutifully model.

Where this stops

Monotonicity is a weak constraint and it will let plenty of nonsense through.

It cannot detect a snapshot that is too high. If a bulk upload of 900 exhibitor guest passes landed and was later reversed, the series goes up and then down, and the algorithm repairs the down by pooling, which leaves the level permanently inflated across the whole block. The constraint enforces order and has no opinion about level.

It also hides the location of the error. Pooling three snapshots into 4,338.33 tells you those three cannot be distinguished, and gives you no way to recover which one was wrong. That is fine for fitting and bad for diagnosis, which is the argument for keeping the raw snapshot rows next to the fitted values rather than overwriting them. A fitted series is a view. The snapshots are the record.

The last limit is that a monotone fit to a cumulative curve does not make the forecast monotone in any useful sense. You can impose non-decreasing behaviour on the fitted history and still extrapolate an asymptote that is below the count you are already holding, if the extrapolation is done separately from the fit. Check the obvious thing before publishing: the forecast at doors should exceed the count in hand today, and I have seen a model that failed that test survive a review because nobody thought to look.

Take one closed edition's snapshot history, compute the difference between consecutive snapshots, and count how many of those differences are negative. If the answer is zero, you have a clean series and can fit whatever you like. If the answer is more than one or two, run the pooling pass before anything else touches the data, and open a ticket against the snapshot process while you are there. The constraint belongs in the fitting code alongside the rest of the forecasting methods you run.