Regularized least squares (RLS) is a family of methods for solving the least-squares problem while using regularization to further constrain the resulting solution. RLS is used for two main reasons. The first comes up when the number of variables in the linear system exceeds the number of observations. In such settings, the ordinary least-squares problem is ill-posed and is therefore impossible to fit because the associated optimization problem has infinitely many solutions. RLS allows the introduction of further constraints that uniquely determine the solution. The second reason for using RLS arises when the learned model suffers from poor generalization. RLS can be used in such cases to improve the generalizability of the model by constraining it at training time. This constraint can either force the solution to be "sparse" in some way or to reflect other prior knowledge about the problem such as information about correlations between features. A Bayesian understanding of this can be reached by showing that RLS methods are often equivalent to priors on the solution to the least-squares problem.
General formulation Consider a learning setting given by a probabilistic space ( X × Y , ρ ( X , Y ) ) {\displaystyle (X\times Y,\rho (X,Y))} , Y ∈ R {\displaystyle Y\in R} . Let S = { x i , y i } i = 1 n {\displaystyle S=\{x_{i},y_{i}\}_{i=1}^{n}} denote a training set of n {\displaystyle n} pairs i.i.d. with respect to the joint distribution ρ {\displaystyle \rho } . Let V : Y × R → [ 0 ; ∞ ) {\displaystyle V:Y\times R\to [0;\infty )} be a loss function. Define F {\displaystyle F} as the space of the functions such that expected risk:
ε ( f ) = ∫ V ( y , f ( x ) ) d ρ ( x , y ) {\displaystyle \varepsilon (f)=\int V(y,f(x))\,d\rho (x,y)}
is well defined. The main goal is to minimize the expected risk:
inf f ∈ F ε ( f ) {\displaystyle \inf _{f\in F}\varepsilon (f)}
Since the problem cannot be solved exactly there is a need to specify how to measure the quality of a solution. A good learning algorithm should provide an estimator with a small risk. As the joint distribution ρ {\displaystyle \rho } is typically unknown, the empirical risk is taken. For regularized least squares the square loss function is introduced:
ε ( f ) = 1 n ∑ i = 1 n V ( y i , f ( x i ) ) = 1 n ∑ i = 1 n ( y i − f ( x i ) ) 2 {\displaystyle \varepsilon (f)={\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},f(x_{i}))={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}
However, if the functions are from a relatively unconstrained space, such as the set of square-integrable functions on X {\displaystyle X} , this approach may overfit the training data, and lead to poor generalization. Thus, it should somehow constrain or penalize the complexity of the function f {\displaystyle f} . In RLS, this is accomplished by choosing functions from a reproducing kernel Hilbert space (RKHS) H {\displaystyle {\mathcal {H}}} , and adding a regularization term to the objective function, proportional to the norm of the function in H {\displaystyle {\mathcal {H}}} :
inf f ∈ F ε ( f ) + λ R ( f ) , λ > 0 {\displaystyle \inf _{f\in F}\varepsilon (f)+\lambda R(f),\lambda >0}
Kernel formulation
Definition of RKHS A RKHS can be defined by a symmetric positive-definite kernel function K ( x , z ) {\displaystyle K(x,z)} with the reproducing property:
⟨ K x , f ⟩ H = f ( x ) , {\displaystyle \langle K_{x},f\rangle _{\mathcal {H}}=f(x),}
… excerpt ends here. Continue reading the full article.
