論文の概要: Language Generation with Infinite Contamination

• arxiv url: http://arxiv.org/abs/2511.07417v1
• Date: Mon, 10 Nov 2025 18:59:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:45.435086
• Title: Language Generation with Infinite Contamination
• Title（参考訳）: 無限汚染による言語生成
• Authors: Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou,
• Abstract要約: そこでは,未知のターゲット言語である$K$から文字列の逆列挙をアルゴリズムが観測する。 私たちは、驚くべきことに、密度のある世代は、同じ一般性で達成可能であることを示しています。 これは、カリキュラム学習がノイズの多いWebデータから学ぶために重要であることを示唆している。
• 参考スコア（独自算出の注目度）: 17.31852533022177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language $K$ and must eventually generate new, unseen strings from $K$. Kleinberg and Mullainathan [KM24] proved that generation is achievable in surprisingly general settings. But their generator suffers from ``mode collapse,'' producing from an ever-smaller subset of the target. To address this, Kleinberg and Wei [KW25] require the generator's output to be ``dense'' in the target language. They showed that generation with density, surprisingly, remains achievable at the same generality. Both results assume perfect data: no noisy insertions and no omissions. This raises a central question: how much contamination can generation tolerate? Recent works made partial progress on this question by studying (non-dense) generation with either finite amounts of noise (but no omissions) or omissions (but no noise). We characterize robustness under contaminated enumerations: 1. Generation under Contamination: Language generation in the limit is achievable for all countable collections iff the fraction of contaminated examples converges to zero. When this fails, we characterize which collections are generable. 2. Dense Generation under Contamination: Dense generation is strictly less robust to contamination than generation. As a byproduct, we resolve an open question of Raman and Raman [ICML25] by showing that generation is possible with only membership oracle access under finitely many contaminated examples. Finally, we introduce a beyond-worst-case model inspired by curriculum learning and prove that dense generation is achievable even with infinite contamination provided the fraction of contaminated examples converges to zero. This suggests curriculum learning may be crucial for learning from noisy web data.
• Abstract（参考訳）: そこでは,未知のターゲット言語である$K$から文字列の逆列挙をアルゴリズムが観測し,最終的に$K$から新しい未知の文字列を生成する必要がある。 Kleinberg と Mullainathan [KM24] は、驚くほど一般的な設定で生成が達成可能であることを証明した。 しかし、ジェネレータはターゲットのより小さなサブセットから生成される'mode collapse'に苦しむ。 これを解決するため、Kleinberg と Wei [KW25] は生成元の出力をターゲット言語で `dense'' でなければならない。 彼らは、驚くべきことに、密度のある世代は同じ一般性で達成可能であることを示した。 どちらの結果も完璧なデータであり、ノイズなしの挿入も省略もない。 これは、どれだけの汚染が許容できるのかという、中心的な疑問を提起する。 最近の研究は、有限量のノイズ(ただし、省略はなし)または省略(ノイズはなし)で(ナンセンスでない)生成を研究することで、この問題を部分的に進展させた。 我々は,汚染列挙の下での頑丈さを特徴付ける。 1. 汚染下の生成: 限界における言語生成は、すべての可算コレクションに対して達成可能である。 これが失敗すると、どのコレクションが生成可能であるかを特徴付ける。 2. 汚染下の高密度発生: 高密度発生は、発電よりも汚染に対して厳格に堅牢でない。 副産物として、RamanとRamanのオープンな問題(ICML25)は、有限個の汚染例の下では、メンバーシップオラクルアクセスのみで生成が可能であることを示すことで解決する。 最後に、カリキュラム学習にインスパイアされた余剰ケースモデルを導入し、汚染されたサンプルのごく一部が0に収束すれば、無限に汚染しても高密度生成が達成可能であることを証明した。 これは、カリキュラム学習がノイズの多いWebデータから学ぶために重要であることを示唆している。

関連論文リスト

• Language Generation: Complexity Barriers and Implications for Learning [51.449718747429756]
  単純でよく研究された言語ファミリであっても、成功した生成に必要なサンプルの数は極端に多いことが示される。 これらの結果は、理論的可能性と効率的な学習可能性の間に大きなギャップがあることを明らかにする。
  論文  参考訳（メタデータ） (2025-11-07T23:06:48Z)
• Language Generation in the Limit: Noise, Loss, and Feedback [10.280148603465697]
  一様生成可能なコレクションの有限和が極限において生成可能であることを示し、非一様生成に対して同じことが真であるかどうかを問う。 均一および非一様生成に対するこれらのモデルの等価性を示し、非一様雑音発生のキャラクタリゼーションを提供する。
  論文  参考訳（メタデータ） (2025-07-21T07:18:04Z)
• On Union-Closedness of Language Generation [48.36356615217017]
  Kleinberg と Mullainathan によるモデルで,Li,Raman,Tewari によって拡張された言語生成について検討する。 我々の結果は、生成可能なクラスや不均一に生成可能なクラスの有限和を証明することによって、Li と al. の2つの開問題を解決する。 提案手法は,言語生成の進展領域に独立した関心を持つ可能性のある,新たな対角化の議論とともに,注意深く構築されたクラスを利用する。
  論文  参考訳（メタデータ） (2025-06-23T13:42:25Z)
• On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability [16.30681257128492]
  [KM24] は、その極限における任意の可算言語コレクションから生成するアルゴリズムである。 近年の研究では、広さの異なる概念を導入し、広さの世代が可能であるかを探求している。 以上の結果から,安定性が要求される場合には,多くの既存概念による生成が等しく困難になることが示唆された。
  論文  参考訳（メタデータ） (2024-12-24T16:24:43Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。 我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。 また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
  論文  参考訳（メタデータ） (2024-11-22T22:13:40Z)
• Unlocking Anticipatory Text Generation: A Constrained Approach for Large Language Models Decoding [75.06872859716049]
  大規模言語モデル(LLM)は、テキスト生成の強力な能力を示している。 毒性や幻覚などの望ましくない行動が現れることがある。 将来制約付き生成問題としてテキスト生成の形式化を提案する。
  論文  参考訳（メタデータ） (2023-12-11T06:35:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。