Isotonic regression

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.

Regression analysis
Part of a series on Statistics

Models
Linear regression Simple regression Ordinary least squares Polynomial regression General linear model
Generalized linear model Discrete choice Logistic regression Multinomial logit Mixed logit Probit Multinomial probit Ordered logit Ordered probit Poisson
Multilevel model Fixed effects Random effects Mixed model
Nonlinear regression Nonparametric Semiparametric Robust Quantile Isotonic Principal components Least angle Local Segmented
Errors-in-variables
Estimation
Least squares Ordinary least squares Linear (math) Partial Total Generalized Weighted Non-linear Non-negative Iteratively reweighted Ridge regression
Least absolute deviations Bayesian Bayesian multivariate
Background
Regression model validation Mean and predicted response Errors and residuals Goodness of fit Studentized residual Gauss–Markov theorem
Statistics portal

In statistics, isotonic regression or monotonic regression is the technique of fitting a free-form line to a sequence of observations under the following constraints: the fitted free-form line has to be non-decreasing everywhere, and it has to lie as close to the observations as possible.

Applications

Isotonic regression has applications in statistical inference, for example, to fit of an isotonic curve to mean experimental results when an order is expected. A benefit of isotonic regression is that it does not assume any form for the target function, such as linearity assumed by linear regression.

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.

Software for computing isotone (monotonic) regression has been developed for the R statistical package ^[2] and the Python programming language.

Algorithms

In terms of numerical analysis, isotonic regression involves finding a weighted least-squares fit $x\in \Bbb{R}^n$ to a vector $a\in \Bbb{R}^n$ with weights vector $w\in \Bbb{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 is the set of variables (observed values) involved, and E is the set of pairs (i, j) for each constraint $x_{i}\leq x_{j}$ . Thus, the IR 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 (1990) 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).^[3]

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.

References

↑ Kruskal, J. B. (1964). "Nonmetric Multidimensional Scaling: A numerical method". Psychometrika. 29 (2): 115–129. doi:10.1007/BF02289694.
↑ 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.
↑ Best, M.J.; Chakravarti N. (1990). "Active set algorithms for isotonic regression; a unifying framework". Mathematical Programming. 47: 425–439. doi:10.1007/BF01580873.

Robertson, T.; Wright, F. T.; Dykstra, R. L. (1988). Order restricted statistical inference. New York: Wiley. ISBN 0-471-91787-7.
Barlow, R. E.; Bartholomew, D. J.; Bremner, J. M.; Brunk, H. D. (1972). Statistical inference under order restrictions; the theory and application of isotonic regression. New York: Wiley. ISBN 0-471-04970-0.
Shively, T.S., Sager, T.W., Walker, S.G. (2009). "A Bayesian approach to non-parametric monotone function estimation". Journal of the Royal Statistical Society, Series B. 71 (1): 159–175. doi:10.1111/j.1467-9868.2008.00677.x.
Wu, W. B.; Woodroofe, M.; Mentz, G. (2001). "Isotonic regression: Another look at the changepoint problem". Biometrika. 88 (3): 793–804. doi:10.1093/biomet/88.3.793.

Statistics

Descriptive statistics

Continuous data

Center	Mean arithmetic geometric harmonic Median Mode

Dispersion	Variance Standard deviation Coefficient of variation Percentile Range Interquartile range

Shape	Moments Skewness Kurtosis L-moments

Count data

Index of dispersion

Summary tables

Dependence

Graphics

Data collection

Study design	Population Statistic Effect size Statistical power Sample size determination Missing data

Survey methodology	Sampling Standard error stratified cluster Opinion poll Questionnaire

Controlled experiments	Design control optimal Controlled trial Randomized Random assignment Replication Blocking Interaction Factorial experiment

Uncontrolled studies	Observational study Natural experiment Quasi-experiment

Statistical inference

Statistical theory

Frequentist inference

Point estimation	Estimating equations Maximum likelihood Method of moments M-estimator Minimum distance Unbiased estimators Mean-unbiased minimum-variance Rao–Blackwellization Lehmann–Scheffé theorem Median unbiased Plug-in

Interval estimation	Confidence interval Pivot Likelihood interval Prediction interval Tolerance interval Resampling Bootstrap Jackknife

Testing hypotheses	1- & 2-tails Power Uniformly most powerful test Permutation test Randomization test Multiple comparisons

Parametric tests	Likelihood-ratio Wald Score

Specific tests

Z (normal) Student's t-test F

Goodness of fit	Chi-squared Kolmogorov–Smirnov Anderson–Darling Normality (Shapiro–Wilk) Likelihood-ratio test Model selection Cross validation AIC BIC

Rank statistics	Sign Sample median Signed rank (Wilcoxon) Hodges–Lehmann estimator Rank sum (Mann–Whitney) Nonparametric anova 1-way (Kruskal–Wallis) 2-way (Friedman) Ordered alternative (Jonckheere–Terpstra)

Bayesian inference

Correlation	Pearson product–moment Partial correlation Confounding variable Coefficient of determination

Regression analysis	Errors and residuals Regression model validation Mixed effects models Simultaneous equations models Multivariate adaptive regression splines (MARS)

Linear regression	Simple linear regression Ordinary least squares General linear model Bayesian regression

Non-standard predictors	Nonlinear regression Nonparametric Semiparametric Isotonic Robust Heteroscedasticity Homoscedasticity

Generalized linear model	Exponential families Logistic (Bernoulli) / Binomial / Poisson regressions

Partition of variance	Analysis of variance (ANOVA, anova) Analysis of covariance Multivariate ANOVA Degrees of freedom

Categorical / Multivariate / Time-series / Survival analysis

Categorical

Multivariate

Time-series

General	Decomposition Trend Stationarity Seasonal adjustment Exponential smoothing Cointegration Structural break Granger causality

Specific tests	Dickey–Fuller Johansen Q-statistic (Ljung–Box) Durbin–Watson Breusch–Godfrey

Time domain	Autocorrelation (ACF) partial (PACF) Cross-correlation (XCF) ARMA model ARIMA model (Box–Jenkins) Autoregressive conditional heteroskedasticity (ARCH) Vector autoregression (VAR)

Frequency domain	Spectral density estimation Fourier analysis Wavelet

Survival

Survival function	Kaplan–Meier estimator (product limit) Proportional hazards models Accelerated failure time (AFT) model First hitting time

Hazard function	Nelson–Aalen estimator

Test	Log-rank test

Applications

Biostatistics	Bioinformatics Clinical trials / studies Epidemiology Medical statistics

Engineering statistics	Chemometrics Methods engineering Probabilistic design Process / quality control Reliability System identification

Social statistics	Actuarial science Census Crime statistics Demography Econometrics National accounts Official statistics Population statistics Psychometrics

Spatial statistics	Cartography Environmental statistics Geographic information system Geostatistics Kriging

Category
Portal
Commons
WikiProject

This article is issued from Wikipedia - version of the 12/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Isotonic regression

Applications

Algorithms

Simply ordered case

References

Further reading