Ridge regression is a method of estimating the
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
s of multiple-
regression model
In statistical modeling, regression analysis is a set of statistical processes for estimating the relationships between a dependent variable (often called the 'outcome' or 'response' variable, or a 'label' in machine learning parlance) and one ...
s in scenarios where the independent variables are highly correlated.
It has been used in many fields including econometrics, chemistry, and engineering.
Also known as Tikhonov regularization, named for
Andrey Tikhonov
Andrey Valeryevich Tikhonov (russian: Андрей Валерьевич Тихонов; born 16 October 1970) is a Russian football manager and a former midfielder who was recently the manager of Kazakhstani club Astana. Tikhonov is primarily ...
, it is a method of
regularization
Regularization may refer to:
* Regularization (linguistics)
* Regularization (mathematics)
* Regularization (physics)
In physics, especially quantum field theory, regularization is a method of modifying observables which have singularities in ...
of
ill-posed problem
The mathematical term well-posed problem stems from a definition given by 20th-century French mathematician Jacques Hadamard. He believed that mathematical models of physical phenomena should have the properties that:
# a solution exists,
# the sol ...
s. It is particularly useful to mitigate the problem of
multicollinearity
In statistics, multicollinearity (also collinearity) is a phenomenon in which one predictor variable in a multiple regression model can be linearly predicted from the others with a substantial degree of accuracy. In this situation, the coeffic ...
in
linear regression
In statistics, linear regression is a linear approach for modelling the relationship between a scalar response and one or more explanatory variables (also known as dependent and independent variables). The case of one explanatory variable is call ...
, which commonly occurs in models with large numbers of parameters. In general, the method provides improved
efficiency in parameter estimation problems in exchange for a tolerable amount of
bias
Bias is a disproportionate weight ''in favor of'' or ''against'' an idea or thing, usually in a way that is closed-minded, prejudicial, or unfair. Biases can be innate or learned. People may develop biases for or against an individual, a group, ...
(see
bias–variance tradeoff
In statistics and machine learning, the bias–variance tradeoff is the property of a model that the variance of the parameter estimated across samples can be reduced by increasing the bias in the estimated parameters.
The bias–variance di ...
).
The theory was first introduced by Hoerl and Kennard in 1970 in their ''
Technometrics Technometrics is a journal of statistics for the physical, chemical, and engineering sciences, published quarterly since 1959 by the American Society for Quality and the American Statistical Association.
Statement of purpose
The purpose of ''Tech ...
'' papers “RIDGE regressions: biased estimation of nonorthogonal problems” and “RIDGE regressions: applications in nonorthogonal problems”.
This was the result of ten years of research into the field of ridge analysis.
Ridge regression was developed as a possible solution to the imprecision of least square estimators when linear regression models have some multicollinear (highly correlated) independent variables—by creating a ridge regression estimator (RR). This provides a more precise ridge parameters estimate, as its variance and mean square estimator are often smaller than the least square estimators previously derived.
Overview
In the simplest case, the problem of a
near-singular moment matrix
In mathematics, a moment matrix is a special symmetric square matrix whose rows and columns are indexed by monomials. The entries of the matrix depend on the product of the indexing monomials only (cf. Hankel matrices.)
Moment matrices play an im ...
is alleviated by adding positive elements to the
diagonals
In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word ''diagonal'' derives from the ancient Greek δ ...
, thereby decreasing its
condition number. Analogous to the
ordinary least squares
In statistics, ordinary least squares (OLS) is a type of linear least squares method for choosing the unknown parameters in a linear regression model (with fixed level-one effects of a linear function of a set of explanatory variables) by the prin ...
estimator, the simple ridge estimator is then given by
:
where
is the
regressand,
is the
design matrix
In statistics and in particular in regression analysis, a design matrix, also known as model matrix or regressor matrix and often denoted by X, is a matrix of values of explanatory variables of a set of objects. Each row represents an individual ob ...
,
is the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
, and the ridge parameter
serves as the constant shifting the diagonals of the moment matrix. It can be shown that this estimator is the solution to the
least squares problem subject to the
constraint , which can be expressed as a Lagrangian:
:
which shows that
is nothing but the
Lagrange multiplier
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied e ...
of the constraint. Typically,
is chosen according to a heuristic criterion, so that the constraint will not be satisfied exactly. Specifically in the case of
, in which the
constraint is non-binding, the ridge estimator reduces to
ordinary least squares
In statistics, ordinary least squares (OLS) is a type of linear least squares method for choosing the unknown parameters in a linear regression model (with fixed level-one effects of a linear function of a set of explanatory variables) by the prin ...
. A more general approach to Tikhonov regularization is discussed below.
History
Tikhonov regularization has been invented independently in many different contexts.
It became widely known from its application to integral equations from the work of
Andrey Tikhonov
Andrey Valeryevich Tikhonov (russian: Андрей Валерьевич Тихонов; born 16 October 1970) is a Russian football manager and a former midfielder who was recently the manager of Kazakhstani club Astana. Tikhonov is primarily ...
and David L. Phillips. Some authors use the term Tikhonov–Phillips regularization.
The finite-dimensional case was expounded by
Arthur E. Hoerl, who took a statistical approach, and by Manus Foster, who interpreted this method as a
Wiener–Kolmogorov (Kriging) filter. Following Hoerl, it is known in the statistical literature as ridge regression, named after the shape along the diagonal of the identity matrix.
Tikhonov regularization
Suppose that for a known matrix
and vector
, we wish to find a vector
such that
:
The standard approach is
ordinary least squares
In statistics, ordinary least squares (OLS) is a type of linear least squares method for choosing the unknown parameters in a linear regression model (with fixed level-one effects of a linear function of a set of explanatory variables) by the prin ...
linear regression. However, if no
satisfies the equation or more than one
does—that is, the solution is not unique—the problem is said to be
ill posed. In such cases, ordinary least squares estimation leads to an
overdetermined, or more often an
underdetermined system of equations. Most real-world phenomena have the effect of
low-pass filters
A low-pass filter is a filter that passes signals with a frequency lower than a selected cutoff frequency and attenuates signals with frequencies higher than the cutoff frequency. The exact frequency response of the filter depends on the filter des ...
in the forward direction where
maps
to
. Therefore, in solving the inverse-problem, the inverse mapping operates as a
high-pass filter
A high-pass filter (HPF) is an electronic filter that passes signals with a frequency higher than a certain cutoff frequency and attenuates signals with frequencies lower than the cutoff frequency. The amount of attenuation for each frequency d ...
that has the undesirable tendency of amplifying noise (
eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
/ singular values are largest in the reverse mapping where they were smallest in the forward mapping). In addition, ordinary least squares implicitly nullifies every element of the reconstructed version of
that is in the null-space of
, rather than allowing for a model to be used as a prior for
.
Ordinary least squares seeks to minimize the sum of squared
residuals, which can be compactly written as
:
where
is the
Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean s ...
.
In order to give preference to a particular solution with desirable properties, a regularization term can be included in this minimization:
:
for some suitably chosen Tikhonov matrix
. In many cases, this matrix is chosen as a scalar multiple of the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
(
), giving preference to solutions with smaller
norms; this is known as regularization. In other cases, high-pass operators (e.g., a
difference operator
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
or a weighted
Fourier operator
The Fourier operator is the kernel of the Fredholm integral of the first kind that defines the continuous Fourier transform, and is a two-dimensional function when it corresponds to the Fourier transform of one-dimensional functions. It is complex ...
) may be used to enforce smoothness if the underlying vector is believed to be mostly continuous.
This regularization improves the conditioning of the problem, thus enabling a direct numerical solution. An explicit solution, denoted by
, is given by
:
The effect of regularization may be varied by the scale of matrix
. For
this reduces to the unregularized least-squares solution, provided that (A
TA)
−1 exists.
regularization is used in many contexts aside from linear regression, such as
classification Classification is a process related to categorization, the process in which ideas and objects are recognized, differentiated and understood.
Classification is the grouping of related facts into classes.
It may also refer to:
Business, organizat ...
with
logistic regression
In statistics, the logistic model (or logit model) is a statistical model that models the probability of an event taking place by having the log-odds for the event be a linear function (calculus), linear combination of one or more independent var ...
or
support vector machine
In machine learning, support vector machines (SVMs, also support vector networks) are supervised learning models with associated learning algorithms that analyze data for classification and regression analysis. Developed at AT&T Bell Laboratorie ...
s, and matrix factorization.
Generalized Tikhonov regularization
For general multivariate normal distributions for
and the data error, one can apply a transformation of the variables to reduce to the case above. Equivalently, one can seek an
to minimize
:
where we have used
to stand for the weighted norm squared
(compare with the
Mahalanobis distance). In the Bayesian interpretation
is the inverse
covariance matrix
In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square matrix giving the covariance between each pair of elements of ...
of
,
is the
expected value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a l ...
of
, and
is the inverse covariance matrix of
. The Tikhonov matrix is then given as a factorization of the matrix
(e.g. the
Cholesky factorization
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for effici ...
) and is considered a
whitening filter.
This generalized problem has an optimal solution
which can be written explicitly using the formula
:
or equivalently
:
Lavrentyev regularization
In some situations, one can avoid using the transpose
, as proposed by
Mikhail Lavrentyev
Mikhail Alekseevich Lavrentyev (or Lavrentiev, russian: Михаи́л Алексе́евич Лавре́нтьев) (November 19, 1900 – October 15, 1980) was a Soviet Union, Soviet mathematician and hydrodynamics, hydrodynamicist.
Early years ...
. For example, if
is symmetric positive definite, i.e.
, so is its inverse
, which can thus be used to set up the weighted norm squared
in the generalized Tikhonov regularization, leading to minimizing
:
or, equivalently up to a constant term,
:
.
This minimization problem has an optimal solution
which can be written explicitly using the formula
:
,
which is nothing but the solution of the generalized Tikhonov problem where
The Lavrentyev regularization, if applicable, is advantageous to the original Tikhonov regularization, since the Lavrentyev matrix
can be better conditioned, i.e., have a smaller
condition number, compared to the Tikhonov matrix
Regularization in Hilbert space
Typically discrete linear ill-conditioned problems result from discretization of
integral equation
In mathematics, integral equations are equations in which an unknown Function (mathematics), function appears under an integral sign. In mathematical notation, integral equations may thus be expressed as being of the form: f(x_1,x_2,x_3,...,x_n ; ...
s, and one can formulate a Tikhonov regularization in the original infinite-dimensional context. In the above we can interpret
as a
compact operator
In functional analysis, a branch of mathematics, a compact operator is a linear operator T: X \to Y, where X,Y are normed vector spaces, with the property that T maps bounded subsets of X to relatively compact subsets of Y (subsets with compact c ...
on
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
s, and
and
as elements in the domain and range of
. The operator
is then a
self-adjoint
In mathematics, and more specifically in abstract algebra, an element ''x'' of a *-algebra is self-adjoint if x^*=x. A self-adjoint element is also Hermitian, though the reverse doesn't necessarily hold.
A collection ''C'' of elements of a st ...
bounded invertible operator.
Relation to singular-value decomposition and Wiener filter
With
, this least-squares solution can be analyzed in a special way using the
singular-value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is relate ...
. Given the singular value decomposition
:
with singular values
, the Tikhonov regularized solution can be expressed as
:
where
has diagonal values
:
and is zero elsewhere. This demonstrates the effect of the Tikhonov parameter on the
condition number of the regularized problem. For the generalized case, a similar representation can be derived using a
generalized singular-value decomposition.
Finally, it is related to the
Wiener filter
In signal processing, the Wiener filter is a filter used to produce an estimate of a desired or target random process by linear time-invariant ( LTI) filtering of an observed noisy process, assuming known stationary signal and noise spectra, and ...
:
:
where the Wiener weights are
and
is the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
of
.
Determination of the Tikhonov factor
The optimal regularization parameter
is usually unknown and often in practical problems is determined by an ''ad hoc'' method. A possible approach relies on the Bayesian interpretation described below. Other approaches include the
discrepancy principle,
cross-validation,
L-curve method,
restricted maximum likelihood In statistics, the restricted (or residual, or reduced) maximum likelihood (REML) approach is a particular form of maximum likelihood estimation that does not base estimates on a maximum likelihood fit of all the information, but instead uses a like ...
and
unbiased predictive risk estimator.
Grace Wahba
Grace Goldsmith Wahba (born August 3, 1934) is an American statistician and now-retired I. J. Schoenberg-Hilldale Professor of Statistics at the University of Wisconsin–Madison. She is a pioneer in methods for smoothing noisy data. Best known f ...
proved that the optimal parameter, in the sense of
leave-one-out cross-validation
Cross-validation, sometimes called rotation estimation or out-of-sample testing, is any of various similar model validation techniques for assessing how the results of a statistical analysis will generalize to an independent data set.
Cross- ...
minimizes
:
where
is the
residual sum of squares
In statistics, the residual sum of squares (RSS), also known as the sum of squared estimate of errors (SSE), is the sum of the squares of residuals (deviations predicted from actual empirical values of data). It is a measure of the discrepan ...
, and
is the
effective number of degrees of freedom.
Using the previous SVD decomposition, we can simplify the above expression:
:
:
and
:
Relation to probabilistic formulation
The probabilistic formulation of an
inverse problem
An inverse problem in science is the process of calculating from a set of observations the causal factors that produced them: for example, calculating an image in X-ray computed tomography, source reconstruction in acoustics, or calculating the ...
introduces (when all uncertainties are Gaussian) a covariance matrix
representing the ''a priori'' uncertainties on the model parameters, and a covariance matrix
representing the uncertainties on the observed parameters. In the special case when these two matrices are diagonal and isotropic,
and
, and, in this case, the equations of inverse theory reduce to the equations above, with
.
Bayesian interpretation
Although at first the choice of the solution to this regularized problem may look artificial, and indeed the matrix
seems rather arbitrary, the process can be justified from a
Bayesian point of view. Note that for an ill-posed problem one must necessarily introduce some additional assumptions in order to get a unique solution. Statistically, the
prior probability
In Bayesian statistical inference, a prior probability distribution, often simply called the prior, of an uncertain quantity is the probability distribution that would express one's beliefs about this quantity before some evidence is taken into ...
distribution of
is sometimes taken to be a
multivariate normal distribution
In probability theory and statistics, the multivariate normal distribution, multivariate Gaussian distribution, or joint normal distribution is a generalization of the one-dimensional (univariate) normal distribution to higher dimensions. One d ...
. For simplicity here, the following assumptions are made: the means are zero; their components are independent; the components have the same
standard deviation
In statistics, the standard deviation is a measure of the amount of variation or dispersion of a set of values. A low standard deviation indicates that the values tend to be close to the mean (also called the expected value) of the set, while ...
. The data are also subject to errors, and the errors in
are also assumed to be
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independ ...
with zero mean and standard deviation
. Under these assumptions the Tikhonov-regularized solution is the
most probable solution given the data and the ''a priori'' distribution of
, according to
Bayes' theorem.
If the assumption of
normality is replaced by assumptions of
homoscedasticity
In statistics, a sequence (or a vector) of random variables is homoscedastic () if all its random variables have the same finite variance. This is also known as homogeneity of variance. The complementary notion is called heteroscedasticity. The s ...
and uncorrelatedness of
errors, and if one still assumes zero mean, then the
Gauss–Markov theorem
In statistics, the Gauss–Markov theorem (or simply Gauss theorem for some authors) states that the ordinary least squares (OLS) estimator has the lowest sampling variance within the class of linear unbiased estimators, if the errors in the ...
entails that the solution is the minimal
unbiased linear estimator.
See also
*
LASSO estimator is another regularization method in statistics.
*
Elastic net regularization
In statistics and, in particular, in the fitting of linear or logistic regression models, the elastic net is a regularized regression method that linearly combines the L1 and L2 penalties of the lasso and ridge methods.
Specification
The elas ...
*
Matrix regularization In the field of statistical learning theory, matrix regularization generalizes notions of vector regularization to cases where the object to be learned is a matrix. The purpose of regularization is to enforce conditions, for example sparsity or smoo ...
Notes
References
Further reading
*
*
*
*
*
{{Authority control
Linear algebra
Estimation methods
Inverse problems
Regression analysis