Definition of RKHS

A RKHS can be defined by a symmetric positive-definite kernel function ${\displaystyle K(x,z)}$ with the reproducing property:

${\displaystyle \langle K_{x},f\rangle _{\mathcal {H}}=f(x),}$

where ${\displaystyle K_{x}(z)=K(x,z)}$. The RKHS for a kernel ${\displaystyle K}$ consists of the completion of the space of functions spanned by ${\displaystyle \left\{K_{x}\mid x\in X\right\}}$: ${\displaystyle f(x)=\sum _{i=1}^{n}\alpha _{i}K_{x_{i}}(x),\,f\in {\mathcal {H}}}$, where all ${\displaystyle \alpha _{i}}$ are real numbers. Some commonly used kernels include the linear kernel, inducing the space of linear functions:

${\displaystyle K(x,z)=x^{T}z,}$

the polynomial kernel, inducing the space of polynomial functions of order ${\displaystyle d}$:

${\displaystyle K(x,z)=(x^{T}z+1)^{d},}$

and the Gaussian kernel:

${\displaystyle K(x,z)=e^{-{\frac {\|x-z\|^{2}}{\sigma ^{2}}}}.}$

Note that for an arbitrary loss function ${\displaystyle V}$, this approach defines a general class of algorithms named Tikhonov regularization. For instance, using the hinge loss leads to the support vector machine algorithm, and using the epsilon-insensitive loss leads to support vector regression.

Arbitrary kernel

The representer theorem guarantees that the solution can be written as:

${\displaystyle f(x)=\sum _{i=1}^{n}c_{i}K(x_{i},x)}$ for some ${\displaystyle c\in \mathbb {R} ^{n}}$.

The minimization problem can be expressed as:

${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|Y-Kc\|_{\mathbb {R} ^{n}}^{2}+\lambda \|f\|_{H}^{2},}$

where, with some abuse of notation, the ${\displaystyle i,j}$ entry of kernel matrix ${\displaystyle K}$ (as opposed to kernel function ${\displaystyle K(\cdot ,\cdot )}$) is ${\displaystyle K(x_{i},x_{j})}$.

For such a function,

${\displaystyle {\begin{aligned}&\|f\|_{H}^{2}=\langle f,f\rangle _{H}=\left\langle \sum _{i=1}^{n}c_{i}K(x_{i},\cdot ),\sum _{j=1}^{n}c_{j}K(x_{j},\cdot )\right\rangle _{H}\\={}&\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}\langle K(x_{i},\cdot ),K(x_{j},\cdot )\rangle _{H}=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})=c^{T}Kc,\end{aligned}}}$

The following minimization problem can be obtained:

${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|Y-Kc\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{T}Kc}$.

As the sum of convex functions is convex, the solution is unique and its minimum can be found by setting the gradient w.r.t ${\displaystyle c}$ to ${\displaystyle 0}$:

${\displaystyle -{\frac {1}{n}}K(Y-Kc)+\lambda Kc=0\Rightarrow K(K+\lambda nI)c=KY\Rightarrow c=(K+\lambda nI)^{-1}Y,}$

where ${\displaystyle c\in \mathbb {R} ^{n}.}$

Prediction

The prediction at a new test point ${\displaystyle x_{*}}$ is:

${\displaystyle f(x_{*})=\sum _{i=1}^{n}c_{i}K(x_{i},x_{*})=K(X,X_{*})^{T}c}$

Linear kernel

For convenience a vector notation is introduced. Let ${\displaystyle X}$ be an ${\displaystyle n\times d}$ matrix, where the rows are input vectors, and ${\displaystyle Y}$ a ${\displaystyle n\times 1}$ vector where the entries are corresponding outputs. In terms of vectors, the kernel matrix can be written as ${\displaystyle \operatorname {K} =\operatorname {X} \operatorname {X} ^{T}}$. The learning function can be written as:

${\displaystyle f(x_{*})=\operatorname {K} _{x_{*}}c=x_{*}^{T}\operatorname {X} ^{T}c=x_{*}^{T}w}$

Here we define ${\displaystyle w=X^{T}c,w\in R^{d}}$. The objective function can be rewritten as:

${\displaystyle {\begin{aligned}&{\frac {1}{n}}\|Y-\operatorname {K} c\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{T}\operatorname {K} c\\[4pt]={}&{\frac {1}{n}}\|y-\operatorname {X} \operatorname {X} ^{T}c\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{T}\operatorname {X} \operatorname {X} ^{T}c={\frac {1}{n}}\|y-\operatorname {X} w\|_{\mathbb {R} ^{n}}^{2}+\lambda \|w\|_{\mathbb {R} ^{d}}^{2}\end{aligned}}}$

