Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations

• URL: http://arxiv.org/abs/2112.09174v1
• Date: Thu, 16 Dec 2021 19:56:44 GMT
• Title: Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations
• Authors: Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, Jishen Zhao
• Abstract summary: Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. In practice, it is often observed that Transformer models have better representation power than LSTM. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns.
• Score: 51.77000472945441
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. Theoretical results show that both are Turing-complete and can represent any context-free language (CFL).In practice, it is often observed that Transformer models have better representation power than LSTM. But the reason is barely understood. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns. To achieve this goal, we introduce an oracle training paradigm, which forces the decomposition of the latent representation of LSTM and the Transformer and supervises with the transitions of the Pushdown Automaton (PDA) of the corresponding CFL. With the forced decomposition, we show that the performance upper bounds of LSTM and Transformer in learning CFL are close: both of them can simulate a stack and perform stack operation along with state transitions. However, the absence of forced decomposition leads to the failure of LSTM models to capture the stack and stack operations, while having a marginal impact on the Transformer model. Lastly, we connect the experiment on the prototypical PDA to a real-world parsing task to re-verify the conclusions

Related papers

• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• MoEUT: Mixture-of-Experts Universal Transformers [75.96744719516813]
  Universal Transformers (UTs) have advantages over standard Transformers in learning compositional generalizations. Layer-sharing drastically reduces the parameter count compared to the non-shared model with the same dimensionality. No previous work has succeeded in proposing a shared-layer Transformer design that is competitive in parameter count-dominated tasks such as language modeling.
  arXiv  Detail & Related papers  (2024-05-25T03:24:32Z)
• Beyond Scaling Laws: Understanding Transformer Performance with Associative Memory [11.3128832831327]
  Increasing the size of a Transformer model does not always lead to enhanced performance. improved generalization ability occurs as the model memorizes the training samples. We present a theoretical framework that sheds light on the memorization process and performance dynamics of transformer-based language models.
  arXiv  Detail & Related papers  (2024-05-14T15:48:36Z)
• Repeat After Me: Transformers are Better than State Space Models at Copying [53.47717661441142]
  We show that while generalized state space models are promising in terms of inference-time efficiency, they are limited compared to transformer models on tasks that require copying from the input context.
  arXiv  Detail & Related papers  (2024-02-01T21:44:11Z)
• How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations [98.7450564309923]
  This paper takes initial steps on understanding in-context learning (ICL) in more complex scenarios, by studying learning with representations. We construct synthetic in-context learning problems with a compositional structure, where the label depends on the input through a possibly complex but fixed representation function. We show theoretically the existence of transformers that approximately implement such algorithms with mild depth and size.
  arXiv  Detail & Related papers  (2023-10-16T17:40:49Z)
• Isomer: Isomerous Transformer for Zero-shot Video Object Segmentation [59.91357714415056]
  We propose two Transformer variants: Context-Sharing Transformer (CST) and Semantic Gathering-Scattering Transformer (S GST) CST learns the global-shared contextual information within image frames with a lightweight computation; S GST models the semantic correlation separately for the foreground and background. Compared with the baseline that uses vanilla Transformers for multi-stage fusion, ours significantly increase the speed by 13 times and achieves new state-of-the-art ZVOS performance.
  arXiv  Detail & Related papers  (2023-08-13T06:12:00Z)
• Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planning [9.801466218905604]
  Automaton based algorithms rely on the manually customized representation of states for the considered task. We develop a Double-Transformer-guided Temporal Logic framework (T2TL) that exploits the structural feature of Transformer twice. As a semantics, progression is exploited to decompose the complex task into learnable sub-goals.
  arXiv  Detail & Related papers  (2022-09-27T07:41:11Z)
• TRANS-BLSTM: Transformer with Bidirectional LSTM for Language Understanding [18.526060699574142]
  Bidirectional Representations from Transformers (BERT) has recently achieved state-of-the-art performance on a broad range of NLP tasks. We propose a new architecture denoted as Transformer with BLSTM (TRANS-BLSTM) which has a BLSTM layer integrated to each transformer block. We show that TRANS-BLSTM models consistently lead to improvements in accuracy compared to BERT baselines in GLUE and SQuAD 1.1 experiments.
  arXiv  Detail & Related papers  (2020-03-16T03:38:51Z)

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.