ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times

• URL: http://arxiv.org/abs/2405.15094v1
• Date: Thu, 23 May 2024 22:57:15 GMT
• Title: ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times
• Authors: Fabian Spaeh, Konstantinos Sotiropoulos, Charalampos E. Tsourakakis,
• Abstract summary: We introduce a unifying strategy for learning mixtures of discrete and continuous-time Markov chains. Specifically, we design a reconstruction algorithm that outputs a mixture which accurately reflects the estimated hitting times.
• Score: 13.299820337462833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study introduces a novel approach for learning mixtures of Markov chains, a critical process applicable to various fields, including healthcare and the analysis of web users. Existing research has identified a clear divide in methodologies for learning mixtures of discrete and continuous-time Markov chains, while the latter presents additional complexities for recovery accuracy and efficiency. We introduce a unifying strategy for learning mixtures of discrete and continuous-time Markov chains, focusing on hitting times, which are well defined for both types. Specifically, we design a reconstruction algorithm that outputs a mixture which accurately reflects the estimated hitting times and demonstrates resilience to noise. We introduce an efficient gradient-descent approach, specifically tailored to manage the computational complexity and non-symmetric characteristics inherent in the calculation of hitting time derivatives. Our approach is also of significant interest when applied to a single Markov chain, thus extending the methodologies previously established by Hoskins et al. and Wittmann et al. We complement our theoretical work with experiments conducted on synthetic and real-world datasets, providing a comprehensive evaluation of our methodology.

Related papers

• Dynamical mixture modeling with fast, automatic determination of Markov chains [0.0]
  Variational EM efficiently identifies the number of Markov chains and dynamics of each chain without expensive model comparisons or posterior sampling. The approach is supported by a theoretical analysis and numerical experiments, including simulated and observational data sets based on $tt Last.fm$ music listening, ultramarathon running, and gene expression.
  arXiv  Detail & Related papers  (2024-06-07T05:43:11Z)
• Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain Mixtures [11.131861804842886]
  We study learning mixtures of continuous-time Markov chains (CTMCs) CTMCs could model intricate continuous-time processes prevalent in various fields including social media, finance, and biology. We introduce a novel framework for exploring CTMCs, emphasizing the influence of observed trails' length and mixture parameters on problem regimes. We apply our algorithms on an extensive collection of Lastfm's user-generated trails spanning three years, demonstrating the capability of our algorithms to differentiate diverse user preferences.
  arXiv  Detail & Related papers  (2024-02-27T18:04:59Z)
• Class-Incremental Mixture of Gaussians for Deep Continual Learning [15.49323098362628]
  We propose end-to-end incorporation of the mixture of Gaussians model into the continual learning framework. We show that our model can effectively learn in memory-free scenarios with fixed extractors.
  arXiv  Detail & Related papers  (2023-07-09T04:33:19Z)
• Detection and Evaluation of Clusters within Sequential Data [58.720142291102135]
  Clustering algorithms for Block Markov Chains possess theoretical optimality guarantees. In particular, our sequential data is derived from human DNA, written text, animal movement data and financial markets. It is found that the Block Markov Chain model assumption can indeed produce meaningful insights in exploratory data analyses.
  arXiv  Detail & Related papers  (2022-10-04T15:22:39Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Adapting to Mixing Time in Stochastic Optimization with Markovian Data [12.709177728330399]
  We consider optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain. Our method relies on a novel combination of multi-level Monte Carlo (ML) gradient estimation together with an adaptive learning method.
  arXiv  Detail & Related papers  (2022-02-09T12:43:11Z)
• Continual Learning In Environments With Polynomial Mixing Times [13.533984338434106]
  We study the effect of mixing times on learning in continual reinforcement learning. We propose a family of model-based algorithms that speed up learning by directly optimizing for the average reward.
  arXiv  Detail & Related papers  (2021-12-13T23:41:56Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• ARISE: ApeRIodic SEmi-parametric Process for Efficient Markets without Periodogram and Gaussianity Assumptions [91.3755431537592]
  We present the ApeRI-miodic (ARISE) process for investigating efficient markets. The ARISE process is formulated as an infinite-sum of some known processes and employs the aperiodic spectrum estimation. In practice, we apply the ARISE function to identify the efficiency of real-world markets.
  arXiv  Detail & Related papers  (2021-11-08T03:36:06Z)
• Contrastive learning of strong-mixing continuous-time stochastic processes [53.82893653745542]
  Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data. We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
  arXiv  Detail & Related papers  (2021-03-03T23:06:47Z)
• Nonlinear Independent Component Analysis for Continuous-Time Signals [85.59763606620938]
  We study the classical problem of recovering a multidimensional source process from observations of mixtures of this process. We show that this recovery is possible for many popular models of processes (up to order and monotone scaling of their coordinates) if the mixture is given by a sufficiently differentiable, invertible function.
  arXiv  Detail & Related papers  (2021-02-04T20:28:44Z)

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.