Max Markov Chain

• URL: http://arxiv.org/abs/2211.01496v1
• Date: Wed, 2 Nov 2022 21:50:54 GMT
• Title: Max Markov Chain
• Authors: Yu Zhang, Mitchell Bucklew
• Abstract summary: We introduce Max Markov Chain (MMC), a novel representation for a useful subset of High-order Markov Chains (HMCs) MMC is parsimony while retaining the expressiveness of HMCs. We show that MMC is a valuable alternative for modeling processes and has many potential applications.
• Score: 4.531240717484252
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce Max Markov Chain (MMC), a novel representation for a useful subset of High-order Markov Chains (HMCs) with sparse correlations among the states. MMC is parsimony while retaining the expressiveness of HMCs. Even though parameter optimization is generally intractable as with HMC approximate models, it has an analytical solution, better sample efficiency, and the desired spatial and computational advantages over HMCs and approximate HMCs. Simultaneously, efficient approximate solutions exist for this type of chains as we show empirically, which allow MMCs to scale to large domains where HMCs and approximate HMCs would struggle to perform. We compare MMC with HMC, first-order Markov chain, and an approximate HMC model in synthetic domains with various data types to demonstrate that MMC is a valuable alternative for modeling stochastic processes and has many potential applications.

Related papers

• Adaptive Fuzzy C-Means with Graph Embedding [84.47075244116782]
  Fuzzy clustering algorithms can be roughly categorized into two main groups: Fuzzy C-Means (FCM) based methods and mixture model based methods. We propose a novel FCM based clustering model that is capable of automatically learning an appropriate membership degree hyper- parameter value.
  arXiv  Detail & Related papers  (2024-05-22T08:15:50Z)
• Learning Energy-Based Prior Model with Diffusion-Amortized MCMC [89.95629196907082]
  Common practice of learning latent space EBMs with non-convergent short-run MCMC for prior and posterior sampling is hindering the model from further progress. We introduce a simple but effective diffusion-based amortization method for long-run MCMC sampling and develop a novel learning algorithm for the latent space EBM based on it.
  arXiv  Detail & Related papers  (2023-10-05T00:23:34Z)
• Ideal Observer Computation by Use of Markov-Chain Monte Carlo with Generative Adversarial Networks [12.521662223741671]
  The Ideal Observer (IO) has been advocated for use as a figure-of-merit (FOM) for evaluating and optimizing medical imaging systems. A sampling-based method that employs Markov-Chain Monte Carlo (MCMC) techniques was previously proposed to estimate the IO performance. In this study, a novel MCMC method that employs a generative adversarial network (GAN)-based SOM, referred to as MCMC-GAN, is described and evaluated.
  arXiv  Detail & Related papers  (2023-04-02T02:51:50Z)
• Mitigating Out-of-Distribution Data Density Overestimation in Energy-Based Models [54.06799491319278]
  Deep energy-based models (EBMs) are receiving increasing attention due to their ability to learn complex distributions. To train deep EBMs, the maximum likelihood estimation (MLE) with short-run Langevin Monte Carlo (LMC) is often used. We investigate why the MLE with short-run LMC can converge to EBMs with wrong density estimates.
  arXiv  Detail & Related papers  (2022-05-30T02:49:17Z)
• Magnetic Manifold Hamiltonian Monte Carlo [7.6146285961466]
  Hamiltonian Monte Carlo (HMC) family of samplers often exhibit improved mixing properties. We introduce magnetic manifold HMC, motivated by the physics of particles constrained to a manifold and moving under magnetic field forces. We demonstrate that magnetic manifold HMC produces favorable sampling behaviors relative to the canonical variant of manifold-constrained HMC.
  arXiv  Detail & Related papers  (2020-10-15T13:53:49Z)
• Scaling Hamiltonian Monte Carlo Inference for Bayesian Neural Networks with Symmetric Splitting [6.684193501969829]
  Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo approach that exhibits favourable exploration properties in high-dimensional models such as neural networks. We introduce a new integration scheme for split HMC that does not rely on symmetric gradients. Our approach demonstrates HMC as a feasible option when considering inference schemes for large-scale machine learning problems.
  arXiv  Detail & Related papers  (2020-10-14T01:58:34Z)
• No MCMC for me: Amortized sampling for fast and stable training of energy-based models [62.1234885852552]
  Energy-Based Models (EBMs) present a flexible and appealing way to represent uncertainty. We present a simple method for training EBMs at scale using an entropy-regularized generator to amortize the MCMC sampling. Next, we apply our estimator to the recently proposed Joint Energy Model (JEM), where we match the original performance with faster and stable training.
  arXiv  Detail & Related papers  (2020-10-08T19:17:20Z)
• MCMC-Interactive Variational Inference [56.58416764959414]
  We propose MCMC-interactive variational inference (MIVI) to estimate the posterior in a time constrained manner. MIVI takes advantage of the complementary properties of variational inference and MCMC to encourage mutual improvement. Experiments show that MIVI not only accurately approximates the posteriors but also facilitates designs of gradient MCMC and Gibbs sampling transitions.
  arXiv  Detail & Related papers  (2020-10-02T17:43:20Z)
• Non-convex Learning via Replica Exchange Stochastic Gradient MCMC [25.47669573608621]
  We propose an adaptive replica exchange SGMCMC (reSGMCMC) to automatically correct the bias and study the corresponding properties. Empirically, we test the algorithm through extensive experiments on various setups and obtain the results.
  arXiv  Detail & Related papers  (2020-08-12T15:02:59Z)
• Involutive MCMC: a Unifying Framework [64.46316409766764]
  We describe a wide range of MCMC algorithms in terms of iMCMC. We formulate a number of "tricks" which one can use as design principles for developing new MCMC algorithms. We demonstrate the latter with two examples where we transform known reversible MCMC algorithms into more efficient irreversible ones.
  arXiv  Detail & Related papers  (2020-06-30T10:21:42Z)
• Hidden Markov Chains, Entropic Forward-Backward, and Part-Of-Speech Tagging [5.778730972088575]
  Hidden Markov Chain (HMC) model associated with classic Forward-Backward probabilities cannot handle arbitrary features. We show that the problem is not due to HMC itself, but to the way its restoration algorithms are computed. We present a new way of computing HMC based restorations using original Entropic Forward and Entropic Backward (EFB) probabilities.
  arXiv  Detail & Related papers  (2020-05-21T13:31:11Z)

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.