Learning Extrapolative Sequence Transformations from Markov Chains

• URL: http://arxiv.org/abs/2505.20251v1
• Date: Mon, 26 May 2025 17:27:47 GMT
• Title: Learning Extrapolative Sequence Transformations from Markov Chains
• Authors: Sophia Hager, Aleem Khan, Andrew Wang, Nicholas Andrews,
• Abstract summary: We show that an autoregressive model can efficiently generate novel sequences that extrapolate along the sequence-level properties of interest.<n>The proposed approach is validated on three problems: protein sequence design, text sentiment control, and text anonymization.
• Score: 6.161395208969171
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Most successful applications of deep learning involve similar training and test conditions. However, tasks such as biological sequence design involve searching for sequences that improve desirable properties beyond previously known values, which requires novel hypotheses that \emph{extrapolate} beyond training data. In these settings, extrapolation may be achieved by using random search methods such as Markov chain Monte Carlo (MCMC), which, given an initial state, sample local transformations to approximate a target density that rewards states with the desired properties. However, even with a well-designed proposal, MCMC may struggle to explore large structured state spaces efficiently. Rather than relying on stochastic search, it would be desirable to have a model that greedily optimizes the properties of interest, successfully extrapolating in as few steps as possible. We propose to learn such a model from the Markov chains resulting from MCMC search. Specifically, our approach uses selected states from Markov chains as a source of training data for an autoregressive model, which is then able to efficiently generate novel sequences that extrapolate along the sequence-level properties of interest. The proposed approach is validated on three problems: protein sequence design, text sentiment control, and text anonymization. We find that the autoregressive model can extrapolate as well or better than MCMC, but with the additional benefits of scalability and significantly higher sample efficiency.

Related papers

• From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers [41.82477691012942]
  We study learning a 1-layer self-attention model from a set of prompts and associated output data. We first establish a precise mapping between the self-attention mechanism and Markov models. We characterize an intriguing winner-takes-all phenomenon where the generative process implemented by self-attention collapses into sampling a limited subset of tokens.
  arXiv  Detail & Related papers  (2024-02-21T03:51:34Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
  Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses. We present Quick Adaptive Ternary (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity.
  arXiv  Detail & Related papers  (2023-05-29T19:37:48Z)
• Langevin Autoencoders for Learning Deep Latent Variable Models [27.60436426879683]
  We present a new deep latent variable model named the Langevin autoencoder (LAE) Based on the ALD, we also present a new deep latent variable model named the Langevin autoencoder (LAE)
  arXiv  Detail & Related papers  (2022-09-15T04:26:22Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class. Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class. We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
  arXiv  Detail & Related papers  (2022-08-26T04:28:01Z)
• Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication [2.055204980188575]
  Symbolic regression is a powerful system identification technique in industrial scenarios where no prior knowledge on model structure is available. In this chapter we introduce a deterministic symbolic regression algorithm specifically designed to address these issues. A finite enumeration of all possible models is guaranteed by structural restrictions as well as a caching mechanism for detecting semantically equivalent solutions.
  arXiv  Detail & Related papers  (2021-09-28T17:47:51Z)
• Efficient Data-specific Model Search for Collaborative Filtering [56.60519991956558]
  Collaborative filtering (CF) is a fundamental approach for recommender systems. In this paper, motivated by the recent advances in automated machine learning (AutoML), we propose to design a data-specific CF model. Key here is a new framework that unifies state-of-the-art (SOTA) CF methods and splits them into disjoint stages of input encoding, embedding function, interaction and prediction function.
  arXiv  Detail & Related papers  (2021-06-14T14:30:32Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  We introduce a novel approach to directly optimize a reinforcement learning objective, maximizing an expected reward. We test our methodology on two tasks: generating molecules with user-defined properties and identifying short python expressions which evaluate to a given target value.
  arXiv  Detail & Related papers  (2020-10-05T20:03:13Z)
• 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)
• Slice Sampling for General Completely Random Measures [74.24975039689893]
  We present a novel Markov chain Monte Carlo algorithm for posterior inference that adaptively sets the truncation level using auxiliary slice variables. The efficacy of the proposed algorithm is evaluated on several popular nonparametric models.
  arXiv  Detail & Related papers  (2020-06-24T17:53:53Z)
• Document Ranking with a Pretrained Sequence-to-Sequence Model [56.44269917346376]
  We show how a sequence-to-sequence model can be trained to generate relevance labels as "target words" Our approach significantly outperforms an encoder-only model in a data-poor regime.
  arXiv  Detail & Related papers  (2020-03-14T22:29:50Z)

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.