The first term is the objective function from ordinary least squares (OLS) regression, corresponding to the residual sum of squares. The second term is a regularization term, not present in OLS, which penalizes large ${\displaystyle w}$ values. As a smooth finite dimensional problem is considered and it is possible to apply standard calculus tools. In order to minimize the objective function, the gradient is calculated with respect to ${\displaystyle w}$ and set it to zero:

${\displaystyle \operatorname {X} ^{T}\operatorname {X} w-\operatorname {X} ^{T}y+\lambda nw=0}$

${\displaystyle w=(\operatorname {X} ^{T}\operatorname {X} +\lambda n\operatorname {I} )^{-1}\operatorname {X} ^{T}y}$

This solution closely resembles that of standard linear regression, with an extra term ${\displaystyle \lambda \operatorname {I} }$. If the assumptions of OLS regression hold, the solution ${\displaystyle w=(\operatorname {X} ^{T}\operatorname {X} )^{-1}\operatorname {X} ^{T}y}$, with ${\displaystyle \lambda =0}$, is an unbiased estimator, and is the minimum-variance linear unbiased estimator, according to the Gauss–Markov theorem. The term ${\displaystyle \lambda n\operatorname {I} }$ therefore leads to a biased solution; however, it also tends to reduce variance. This is easy to see, as the covariance matrix of the ${\displaystyle w}$-values is proportional to ${\displaystyle (\operatorname {X} ^{T}\operatorname {X} +\lambda n\operatorname {I} )^{-1}}$, and therefore large values of ${\displaystyle \lambda }$ will lead to lower variance. Therefore, manipulating ${\displaystyle \lambda }$ corresponds to trading-off bias and variance. For problems with high-variance ${\displaystyle w}$ estimates, such as cases with relatively small ${\displaystyle n}$ or with correlated regressors, the optimal prediction accuracy may be obtained by using a nonzero ${\displaystyle \lambda }$, and thus introducing some bias to reduce variance. Furthermore, it is not uncommon in machine learning to have cases where ${\displaystyle n<d}$, in which case ${\displaystyle X^{T}X}$ is rank-deficient, and a nonzero ${\displaystyle \lambda }$ is necessary to compute ${\displaystyle (\operatorname {X} ^{T}\operatorname {X} +\lambda n\operatorname {I} )^{-1}}$.

Ridge regression (or Tikhonov regularization)

One particularly common choice for the penalty function ${\displaystyle R}$ is the squared ${\displaystyle \ell _{2}}$ norm, i.e.,

${\displaystyle R(w)=\sum _{j=1}^{d}w_{j}^{2}}$

