Isotonic regression


In statistics, isotonic regression or monotonic regression is the technique of fitting a free-form line to a sequence of observations such that the fitted line is non-decreasing everywhere, and lies as close to the observations as possible.

Applications

Isotonic regression has applications in statistical inference. For example, one might use it to fit an isotonic curve to the means of some set of experimental results when an increase in those means according to some particular ordering is expected. A benefit of isotonic regression is that it is not constrained by any functional form, such as the linearity imposed by linear regression, as long as the function is monotonic increasing.
Another application is nonmetric multidimensional scaling, where a low-dimensional embedding for data points is sought such that order of distances between points in the embedding matches order of dissimilarity between points. Isotonic regression is used iteratively to fit ideal distances to preserve relative dissimilarity order.
Isotonic regression is also used in probablistic classification to calibrate the predicted probabilities of supervised machine learning models.
Software for computing isotone regression has been developed for R, Stata, and Python.

Algorithms

In terms of numerical analysis, isotonic regression involves finding a weighted least-squares fit to a vector with weights vector subject to a set of non-contradictory constraints of the kind. The usual choice for the constraints is, or in other words: every point must be at least as high as the previous point.
Such constraints define a partial ordering or total ordering and can be represented as a directed graph, where is the set of variables involved, and is the set of pairs for each constraint. Thus, the isotonic regression problem corresponds to the following quadratic program :
In the case when is a total ordering, a simple iterative algorithm for solving this quadratic program is called the pool adjacent violators algorithm. Conversely, Best and Chakravarti studied the problem as an active set identification problem, and proposed a primal algorithm. These two algorithms can be seen as each other's dual, and both have a computational complexity of

Simply ordered case

To illustrate the above, let the constraints be.
The isotonic estimator,, minimizes the weighted least squares-like condition:
where is the set of all piecewise linear, non-decreasing, continuous functions and is a known function.