Random Ridge-adding Approach For Regularization Path Singularities

The regularization path approach,which is an effective method for parameter selection in statistical machine learning,can obtain the corresponding solutions for all the regularization parameters.The regularization path method plays an important role in the parameter selection of l1-norm minimization and support vector machine(SVM).The regularization path method mainly tracks the solution path along the Karush-Kuhn-Tucker(KKT)optimality conditions by utilizing the active set method.However,the singularity problem might be encountered if there are duplicate samples,approximate samples or samples that are linearly dependent in the kernel space.Currently,many effective methods have been proposed for handling the singularity problem in the regularization path method.Among them,the random ridge-adding method is the simplest one and does not require other additional steps.However,the existing ridge-adding method suffers from the following drawbacks:1)it modifies each data point to ensure that only one index is added into or removed from the active set in each iteration.However,it is challenging to select the suitable ridge terms,because the value of each element of data points varies from time to time in practical;2)the number of added ridges could be very large for high-dimensional data sets,and thus the influence of ridges on the solution path can be very serious.Focusing on the parameter selection of l1-norm minimization and SVM,this thesis proposes a novel ridge-adding approach for handling the singularity problem in the regularization path method.The main research contents are given as followsIn the aspect of parameter selection of l1-norm minimization,a novel regularization path algorithm with random ridges is proposed to deal with the singularity problem.Without directly modifying the measurement matrix,the proposed method introduces a small random ridge vector into the optimization problem to avoid singularities.Our method overcomes the diff-iculty of choosing suitable ridge terms and significantly reduces the influence of random ridges on the entire solution path.Experimental results show that the proposed algorithm can effectively deal with the singularity problem and has great advantages in training time compared with the traditional regularization path algorithm when solving a constrained l1-norm minimization problemIn the aspect of parameter selection of SVM,a new regularization path algorithm based on random ridges is proposed to handle the singularity problem in the SVMpath algorithm.The proposed approach introduces some random ridge scalars to the primary SVM problem to avoid singularities,instead of modifying each data point.With a simpler implementation,our method overcomes the difficulty of choosing suitable ridge terms and can greatly reduce the influence of the added ridges on the solution path.Simulation results demonstrate that the proposed method can effectively avoid singularities and fit the whole path of SVM solutions correctly Moreover,the performance of our method is much better than the existing algorithms.