Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
Welcome to the PQSQ-regularized-regression wiki! Here you have short introduction into PQSQ-based regression regularization method. This page also contains some Supplementary Material to the paper "Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning" by A.N.Gorban, E.Mirkes, A.Zinovyev.
Brief description of the algorithm for PQSQ-based regularization method
basic approach to regularise regression using arbitrary regularization term approximated by PQSQ function
PQSQ-based regularized regression is a solution of the following optimization problem
where N is the number of data points, m is the number of attributes, x are dependent and y is independent variables, β are regression coefficients, λ is the regularization parameter, and u(x) is a piecewise quadratic function penalizing the absolute values of the regression coefficients. u(x) can imitate L1 norm (lasso-like) or a mixture of L1 and L2 norm (elastic net-like) or any other penalty. Solution of this problem can be found by iterations; at each iteration a simply modified system of linear equations for usual regression is solved. Convergence of the algorithm is guaranteed by the general theory of the cones of minorant functions.
Below is an example of a PQSQ (piece-wise quadratic function of subquadratic growth) potential function u(x). f(x) is a majorant function; here it is f(x)=x; the potential is defined with trimming after r3.
PQSQ function can be used to approximate spheres in various metrics. For example, below are approximations of a L1 sphere in 2D. The precision of approximation depends on the choice of intervals. In practice, using 5 intervals gives a reasonably precise approximation.
PQSQ regularized regression works just as regularized regression based on L1-norm (lasso) by confining the regression coefficients to a sphere of certain radius:
'black hole' trick for introducing sparsity in the regression estimation
Unlike pure L1-based penalty, the coefficients of PQSQ-regularized regression diminish with increase of λ but there is nothing to shrink them to exact zero values, same as in ridge regression. However, it is relatively straightforward to modify the algorithm, to achieve sparsity of the regression solution. The 'black hole' trick consists in eliminating from regression training after each iteration all regression coefficients βk smaller by absolute value than a given parameter ε ('black hole radius'). Those regression coefficients which have passed the 'black hole radius' are put to zero and do not have any chance to change their values in the next iterations.
Time performance comparison for 8 datasets of various sizes (MatLab lasso function, ordinary laptop)
Comparison with MatLab lasso function of approximation error for regularized regression for 8 datasets of different sizes
Links to the datasets used in the PQSQ method testing (most are from UC Irvine Machine Learning Repository, Regression tasks)
Prostate cancer dataset: original example from the seminal LASSO paper
Communities and Crime dataset. Note: 'Crime reduced' dataset has been formed by selecting each 10th row of the complete Crime matrix.
'Random' regression example was constructed using the code from the MATLAB lasso command documentation:
n = 1000; p = 250; X = randn(n,p); beta = randn(p,1); beta0 = randn; Y = beta0 + X*beta + randn(n,1);