論文の概要: Pareto-optimal Non-uniform Language Generation
- arxiv url: http://arxiv.org/abs/2510.02795v1
- Date: Fri, 03 Oct 2025 08:08:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-06 16:35:52.309532
- Title: Pareto-optimal Non-uniform Language Generation
- Title（参考訳）: Pareto-Optimal Non-Uniform Language Generation
- Authors: Moses Charikar, Chirag Pabbaraju,
- Abstract要約: ある言語に対する生成時間$L$が$tstar(L)$より厳密に小さいアルゴリズムは、他の言語に対する生成時間$L’$が$tstar(L')$より厳密に悪いことを満たさなければならない。
提案手法は,非一様生成アルゴリズムを,雑音や代表生成といった現実的に動機付けられた設定に適応させるのに便利である。
- 参考スコア（独自算出の注目度）: 11.279808969568252
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kleinberg and Mullainathan (2024) recently proposed an interesting model for language generation in the limit: Given a countable collection of languages, and an adversary enumerating the strings of some language $L$ from the collection, the objective is to generate new strings from the target language, such that all strings generated beyond some finite time are valid. Li, Raman and Tewari (2024) and Charikar and Pabbaraju (2024) showed strong non-uniform generation guarantees in this model, giving algorithms that generate new valid strings from $L$ after seeing a number of distinct input strings $t(L)$ that depends only on $L$ (and the collection), but not the enumeration order. However, for both these works, the language-wise generation times $t(L)$ of the algorithm can be strictly sub-optimal. In this work, we study Pareto-optimality of non-uniform language generation in the limit. We propose an algorithm, whose generation times $t^\star(L)$ are (almost) Pareto-optimal: any other algorithm whose generation time for some language $L$ is strictly smaller than $t^\star(L)$, must satisfy that its generation time for some other language $L'$ is strictly worse than $t^\star(L')$. Pareto-optimality is essentially the best that one can achieve for non-uniform generation. Our algorithmic framework conveniently adapts to further give Pareto-optimal non-uniform generation algorithms in the practically motivated settings of noisy as well as representative generation.
- Abstract（参考訳）: Kleinberg と Mullainathan (2024) は、最近、この限界における言語生成の興味深いモデルを提案した。 可算な言語コレクションと、ある言語の文字列をコレクションから$L$で列挙する敵が与えられた場合、目的は、ある有限時間を超えて生成されたすべての文字列が有効であるように、ターゲット言語から新しい文字列を生成することである。
Li, Raman and Tewari (2024) と Charikar and Pabbaraju (2024) はこのモデルにおいて強い一様でない生成保証を示し、$L$から新しい有効文字列を生成するアルゴリズムを与える。
しかし、これら両方の研究に対して、アルゴリズムの言語ワイド生成時間$t(L)$は厳密に準最適である。
本研究では,非一様言語生成のパレート最適性について,その限界において検討する。
生成時間 $t^\star(L)$ が(ほぼ)パレート最適化であるようなアルゴリズムを提案する:ある言語に対する生成時間 $L$ が $t^\star(L)$ より厳密に小さい他の言語に対する生成時間 $L'$ が $t^\star(L')$ より厳密に悪いことを満たさなければならない。
パレート最適性(Pareto-Optimality)は、本質的には、一様でない生成に対して達成できる最良の方法である。
我々のアルゴリズムフレームワークは、実用的なノイズ設定や代表生成において、パレート最適化非一様生成アルゴリズムをさらに活用するために便利である。
関連論文リスト
- Language Generation in the Limit: Noise, Loss, and Feedback [10.280148603465697]
一様生成可能なコレクションの有限和が極限において生成可能であることを示し、非一様生成に対して同じことが真であるかどうかを問う。
均一および非一様生成に対するこれらのモデルの等価性を示し、非一様雑音発生のキャラクタリゼーションを提供する。
論文 参考訳（メタデータ） (2025-07-21T07:18:04Z) - Density Measures for Language Generation [2.2872032473279065]
言語生成アルゴリズムの妥当性と広さのトレードオフについて検討する。
限界における言語生成のための既存のアルゴリズムは、真の言語でゼロ密度を持つ出力セットを生成する。
しかしながら、出力が厳密に正の密度を持つ極限における言語生成のアルゴリズムが$K$であることを示す。
論文 参考訳（メタデータ） (2025-04-19T18:08:18Z) - On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability [16.30681257128492]
[KM24] は、その極限における任意の可算言語コレクションから生成するアルゴリズムである。
近年の研究では、広さの異なる概念を導入し、広さの世代が可能であるかを探求している。
以上の結果から,安定性が要求される場合には,多くの既存概念による生成が等しく困難になることが示唆された。
論文 参考訳（メタデータ） (2024-12-24T16:24:43Z) - Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Exploring Facets of Language Generation in the Limit [10.18252143035175]
任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。
我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。
また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
論文 参考訳（メタデータ） (2024-11-22T22:13:40Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Interactive Code Generation via Test-Driven User-Intent Formalization [60.90035204567797]
大きな言語モデル(LLM)は、非公式な自然言語(NL)の意図からコードを生成する。
自然言語は曖昧であり、形式的な意味論が欠けているため、正確性の概念を定義するのは難しい。
言語に依存しない抽象アルゴリズムと具体的な実装TiCoderについて述べる。
論文 参考訳（メタデータ） (2022-08-11T17:41:08Z) - 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) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。