Machine Learning on Graphs

Abstract

Many datasets can be looked at as signals over a graph structure. To this end, the field of graphical models has been a fruitful area of research. This thesis examines a model for time series data called the Sticky Hierarchical Dirichlet Process Hidden Markov Model (SHDPHMM), proposed by Emily Fox. It is useful for clustering time series data where the number of hidden states is unknown, which is often the case in practice. The contribution of this thesis is the derivation of the deterministic variational inference update equations for doing inference on the SHDPHMM. This is an improvement over the Markov Chain Monte Carlo (MCMC) algorithm proposed by Fox as it allows for direct assessment of convergence and can run faster.

For a noisy signal over the nodes in a graph, the fused lasso can be used as a denoising method. The fused lasso is a particular case of the generalized lasso, a regularized regression problem which encourages sparsity in a linear transformation of the regression coefficients. This thesis completes the picture of equivalences between the generalized lasso, its dual problem, and the subspace constrained lasso (SCL) and its dual problem. The sparsity is directly expressed in the SCL. The structure of this problem allows for codeword screening. Many of the screening methods both of the single shot and sequential variety are derived in this thesis for the SCL, which depends on the structure of the dual problem. Screening in this case is not as effective as it is for the lasso, where it can reduce very large dictionaries to a fraction of the size. However, it is still an important tool which allows for increased speed of solving the SCL and hence the generalized lasso.