Regularization (mathematics)

Regularization can be motivated as a technique to improve the generalizability of a learned model.

The goal of this learning problem is to find a function that fits or predicts the outcome (label) that minimizes the expected error over all possible inputs and labels. The expected error of a function ${\displaystyle f_{n}}$ is:

${\displaystyle I[f_{n}]=\int _{X\times Y}V(f_{n}(x),y)\rho (x,y)\,dx\,dy}$

where ${\displaystyle X}$ and ${\displaystyle Y}$ are the domains of input data ${\displaystyle x}$ and their labels ${\displaystyle y}$ respectively.

Typically in learning problems, only a subset of input data and labels are available, measured with some noise. Therefore, the expected error is unmeasurable, and the best surrogate available is the empirical error over the ${\displaystyle N}$ available samples:

${\displaystyle I_{S}[f_{n}]={\frac {1}{n}}\sum _{i=1}^{N}V(f_{n}({\hat {x}}_{i}),{\hat {y}}_{i})}$

Without bounds on the complexity of the function space (formally, the reproducing kernel Hilbert space) available, a model will be learned that incurs zero loss on the surrogate empirical error. If measurements (e.g. of ${\displaystyle x_{i}}$) were made with noise, this model may suffer from overfitting and display poor expected error. Regularization introduces a penalty for exploring certain regions of the function space used to build the model, which can improve generalization.

The learning problem with the least squares loss function and Tikhonov regularization can be solved analytically. Written in matrix form, the optimal ${\displaystyle w}$ is the one for which the gradient of the loss function with respect to ${\displaystyle w}$ is 0.

${\displaystyle \min _{w}{\frac {1}{n}}({\hat {X}}w-Y)^{T}({\hat {X}}w-Y)+\lambda \|w\|_{2}^{2}}$

${\displaystyle \nabla _{w}={\frac {2}{n}}{\hat {X}}^{T}({\hat {X}}w-Y)+2\lambda w}$

${\displaystyle 0={\hat {X}}^{T}({\hat {X}}w-Y)+n\lambda w}$    (first-order condition)

${\displaystyle w=({\hat {X}}^{T}{\hat {X}}+\lambda nI)^{-1}({\hat {X}}^{T}Y)}$

By construction of the optimization problem, other values of ${\displaystyle w}$ give larger values for the loss function. This can be verified by examining the second derivative ${\displaystyle \nabla _{ww}}$.

During training, this algorithm takes ${\displaystyle O(d^{3}+nd^{2})}$ time. The terms correspond to the matrix inversion and calculating ${\displaystyle X^{T}X}$, respectively. Testing takes ${\displaystyle O(nd)}$ time.

Consider the finite approximation of Neumann series for an invertible matrix A where ${\displaystyle \|I-A\|<1}$:

${\displaystyle \sum _{i=0}^{T-1}(I-A)^{i}\approx A^{-1}}$

This can be used to approximate the analytical solution of unregularized least squares, if γ is introduced to ensure the norm is less than one.

${\displaystyle w_{T}={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}}$

The exact solution to the unregularized least squares learning problem minimizes the empirical error, but may fail. By limiting T, the only free parameter in the algorithm above, the problem is regularized for time, which may improve its generalization.

The algorithm above is equivalent to restricting the number of gradient descent iterations for the empirical risk

${\displaystyle I_{s}[w]={\frac {1}{2n}}\|{\hat {X}}w-{\hat {Y}}\|_{\mathbb {R} ^{n}}^{2}}$

with the gradient descent update:

${\displaystyle {\begin{aligned}w_{0}&=0\\w_{t+1}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})w_{t}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

The base case is trivial. The inductive case is proved as follows:

${\displaystyle {\begin{aligned}w_{T}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}}){\frac {\gamma }{n}}\sum _{i=0}^{T-2}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=1}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

While the ${\displaystyle L_{1}}$ norm does not result in an NP-hard problem, the ${\displaystyle L_{1}}$ norm is convex but is not strictly differentiable due to the kink at x = 0. Subgradient methods which rely on the subderivative can be used to solve ${\displaystyle L_{1}}$ regularized learning problems. However, faster convergence can be achieved through proximal methods.

For a problem ${\displaystyle \min _{w\in H}F(w)+R(w)}$ such that ${\displaystyle F}$ is convex, continuous, differentiable, with Lipschitz continuous gradient (such as the least squares loss function), and ${\displaystyle R}$ is convex, continuous, and proper, then the proximal method to solve the problem is as follows. First define the proximal operator

