Learning latent variable models : efficient algorithms and applications

Abstract

Learning latent variable models is a fundamental machine learning problem, and the models belonging to this class - which include topic models, hidden Markov models, mixture models and many others - have a variety of real-world applications, like text mining, clustering and time series analysis. For many practitioners, the decade-old Expectation Maximization method (EM) is still the tool of choice, despite its known proneness to local minima and long running times. To overcome these issues, algorithms based on the spectral method of moments have been recently proposed. These techniques recover the parameters of a latent variable model by solving - typically via tensor decomposition - a system of non-linear equations relating the low-order moments of the observable data with the parameters of the model to be learned. Moment-based algorithms are in general faster than EM as they require a single pass over the data, and have provable guarantees of learning accuracy in polynomial time. Nevertheless, methods of moments have room for improvements: their ability to deal with real-world data is often limited by a lack of robustness to input perturbations. Also, almost no theory studies their behavior when some of the model assumptions are violated by the input data. Extending the theory of methods of moments to learn latent variable models and providing meaningful applications to real-world contexts is the focus of this thesis. ssuming data to be generated by a certain latent variable model, the standard approach of methods of moments consists of two steps: first, finding the equations that relate the moments of the observable data with the model parameters and then, to solve these equations to retrieve estimators of the parameters of the model. In Part I of this thesis we will focus on both steps, providing and analyzing novel and improved model-specific moments estimators and techniques to solve the equations of the moments. In both the cases we will introduce theoretical results, providing guarantees on the behavior of the proposed methods, and we will perform experimental comparisons with existing algorithms. In Part II, we will analyze the behavior of methods of moments when data violates some of the model assumptions performed by a user. First, we will observe that in this context most of the theoretical infrastructure underlying methods of moments is not valid anymore, and consequently we will develop a theoretical foundation to methods of moments in the misspecified setting, developing efficient methods, guaranteed to provide meaningful results even when some of the model assumptions are violated.

During all the thesis, we will apply the developed theoretical results to challenging real-world applications, focusing on two main domains: topic modeling and healthcare analytics. We will extend the existing theory of methods of moments to learn models that are traditionally used to do topic modeling – like the single-topic model and Latent Dirichlet Allocation – providing improved learning techniques and comparing them with existing methods, which we prove to outperform in terms of speed and learning accuracy. Furthermore, we will propose applications of latent variable models to the analysis of electronic healthcare records, which, similarly to text mining, are very likely to become massive datasets; we will propose a method to discover recurrent phenotypes in populations of patients and to cluster them in groups with similar clinical profiles - a task where the efficiency properties of methods of moments will constitute a competitive advantage over traditional approaches.

Aprender modelos de variable latente es un problema fundamental de machine learning, y los modelos que pertenecen a esta clase, como topic models, hidden Markov models o mixture models, tienen muchas aplicaciones en el mundo real, por ejemplo text mining, clustering y time series analysis. El método de Expectation Maximization (EM) sigue siendo la herramienta más utilizada, a pesar de su conocida tendencia a producir soluciones subóptimas y sus largos tiempos de ejecución. Para superar estos problemas, se han propuesto recientemente algoritmos basados en el método de los momentos. Estas técnicas aprenden los parámetros de un modelo resolviendo un sistema de ecuaciones no lineales que relacionan los momentos de los datos observables con los parámetros del modelo que se debe aprender. Los métodos de los momentos son en general más rápidos que EM, ya que requieren una sola pasada sobre los datos y tienen garantías de producir estimadores consistentes en tiempo polinomial. A pesar de estas ventajas, los métodos de los momentos todavía tienen margen de mejora: cuando se utilizan con datos reales, los métodos de los momentos se revelan inestables, con una fuerte sensibilidad a las perturbaciones. Además, las garantías de estos métodos son válidas solo si el usuario conoce el modelo probabilístico que genera los datos, y no existe alguna teoría que estudie lo que pasa cuando ese modelo es desconocido o no correctamente especificado. El objetivo de esta tesis es ampliar la teoría de métodos de los momentos, estudiar sus aplicaciones para aprender modelos de variable latente, extendiendo la teoría actual. Además se proporcionarán aplicaciones significativas a contextos reales. Típicamente, el método de los momentos consta de de dos partes: primero, encontrar las ecuaciones que relacionan los momentos de los datos observables con los parámetros del modelo y segundo, resolver estas ecuaciones para recuperar estimadores consistentes de los parámetros del modelo. En la Parte I de esta tesis, nos centraremos en ambos pasos, proporcionando y analizando nuevos estimadores de momentos para una variedad de modelos, y técnicas para resolver las ecuaciones de los momentos. En ambos casos, introduciremos resultados teóricos, proporcionaremos garantías sobre el comportamiento de los métodos propuestos y realizaremos comparaciones experimentales con algoritmos existentes. En la Parte II, analizaremos el comportamiento de los métodos de los momentos cuando algunas de las hipótesis de modelo se encuentran violadas por los datos. Como primera cosa, observaremos que en este contexto, la mayoría de la infraestructura teórica que subyace a estos métodos pierde de validez y, por lo tanto, desarrollaremos una base teórica nueva, presentando métodos eficientes, garantizados para proporcionar resultados razonables incluso cuando algunas de las hipótesis del modelo son violadas. En toda la tesis aplicamos los resultados obtenidos a nivel teórico a aplicaciones del mundo real, centrándonos en dos áreas principales: topic modeling y healthcare analytics. Ampliamos la teoría existente de los métodos de momentos para aprender los modelos que se usan tradicionalmente en el ámbito de topic modeling, como el single-topic model y la Latent Dirichlet Allocation, proporcionando nuevas técnicas de aprendizaje y comparándolas con los métodos existentes. Además, estudiamos aplicaciones de modelos de variable latente en el análisis de datos del ámbito healthcare; proponemos un método para descubrir fenotipos recurrentes en poblaciones de pacientes y agruparlos en clusters con perfiles clínicos similares, una tarea donde las propiedades de eficiencia de los métodos de los momentos constituyen una ventaja competitiva sobre los métodos tradicionales.