Efficient Optimization Methods for Regularized Learning: Support Vector Machines and Total-Variation Regularization

RESUMEN:

En el ámbito de los métodos de aprendizaje automático, la regularización se ha convertido en una práctica habitual para controlar el sobreajuste en el proceso de modelización, así como para inducir una estructura en los modelos resultantes. Al mismo tiempo, la flexibilidad otorgada por este marco de regularización permite abarcar bajo un punto de vista único tanto modelos de aprendizaje estándar en el área como propuestas recientes. Esta riqueza está fundamentada en su simplicidad, que convierte el problema del aprendizaje en un problema de optimización compuesto por una función de pérdida más un regularizador. La selección apropiada de diferentes funciones de pérdida y regularizadores permite, por tanto, obtener toda una serie de modelos diferentes para cada situación.

Esta elegante modularidad, no obstante, no está exenta de un coste, puesto que debe aplicarse o diseñarse un algoritmo adecuado para resolver el problema de optimización resultante. A pesar de que existen métodos estándar de optimización capaces de resolver directamente tal problema en muchos de los casos, generalmente estos métodos tienen malos resultados en términos de eficiencia y escalabilidad. O lo que es peor, si la función de pérdida o el regularizador resultan ser funciones no diferenciables o no convexas, dando lugar a modelos más complejos, tales métodos suelen ser completamente inaplicables. Por tanto, el diseño de algoritmos de optimización adecuados a los modelos elegidos resulta ser una pieza clave en el éxito del proceso de aprendizaje regularizado.

En esta tesis se estudian en profundidad dos casos particulares de regularización. En primer lugar, las Máquinas de Vectores de Soporte se presentan en sus diferentes formas, las cuales son consideradas como modelos bien establecidos en el área. Mediante una observación detallada de los algoritmos que resuelven este problema se detectan deficiencias ocultas en los mismos, y se proponen formas de corregirlas mediante un mejor uso de la información manejada por tales algoritmos, obteniendo mejoras significativas en tiempos de ejecución. En segundo lugar se estudia la clase de regularizadores conocida como de Variación Total, los cuales han sido ampliamente utilizados en los campos de procesado de señal y de imagen para producir modelos de parámetros dispersos. A pesar de que ya se han analizado múltiples formas de abordar esta clase de problemas, en esta tesis se demuestra que haciendo uso explícito de sus propiedades estructurales y adaptando algoritmos de optimización apropiados pueden conseguirse mejoras relevantes en eficiencia y escalabilidad. Como parte de esta tesis se incluyen también programas implementando las soluciones algorítmicas aquí desarrolladas.

ABSTRACT:

In the context of machine learning methods, regularization has become an established practice to control overfitting in the modeling process and to induce structure into the resultant models. At the same time, the flexibility of the regularization framework has provided a common point of view embracing classical and established learning models, as well as recent proposals in the topic. This richness comes from its appealing simplicity, which casts the learning process into a composite optimization problem formed by a loss function and a regularizer; different models are obtained through the selection of appropriate loss and regularizer functions.

This elegant modularity, however, does not come at no cost, as an adequate optimization algorithm must be applied or devised in order to solve the resultant problem. While general purpose solvers are directly applicable out--of--the--box in some settings, they usually produce poor results in terms of efficiency and scalability. Further, in more complex models featuring non-smooth or even non-convex loss or regularizer functions, such approaches easily become inapplicable. Consequently, the design of a adequate optimization methods becomes a key task for the success of a regularized learning process.

In this thesis two particular cases of regularization are studied in depth. On the one hand, the well established and successful Support Vector Machine model is presented in its different forms. A careful observation at the current algorithmic solutions to this problem shows that correcting hidden deficiencies and making a better use of the gathered information can lead to significant improvements in running times, surpassing state of the art methods. On the other hand, a class of sparsity-inducing regularizers known as Total--Variation is studied, with wide application in the fields of signal and image processing. While a variety of approaches have been applied to solve this class of problems, it is shown here that by taking advantage of their strong structural properties and adapting suitable optimization algorithms, relevant improvements in efficiency and scalability can be obtained as well. Software implementing the developed methods is also made available as part of this thesis.