Fugu-MT 論文翻訳(概要): Space-Efficient Language Generation in the Limit

論文の概要: Space-Efficient Language Generation in the Limit

arxiv url: http://arxiv.org/abs/2606.25777v1
Date: Wed, 24 Jun 2026 12:55:34 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-25 17:05:30.32991
Title: Space-Efficient Language Generation in the Limit
Title（参考訳）: 限界における空間効率の良い言語生成
Abstract要約: 本稿では,空間効率の最小限の制約の下で,テキスト生成の資源認識理論を提案する。私たちは$mathcalC_s,k$という,DFAが認識する言語のコレクションに注目しています。より厳格なメモリ予算の下では、最強の世代保証を特徴付ける。
参考スコア（独自算出の注目度）: 34.38365460078856
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language $K$ and must eventually output a hallucination-free hypothesis language $L \subseteq K$ while omitting at most $Δ$ strings of $K$. We focus on $\mathcal{C}_{s,k}$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target $K$. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using $\mathrm{poly}(s,k)$ space that converges to a hypothesis with generation gap $Δ= O(k^{2s-2})$. Moreover, the learned hypothesis captures every string in $K$ of length at least $2s-1$. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap $Δ\le k^{(1-\varepsilon)s}$ requires $k^{Ω(\varepsilon s)}$ memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.
Abstract（参考訳）: 我々は、空間効率の最小限の制約の下で、リソースを意識した「極限におけるtextit{lang generation in the limit}」理論を開始する。我々のフレームワークでは、学習者はターゲット言語である$K$の逆正のストリームを観察し、最終的には幻覚のない仮説言語である$L \subseteq K$を出力し、最大$K$のΔ$文字列を省略しなければならない。メモリバウンダリ学習者の自然な仮説クラスとして,DFAが認識する言語コレクションである$\mathcal{C}_{s,k}$に注目した。指数空間系では、学習者がターゲットのK$を正確に識別できることが証明される。より厳格なメモリ予算の下では、最強の世代保証を特徴付ける。特に、生成ギャップが$Δ= O(k^{2s-2})$の仮説に収束する$\mathrm{poly}(s,k)$空間を用いたストリーミングアルゴリズムを提案する。さらに、学習された仮説は、すべての文字列を少なくとも$2s-1$の長さのK$でキャプチャする。この結果を、標準的な通信複雑性問題からの還元により、ほぼ一致した下界で補完する。具体的には、生成ギャップを$Δ\le k^{(1-\varepsilon)s}$を達成するには、$k^{Ω(\varepsilon s)}$メモリが必要である。これらの結果は、多項式空間の生成と指数空間の正確な同定の急激な遷移を示す。

関連論文リスト

An Optimal Agnostic PAC Algorithm [15.361702135159845]
2進リスクに対して$L$と$L*=min_hin HL(h)$を書き、統計的に最適なリスク境界を達成する学習者を構築する。これにより、PACが任意の固定された$L*$で普遍定数まで学習する際の無知なサンプル複雑性が解決される。
論文参考訳（メタデータ） (2026-08-06T17:57:25Z)
On the Price of Privacy for Language Identification and Generation [39.91890433860882]
本研究では,言語学習におけるプライバシのコストについて,差分プライベート(DP)言語識別と生成について検討する。以上の結果から,言語学習におけるプライバシのコストは驚くほど軽度であることが示唆された。
論文参考訳（メタデータ） (2026-04-08T16:04:16Z)
Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文参考訳（メタデータ） (2026-03-19T15:53:41Z)
Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations [1.6203023551115867]
敵が未知の言語から文字列を列挙する極限における言語生成の枠組みについて検討する。 C$が$K$でより低い密度$alpha$を持つなら、アルゴリズムの出力は少なくとも$alpha/2$を達成する。 M_t$を仮定すると、最終的に$Cサブセットeq Mサブセットeq K$が満たされる。
論文参考訳（メタデータ） (2025-11-07T14:56:04Z)
Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文参考訳（メタデータ） (2025-09-25T07:39:25Z)
Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文参考訳（メタデータ） (2025-04-29T15:56:48Z)
On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。注目すべきは,上界が決定論的学習者によって達成できることである。
論文参考訳（メタデータ） (2022-10-06T06:49:48Z)
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case [3.729242965449096]
We consider streaming algorithm for Approximating the value of Unique Games on a hypergraph with $t$-size hyperedges。この値の$(r-varepsilon)$-approximationを達成する逆モデルの全てのストリーミングアルゴリズムは、$Omega(n1-2/t)$量子空間を必要とする。
論文参考訳（メタデータ） (2021-09-06T16:56:19Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
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)

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

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