Learning Mixtures of Markov Chains with Quality Guarantees

• URL: http://arxiv.org/abs/2302.04680v1
• Date: Thu, 9 Feb 2023 14:55:17 GMT
• Title: Learning Mixtures of Markov Chains with Quality Guarantees
• Authors: Fabian Spaeh, Charalampos E. Tsourakakis
• Abstract summary: A large number of modern applications generate a plethora of user trails. One approach to modeling this problem mathematically is as a mixture of Markov chains. Recently, Gupta, Kumar and Vassilvitski [GKV16] introduced an algorithm that can perfectly recover a mixture of L chains on n states.
• Score: 8.528384027684192
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A large number of modern applications ranging from listening songs online and browsing the Web to using a navigation app on a smartphone generate a plethora of user trails. Clustering such trails into groups with a common sequence pattern can reveal significant structure in human behavior that can lead to improving user experience through better recommendations, and even prevent suicides [LMCR14]. One approach to modeling this problem mathematically is as a mixture of Markov chains. Recently, Gupta, Kumar and Vassilvitski [GKV16] introduced an algorithm (GKV-SVD) based on the singular value decomposition (SVD) that under certain conditions can perfectly recover a mixture of L chains on n states, given only the distribution of trails of length 3 (3-trail). In this work we contribute to the problem of unmixing Markov chains by highlighting and addressing two important constraints of the GKV-SVD algorithm [GKV16]: some chains in the mixture may not even be weakly connected, and secondly in practice one does not know beforehand the true number of chains. We resolve these issues in the Gupta et al. paper [GKV16]. Specifically, we propose an algebraic criterion that enables us to choose a value of L efficiently that avoids overfitting. Furthermore, we design a reconstruction algorithm that outputs the true mixture in the presence of disconnected chains and is robust to noise. We complement our theoretical results with experiments on both synthetic and real data, where we observe that our method outperforms the GKV-SVD algorithm. Finally, we empirically observe that combining an EM-algorithm with our method performs best in practice, both in terms of reconstruction error with respect to the distribution of 3-trails and the mixture of Markov Chains.

Related papers

• Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
  We introduce a novel convex convex model for semi/library-based unmixing. We demonstrate the efficacy of Alternating Methods of sparse unsupervised unmixing.
  arXiv  Detail & Related papers  (2024-01-23T10:07:41Z)
• Chain of Log-Concave Markov Chains [2.9465623430708905]
  We introduce a theoretical framework for sampling from unnormalized densities. We prove one can decompose sampling from a density into a sequence of sampling from log-concave conditional densities. We report a remarkable capacity of our algorithm to "tunnel" between modes of a distribution.
  arXiv  Detail & Related papers  (2023-05-31T01:00:35Z)
• Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints [7.936519714074615]
  The Kaczmarz matrix (KZ) and its variants have been extensively studied due to their simplicity and efficiency in solving sub linear equation systems. We provide the first theoretical convergence guarantees for KHT by showing that it converges linearly to the solution of a system with sparsity constraints.
  arXiv  Detail & Related papers  (2023-04-20T07:14:24Z)
• Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
  We study a variation of vanilla gradient descent where the only has access to a Markovian sampling scheme. We focus on obtaining rates of convergence under the least restrictive assumptions possible on the underlying Markov chain.
  arXiv  Detail & Related papers  (2023-02-28T09:18:00Z)
• Orthogonal SVD Covariance Conditioning and Latent Disentanglement [65.67315418971688]
  Inserting an SVD meta-layer into neural networks is prone to make the covariance ill-conditioned. We propose Nearest Orthogonal Gradient (NOG) and Optimal Learning Rate (OLR) Experiments on visual recognition demonstrate that our methods can simultaneously improve covariance conditioning and generalization.
  arXiv  Detail & Related papers  (2022-12-11T20:31:31Z)
• Rethinking skip connection model as a learnable Markov chain [12.135167279383815]
  We deep dive into the model's behaviors with skip connections which can be formulated as a learnable Markov chain. An efficient Markov chain is preferred as it always maps the input data to the target domain in a better way. We propose a simple routine of penal connection to make any residual-like model become a learnable Markov chain.
  arXiv  Detail & Related papers  (2022-09-30T07:31:49Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  We study the problem of learning computational mixtures of low-rank models. We develop an algorithm that is guaranteed to recover the unknown matrices with near-optimal sample. In addition, the proposed algorithm is provably stable against random noise.
  arXiv  Detail & Related papers  (2020-09-23T17:53:48Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $tau_mathsfmix$. We propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate.
  arXiv  Detail & Related papers  (2020-06-16T04:26:50Z)
• Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
  Graph representation learning has attracted much attention in supporting high quality candidate search at scale. Despite its effectiveness in learning embedding vectors for objects in the user-item interaction network, the computational costs to infer users' preferences in continuous embedding space are tremendous. We propose a simple yet effective discrete representation learning framework to jointly learn continuous and discrete codes.
  arXiv  Detail & Related papers  (2020-03-04T06:59:56Z)

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.