Masterproef T705 : Tensor-based algorithms for learning latent variable models

Begeleiding:

Informatie:	Karl Meerbergen	Nick Vannieuwenhoven
Promotoren:	Karl Meerbergen	Nick Vannieuwenhoven
Begeleider:	Nick Vannieuwenhoven

Onderzoeksgroep:

Numerieke Approximatie en Lineaire Algebra Groep

Context:

Tensor decompositions are a novel approach for learning the parameters of a wide array of latent variable models, such as exchangeable topic models, independent component analysis (ICA), naï Bayes, Gaussian mixtures, and hidden Markov models (HMMs). Even neural networks can be trained under suitable assumptions. The approach consists of estimating the kth order moment tensor of these models from the input data and then computing a tensor rank decomposition.

A kth order moment tensor is an array with k indices. It turns out that several latent variable models admit a very specific structure in their 3rd or 4th order moment tensor, namely they correspond with a tensor rank decomposition. Such a decomposition is comparable with a singular value decomposition of a matrix, but one that applies to higher orders as well. Computing the tensor rank decomposition then yields the hidden parameter values of the model.

Having obtained the parameters of the model via the tensor method, it can be employed for a variety of machine learning tasks. For instance, even the simplest exchangeable topic models may be employed for document clustering.

Doel:

Design and implement a clustering algorithm by computing a tensor decomposition of the fourth-order moment tensor of the data.

Mogelijke Onderzoeksvragen:

Depending on the interests of the student(s), the research could focus on several issues ranging from investigating several latent variable models and their tensor structures, optimization of the tensor decomposition algorithm, or investigation of the tensor-based method versus classic expectation-maximization for learning parameters. This could lead to questions such as:

For which problems are the assumptions of the tensor-based clustering algorithm accurate?
How do the algorithms for computing the tensor decomposition perform? Which algorithm is best?
How does the algorithm scale in terms of memory and time? What optimizations should we use in practice? Can we exploit parallelism?
How well are the parameters of the model learned with respect to expectation-maximization?
How does the algorithm compare with, e.g., k-means clustering on a particular clustering problem?

Uitwerking:

Study the relevant literature
Design and implementation of a basic tensor-based algorithm for learning latent variable models
Optimization of memory and time complexity
Evaluation of the algorithm on model problems (e.g. document clustering, MNIST handwritten digit classification)
Comparison with another general-purpose clustering algorithm such as k-means clustering

Relevante literatuur:

Kolda and Bader, Tensor decompositions and applications, SIAM Review 51, 2009.
Anandkumar et al., Tensor decompositions for learning latent variable models, Journal of Machine Learning Research 15, 2014.
Allman, Matias and Rhodes, Identifiability of parameters in latent structure models with many observed variables, The Annals of Statistics 37, 2009.

Profiel:

Both theoretical and implementation-oriented approaches are possible.

Deze masterproef is voor 1 student.