論文の概要: Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

• arxiv url: http://arxiv.org/abs/2609.10525v2
• Date: Thu, 10 Sep 2026 11:32:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 14:47:34.311742
• Title: Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
• Title（参考訳）: 限界における言語生成の特徴:有限性と分離幅階層
• Abstract要約: 生成は、各ターゲットを有限の正の証人に割り当てることが可能である。 未確認の履歴を検索すると、任意の成功した生成元は観測された集合のみに依存して1つに変換される。 数え切れない族はシングルトンの証人を認め、明示的な族はすべての有限の幅を認識でき、無限の共通核を持つ2つの族の統合は有限の証人を必要とする。
• 参考スコア（独自算出の注目度）: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization
• Abstract（参考訳）: 極限における言語生成は、未知の無限言語の全肯定的な表現から、有効な未知の要素を求める。 我々は、このタスクを可算宇宙上の任意の族に対して特徴づける。 生成は、任意の有限サンプルによって活性化されるターゲットが無限共通交叉を持つように、各ターゲットを有限正の証人に割り当てることが正確に可能である。 普遍正規化(Universal normalization)とは、未確認の履歴による探索によって、任意の成功した生成元を、観測された集合のみに依存する1つに変換するものである。 その上で,互換性のある目撃者がどの程度大きいのかを尋ねます。 正の分離幅は最小の均一サイズを記録しており、未有界有限証人に対してさらに2つのレベルが与えられ、互換性のある有限知性の割り当てが存在しない。 あらゆるレベルが生じる。 数え切れない族はシングルトン証人を認め、明示的な族はすべての有限幅を認識でき、無限の共通核を持つ2つの族の統合には有界な有限証人が必要である。 最後に、可算かつ有限な障害は、なぜ局所組合せデータが極限の生成を決定できないのかを説明する。 キャラクタリゼーションと全幅階層は、単純化された正規化と直接対角キャプチャ・レムマを含むLeanでチェックされる。 付随するリーン開発はhttps://github.com/xiaoyulics/言語世代の特徴付けで維持される

関連論文リスト

• A Formal Limitation on Learning Human Language From Textual Corpora [54.22186267212778]
  我々は,デコーダが発話の表現から話者の意図した意味を回復する確率に基づいて,上位境界を導出する。 人工言語、マンダリンゼロ代名詞分解、色基準の実験は、この理論を支持する実証的な証拠を提供する。
  論文  参考訳（メタデータ） (2026-08-28T17:38:24Z)
• On Language Generation in the Limit with Bounded Memory [17.70989972580602]
  境界メモリ下での限界における言語生成について検討する。 このタスクでは、学習者は未知のターゲット言語からサンプルを一度に観察し、最終的には新しい有効なサンプルのみを出力しなければならない。
  論文  参考訳（メタデータ） (2026-05-28T17:57:03Z)
• Contrastive Identification and Generation in the Limit [39.91890433860882]
  本研究では,学習者がデータに対するコントラスト的表現を観察する限界における,コントラスト的識別と生成について検討する。 我々は、敵の汚職の下で鋭い逆転を証明している:いかなる有限の汚職予算の下でも、対照的なペアから識別できるクラスが存在する。 統一された技術的対象は共通横断グラフであり、ペアワイズあいまいさ、家族レベルの生成障害、単一カバレッジ・アンド・インシデンス言語における腐敗欠陥をエンコードする。
  論文  参考訳（メタデータ） (2026-05-07T13:14:51Z)
• 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)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。 我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。 また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
  論文  参考訳（メタデータ） (2024-11-22T22:13:40Z)
• A Measure-Theoretic Characterization of Tight Language Models [105.16477132329416]
  病理学的には「確率質量」が無限列の集合に漏れることがある。 本稿では,言語モデリングの尺度論的扱いについて述べる。 多くのポピュラーな言語モデルファミリーが実際に密接な関係にあることを証明しています。
  論文  参考訳（メタデータ） (2022-12-20T18:17:11Z)
• Language learnability in the limit for general metrics: a Gold-Angluin result [91.3755431537592]
  我々は、blum and blum (1975) によるniyogi の拡張版の定理を用いて、任意の計量における任意の言語族の極限における学習可能性に必要な条件を証明している。 言語ファミリーがさらにすべての有限言語を含むと仮定すると、同じ条件は限界における学習可能性にも十分になる。
  論文  参考訳（メタデータ） (2021-03-24T13:11:09Z)

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

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