A Neural Model for Regular Grammar Induction

• URL: http://arxiv.org/abs/2209.11628v1
• Date: Fri, 23 Sep 2022 14:53:23 GMT
• Title: A Neural Model for Regular Grammar Induction
• Authors: Peter Belc\'ak, David Hofer, Roger Wattenhofer
• Abstract summary: We treat grammars as a model of computation and propose a novel neural approach to induction of regular grammars from positive and negative examples. Our model is fully explainable, its intermediate results are directly interpretable as partial parses, and it can be used to learn arbitrary regular grammars when provided with sufficient data.
• Score: 8.873449722727026
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Grammatical inference is a classical problem in computational learning theory and a topic of wider influence in natural language processing. We treat grammars as a model of computation and propose a novel neural approach to induction of regular grammars from positive and negative examples. Our model is fully explainable, its intermediate results are directly interpretable as partial parses, and it can be used to learn arbitrary regular grammars when provided with sufficient data. Our method consistently attains high recall and precision scores across a range of tests of varying complexity. We make the detailed results and code readily available.

Related papers

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  Formal language theory pertains specifically to recognizers. It is common to instead use proxy tasks that are similar in only an informal sense. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distribution [4.01799362940916]
  We present a setup for training, evaluating and interpreting neural language models, that uses artificial, language-like data. The data is generated using a massive probabilistic grammar, that is itself derived from a large natural language corpus. With access to the underlying true source, our results show striking differences and outcomes in learning dynamics between different classes of words.
  arXiv  Detail & Related papers  (2023-10-23T12:03:01Z)
• Learning grammar with a divide-and-concur neural network [4.111899441919164]
  We implement a divide-and-concur iterative projection approach to context-free grammar inference. Our method requires a relatively small number of discrete parameters, making the inferred grammar directly interpretable.
  arXiv  Detail & Related papers  (2022-01-18T22:42:43Z)
• On The Ingredients of an Effective Zero-shot Semantic Parser [95.01623036661468]
  We analyze zero-shot learning by paraphrasing training examples of canonical utterances and programs from a grammar. We propose bridging these gaps using improved grammars, stronger paraphrasers, and efficient learning methods. Our model achieves strong performance on two semantic parsing benchmarks (Scholar, Geo) with zero labeled data.
  arXiv  Detail & Related papers  (2021-10-15T21:41:16Z)
• Extracting Grammars from a Neural Network Parser for Anomaly Detection in Unknown Formats [79.6676793507792]
  Reinforcement learning has recently shown promise as a technique for training an artificial neural network to parse sentences in some unknown format. This paper presents procedures for extracting production rules from the neural network, and for using these rules to determine whether a given sentence is nominal or anomalous.
  arXiv  Detail & Related papers  (2021-07-30T23:10:24Z)
• Grammatical Error Generation Based on Translated Fragments [0.0]
  We perform neural machine translation of sentence fragments in order to create large amounts of training data for English grammatical error correction. Our method aims at simulating mistakes made by second language learners, and produces a wider range of non-native style language.
  arXiv  Detail & Related papers  (2021-04-20T12:43:40Z)
• Unnatural Language Inference [48.45003475966808]
  We find that state-of-the-art NLI models, such as RoBERTa and BART, are invariant to, and sometimes even perform better on, examples with randomly reordered words. Our findings call into question the idea that our natural language understanding models, and the tasks used for measuring their progress, genuinely require a human-like understanding of syntax.
  arXiv  Detail & Related papers  (2020-12-30T20:40:48Z)
• Comparison of Interactive Knowledge Base Spelling Correction Models for Low-Resource Languages [81.90356787324481]
  Spelling normalization for low resource languages is a challenging task because the patterns are hard to predict. This work shows a comparison of a neural model and character language models with varying amounts on target language data. Our usage scenario is interactive correction with nearly zero amounts of training examples, improving models as more data is collected.
  arXiv  Detail & Related papers  (2020-10-20T17:31:07Z)
• Learning Compositional Rules via Neural Program Synthesis [67.62112086708859]
  We present a neuro-symbolic model which learns entire rule systems from a small set of examples. Instead of directly predicting outputs from inputs, we train our model to induce the explicit system of rules governing a set of previously seen examples.
  arXiv  Detail & Related papers  (2020-03-12T01:06:48Z)

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.