Online Kernel Matrix Factorization

Abstract

Abstract. The problem of effciently applying a kernel-induced feature space factorization to a large-scale data sets is addressed in this thesis. Kernel matrix factorization methods have showed good performances solving machine learning and data analysis problems. However, the present growth of the amount of information available implies the problems can not be solved with conventional methods, due their high time and memory requirements. To solve this problem, a new kernel matrix factorization method is proposed called online kernel matrix factorization (OKMF). This method overcomes the time and memory limitations with two strategies. The first is imposing a budget restriction, i.e., restricting the number of samples needed to represent the feature space base. The second is using stochastic gradient descent to compute the factorization, allowing OKMF to scale linearly in time to large-scale data sets. Experimental results show OKMF is competitive with other kernel methods and is capable to scale to a large-scale data sets.

El problema de aplicar una factorización de un espacio de características inducido por kernel es abordado en esta tesis. Los métodos de factorización de kernel han mostrado buen rendimiento solucionando problemas de aprendizaje de máquina y problemas de análisis de datos. Sin embargo, el presente crecimiento de la cantidad de información disponible implica que los problemas no pueden ser resueltos con métodos convencionales, debido a sus grandes requerimientos de tiempo y memoria. Con el fin de resolver este problema, un nuevo método de factorización de kernel es propuesto, llamado online kernel matrix factorization (OKMF). Este método solventa los problemas de tiempo y memoria usando dos estrategias. La primera es imponer una restricción de presupuesto, esto es, restringir el número de ejemplos necesarios para representar la base del espacio de características. La segunda es usar gradiente descendente estocástico para calcular la factorización, permitiendo a OKMF escalar linealmente en tiempo a grandes conjuntos de datos. Resultados experimentales muestran que OKMF es competitivo con otros métodos de kernel y es capaz de escalar a grandes conjuntos de datos.