Scalable Structure Learning for Sparse Context-Specific Systems

• URL: http://arxiv.org/abs/2402.07762v2
• Date: Wed, 16 Oct 2024 13:42:33 GMT
• Title: Scalable Structure Learning for Sparse Context-Specific Systems
• Authors: Felix Leopoldo Rios, Alex Markham, Liam Solus,
• Abstract summary: We present an algorithm for learning context-specific models that scales to hundreds of variables. Our method is shown to perform well on synthetic data and real world examples.
• Score: 0.0
• License:
• Abstract: Several approaches to graphically representing context-specific relations among jointly distributed categorical variables have been proposed, along with structure learning algorithms. While existing optimization-based methods have limited scalability due to the large number of context-specific models, the constraint-based methods are more prone to error than even constraint-based directed acyclic graph learning algorithms since more relations must be tested. We present an algorithm for learning context-specific models that scales to hundreds of variables. Scalable learning is achieved through a combination of an order-based Markov chain Monte-Carlo search and a novel, context-specific sparsity assumption that is analogous to those typically invoked for directed acyclic graphical models. Unlike previous Markov chain Monte-Carlo search methods, our Markov chain is guaranteed to have the true posterior of the variable orderings as the stationary distribution. To implement the method, we solve a first case of an open problem recently posed by Alon and Balogh. Future work solving increasingly general instances of this problem would allow our methods to learn increasingly dense models. The method is shown to perform well on synthetic data and real world examples, in terms of both accuracy and scalability.

Related papers

• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  Laplacian regularized stratified models (LRSM) are models that utilize the explicit or implicit network structure of the sub-problems. This paper shows the importance and sensitivity of graph weights in LRSM, and provably show that the sensitivity can be arbitrarily large. We propose a generic approach to jointly learn the graph while fitting the model parameters by solving a single optimization problem.
  arXiv  Detail & Related papers  (2023-05-04T06:06:29Z)
• RandomSCM: interpretable ensembles of sparse classifiers tailored for omics data [59.4141628321618]
  We propose an ensemble learning algorithm based on conjunctions or disjunctions of decision rules. The interpretability of the models makes them useful for biomarker discovery and patterns discovery in high dimensional data.
  arXiv  Detail & Related papers  (2022-08-11T13:55:04Z)
• A Unified Analysis of Dynamic Interactive Learning [5.474944738795308]
  Previous work by Emamjomeh-Zadeh et al. [ 2020] introduced dynamics into interactive learning as a way to model non-static user preferences. We give a framework that captures both of the models analyzed by [Emamjomeh-Zadeh et al., 2020], which allows us to study any type of concept evolution. We also study an efficient algorithm where the learner simply follows the feedback at each round.
  arXiv  Detail & Related papers  (2022-04-14T16:03:37Z)
• Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
  A regularized version of Mixture Models is proposed to learn a principal graph from a distribution of $D$-dimensional data points. Parameters of the model are iteratively estimated through an Expectation-Maximization procedure.
  arXiv  Detail & Related papers  (2021-06-16T18:00:02Z)
• Structured Reordering for Modeling Latent Alignments in Sequence Transduction [86.94309120789396]
  We present an efficient dynamic programming algorithm performing exact marginal inference of separable permutations. The resulting seq2seq model exhibits better systematic generalization than standard models on synthetic problems and NLP tasks.
  arXiv  Detail & Related papers  (2021-06-06T21:53:54Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables [28.893119229428713]
  We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables. In particular, we generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formalize the IP-based ADMG learning model.
  arXiv  Detail & Related papers  (2021-02-05T12:10:16Z)
• Information Theoretic Meta Learning with Gaussian Processes [74.54485310507336]
  We formulate meta learning using information theoretic concepts; namely, mutual information and the information bottleneck. By making use of variational approximations to the mutual information, we derive a general and tractable framework for meta learning.
  arXiv  Detail & Related papers  (2020-09-07T16:47:30Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)
• Learning the Markov order of paths in a network [1.5229257192293197]
  We study the problem of learning the Markov order in categorical sequences that represent paths in a network. Adopting a multi-order modelling framework for paths, we develop a Bayesian learning technique that more reliably detects the correct Markov order. Our work is further relevant for the growing body of research that emphasizes the need for higher-order models in network analysis.
  arXiv  Detail & Related papers  (2020-07-06T16:27:02Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.