Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes

• URL: http://arxiv.org/abs/2010.04782v3
• Date: Thu, 17 Jun 2021 12:52:05 GMT
• Title: Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes
• Authors: Timo K\"otzing, Karen Seidel
• Abstract summary: We show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and a bounded memory in form of states. Such a bounded memory states (BMS) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states. We give the complete map of all pairwise relations for an established collection of criteria of successfull learning. Most prominently, we show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. Some results carry over from iterative learning by a general lemma showing that, for a wealth of restrictions (the semantic restrictions), iterative and bounded memory states learning are equivalent. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.

Related papers

• Demystifying Verbatim Memorization in Large Language Models [67.49068128909349]
  Large Language Models (LLMs) frequently memorize long sequences verbatim, often with serious legal and privacy implications. We develop a framework to study verbatim memorization in a controlled setting by continuing pre-training from Pythia checkpoints with injected sequences. We find that (1) non-trivial amounts of repetition are necessary for verbatim memorization to happen; (2) later (and presumably better) checkpoints are more likely to memorize verbatim sequences, even for out-of-distribution sequences.
  arXiv  Detail & Related papers  (2024-07-25T07:10:31Z)
• Pixel Sentence Representation Learning [67.4775296225521]
  In this work, we conceptualize the learning of sentence-level textual semantics as a visual representation learning process. We employ visually-grounded text perturbation methods like typos and word order shuffling, resonating with human cognitive patterns, and enabling perturbation to be perceived as continuous. Our approach is further bolstered by large-scale unsupervised topical alignment training and natural language inference supervision.
  arXiv  Detail & Related papers  (2024-02-13T02:46:45Z)
• Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacy [91.98116450958331]
  We argue that verbatim memorization definitions are too restrictive and fail to capture more subtle forms of memorization. Specifically, we design and implement an efficient defense that perfectly prevents all verbatim memorization. We conclude by discussing potential alternative definitions and why defining memorization is a difficult yet crucial open question for neural language models.
  arXiv  Detail & Related papers  (2022-10-31T17:57:55Z)
• Quantifying Memorization Across Neural Language Models [61.58529162310382]
  Large language models (LMs) have been shown to memorize parts of their training data, and when prompted appropriately, they will emit the memorized data verbatim. This is undesirable because memorization violates privacy (exposing user data), degrades utility (repeated easy-to-memorize text is often low quality), and hurts fairness (some texts are memorized over others). We describe three log-linear relationships that quantify the degree to which LMs emit memorized training data.
  arXiv  Detail & Related papers  (2022-02-15T18:48:31Z)
• Provable Limitations of Acquiring Meaning from Ungrounded Form: What will Future Language Models Understand? [87.20342701232869]
  We investigate the abilities of ungrounded systems to acquire meaning. We study whether assertions enable a system to emulate representations preserving semantic relations like equivalence. We find that assertions enable semantic emulation if all expressions in the language are referentially transparent. However, if the language uses non-transparent patterns like variable binding, we show that emulation can become an uncomputable problem.
  arXiv  Detail & Related papers  (2021-04-22T01:00:17Z)
• Language learnability in the limit for general metrics: a Gold-Angluin result [91.3755431537592]
  We use Niyogi's extended version of a theorem by Blum and Blum (1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages in any given metric. When the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit.
  arXiv  Detail & Related papers  (2021-03-24T13:11:09Z)
• Multi-Adversarial Learning for Cross-Lingual Word Embeddings [19.407717032782863]
  We propose a novel method for inducing cross-lingual word embeddings. It induces the seed cross-lingual dictionary through multiple mappings, each induced to fit the mapping for one subspace. Our experiments on unsupervised bilingual lexicon induction show that this method improves performance over previous single-mapping methods.
  arXiv  Detail & Related papers  (2020-10-16T14:54:28Z)
• Maps for Learning Indexable Classes [1.2728819383164875]
  We study learning of indexed families from positive data where a learner can freely choose a hypothesis space. We are interested in various restrictions on learning, such as consistency, conservativeness or set-drivenness.
  arXiv  Detail & Related papers  (2020-10-15T09:34:07Z)

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.