${\displaystyle {\frac {1}{n}}\|Y-\operatorname {X} w\|_{2}^{2}+\lambda \sum _{j=1}^{d}|w_{j}|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

The most common names for this are called Tikhonov regularization and ridge regression. It admits a closed-form solution for ${\displaystyle w}$:

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

The name ridge regression alludes to the fact that the ${\displaystyle \lambda I}$ term adds positive entries along the diagonal "ridge" of the sample covariance matrix ${\displaystyle X^{T}X}$.

When ${\displaystyle \lambda =0}$, i.e., in the case of ordinary least squares, the condition that ${\displaystyle d>n}$ causes the sample covariance matrix ${\displaystyle X^{T}X}$ to not have full rank and so it cannot be inverted to yield a unique solution. This is why there can be an infinitude of solutions to the ordinary least squares problem when ${\displaystyle d>n}$. However, when ${\displaystyle \lambda >0}$, i.e., when ridge regression is used, the addition of ${\displaystyle \lambda I}$ to the sample covariance matrix ensures that all of its eigenvalues will be strictly greater than 0. In other words, it becomes invertible, and the solution becomes unique.

Compared to ordinary least squares, ridge regression is not unbiased. It accepts bias to reduce variance and the mean square error.

Lasso regression

The least absolute selection and shrinkage (LASSO) method is another popular choice. In lasso regression, the lasso penalty function ${\displaystyle R}$ is the ${\displaystyle \ell _{1}}$ norm, i.e.

${\displaystyle R(w)=\sum _{j=1}^{d}\left|w_{j}\right|}$

${\displaystyle {\frac {1}{n}}\|Y-\operatorname {X} w\|_{2}^{2}+\lambda \sum _{j=1}^{d}|w_{j}|\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

Note that the lasso penalty function is convex but not strictly convex. Unlike Tikhonov regularization, this scheme does not have a convenient closed-form solution: instead, the solution is typically found using quadratic programming or more general convex optimization methods, as well as by specific algorithms such as the least-angle regression algorithm.

An important difference between lasso regression and Tikhonov regularization is that lasso regression forces more entries of ${\displaystyle w}$ to actually equal 0 than would otherwise. In contrast, while Tikhonov regularization forces entries of ${\displaystyle w}$ to be small, it does not force more of them to be 0 than would be otherwise. Thus, LASSO regularization is more appropriate than Tikhonov regularization in cases in which we expect the number of non-zero entries of ${\displaystyle w}$ to be small, and Tikhonov regularization is more appropriate when we expect that entries of ${\displaystyle w}$ will generally be small but not necessarily zero. Which of these regimes is more relevant depends on the specific data set at hand.

Besides feature selection described above, LASSO has some limitations. Ridge regression provides better accuracy in the case ${\displaystyle n>d}$ for highly correlated variables.^[1] In another case, ${\displaystyle n<d}$, LASSO selects at most ${\displaystyle n}$ variables. Moreover, LASSO tends to select some arbitrary variables from group of highly correlated samples, so there is no grouping effect.

ℓ₀ Penalization

${\displaystyle {\frac {1}{n}}\|Y-\operatorname {X} w\|_{2}^{2}+\lambda \|w_{j}\|_{0}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

The most extreme way to enforce sparsity is to say that the actual magnitude of the coefficients of ${\displaystyle w}$ does not matter; rather, the only thing that determines the complexity of ${\displaystyle w}$ is the number of non-zero entries. This corresponds to setting ${\displaystyle R(w)}$ to be the ${\displaystyle \ell _{0}}$ norm of ${\displaystyle w}$. This regularization function, while attractive for the sparsity that it guarantees, is very difficult to solve because doing so requires optimization of a function that is not even weakly convex. Lasso regression is the minimal possible relaxation of ${\displaystyle \ell _{0}}$ penalization that yields a weakly convex optimization problem.

Elastic net

For any non-negative ${\displaystyle \lambda _{1}}$ and ${\displaystyle \lambda _{2}}$ the objective has the following form:

${\displaystyle {\frac {1}{n}}\|Y-\operatorname {X} w\|_{2}^{2}+\lambda _{1}\sum _{j=1}^{d}|w_{j}|+\lambda _{2}\sum _{j=1}^{d}|w_{j}|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$

Let ${\displaystyle \alpha ={\frac {\lambda _{1}}{\lambda _{1}+\lambda _{2}}}}$, then the solution of the minimization problem is described as:

${\displaystyle {\frac {1}{n}}\|Y-\operatorname {X} w\|_{2}^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}{\text{ s.t. }}(1-\alpha )\|w\|_{1}+\alpha \|w\|_{2}\leq t}$ for some ${\displaystyle t}$.

Consider ${\displaystyle (1-\alpha )\|w\|_{1}+\alpha \|w\|_{2}\leq t}$ as an Elastic Net penalty function.

When ${\displaystyle \alpha =1}$, elastic net becomes ridge regression, whereas ${\displaystyle \alpha =0}$ it becomes Lasso. ${\displaystyle \forall \alpha \in (0,1]}$ Elastic Net penalty function doesn't have the first derivative at 0 and it is strictly convex ${\displaystyle \forall \alpha >0}$ taking the properties both lasso regression and ridge regression.

One of the main properties of the Elastic Net is that it can select groups of correlated variables. The difference between weight vectors of samples ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ is given by:

${\displaystyle |w_{i}^{*}(\lambda _{1},\lambda _{2})-w_{j}^{*}(\lambda _{1},\lambda _{2})|\leq {\frac {\sum _{i=1}^{n}|y_{i}|}{\lambda _{2}}}{\sqrt {2(1-\rho _{ij})}}}$, where ${\displaystyle \rho _{ij}=x_{i}^{T}x_{j}}$.^[2]

If ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ are highly correlated ( ${\displaystyle \rho _{ij}\rightarrow 1}$), the weight vectors are very close. In the case of negatively correlated samples ( ${\displaystyle \rho _{ij}\rightarrow -1}$) the samples ${\displaystyle -x_{j}}$ can be taken. To summarize, for highly correlated variables the weight vectors tend to be equal up to a sign in the case of negative correlated variables.