Regularized least squares classification or regression with leave-one-out (LOO) error
Techniques are disclosed that implement algorithms for rapidly finding the leave-one-out (LOO) error for regularized least squares (RLS) problems over a large number of values of the regularization parameter λ. Algorithms implementing the techniques use approximately the same time and space as training a single regularized least squares classifier/regression algorithm. The techniques include a classification/regression process suitable for moderate sized datasets, based on an eigendecomposition of the unregularized kernel matrix. This process is applied to a number of benchmark datasets, to show empirically that accurate classification/regression can be performed using a Gaussian kernel with surprisingly large values of the bandwidth parameter σ. It is further demonstrated how to exploit this large σ regime to obtain a linear-time algorithm, suitable for large datasets, that computes LOO values and sweeps over λ.
1. A computer-implemented methodology for regularized least squares (RLS) classification or regression, the method executed by one or more computer systems comprising a processor and a memory, the method comprising:
receiving, by a processor, a training set of data;
generating a kernel matrix K based on the training set, wherein the kernel matrix is represented explicitly in an n by n matrix satisfying K ij =K( x i , x j ) and having a form
K
(
x
_
i
,
x
_
j
)
=
exp
(
x
_
i
-
x
_
j
2
2
σ
2
)
,
where x is a vector of data points included in the training set and σ is a user-selected bandwidth parameter;
computing, by the processor, an eigendecomposition of the kernel matrix K;
receiving a plurality of regularization parameters λ;
computing, by the processor, coefficients c for each regularization parameter λ based on the eigendecomposition of the kernel matrix K;
computing, by the processor, a leave-one-out (LOO) error for each of the regularization parameters λ, wherein the LOO error for all the regularization parameters λ are computed in O(n 3 +n 2 d) time and O(n 2 ) space, where n is the number of points in d dimensions of the training set;
selecting the regularization parameter λ with the lowest LOO error;
identifying a hyperplane function w based on the selected regularization parameter λ and the training set of data; and
storing the hyperplane function w in the memory.
2. The method of claim 1 , wherein the hyperplane function w is used in regularized least squares (RLS) classification, the regularized least squares (RLS) classification comprising:
predicting a class y associated with a set of input data points based on at least one of coefficients c and the hyperplane function w.
3. The method of claim 2 , wherein the input data points and the training set of data represent one selected from a group consisting of face recognition data, object tracking data, room navigation data, medical image analysis data, and voice recognition data.
4. The method of claim 1 further comprising:
storing the kernel matrix K in the memory.
5. The method of claim 1 , wherein the hyperplane function w is used in regularized least squares (RLS) regression and further comprising:
predicting a set of values associated with a set of input data points based on at least one of coefficients c and the hyperplane function w.
6. A machine-readable medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for regularized least squares (RLS) classification or regression, the process comprising:
receiving, by a processor, a training set of data;
generating a kernel matrix K based on the training set, wherein the kernel matrix is represented explicitly in an n by n matrix satisfying K ij =K( x i , x j ) and having a form
K
(
x
_
i
,
x
_
j
)
=
exp
(
x
_
i
-
x
_
j
2
2
σ
2
)
,
where x is a vector of data points included in the training set and σ is a user-selected bandwidth parameter;
computing, by the processor, an eigendecomposition of the kernel matrix K;
receiving a plurality of regularization parameters λ;
computing, by the processor, coefficients c for each regularization parameter λ based on the eigendecomposition of the kernel matrix K;
computing, by the processor, a leave-one-out (LOO) error for each of the regularization parameters λ, wherein the LOO error for all the regularization parameters λ are computed in O(n 3 +n 2 d) time and O(n 2 ) space, where n is the number of points in d dimensions of the training set;
selecting the regularization parameter with the lowest LOO error;
identifying a hyperplane function w based on the selected regularization parameter λ and the training set of data; and
storing the hyperplane function w in a memory associated with the processor.
7. The machine-readable medium of claim 6 , wherein the hyperplane function w is used in regularized least squares (RLS) classification, the regularized least squares (RLS) classification comprising:
predicting a class y associated with a set of input data points based on at least one of coefficients c and the hyperplane function w.
8. The medium of claim 7 , wherein the input data points and the training set of data represent one selected from a group consisting of face recognition data, object tracking data, room navigation data, medical image analysis data, and voice recognition data.
9. The machine-readable medium of claim 6 , the process further comprising:
storing the kernel matrix K in the memory associated with the processor.
10. The medium of claim 6 , wherein the hyperplane function w is used in regularized least squares (RLS) regression and further comprising:
predicting a set of values associated with a set of input data points based on at least one of coefficients c and the hyperplane function w.
11. A regularized least squares (RLS) classification or regression system, comprising:
a processor;
an input module to receive a training set of data at the processor;
a kernel matrix generator to generate a kernel matrix K based on the training set, wherein the kernel matrix is represented explicitly in an n by n matrix satisfying K ij =K( x i , x j ) and having a form
K
(
x
_
,
x
_
j
)
=
exp
(
x
_
i
-
x
_
j
2
2
σ
2
)
,
where x is a vector of data points included in the training set and σ is a user-selected bandwidth parameter;
a matrix decomposition module to compute an eigendecomposition of the kernel matrix K at the processor;
a coefficient computation module to receive a plurality of regularization parameters λ and computing, at the processor, coefficients c for each regularization parameter λ using the eigendecomposition of the kernel matrix K;
a LOO error computation module to receive the plurality of regularization parameters λ and computing, at the processor, a leave-one-out (LOO) error for each of the regularization parameters λ, wherein the LOO error for all the regularization parameters λ are computed in O(n 3 +n 2 d time and O(n 2 ) space, where n is the number of points in d dimensions of the training set;
a regularization parameter selection module to select the regularization parameter λ with the lowest LOO error; and
an RLS classification or regression module to identify a hyperplane function w based on the selected regularization parameter λ and the training set of data and storing the hyperplane function w in a memory associated with the processor.
12. The system of claim 11 wherein the hyperplane function w is used in regularized least squares (RLS) classification and the system further comprises:
a prediction module to predict a class y associated with a set of input data points based on at least one of coefficients c and the hyperplane function w.
13. The system of claim 12 , wherein the input data points and the training set of data represent one selected from a group consisting of face recognition data, object tracking data, room navigation data, medical image analysis data, and voice recognition data.
14. The system of claim 11 further comprising:
a memory for storing the kernel matrix K.
15. The system of claim 11 , wherein the hyperplane function w is used in regularized least squares (RLS) regression and the system further comprises:
a prediction module to predict a set of values associated with a set of input data points based on at least one of the coefficients c and the hyperplane function w.