Skip to Main content Skip to Navigation

Structured Sparse Learning on Graphs in High-Dimensional Data with Applications to NeuroImaging

Abstract : This dissertation presents novel structured sparse learning methods on graphs that address commonly found problems in the analysis of neuroimaging data as well as other high dimensional and few sample data. The first part of the thesis focuses on developing and utilizing convex relaxations of discrete and combinatorial penalties. These are developed with the aim of learning an interpretable predictive linear model satisfying sparse and graph based constraints. In the context of neuroimaging these models can leverage implicit structured sparsity properties to learn predictive and interpretable models that can inform analysis of neuro-imaging data. In particular we study the problem of statistical estimation with a signal known to be sparse, spatially contiguous, and containing many highly correlated variables. We take inspiration from the k-support norm, which has been successfully applied to sparse prediction problems with correlated features, but lacks any explicit structural constraints commonly found in machine learning and image processing. We address this problem by incorporating a total variation penalty in the k-support framework. We introduce the (k, s) support total variation norm as the tightest convex relaxation of the intersection of a set of discrete sparsity and total variation penalties. We show that this norm leads to an intractable combinatorial graph optimization problem, which we prove to be NP-hard. We then introduce a tractable relaxation with approximation guarantees. We demonstrate the effectiveness of this penalty on classification in the low-sample regime with M/EEG neuroimaging data and fMRI data, as well as image recovery with synthetic and real data background subtracted image recovery tasks. We show that our method is particularly useful compared to existing methods in terms of accuracy, interpretability, and stability. We consider structure discovery of undirected graphical models from observational data. We then consider the problem of learning the structure of graphical models with structured sparse constraints. Functional brain networks are well described and estimated from data with Gaussian Graphical Models (GGMs), e.g. using sparse inverse covariance estimators. In this thesis we make two contributions for estimating Gaussian Graphical Models under various constraints. Our first contribution is to identify differences in GGMs known to have similar structure. We characterize the uncertainty of differences with confidence intervals obtained using a parametric distribution on parameters of a sparse estimator. Sparse penalties enable statistical guarantees and interpretable models even in high-dimensional and low-sample settings. Characterizing the distributions of sparse models is inherently challenging as the penalties produce a biased estimator. Recent work invokes the sparsity assumptions to effectively remove the bias from a sparse estimator such as the lasso. These distributions can be used to give confidence intervals on edges in GGMs, and by extension their differences. However, in the case of comparing GGMs, these estimators do not make use of any assumed joint structure among the GGMs. Inspired by priors from brain functional connectivity we derive the distribution of parameter differences under a joint penalty when parameters are known to be sparse in the difference. This leads us to introduce the debiased multi-task fused lasso, whose distribution can be characterized in an efficient manner. We show how the debiased lasso and multi-task fused lasso can be used to obtain confidence intervals on edge differences in GGMs. We validate the techniques proposed on a set of synthetic examples as well as neuro-imaging dataset created for the study of autism. Finally, we consider a novel approach to the structure discovery of undirected graphical models from observational data. Although, popular methods rely on estimating a penalized maximum likelihood of the precision matrix, in these approaches structure recovery is an indirect consequence of the data-fit term, the penalty can be difficult to adapt for domain-specific knowledge, and the inference is computationally demanding. By contrast, it may be easier to generate training samples of data that arise from graphs with the desired structure properties. We propose to leverage this latter source of information as training data to learn a function, parametrized by a neural network that maps empirical covariance matrices to estimated graph structures. Learning this function brings two benefits: it implicitly models the desired structure or sparsity properties to form suitable priors, and it can be tailored to the specific problem of edge structure discovery, rather than maximizing data likelihood. Applying this framework, we find our learnable graph-discovery method trained on synthetic data generalizes well: identifying relevant edges in both synthetic and real data, completely unknown at training time. We find that on genetics, brain imaging, and simulation data we obtain performance generally superior to analytical methods.
Document type :
Complete list of metadata

Cited literature [173 references]  Display  Hide  Download
Contributor : Eugene Belilovsky <>
Submitted on : Wednesday, October 16, 2019 - 12:23:09 AM
Last modification on : Saturday, May 1, 2021 - 3:49:16 AM
Long-term archiving on: : Friday, January 17, 2020 - 1:23:52 PM


Thesis_Manuscript_Final (1).pd...
Files produced by the author(s)


  • HAL Id : tel-02317341, version 1


Eugene Belilovsky. Structured Sparse Learning on Graphs in High-Dimensional Data with Applications to NeuroImaging. Machine Learning [cs.LG]. CentraleSupelec, 2018. English. ⟨tel-02317341⟩



Record views


Files downloads