Isotonic Regression

Keep x positions in fixed order. Fit nondecreasing theta minimizing weighted sum of squared differences using pool-adjacent-violators algorithm.

Concept Overview

Isotonic Regression is a technique used to fit a non-decreasing line (or curve) to a sequence of observations. Given an ordered set of observations y and corresponding weights w, the goal is to find a non-decreasing sequence θ that minimizes the weighted sum of squared differences:∑ w_i(y_i - θ_i)².

Worked Example: Pool-Adjacent-Violators Algorithm

The standard algorithm to compute isotonic regression is the Pool-Adjacent-Violators Algorithm (PAVA). Let's perform a manual step-by-step calculation using a small dataset.

Initial State: Dataset = [3, 1, 2] with equal weights [1, 1, 1].

Start with the first observation: Block 1 is [3], weight = 1, mean = 3.
Consider the second observation [1]. Since 1 < 3, we have a violation of the non-decreasing constraint.
Merge (Pool): Combine Block 1 and the new observation into a single block.
New mean = (1×3 + 1×1) / (1 + 1) = 4 / 2 = 2.
New block weight = 2. Values are now represented as [2, 2].
Consider the third observation [2]. Since 2 is not strictly less than the previous block's mean of 2, there is no violation.
Result: The sequence of block means is [2, 2, 2], which is our fitted isotonic sequence θ.
Weighted Squared Error: 1×(3-2)² + 1×(1-2)² + 1×(2-2)² = 1 + 1 + 0 = 2.000000.

Experiment: Interactive Validation

You can verify the behavior of PAVA using the Isotonic Regression module controls.

Set the Dataset control to Decreasing (which is [4, 3, 2, 1]).
Set the Second weight control to 1.
Observe the Fitted Values. Because the entire dataset is strictly decreasing, PAVA merges all points into a single block. The overall mean is (4+3+2+1)/4 = 10/4 = 2.500000.
The algorithm resolves the sequence to a single flat level at θ = 5/2, with unnormalized weighted squared error 5.
Choose Dataset = Dip and Second weight = 3. Pooling the first pair gives (3 + 3×1)/4 = 3/2, so the fit is [3/2, 3/2, 2], with weighted squared error 3.
Choose Dataset = Increasing, keeping Second weight = 3. The input [0, 1, 2] already satisfies the constraint, so the fit is unchanged and loss is zero.
Choose Dataset = Ties and Second weight = 1. After the second pair pools, its mean 3/2 violates the first level 2; the final block mean is 5/3 at all three positions and loss is 2/3.

Limitations

This experiment fits only the selected small ordered sequence with strictly positive weights. It does not train or evaluate a classifier, calibrate predicted probabilities, or choose an ordering from the responses. The loss is an unnormalized sum, not a mean squared error. Further limitations are:

No Strict Extrapolation: Isotonic regression essentially outputs step functions. It cannot naturally extrapolate beyond the range of the observed input values without an explicitly selected extension rule. Interpolating between fitted positions and extending outside the observed range are separate choices, neither inferred here.
Overfitting to Noise: With large datasets, unconstrained isotonic regression can fit to noise, resulting in many small steps that may not reflect the true underlying smooth function. It lacks regularization beyond the monotonicity constraint.
Rounding: In this implementation, displayed numerical outputs are rounded to 6 decimal places, although full-precision arithmetic is used internally for loss calculations.

References

The following reference provides more information on the implementation and applications of isotonic regression:

scikit-learn: Isotonic regression documentation

Isotonic Regression