論文の概要: Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

• arxiv url: http://arxiv.org/abs/2511.05295v1
• Date: Fri, 07 Nov 2025 14:56:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-10 21:00:44.801797
• Title: Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
• Title（参考訳）: 部分列挙による言語生成と識別:高密度境界とトポロジカル特徴
• Authors: Jon Kleinberg, Fan Wei,
• Abstract要約: 敵が未知の言語から文字列を列挙する極限における言語生成の枠組みについて検討する。 C$が$K$でより低い密度$alpha$を持つなら、アルゴリズムの出力は少なくとも$alpha/2$を達成する。 M_t$を仮定すると、最終的に$Cサブセットeq Mサブセットeq K$が満たされる。
• 参考スコア（独自算出の注目度）: 1.6203023551115867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of \emph{language generation in the limit}, where an adversary enumerates strings from an unknown language $K$ drawn from a countable class, and an algorithm must generate unseen strings from $K$. Prior work showed that generation is always possible, and that some algorithms achieve positive lower density, revealing a \emph{validity--breadth} trade-off between correctness and coverage. We resolve a main open question in this line, proving a tight bound of $1/2$ on the best achievable lower density. We then strengthen the model to allow \emph{partial enumeration}, where the adversary reveals only an infinite subset $C \subseteq K$. We show that generation in the limit remains achievable, and if $C$ has lower density $\alpha$ in $K$, the algorithm's output achieves density at least $\alpha/2$, matching the upper bound. This generalizes the $1/2$ bound to the partial-information setting, where the generator must recover within a factor $1/2$ of the revealed subset's density. We further revisit the classical Gold--Angluin model of \emph{language identification} under partial enumeration. We characterize when identification in the limit is possible -- when hypotheses $M_t$ eventually satisfy $C \subseteq M \subseteq K$ -- and in the process give a new topological formulation of Angluin's characterization, showing that her condition is precisely equivalent to an appropriate topological space having the $T_D$ separation property.
• Abstract（参考訳）: 大規模言語モデル(LLM)の成功は、言語生成と学習の形式理論を動機付けている。 ここでは,未知の言語である$K$を可算クラスから抽出した未知の言語から列挙し,アルゴリズムは$K$から未知の文字列を生成する。 以前の研究は、生成は常に可能であり、いくつかのアルゴリズムは正の低い密度を達成することを示し、正しさとカバレッジの間のトレードオフを明らかにした。 この行において、最も達成可能な低い密度に対して、1/2$の厳密な境界を証明して、主要な開問題を解決する。 すると、モデルを強化して \emph{partial enumeration} を許容し、敵は無限の部分集合 $C \subseteq K$ だけを明らかにする。 C$ がより低い密度 $\alpha$ in $K$ を持つなら、アルゴリズムの出力は少なくとも$\alpha/2$ の密度を達成でき、上限値に一致する。 これは部分情報設定にバインドされた1/2$を一般化し、生成元は明らかにされた部分集合の密度の1/2$の範囲内で回復しなければならない。 さらに、部分列挙化の下での古典的ゴールド・アングルインモデルについて再検討する。極限における識別が可能であるとき、すなわち、$M_t$が最終的に$C \subseteq M \subseteq K$を満たすとき、その過程でアングルンの特徴づけの新たな位相的定式化を行い、彼女の状態が$T_D$分離性を持つ適切な位相空間と正確に等価であることを示す。

関連論文リスト

• Quantum Search With Generalized Wildcards [0.4310167974376404]
  我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。 以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
  論文  参考訳（メタデータ） (2025-11-06T18:55:05Z)
• Pareto-optimal Non-uniform Language Generation [11.279808969568252]
  ある言語に対する生成時間$L$が$tstar(L)$より厳密に小さいアルゴリズムは、他の言語に対する生成時間$L’$が$tstar(L')$より厳密に悪いことを満たさなければならない。 提案手法は,非一様生成アルゴリズムを,雑音や代表生成といった現実的に動機付けられた設定に適応させるのに便利である。
  論文  参考訳（メタデータ） (2025-10-03T08:08:20Z)
• Density Measures for Language Generation [2.2872032473279065]
  言語生成アルゴリズムの妥当性と広さのトレードオフについて検討する。 限界における言語生成のための既存のアルゴリズムは、真の言語でゼロ密度を持つ出力セットを生成する。 しかしながら、出力が厳密に正の密度を持つ極限における言語生成のアルゴリズムが$K$であることを示す。
  論文  参考訳（メタデータ） (2025-04-19T18:08:18Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits [22.18577284185939]
  我々は、重尾の多腕バンディットのためのロバストなベスト・オブ・ザ・ワールドスアルゴリズムを開発した。 textttHTINFは、両方の環境と敵環境に最適な後悔を同時に達成する。 textttAdaTINFは、alpha$と$sigma$の両方に適応できる最初のアルゴリズムであり、最適のギャップを逸脱した後悔境界を達成する。
  論文  参考訳（メタデータ） (2022-01-28T03:53:39Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。 明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
  論文  参考訳（メタデータ） (2020-10-15T04:42:29Z)

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

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