Column generation-based decomposition for large-scale feature selection problems

Abstract

El actual crecimiento en los datos disponibles y su utilizaci´on en campos como el aprendizaje autom´atico ha aumentado la demanda de algoritmos capaces de abordar problemas de gran escala. En consecuencia, el problema de selecci´on de atributos es fundamental para construir modelos precisos y coherentes a partir de grandes conjuntos de datos. A pesar de que existe una gran cantidad de m´etodos para este problema, s´olo un n´umero limitado de estos es capaz de producir soluciones en un tiempo razonable y sin comprometer la calidad de las soluciones en problemas de este tipo. Esta investigaci´on propone un algoritmo escalable, usando un m´etodo de descomposici´on para problemas de optimizaci´on c´onica de gran complejidad. Se trata de un m´etodo de generaci´on de columnas que descompone una versi´on c´onica de segundo orden del problema de selecci´on de atributos, regularizando coeficientes asignando par´ametros de penalizaci´on. Se demuestra que el m´etodo es equivalente a LASSO, y es capaz de resolver instancias de escala “mediana a grande” (miles de atributos y observaciones) en cuesti´on de segundos, en instancias donde otras alternativas demoran minutos o incluso horas. El m´etodo es similar a un enfoque Dantzig-Wolfe, dado que resuelve dos subproblemas en cada iteraci´on: (1) el problema c´onico de segundo orden original, pero en un subconjunto de su regi´on factible, y (2) un problema relajado obtenido mediante la relajaci´on Lagrangiana de las restricciones c´onicas de alta complejidad. El problema relajado genera nuevas soluciones para expandir la regi´on factible del problema maestro. En este trabajo se modifica el m´etodo de generaci´on de columnas para considerar casos de problemas relajados no acotados y construir soluciones artificiales en ellos. Estas soluciones artificiales se construyen a partir de informaci´on de los problemas no acotados. El m´etodo propuesto puede resolver eficientemente instancias de escala “mediana a grande”, con una penalizaci´on considerable, en cuesti´on de minutos, mientras que el problema original y LASSO requieren m´as de 20 minutos para producir esa soluci´on. Sin embargo, el m´etodo propuesto muestra un rendimiento m´as lento en algunos casos. Espec´ıficamente, el m´etodo de descomposici´on es m´as eficiente que el problema original cuando selecciona 40% o menos atributos, y es m´as eficiente que LASSO cuando selecciona 4% o m´as atributos.

The current growth in the size of available datasets and its uses in machine learning has increased the demand for fast algorithms capable of addressing large-scale problems. Consequently, the feature selection problem is central to construct meaningful and accurate models from large-scale data. While numerous methods for this problem exist, only a limited number of them can effectively handle large-scale datasets in a reasonable time without compromising solution quality. This research proposes a scalable algorithm based on a decomposition method for hardto- solve instances of conic optimization problems. The solution involves a column generation method that deconstructs a Second-Order Cone formulation of the feature selection problem. It regularizes the coefficients using penalization parameters and has been proven to be equivalent to LASSO. The method can solve medium-to-large scale instances (thousands of features and observations) in a matter of seconds, whereas other exact optimization alternatives take minutes or even hours. The method is similar to a Dantzig-Wolfe approach. It solves two subproblems in each iteration: (1) the original Second-Order Cone Problem on a subset of its feasible region, and (2) a relaxed problem obtained via Lagrange relaxation of the challenging conic constraints. The relaxed problem provides new solutions to expand the master problem’s feasible region. In this work, the column generation method is adjusted by considering cases of unbounded relaxed problems, and constructing artificial solutions when that is the case. These artificial solutions take into account the characteristics of the unbounded problems. The proposed method can efficiently solve medium-to-large instances with substantial penalization within a couple of minutes, while the original problem and LASSO require over 20 minutes to produce a solution. However, the proposed method exhibits slower performance in some cases. Specifically, the decomposition method outperforms the execution time of the original problem when selecting 40% or fewer features, while it outperforms LASSO when selecting 4% or more features.