Tesis:
Column subset selection in practice : efficient heuristics and regularization
- Autor: ORDOZGOITI RUBIO, Bruno
- Título: Column subset selection in practice : efficient heuristics and regularization
- Fecha: 2018
- Materia: Sin materia definida
- Escuela: E.T.S.I. DE SISTEMAS INFORMÁTICOS
- Departamentos: SISTEMAS INFORMATICOS
- Acceso electrónico: http://oa.upm.es/54718/
- Director/a 1º: MOZO VELASCO, Alberto
- Director/a 2º: GARCÍA LÓPEZ DE LACALLE, Jesús
- Resumen: Hoy en día, los datos están disponibles en un volumen sin precedentes. Una cantidad abrumadora de dispositivos conectados a Internet genera un flujo constante de información por todo el mundo, mucha de la cual se procesa en tiempo real o se almacena para usos posteriores. Extraer conocimiento de estos ingentes conjuntos de datos suele ser una tarea difícil. Su tamaño exige el uso de recursos computacionales masivos, lo que motiva el diseño de algoritmos eficientes. Además, estos datos suelen contener mediciones de una gran cantidad de variables, y esto acarrea una amplia serie de problemas. Para atajarlos, se estudia una familia de técnicas conocida como ”reducción de la dimensionalidad”. En esta tesis abordamos el tema de la selección de variables, un subconjunto de las técnicas de reducción de la dimensionalidad con la particularidad de que preservan el significado semántico de las variables originales. Para ello, analizamos un problema conocido ”selección de un subconjunto de columnas”. Una ventaja significativa de este problema es que da lugar a modelos simples y en ocasiones fáciles de interpretar. En la actualidad, los avances en ciencias de la computación aplicada van a menudo acompañados de preocupaciones sobre ética y transparencia, por lo que la simplicidad de los modelos utilizados puede ser clave en muchos casos. El problema de la ”selección de un subconjunto de columnas” ha recibido bastante atención durante los últimos años, principalmente desde un punto de vista teórico. En este texto analizamos el problema desde una perspectiva más práctica. Las contribuciones aquí recogidas se resumen a continuación. En primer lugar proponemos el uso de una heurística de búsqueda local. Mostramos empíricamente que ofrece un rendimiento superior al de otros algoritmos y demostramos garantías de aproximación elementales. Además, aprovechamos la naturaleza del problema para formular una implementación eficiente adecuada para el uso práctico. En segundo lugar, introducimos formulaciones regularizadas del problema. Proponemos un algoritmo voraz para optimizarlas y demostramos empíricamente que los subconjuntos de columnas resultantes son superiores con respecto a múltiples criterios. ----------ABSTRACT---------- Today, data are available at an unprecedented scale. An overwhelming quantity of Internet-connected devices generate a constant trickle of pieces of information all over the world, much of which are processed in real time or stored for later use. Making sense of these enormous data sets is often an challenging endeavour. Their size demands the use of massive computational resources, which motivates the design of efficient algorithms. Additionally, these data usually contain measurements of a large number of variables, which poses a wide variety of problems. To address the latter, a family of techniques commonly referred to as dimensionality reduction is studied. In this thesis we address the problem of feature selection, a subset of dimensionality reduction methods that preserve the semantic meaning of the original data variables. To do so, we analyze a problem formulation known as column subset selection. A significant advantage of column subset selection is that the models it produces are simple and in some cases easy to interpret. In an age where notable advances in applied computer science are met with growing concerns about ethics and transparency, model simplicity can become a key requirement in many scenarios. The column subset selection problem has received significant attention in the computer science literature over the last few years, mainly from a theoretical perspective. Here we analyze the problem from a more practical standpoint. Our contributions can be summarized as follows. First, we propose the use of a local search heuristic. We show empirically that it outperforms existing algorithms and derive elementary approximation guarantees. Furthermore, we take advantage of the nature of the problem formulation to derive an efficient implementation suitable for practical use. Second, we introduce regularized formulations of the problem. We derive a greedy algorithm for these new objectives and demonstrate empirically that it produces improved subsets with respect to multiple criteria.