Logistic regression with L1-regularization has been recognized as a prominent method for feature extraction in linear classification problems. Various optimization methods for L1 logistic regression have been proposed in recent years. However there have been few studies conducted to compare such methods. This paper reviews existing methods for optimization and then tests the methods over a binary dataset. Results are recorded and comparisons are made. After analyzing the results, the conclusion is that the GLMNET method is the best in terms of time efficiency.
Digital information is growing at an extreme rate. Emerging technologies have created an environment that is information driven. From social media to medical records, data is collected in all forms from around the world. Current trends suggest a jump in information gathered and collected over the next decade and beyond. Never before has there been an abundance of data and information as we see today.
As the amount of data collected continues to grow so does the challenge of processing and gathering information. The data is growing wide, and the amount of attributes and features that can be derived sometimes outnumber the sample size. Now, more and more binary large objects are appearing in databases which require a different approach to identifying and extracting information.
Researchers have turned to regularized general linear
models to form relationships about the binary data.
Regularization is required to avoid over-fitting when there
are a large number of parameters. In particular,
L1regularized regression is often used for feature selection,
and has been shown to generate sparse models
Recently, there has been a large amount of research
conducted to related regularization methods. Each method
is differentiated by various aspects including: convergence
speed, implementation, and practicability. Therefore, there
is significance in conducting a thorough comparison and
evaluation
Logistic regression is used for prediction of the probability
of occurrence of an event by fitting data to a function. It is
a generalized linear model used for binomial regression.
Like other forms of regression analysis, it makes use of one
or more predictor variables that may be either numerical or
categorical. The logistic regression problem is an
optimization problem, and can be solved by a wide variety
of methods; such as gradient descent, steepest descent, and
Newton. Once optimization is complete and maximum
likelihood values are found, a prediction on the probability
of the two possible outcomes can be made
[1]
Where b (-1, +1) denotes the associated binary output and
where Prob(b|x) is the conditional probability of b.
L1-regularized logistic regression has recently received
attention. The main motivation is that L1-regularized
logistic regression yields a sparse vector and has relatively
few nonzero coefficients
The L1-regularized logistic regression problem minimizes
the following equation:
lavg(v,w)+l||w||1=(1=m)
f(wTai+vbi)+l
||w|| [2]
Where λ > 0 is the regularization parameter. A solution
must exist, but it need not be exclusive. The objective
function in the L1-regularized Logistic regression problem
is not differentiable so solving the problem is a
computational challenge
Each method uses a type of optimization approach to find the regularization path as well as λ. The general model used in each method consists of iterations of the descent, where a chosen subset of variables is deemed the working set and all other variables become fixed. With every step the resulting sub-problem contains fewer variables and therefore solved easier.
Typically, a coordinate descent method sequentially goes
through all variables and then repeats the same process.
By solving the regression problem along an entire path of
values, this method efficiently calculates the regularization
parameters
GLMNET applies a shrinking technique to solve smaller
optimization problems. GLMNET conducts feature-wise
normalization before solving the optimization problem.
Then, GLMNET measures the relative step change in the
successive coordinate descent iterations
An effective regularization strategy in generalized
regression is using validation methods to choose a suitable
point in a trajectory or a family. Due to the use of gradient
information, the number of iterations is less than cyclic
coordinate descent methods. However, the cost per
iteration is higher
LARS relates to the classic model-selection method known
as Forward Selection
Relaxo is a generalization of the Lasso shrinkage technique for linear regression. Both variable selection and parameter estimation is achieved by regular Lasso, yet both steps do not necessarily use the same penalty parameter. The results include all Lasso solutions but allow for sparser models while having similar predictive performance if many predictor variables are present. The package is based on the LARS package (Meinshausen 2007).
All the experiments were done using the Leukemia dataset, a gene-expression data. This dataset was first mentioned in (Golub et al. 1999). The pre-processed dataset using methods from (Dettling, 2004) was used. The datasets consists of 72 genes that are part of two classes 0 and 1. There are 47 genes are from class 0 and 25 are from class 1. There are 3,571 predictor variables that have numeric values in the interval [-10, 10] with most of the values close to 0.
The two figures above represent the histograms for two of the variables, the first one and the 250th one. More than 75% of the values of variable 1 are in the [-1, 0] interval. The values of variable 250 are normally distributed in the [-2.5, 2.5] interval.
So far, we have described several large-scale optimization methods for solving L1-regularized logistic regression problems. In this section, we conduct experiments to investigate their individual and group performances. First we describe the experimental settings. Then the optimization methods are compared in terms of accuracy and time.
To be able to provide good predictions using the
GLMNET algorithm, the regularized parameter λ has to be
found first. That can be done in R using a grid search and
functions from the caret package
The coefficients from step 1 to 100 were recorded and their profile is plotted in figures 4, 5 and 6. Unfortunately we were unable to plot the coefficients of the Relaxo package. 10 Fold cross validation was used, and timings were recorded. Timing in seconds for GLMNET, CGGD, Relaxo, and LARS over Leukemia data is presented. The timings were performed on one HP TX2000 series laptop.
When compared, GLMNET is the more efficient algorithm. By the 100th step the predicted coefficients for GLMNET are stronger than both CGGD and LARS. When comparing the timings, GLMNET is almost 4 times as quick as CGGD in both optimization and cross validation. Relaxo is the almost twice as slow as GLMNET when comparing optimization and almost 10 times as slow when cross validating. We can conclude that the most efficient method for L1-regularized logistic regression is GLMNET. The Leukemia dataset has a larger number of features compare to the number of instances. Linear models work well with datasets with such characteristics. The data while large however contained a small number of samples. Testing over a dataset with a large sample and small feature should be further investigated. Dettling M. 2004. BagBoosting for Tumor Classification with Gene Expression Data. Bioinformatics, 20, 35833593.