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 (or non-increasing) everywhere, and lies as close to the observations as possible.

An example of isotonic regression (solid red line) compared to linear regression on the same data, both fit to minimize the mean squared error. The free-form property of isotonic regression means the line can be steeper where the data are steeper; the isotonicity constraint means the line does not decrease.

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,[1] 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 probabilistic classification to calibrate the predicted probabilities of supervised machine learning models.[2]

Isotonic regression for the simply ordered case with univariate $x,y$ has been applied to estimating continuous dose-response relationships in fields such as anesthesiology and toxicology. Narrowly speaking, isotonic regression only provides point estimates at observed values of $x.$ Estimation of the complete dose-response curve without any additional assumptions is usually done via linear interpolation between the point estimates. [3]

Software for computing isotone (monotonic) regression has been developed for R,[4][5] Stata, and Python.[6]

Algorithms

In terms of numerical analysis, isotonic regression involves finding a weighted least-squares fit $x\in \mathbb {R} ^{n}$ to a vector $a\in \mathbb {R} ^{n}$ with weights vector $w\in \mathbb {R} ^{n}$ subject to a set of non-contradictory constraints of the kind $x_{i}\leq x_{j}$ . The usual choice for the constraints is $x_{i}\leq x_{i+1}$ , 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 $G=(N,E)$ , where $N$ (nodes) is the set of variables (observed values) involved, and $E$ (edges) is the set of pairs $(i,j)$ for each constraint $x_{i}\leq x_{j}$ . Thus, the isotonic regression problem corresponds to the following quadratic program (QP):

\min \sum _{i=1}^{n}w_{i}(x_{i}-a_{i})^{2}

{\text{subject to }}x_{i}\leq x_{j}{\text{ for all }}(i,j)\in E.

In the case when $G=(N,E)$ is a total ordering, a simple iterative algorithm for solving this quadratic program is called the pool adjacent violators algorithm. Conversely, Best and Chakravarti[7] 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 $O(n)$ on already sorted data.[7]

Simply ordered case

To illustrate the above, let the $x_{i}\leq x_{j}$ constraints be $x_{1}\leq x_{2}\leq \ldots \leq x_{n}$ .

The isotonic estimator, $g^{*}$ , minimizes the weighted least squares-like condition:

\min _{g\in {\mathcal {A}}}\sum _{i=1}^{n}w_{i}(g(x_{i})-f(x_{i}))^{2}

where ${\mathcal {A}}$ is the set of all piecewise linear, non-decreasing, continuous functions and $f$ is a known function.

Centered Isotonic Regression

As this article's first figure shows, in the presence of monotonicity violations the resulting interpolated curve will have flat (constant) intervals. In dose-response applications it is usually known that $f(x)$ is not only monotone but also smooth. The flat intervals are incompatible with $f(x)$ 's assumed shape, and can be shown to be biased. A simple improvement for such applications, named centered isotonic regression (CIR), was developed by Oron and Flournoy and shown to substantially reduce estimation error for both dose-response and dose-finding applications.[8] Both CIR and the standard isotonic regression for the univariate, simply ordered case, are implemented in the R package "cir".[4] This package also provides analytical confidence-interval estimates.

References

Kruskal, J. B. (1964). "Nonmetric Multidimensional Scaling: A numerical method". Psychometrika. 29 (2): 115–129. doi:10.1007/BF02289694.
"Predicting good probabilities with supervised learning | Proceedings of the 22nd international conference on Machine learning". dl.acm.org. Retrieved 2020-07-07.
Stylianou, MP; Flournoy, N (2002). "Dose finding using the biased coin up-and-down design and isotonic regression". Biometrics. 58: 171–177. doi:10.1111/j.0006-341x.2002.00171.x.
Oron, Assaf. "Package 'cir'". CRAN. R Foundation for Statistical Computing. Retrieved 26 December 2020.
Leeuw, Jan de; Hornik, Kurt; Mair, Patrick (2009). "Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods". Journal of Statistical Software. 32 (5): 1–24. doi:10.18637/jss.v032.i05. ISSN 1548-7660.
Pedregosa, Fabian; et al. (2011). "Scikit-learn:Machine learning in Python". Journal of Machine Learning Research. 12: 2825–2830. arXiv:1201.0490. Bibcode:2012arXiv1201.0490P.
Best, Michael J.; Chakravarti, Nilotpal (1990). "Active set algorithms for isotonic regression; A unifying framework". Mathematical Programming. 47 (1–3): 425–439. doi:10.1007/bf01580873. ISSN 0025-5610.
Oron, AP; Flournoy, N (2017). "Centered Isotonic Regression: Point and Interval Estimation for Dose-Response Studies". Statistics in Biopharmaceutical Research. 9: 258–267. arXiv:1701.05964. doi:10.1080/19466315.2017.1286256.