Isotonic Regression
Keep x positions in fixed order. Fit nondecreasing theta minimizing weighted sum of squared differences using pool-adjacent-violators algorithm.
Free theory articleKeep x positions in fixed order. Fit nondecreasing theta minimizing weighted sum of squared differences using pool-adjacent-violators algorithm.
Concept & interpretation
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:∑ wi(yi - θi)2.
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.