Exploring Facets of Language Generation in the Limit

• URL: http://arxiv.org/abs/2411.15364v1
• Date: Fri, 22 Nov 2024 22:13:40 GMT
• Title: Exploring Facets of Language Generation in the Limit
• Authors: Moses Charikar, Chirag Pabbaraju,
• Abstract summary: We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit. We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation. Our result shows that a tradeoff between validity and breadth is inherent for generation in the limit.
• Score: 10.18252143035175
• License:
• Abstract: The recent work of Kleinberg and Mullainathan [KM24] provides a concrete model for language generation in the limit: given a sequence of examples from an unknown target language, the goal is to generate new examples from the target language such that no incorrect examples are generated beyond some point. In sharp contrast to strong negative results for the closely related problem of language identification, they establish positive results for language generation in the limit for all countable collections of languages. Follow-up work by Raman and Tewari [RT24] studies bounds on the number of distinct inputs required by an algorithm before correct language generation is achieved -- namely, whether this is a constant for all languages in the collection (uniform generation) or a language-dependent constant (non-uniform generation). We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit. However, while the generation algorithm of [KM24] can be implemented using membership queries, we show that any algorithm cannot non-uniformly generate even for collections of just two languages, using only membership queries. We also formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation, and show a strong negative result for exhaustive generation. Our result shows that a tradeoff between validity and breadth is inherent for generation in the limit. Finally, inspired by algorithms that can choose to obtain feedback, we consider a model of uniform generation with feedback, completely characterizing language collections for which such uniform generation with feedback is possible in terms of a complexity measure of the collection.

Related papers

• On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse [16.30681257128492]
  Given samples from an unknown language, a language model should produce valid strings not seen in training. Otherwise, outputting invalid strings constitutes "hallucination," and failing to capture the full range leads to "mode collapse" We investigate this within a statistical language generation setting building on Gold and Angluin.
  arXiv  Detail & Related papers  (2024-11-14T18:06:55Z)
• Multi-Programming Language Ensemble for Code Generation in Large Language Model [5.882816711878273]
  Large language models (LLMs) have significantly improved code generation, particularly in one-pass code generation. Most existing approaches focus solely on generating code in a single programming language, overlooking the potential of leveraging the multi-language capabilities of LLMs. We propose Multi-Programming Language Ensemble (MPLE), a novel ensemble-based method that utilizes code generation across multiple programming languages to enhance overall performance.
  arXiv  Detail & Related papers  (2024-09-06T08:31:18Z)
• Language Generation in the Limit [0.7787343335258782]
  We show that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning.
  arXiv  Detail & Related papers  (2024-04-10T05:53:25Z)
• Retrieval is Accurate Generation [99.24267226311157]
  We introduce a novel method that selects context-aware phrases from a collection of supporting documents. Our model achieves the best performance and the lowest latency among several retrieval-augmented baselines.
  arXiv  Detail & Related papers  (2024-02-27T14:16:19Z)
• Multi-lingual Evaluation of Code Generation Models [82.7357812992118]
  We present new benchmarks on evaluation code generation models: MBXP and Multilingual HumanEval, and MathQA-X. These datasets cover over 10 programming languages. We are able to assess the performance of code generation models in a multi-lingual fashion.
  arXiv  Detail & Related papers  (2022-10-26T17:17:06Z)
• Bridging the Gap Between Training and Inference of Bayesian Controllable Language Models [58.990214815032495]
  Large-scale pre-trained language models have achieved great success on natural language generation tasks. BCLMs have been shown to be efficient in controllable language generation. We propose a "Gemini Discriminator" for controllable language generation which alleviates the mismatch problem with a small computational cost.
  arXiv  Detail & Related papers  (2022-06-11T12:52:32Z)
• Quark: Controllable Text Generation with Reinforced Unlearning [68.07749519374089]
  Large-scale language models often learn behaviors that are misaligned with user expectations. We introduce Quantized Reward Konditioning (Quark), an algorithm for optimizing a reward function that quantifies an (un)wanted property. For unlearning toxicity, negative sentiment, and repetition, our experiments show that Quark outperforms both strong baselines and state-of-the-art reinforcement learning methods.
  arXiv  Detail & Related papers  (2022-05-26T21:11:51Z)
• Typical Decoding for Natural Language Generation [76.69397802617064]
  We study why high-probability texts can be dull or repetitive. We show that typical sampling offers competitive performance in terms of quality.
  arXiv  Detail & Related papers  (2022-02-01T18:58:45Z)
• Multilingual AMR-to-Text Generation [22.842874899794996]
  We create multilingual AMR-to-text models that generate in twenty one different languages. For eighteen languages, based on automatic metrics, our multilingual models surpass baselines that generate into a single language. We analyse the ability of our multilingual models to accurately capture morphology and word order using human evaluation, and find that native speakers judge our generations to be fluent.
  arXiv  Detail & Related papers  (2020-11-10T22:47:14Z)
• Limits of Detecting Text Generated by Large-Scale Language Models [65.46403462928319]
  Some consider large-scale language models that can generate long and coherent pieces of text as dangerous, since they may be used in misinformation campaigns. Here we formulate large-scale language model output detection as a hypothesis testing problem to classify text as genuine or generated.
  arXiv  Detail & Related papers  (2020-02-09T19:53:23Z)

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.