論文の概要: On Language Generation in the Limit with Bounded Memory

• arxiv url: http://arxiv.org/abs/2605.30324v1
• Date: Thu, 28 May 2026 17:57:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:56.734868
• Title: On Language Generation in the Limit with Bounded Memory
• Title（参考訳）: 境界記憶を持つ限界における言語生成について
• Authors: Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas,
• Abstract要約: 境界メモリ下での限界における言語生成について検討する。 このタスクでは、学習者は未知のターゲット言語からサンプルを一度に観察し、最終的には新しい有効なサンプルのみを出力しなければならない。
• 参考スコア（独自算出の注目度）: 17.70989972580602
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that a sliding window of the last $W$ examples does not improve this worst-case density, whereas allowing it to store $b$ adaptively chosen past examples improves the achievable density for every $b \geq 1$. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.
• Abstract（参考訳）: 境界メモリ下での限界における言語生成について検討する。 このタスクでは、学習者は未知のターゲット言語からサンプルを一度に観察し、最終的には新しい有効なサンプルのみを出力しなければならない。 それまでの作業では、履歴全体へのアクセスを前提としていたが、現実的なアルゴリズムが過去の限られた情報を保持するため、強い仮定である。 学習理論における古典的な研究は、記憶の制約によって学習可能性が劇的に変化することを示している。 まず、メモリレスジェネレータについて研究する。 軽い列挙制限の下では、無限言語の可算集合は記憶なしで生成可能である。 この制限がなければ、メモリレス生成が可能になったら正確に特徴付けます。 有限コレクションに対しては、メモリレスジェネレータによって達成可能な最適ミニマックス密度を特徴付けます。 この組合せ境界は、スペルナーの定理と対称鎖分解に依存する。 さらに、最後の$W$のスライディングウィンドウは、この最悪のケース密度を改善せず、また、適応的に選択された過去の例を$b$に格納することは、$b \geq 1$毎の達成可能な密度を改善する。 最後に,学習者が対象言語に対して1つの正しい仮説に収束しなければならない限界における同定を再考する。 我々は、学習者が以前の推測だけを記憶するインクリメンタルな変種に焦点を当てる。 ここでは、正確な識別はわずか3つの言語の集合で失敗するが、ターゲットの `<approximate'' バージョンへの収束を必要とする緩やかな緩和は、すべての有限個の集合に対して達成可能である。 生成はすべての可算コレクションに対して達成可能であるが、密度と識別は有限コレクションに限られており、コレクションが大きくなるにつれて保証される。

関連論文リスト

• Mistake-Bounded Language Generation [6.034531760235531]
  言語生成の限界における学習課題について検討する。 我々は、伝統的なラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ 我々のフレームワークは、ノイズの多い敵に適応できるように拡張可能であることを示す。
  論文  参考訳（メタデータ） (2026-05-11T16:32:01Z)
• A Characterization of List Language Identification in the Limit [31.38302438096483]
  本研究では,対象言語からのサンプルの列を与えられた限界における言語識別の問題について検討する。 学習者の目標は、ある有限時間を超える推測が正しいように、対象言語に対する推測列を出力することである。 制限で特定できる$k$-listの言語コレクションの正確な特徴付けを与えます。
  論文  参考訳（メタデータ） (2025-11-06T06:39:20Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。 我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。 また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
  論文  参考訳（メタデータ） (2024-11-22T22:13:40Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• Lift Yourself Up: Retrieval-augmented Text Generation with Self Memory [72.36736686941671]
  本稿では,検索拡張生成モデルを改善するための新しいフレームワーク,Selfmemを提案する。 Selfmemは、検索拡張ジェネレータを反復的に使用して、無制限のメモリプールを生成し、メモリセレクタを使用して、続く生成ラウンドの1つの出力をメモリとして選択する。 我々は,3つの異なるテキスト生成タスクにおける自己メモの有効性を評価する。
  論文  参考訳（メタデータ） (2023-05-03T21:40:54Z)
• 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)
• Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes [0.0]
  非U字型性は制限的ではなく、保守性や(強い)単調性は制限的であることを示す。 また,2つの設定が異なる非意味的制約(強い非U字型性)の例を示す。
  論文  参考訳（メタデータ） (2020-10-09T19:59:49Z)

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

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