${\displaystyle \operatorname {prox} _{R}(v)=\operatorname {argmin} \limits _{w\in \mathbb {R} ^{D}}\{R(w)+{\frac {1}{2}}\|w-v\|^{2}\},}$

and then iterate

${\displaystyle w_{k+1}=\operatorname {prox} \limits _{\gamma ,R}(w_{k}-\gamma \nabla F(w_{k}))}$

The proximal method iteratively performs gradient descent and then projects the result back into the space permitted by ${\displaystyle R}$.

When ${\displaystyle R}$ is the ${\displaystyle L_{1}}$ regularizer, the proximal operator is equivalent to the soft-thresholding operator,

${\displaystyle S_{\lambda }(v)f(n)={\begin{cases}v_{i}-\lambda ,&{\text{if }}v_{i}>\lambda \\0,&{\text{if }}v_{i}\in [-\lambda ,\lambda ]\\v_{i}+\lambda ,&{\text{if }}v_{i}<-\lambda \end{cases}}}$

This allows for efficient computation.

Groups of features can be regularized by a sparsity constraint, which can be useful for expressing certain prior knowledge into an optimization problem.

In the case of a linear model with non-overlapping known groups, a regularizer can be defined:

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$ where ${\displaystyle \|w_{g}\|_{2}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}$

This can be viewed as inducing a regularizer over the ${\displaystyle L_{2}}$ norm over members of each group followed by an ${\displaystyle L_{1}}$ norm over groups.

This can be solved by the proximal method, where the proximal operator is a block-wise soft-thresholding function:

${\displaystyle \operatorname {prox} \limits _{\lambda ,R,g}(w_{g})={\begin{cases}(1-{\frac {\lambda }{\|w_{g}\|_{2}}})w_{g},&{\text{if }}\|w_{g}\|_{2}>\lambda \\0,&{\text{if }}\|w_{g}\|_{2}\leq \lambda \end{cases}}}$

The algorithm described for group sparsity without overlaps can be applied to the case where groups do overlap, in certain situations. This will likely result in some groups with all zero elements, and other groups with some non-zero and some zero elements.

If it is desired to preserve the group structure, a new regularizer can be defined:

${\displaystyle R(w)=\inf \left\{\sum _{g=1}^{G}\|w_{g}\|_{2}:w=\sum _{g=1}^{G}{\bar {w}}_{g}\right\}}$

For each ${\displaystyle w_{g}}$, ${\displaystyle {\bar {w}}_{g}}$ is defined as the vector such that the restriction of ${\displaystyle {\bar {w}}_{g}}$ to the group ${\displaystyle g}$ equals ${\displaystyle w_{g}}$ and all other entries of ${\displaystyle {\bar {w}}_{g}}$ are zero. The regularizer finds the optimal disintegration of ${\displaystyle w}$ into parts. It can be viewed as duplicating all elements that exist in multiple groups. Learning problems with this regularizer can also be solved with the proximal method with a complication. The proximal operator cannot be computed in closed form, but can be effectively solved iteratively, inducing an inner iteration within the proximal method iteration.

${\displaystyle R(w)=\sum _{i=1}^{D}\|W\|_{2,1}}$

This regularizer defines an L2 norm on each column and an L1 norm over all columns. It can be solved by proximal methods.

${\displaystyle R(w)=\|\sigma (W)\|_{1}}$ where ${\displaystyle \sigma (W)}$ is the eigenvalues in the singular value decomposition of ${\displaystyle W}$.

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t=1}^{T}\|f_{t}-{\frac {1}{T}}\sum _{s=1}^{T}f_{s}\|_{H_{k}}^{2}}$

This regularizer constrains the functions learned for each task to be similar to the overall average of the functions across all tasks. This is useful for expressing prior information that each task is expected to share with each other task. An example is predicting blood iron levels measured at different times of the day, where each task represents an individual.

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{r=1}^{C}\sum _{t\in I(r)}\|f_{t}-{\frac {1}{I(r)}}\sum _{s\in I(r)}f_{s}\|_{H_{k}}^{2}}$ where ${\displaystyle I(r)}$ is a cluster of tasks.

This regularizer is similar to the mean-constrained regularizer, but instead enforces similarity between tasks within the same cluster. This can capture more complex prior information. This technique has been used to predict Netflix recommendations. A cluster would correspond to a group of people who share similar preferences.

More generally than above, similarity between tasks can be defined by a function. The regularizer encourages the model to learn similar functions for similar tasks.

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t,s=1,t\neq s}^{T}\|f_{t}-f_{s}\|^{2}M_{ts}}$ for a given symmetric similarity matrix ${\displaystyle M}$.